题目描述

有一个长度为 $N$ 的只包含 0 和 1 的字符串 $S$。你需要按照以下方式，对每个 $1 \leq i \leq 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$ 取模。

样例 1

输入

5 2
01001
2 4
3 5

输出

6

样例 2

输入

9 3
110111110
1 4
4 6
6 9

输出

26

样例 3

输入

11 6
00101000110
2 4
2 3
4 7
5 6
6 10
10 11

输出

143

说明/提示

限制条件

• $2 \leq N \leq 3000$
• $1 \leq M \leq 3000$
• $S$ 只包含 0 和 1。
• $S$ 的长度等于 $N$。
• $1 \leq l_i < r_i \leq N$
• $l_i \leq l_{i+1}$

样例解释 1

第一次操作后，$S$ 可能出现的字符串有 01001、00101、00011，共 $3$ 种。第二次操作后，$S$ 可能出现的字符串有 01100、01010、01001、00011、00101、00110，共 $6$ 种。

由 ChatGPT 4.1 翻译