AT_arc065_d [ARC065F] シャッフル

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

### 制約 - $ 2≦N≦3000 $ - $ 1≦M≦3000 $ - $ S $ は`0`, `1` からなる。 - $ S $ の長さは $ N $ と等しい。 - $ 1≦l_i\