← 返回题目列表

AtCoder · arc065_d

F. 洗牌

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

有一个字符串 S 长度 N 由字符组成 0 和 1。您将为每个执行以下操作 i = 1, 2, ..., m:

  • 任意排列子串内的字符 S 开始于 l_i从左边算起第一个字符并延伸到 r_i- 第一个字符。

这里,序列 l_i 不减少。

有多少个可能的值 S 之后 M 运算,模数 1000000007(= 10^9+7)?

约束

  • 2≦N≦3000
  • 1≦M≦3000
  • S 由字符组成 0 和 1.
  • 的长度 S 等于 N.
  • 1≦l_i < r_i≦N
  • l_i ≦ l_{i+1}

输入

输入由标准输入按以下格式给出:

N M
S
l_1 r_1
:
l_M r_M

输出

打印可能值的数量 S 之后 M 运算,模数 1000000007.


示例输入 1

5 2
01001
2 4
3 5

示例输出 1

6

第一次操作后, S 可以是以下三个之一: 01001, 00101 和 00011.

第二次操作后, S 可以是以下六种之一: 01100, 01010, 01001, 00011, 00101 和 00110.


示例输入 2

9 3
110111110
1 4
4 6
6 9

示例输出 2

26

示例输入 3

11 6
00101000110
2 4
2 3
4 7
5 6
6 10
10 11

示例输出 3

143