You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

##题目描述 鸡先生也是一名华中科技大学的大一新生。

和大家预想的不太一样的是, 鸡先生并没有加入联创团队, 也不喜欢唱跳和球。

鸡先生正在准备冰岩作坊游戏组的实习任务, 他现在遇到了一个棘手的问题。

鸡先生要构造出一个地图种子, 具体来说, 这是一个长度为 $n 的 01 串 s$ 。然而鸡先生想 要构造出更多的地图种子, 因此鸡先生给出了 $m$ 个区间 $[Li , Ri ]$ 鸡先生可以对区间内的数进 行重排。 每个区间只能操作一次, 并且区间操作需要按照顺序依次进行。

对 $m$ 个区间内的数全部重排之后, 鸡先生想知道, 这样可以得到多少个本质不同的 $01$ 串?

为了方便你处理, 鸡先生向你保证, 这些区间的 L 是单调不降的, 即保证了 $Li ≤ Li+1$

由于答案有点大, 因此你需要对 $10^9 + 7$ (一个质数) 取模 ##输入格式 第一行两个整数 n，m ，意义如题所示。 第二行一个字符串，为 s 接下来 m 行，每行两个整数，分别表示 [Li , Ri ] ##输出格式 一行一个整数，表示答案 ##输入样例 1

5 2
01001
2 4
3 5

##输出样例 1

6

##输入样例 2

9 3
110111110
1 4
4 6
6 9

##输出样例 2

26

##数据范围 对于 30% 的数据，$1 ≤ n, m ≤ 10 ；$

对于 60% 的数据，$1 ≤ n, m ≤ 100 ；$

对于 100% 的数据，$1 ≤ n, m ≤ 2000 ；$