Chtholly defines a "term" as a string formed by concatenating one or more ($\ge 1$) digits ($0 \cdots 9$) (e.g., 123 and 000 are valid terms, while **, -1, and +5 are invalid). A valid expression can be a single term (e.g., 233), two expressions connected by +, -, or * (e.g., 2*3+5*5, 6-6*6), or an expression enclosed in a pair of parentheses (e.g., (2*3*3)).

Note: An empty string is not a valid expression.

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

1 x y: Change the character at position $x$ to $y$.

2 l r: Query the result of evaluating the substring $[l, r]$ as an expression modulo $10^9+7$. If the string is not a valid expression, the result is $-1$.

Input

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

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

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

Output

For each operation of type 2, output a single integer representing the result on a new line.

Examples

Input 1

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

Output 1

2
3
6
-1
46
4
-1
8

Constraints

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

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

If ( is treated as $1$, ) as $-1$, and all other characters as $0$, it is guaranteed that at any time, the absolute value of the prefix sum of the string does not exceed $50$.