덧셈 로봇

여러 번 두 수를 더하는 일은 시간이 많이 걸리므로, 로봇을 하나 만들려고 한다. 로봇의 메모리에는 덧셈 명령을 나타내는 길이 $N$의 문자열 $S = S_1S_2\ldots 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)
  

로봇이 기대대로 동작하도록 구현하라.

첫 줄에 두 정수 $N$과 $Q$가 주어진다. ($1 \le N, Q \le 100\,000$) $N$은 로봇 메모리 속 문자의 수, $Q$는 명령의 수이다. 다음 줄에는 로봇 메모리의 초기 문자열을 나타내는 길이 $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$로 나눈 나머지를 출력한다.

첫 번째 명령에서 $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)$을 반환한다.