该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

你有一个字符串 $s = S_1 S_2 \dots S_n$，其中每个字符是 0 或 1。你需要处理 $q$ 条命令，每条命令是以下两种类型之一：

1. 1 l r：将区间 $[l, r]$ 内的每个字符设置为 0。
2. 2 l r：将区间 $[l, r]$ 内的每个字符设置为 1。
3. 3 l r：翻转 $s$ 的区间 $[l, r]$ 内的每个字符（0 变为 1，1 变为 0）。
4. 4 l r：求子串 $[l, r]$ 中互不相同的非空子序列数量，对 $1\,000\,000\,007$ 取模。

你需要处理所有命令，并对每个类型 4 的命令输出结果。

Constraints and Subtasks

对于所有测试数据，满足：

• $1 \leq n, q \leq 10^5$；
• $S$ 的长度为 $n$，且仅由 0 和 1 构成；
• $1 \leq l \leq r \leq n$；
• 除字符串以外的输入为整数。

另外，还有一些测试点满足特殊要求。

Input

输入格式如下：

$ \boxed{ \begin{aligned} & id \\ & n \quad q \\ & s \\ & t_1 \quad l_1 \quad r_1 \\ & t_2 \quad l_2 \quad r_2 \\ & \vdots \\ & t_q \quad l_q \quad r_q \\ \end{aligned} } $

其中 $t_i$ 表示第 $i$ 次操作的操作类型。

Output

对于每个类型 4 的命令，输出一行一个整数，表示区间内互不相同的子序列数量对 $1\,000\,000\,007$ 取模的结果。

Samples

6 5
110101
4 1 3
1 1 3
2 1 2
3 1 4
4 2 6

5
15

第一个操作要查询 $S=$110 中互不相同的非空子序列数量。

• 子序列 $S_1$ 为 1；
• 子序列 $S_2$ 为 1；
• 子序列 $S_3$ 为 0；
• 子序列 $S_1, S_2$ 为 11；
• 子序列 $S_1, S_3$ 为 10；
• 子序列 $S_2, S_3$ 为 10；
• 子序列 $S_1, S_2, S_3$ 为 110；

互不相同的非空子序列有 1、0、11、10 和 110，所以答案为 $5$。