AT_arc065_d [ARC065F] シャッフル

有一个长度为 $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$ 取模。

## 限制条件 - $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 翻译