問題文

長さ $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