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.

题目描述 注意：此题本质不同的01串指长的不同。 鸡先生是一名华中科技大学的大一新生。

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

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

鸡先生要构造出一个地图种子,具体来说,这是一个长度为$n$的01串$s$。然而鸡先生想要构造出更多的地图种子,因此鸡先生给出了$m$个区间$[L_i,R_i]$鸡先生可以对区间内的数进行重排。

每个区间只能操作一次,并且区间操作需要按照顺序依次进行。

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

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

由于答案有点大,因此你需要对$10^9+7$(一个质数)取模

【输入格式】

第一行两个整数$n，m$ ，意义如题所示。

第二行一个字符串，为$s$

接下来$m$行，每行两个整数，分别表示$[L_i,R_i]$

【输出格式】

一行一个整数，表示答案

【输入样例1】

5 2
01001
2 4
3 5

输出样例1

6

输入样例2

9 3
110111110
1 4
4 6
6 9

输出样例2

26

数据范围

对于$30\%$的数据，$1\leq n,m\leq 10$；

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

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