[ARC065F] シャッフル
题意翻译
有一个长度为 $N$ 的 $01$ 串 $S$。对于每个 $i=1,2,\ldots,M$，你将要按顺序地进行以下操作：
* 任意地排列 $S$ 中第 $l_i$ 到第 $r_i$ 个字符之间的字符。
保证 $l_i$ 是不降的。
请你求出在 $M$ 次操作后，可以出现多少种不同的 $01$ 串。答案对 $10^9+7$ 取模。
$N, M \leq 3000$。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc065/tasks/arc065_d
長さ $ N $ の `0`、`1` からなる文字列 $ S $ があります。あなたは、以下の操作を各 $ 1≦i≦M $ に対し $ i $ の昇順に行います。
- $ S $ のうち、左から $ l_i $ 文字目から $ r_i $ 文字目までの部分文字列を自由な順番で並び替える。
ただし、$ l_i $ は非減少です。
$ M $ 回の操作後の $ S $ としてありうるものの数を $ 1000000007(=\ 10^9+7) $ で割った余りを求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $ $ S $ $ l_1 $ $ r_1 $ : $ l_M $ $ r_M $
输出格式
$ M $ 回の操作後の $ S $ としてありうるものの数を $ 1000000007 $ で割った余りを出力してください。
输入输出样例
输入样例 #1
5 2
01001
2 4
3 5输出样例 #1
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说明
### 制約
- $ 2≦N≦3000 $
- $ 1≦M≦3000 $
- $ S $ は`0`, `1` からなる。
- $ S $ の長さは $ N $ と等しい。
- $ 1≦l_i\ <\ r_i≦N $
- $ l_i\ ≦\ l_{i+1} $
### Sample Explanation 1
$ 1 $回目の操作後の $ S $ としてありうるものは、 `01001`, `00101`, `00011` の $ 3 $ つです。 $ 2 $回目の操作後の $ S $ としてありうるものは、 `01100`, `01010`, `01001`, `00011`, `00101`, `00110` の $ 6 $ つです。