Description

珂朵莉定义项为指若干个（$\ge1$）数字（$0\cdots 9$）相连得到的字符串（如 123 000 是合法的项，** *-1 +5 是不合法的项）。一个合法的表达式可以为一个项（如 233）、两个表达式以 + -* 相连（如2*3+5*5 6-6*6）、一个表达式在左右添一对括号（如 (2*3*3)）。

注意：空串不是一个合法的表达式。

在一开始，你会得到一个长为 $n$ 的字符串，之后会给定 $m$ 个操作。 有两种操作：

1 x y 表示将位置 $x$ 的字符改成 $y$。

2 l r 表示询问 $[l,r]$ 的字符串作为表达式求值在 $\bmod (10^9+7)$ 意义下的结果。若该串不是一个合法的表达式，结果为 $-1$。

Input Format

第一行有两个整数 $n,m$。

第二行有一个长为 $n$ 的字符串。

接下来 $m$ 行，每行为 1 x y 或 2 l r，分别表示两种操作。

Output Format

对所有 $2$ 的操作，输出一行，包含一个整数，表示答案。

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

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

字符集为 0 1 2 3 4 5 6 7 8 9 + - * ( )

若将 ( 作为 $1$，) 作为 $-1$，其他字符作为 $0$，则保证在任意时刻，该串的任意前缀和的绝对值不超过 $50$。