Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 900 点
問題文
長さ N の 0
、1
からなる文字列 S があります。あなたは、以下の操作を各 1≦i≦M に対し i の昇順に行います。
- S のうち、左から l_i 文字目から r_i 文字目までの部分文字列を自由な順番で並び替える。
ただし、l_i は非減少です。
M 回の操作後の S としてありうるものの数を 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
出力
M 回の操作後の S としてありうるものの数を 1000000007 で割った余りを出力してください。
入力例 1
5 2 01001 2 4 3 5
出力例 1
6
1回目の操作後の S としてありうるものは、 01001
, 00101
, 00011
の 3 つです。
2回目の操作後の S としてありうるものは、 01100
, 01010
, 01001
, 00011
, 00101
, 00110
の 6 つです。
入力例 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
Score : 900 points
Problem Statement
There is a string S of length N consisting of characters 0
and 1
. You will perform the following operation for each i = 1, 2, ..., m:
- Arbitrarily permute the characters within the substring of S starting at the l_i-th character from the left and extending through the r_i-th character.
Here, the sequence l_i is non-decreasing.
How many values are possible for S after the M operations, modulo 1000000007(= 10^9+7)?
Constraints
- 2≦N≦3000
- 1≦M≦3000
- S consists of characters
0
and1
. - The length of S equals N.
- 1≦l_i < r_i≦N
- l_i ≦ l_{i+1}
Input
The input is given from Standard Input in the following format:
N M S l_1 r_1 : l_M r_M
Output
Print the number of the possible values for S after the M operations, modulo 1000000007.
Sample Input 1
5 2 01001 2 4 3 5
Sample Output 1
6
After the first operation, S can be one of the following three: 01001
, 00101
and 00011
.
After the second operation, S can be one of the following six: 01100
, 01010
, 01001
, 00011
, 00101
and 00110
.
Sample Input 2
9 3 110111110 1 4 4 6 6 9
Sample Output 2
26
Sample Input 3
11 6 00101000110 2 4 2 3 4 7 5 6 6 10 10 11
Sample Output 3
143