题目描述

有一个长度为 $N$ 的字符串 $S$，由字符 0 和 1 组成。对于每个 $i = 1, 2, ..., m$，你将执行以下操作：

• 随机排列 $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

第一次操作后，$S$ 可能是以下三种情况之一： 01001， 00101 和 00011。

第二次操作后，$S$ 可能是以下六种情况之一： 01100， 01010， 01001， 00011， 00101 和 00110。

示例输入 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