分数: 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