题目描述

長さ $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$ で割った余りを出力してください。

题目大意

有一个长度为 $N$ 的 $01$ 串 $S$。对于每个 $i=1,2,\ldots,M$，你将要按顺序地进行以下操作：

• 任意地排列 $S$ 中第 $l_i$ 到第 $r_i$ 个字符之间的字符。

保证 $l_i$ 是不降的。

请你求出在 $M$ 次操作后，可以出现多少种不同的 $01$ 串。答案对 $10^9+7$ 取模。

$N, M \leq 3000$。

5 2
01001
2 4
3 5

6

9 3
110111110
1 4
4 6
6 9

26

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

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$ つです。