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.
Output
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\).
Note
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
|
5 3
ABAAA
2 1 5 1 1
1 3 5
2 2 5 0 1000000000
|
11 3
0 1000000000
|