쿼리는 락이 아니다

면접 대비

시간 제한2초메모리 제한1024 MB

요약

문자열의 한 글자를 바꾸는 연산과 구간 질의가 주어질 때, 구간에서 ROCK과 같은 부분수열의 개수를 10^9+7로 나눈 나머지로 구합니다.

문제

나락도 락이고, 부모님께 온 연락도 락이고, 오락가락?도 락?이지만?, 아쉽게도 쿼리는 락이 아니다.

알파벳 대문자로 이루어진 길이 $N$ 의 문자열 $S=s_1 s_2 \ldots s_N$ 이 주어진다. 이때, 다음과 같은 쿼리를 $Q$ 번 처리해야 한다.

$1$ $idx$ $c$ : $s_{idx}$ 를 $c$ 로 변경한다. $(1 \leq idx \leq N,\ c$ 는 알파벳 대문자 $)$
$2$ $l$ $r$ : $s_l s_{l+1} \ldots s_r$ 의 부분열 중 ROCK으로 끝나는 문자열의 개수를 출력한다. 단, 수가 매우 클 수 있으니 $10^9+7$ 로 나눈 나머지를 출력한다. $(1 \leq l \leq r \leq N)$

첫 번째 줄에 문자열 $S$ 의 길이 $N$ 이 주어진다. $(4 \leq N \leq 250000)$

두 번째 줄에 알파벳 대문자로만 이루어진 문자열 $S$ 가 주어진다.

세 번째 줄에 쿼리의 개수 $Q$ 가 주어진다. $(1 \leq Q \leq 250000)$

네 번째 줄부터 $Q$ 개의 줄에 걸쳐 쿼리가 주어진다. 가장 마지막으로 주어지는 쿼리는 $2$ 번 쿼리이다.

$2$ 번 쿼리에 대해 정답을 한 줄에 하나씩 출력한다.

문자열의 부분열이란 문자열에서 $0$ 개 이상의 문자를 지운 문자열을 의미한다. 예를 들어, aan은 hanyang의 부분열이다.