配点 : $900$ 点

問題文

長さ $N$ の 0、1 からなる文字列 $S$ があります。あなたは、以下の操作を各 $1 \leq i \leq M$ に対し $i$ の昇順に行います。

• $S$ のうち、左から $l_i$ 文字目から $r_i$ 文字目までの部分文字列を自由な順番で並び替える。

ただし、$l_i$ は非減少です。

$M$ 回の操作後の $S$ としてありうるものの数を $1000000007(= 10^9+7)$ で割った余りを求めてください。

制約

• $2 \leq N \leq 3000$
• $1 \leq M \leq 3000$
• $S$ は0, 1 からなる。
• $S$ の長さは $N$ と等しい。
• $1 \leq l_i < r_i \leq N$
• $l_i \leq l_{i+1}$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$S$

$l_1$ $r_1$

:

$l_M$ $r_M$

出力

$M$ 回の操作後の $S$ としてありうるものの数を $1000000007$ で割った余りを出力してください。

5 2
01001
2 4
3 5

6

$1$回目の操作後の $S$ としてありうるものは、 01001, 00101, 00011 の $3$ つです。 $2$回目の操作後の $S$ としてありうるものは、 01100, 01010, 01001, 00011, 00101, 00110 の $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