Queries are not locks

Na-rak is a lock, a call from your parents is a lock, and 오락가락? is a lock?, but sadly a query is not a lock.

You are given a string $S=s_1 s_2 \ldots s_N$ of length $N$ made of uppercase English letters. Process $Q$ queries of the following kinds.

• $1$ $idx$ $c$: Change $s_{idx}$ to $c$. $(1 \leq idx \leq N,\ c$ is an uppercase English letter$)$
• $2$ $l$ $r$: Print the number of subsequences of $s_l s_{l+1} \ldots s_r$ that end with ROCK. Since the count can be very large, print it modulo $10^9+7$. $(1 \leq l \leq r \leq N)$

The first line contains the length $N$ of the string $S$. $(4 \leq N \leq 250000)$

The second line contains the string $S$, which consists only of uppercase English letters.

The third line contains the number of queries $Q$. $(1 \leq Q \leq 250000)$

The next $Q$ lines contain the queries. The last query given is a type 2 query.

For each type 2 query, print the answer on its own line.

A subsequence of a string is a string obtained by deleting zero or more characters from it. For example, aan is a subsequence of hanyang.