Description

Chtholly defines a term as a string formed by concatenating several ($\ge 1$) digits ($0\cdots 9$) (for example, 123 and 000 are valid terms, while ** *-1 +5 are invalid terms). A valid expression can be:

• A term (e.g. 233).
• Two expressions connected by + - * (e.g. 2*3+5*5, 6-6*6).
• An expression with a pair of parentheses added to its left and right (e.g. (2*3*3)).

Note: the empty string is not a valid expression.

Initially, you are given a string of length $n$. Then $m$ operations are given. There are two types of operations:

• 1 x y: change the character at position $x$ to $y$.
• 2 l r: query the value of the substring $[l, r]$ as an expression modulo $\bmod (10^9+7)$. If the substring is not a valid expression, the result is $-1$.

Input Format

The first line contains two integers $n, m$.

The second line contains a string of length $n$.

The next $m$ lines each contain 1 x y or 2 l r, representing the two types of operations.

Output Format

For every operation of type 2, output one line containing one integer, which is the answer.

5 12
2*(3)
2 1 1
2 4 4
2 1 5
1 3 2
2 1 5
2 1 4
2 1 3
2 2 3
1 1 (
1 2 5
1 3 +
2 1 5

2
3
6
-1
46
4
-1
8

Hint

Idea: mcfx, Solution: mcfx, Code: mcfx, Data: mcfx.

Constraints: $1\leq n, m \leq 10^5$, $1 \leq l \leq r \leq n$, $1 \leq x \leq n$.

The character set is 0 1 2 3 4 5 6 7 8 9 + - * ( ).

If we treat ( as $1$, ) as $-1$, and other characters as $0$, then it is guaranteed that at any moment, for any prefix of the string, the absolute value of the prefix sum is at most $50$.

Translated by ChatGPT 5