CF1252K.Addition Robot

Adding two numbers several times is a time-consuming task, so you want to build a robot. The robot should have a string $S = S_1 S_2 \dots S_N$ of $N$ characters on its memory that represents addition instructions. Each character of the string, $S_i$, is either 'A' or 'B'.

You want to be able to give $Q$ commands to the robot, each command is either of the following types:

• 1 $L$ $R$. The robot should toggle all the characters of $S_i$ where $L \le i \le R$. Toggling a character means changing it to 'A' if it was previously 'B', or changing it to 'B' if it was previously 'A'.

• 2 $L$ $R$ $A$ $B$. The robot should call $f(L, R, A, B)$ and return two integers as defined in the following pseudocode:

      function f(L, R, A, B):      FOR i from L to R        if S[i] = 'A'          A = A + B        else          B = A + B      return (A, B)  
  

You want to implement the robot's expected behavior.

多次执行两个数相加是一项耗时的任务，因此你希望构建一个机器人。该机器人内存中应存储一个长度为 $N$ 的字符串 $S = S_1 S_2 \dots S_N$，用于表示加法指令。字符串的每个字符 $S_i$ 要么是 'A'，要么是 'B'。

你希望向机器人发出 $Q$ 条命令，每条命令为以下两种类型之一：

• 1 $L$ $R$：机器人应翻转所有满足 $L \le i \le R$ 的字符 $S_i$。翻转一个字符指：若其原为 'B'，则变为 'A'；若其原为 'A'，则变为 'B'。

• 2 $L$ $R$ $A$ $B$：机器人应调用函数 $f(L, R, A, B)$ 并返回两个整数，该函数定义如下伪代码所示：

      function f(L, R, A, B):      FOR i from L to R        if S[i] = 'A'          A = A + B        else          B = A + B      return (A, B)  
  

你需要实现该机器人所期望的行为。

Input begins with a line containing two integers: $N$ $Q$ ($1 \le N, Q \le 100\,000$) representing the number of characters in the robot's memory and the number of commands, respectively. The next line contains a string $S$ containing $N$ characters (each either 'A' or 'B') representing the initial string in the robot's memory. The next $Q$ lines each contains a command of the following types.

• 1 $L$ $R$ ($1 \le L \le R \le N$)
• 2 $L$ $R$ $A$ $B$ ($1 \le L \le R \le N$; $0 \le A, B \le 10^9$)

There is at least one command of the second type.

输入的第一行包含两个整数：$N$ 和 $Q$（$1 \le N, Q \le 100\,000$），分别表示机器人内存中的字符数量和命令数量。
第二行包含一个长度为 $N$ 的字符串 $S$，其中每个字符均为 'A' 或 'B'，表示机器人内存中的初始字符串。
接下来的 $Q$ 行每行包含以下两种类型之一的命令：

• 1 $L$ $R$（$1 \le L \le R \le N$）
• 2 $L$ $R$ $A$ $B$（$1 \le L \le R \le N$；$0 \le A, B \le 10^9$）

至少存在一条第二类命令。

For each command of the second type in the same order as input, output in a line two integers (separated by a single space), the value of $A$ and $B$ returned by $f(L, R, A, B)$, respectively. As this output can be large, you need to modulo the output by $1\,000\,000\,007$.

对于输入中每个第二类命令，按输入顺序，每行输出两个整数（用单个空格分隔），分别为函数 $f(L, R, A, B)$ 返回的 $A$ 和 $B$ 的值。由于该输出可能很大，你需要将输出对 $1\,000\,000\,007$ 取模。

Explanation for the sample input/output #1

For the first command, calling $f(L, R, A, B)$ causes the following:

• Initially, $A = 1$ and $B = 1$.
• At the end of $i = 1$, $A = 2$ and $B = 1$.
• At the end of $i = 2$, $A = 2$ and $B = 3$.
• At the end of $i = 3$, $A = 5$ and $B = 3$.
• At the end of $i = 4$, $A = 8$ and $B = 3$.
• At the end of $i = 5$, $A = 11$ and $B = 3$.

Therefore, $f(L, R, A, B)$ will return $(11, 3)$.

For the second command, string $S$ will be updated to "ABBBB".

For the third command, the value of $A$ will always be $0$ and the value of $B$ will always be $1\,000\,000\,000$. Therefore, $f(L, R, A, B)$ will return $(0, 1\,000\,000\,000)$.

样例输入/输出 #1 的说明

对于第一条命令，调用 $f(L, R, A, B)$ 将导致以下过程：

• 初始时，$A = 1$ 且 $B = 1$。
• 在 $i = 1$ 结束时，$A = 2$ 且 $B = 1$。
• 在 $i = 2$ 结束时，$A = 2$ 且 $B = 3$。
• 在 $i = 3$ 结束时，$A = 5$ 且 $B = 3$。
• 在 $i = 4$ 结束时，$A = 8$ 且 $B = 3$。
• 在 $i = 5$ 结束时，$A = 11$ 且 $B = 3$。

因此，$f(L, R, A, B)$ 将返回 $(11, 3)$。

对于第二条命令，字符串 $S$ 将被更新为 "ABBBB"。

对于第三条命令，$A$ 的值始终为 $0$，而 $B$ 的值始终为 $1\,000\,000\,000$。因此，$f(L, R, A, B)$ 将返回 $(0, 1\,000\,000\,000)$。