CF1252K Addition Robot

多次将两个数相加是一项耗时的任务，因此你想要制造一个机器人。该机器人在其内存中有一个长度为 $N$ 的字符串 $S = S_1 S_2 \dots S_N$，用于表示加法指令。字符串中的每个字符 $S_i$ 要么是 'A'，要么是 'B'。 你希望能够向机器人发出 $Q$ 个指令，每条指令有以下两种类型之一： - 1 $L$ $R$ ：机器人应当将所有满足 $L \le i \le R$ 的 $S_i$ 字符进行切换。切换字符的含义是：如果原本是 'A'，则变为 'B'；如果原本是 'B'，则变为 'A'。 - 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) ``` 你需要实现机器人的上述功能。

输入的第一行包含两个整数 $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$） 保证至少有一条第二种类型的指令。

对于每条第二种类型的指令，按输入顺序输出一行两个整数（用一个空格分隔），即 $f(L, R, A, B)$ 返回的 $A$ 和 $B$ 的值。由于输出可能很大，需要对 $1\,000\,000\,007$ 取模。

样例输入输出 #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)$。 由 ChatGPT 4.1 翻译