Calculation mistake

Suchan uses a calculator that only adds and subtracts. It has the digit buttons 0 through 9, the operator buttons + and -, an = button that shows the result, and an AC button that returns the calculator to its initial state. There is no C button that clears only the number being typed.

Type an expression in order and press =, and the screen shows the result. The numbers have no range limit, and a number may start with 0. To keep a mistyped operator from spoiling the result, the calculator follows three rules.

1. When operators appear one after another, only the last one counts.
2. When the expression starts with an operator, a 0 is treated as written in front of it.
3. When the expression ends with an operator, that operator is ignored.

For example, press -15+0035-+-3- in order and then =. The calculator evaluates $0 - 15 + 35 - 3$ and shows 17. Press only - and then =: the expression becomes $0-$, the final - is ignored, and the result is 0.

Without a C button, one wrong digit forces Suchan to press AC and type the whole expression again. To get rid of that, he decided to build the following data structure.

There is a string $S$ of length $N$ made only of 0 through 9, +, and -. For a string $X$ and $1 \le i \le j \le |X|$, let $X[i..j]$ be the substring formed by concatenating the $i$-th through $j$-th characters of $X$.

Implement a data structure that supports the two operations below.

1. Replace: change $S[a..b]$ into a new string $T$ of length $b - a + 1$. That is, for every $i$ with $a \le i \le b$, set $S[i]$ to $T[i - a + 1]$.
2. Evaluate: press AC, type $S[a..b]$ into the calculator, press =, and report the value shown on the screen.

The first line contains the length of the string, $N$ ($1 \le N \le 200\,000$).

The second line contains the string $S$. Its length is $N$.

The third line contains the number of queries, $Q$ ($1 \le Q \le 300\,000$).

Each of the next $Q$ lines contains one operation. The formats are below.

• A replace operation is given as 1 a b T. Here $a$ and $b$ are integers with $1 \le a \le b \le N$, and $T$ is a string of length $b - a + 1$. The lengths of $T$ over all replace operations sum to at most $200\,000$.
• An evaluate operation is given as 2 a b. Here $a$ and $b$ are integers with $1 \le a \le b \le N$. At least one evaluate operation is given.

Every string in the input consists only of 0 through 9, +, and -.

For each evaluate operation, print the result modulo $10^9 + 7$ on its own line. The remainder of an integer $x$ modulo $10^9 + 7$ is the value of $r$ for which integers $q$ and $r$ satisfy $x = q(10^9 + 7) + r$ and $0 \le r < 10^9 + 7$.