쿼리는 락이 아니다

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

알파벳 대문자로 이루어진 길이 $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의 부분열이다.