Expression Evaluator with Updates

This problem involves evaluating arithmetic expressions that may be updated over time. An item is defined as a non-empty string of digits (from 0 to 9). A valid expression is defined by the following grammar:

1. A term is one or more digits, for example, 123 or 000.
2. A factor is either a term or an expression wrapped in a pair of parentheses: (expression).
3. An expression is a factor, or two expressions concatenated with one of the operators +, -, or *.

Note that the empty string is not considered a valid expression.

The operators obey the usual precedence: multiplication (*) has higher precedence than addition (+) and subtraction (-), and parentheses can be used to override this order. All operations are computed under modulo \(10^9+7\).

You are given an initial string of length \(n\), followed by \(m\) operations. Two types of operations can occur:

• 1 x y: Update the character at position \(x\) (1-indexed) with character \(y\).
• 2 l r: Evaluate the substring from index \(l\) to \(r\) (inclusive) as an expression. If the substring is not a valid expression, output -1.

Make sure that your answer code parses the expression correctly following this grammar. Use the following grammar in LaTeX format for your reference:

[ \begin{array}{rcl} \text{number} & ::= & \text{digit}+ \ \text{factor} & ::= & \text{number} ;|; (,\text{expression},) \ \text{term} & ::= & \text{factor} ; (, ,\text{factor},) \ \text{expression} & ::= & \text{term} ; ((, + ;|; -,) \text{term})* \end{array} ]

Good luck!

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) -- the length of the string and the number of operations, respectively.

The next line contains a string \(S\) of length \(n\) which consists of digits (0-9), the operators +, -, * and/or parentheses.

Then follow \(m\) lines, each representing an operation. An operation is given in one of the following two formats:

• 1 x y: Update the character at the \(x\text{-th}\) position of \(S\) to character y.
• 2 l r: Query the substring \(S[l...r]\). If it forms a valid expression according to the rules described, output its value evaluated modulo \(10^9+7\); otherwise, output -1.

outputFormat

For each operation of type 2, output a single line containing the evaluated result modulo \(10^9+7\) if the substring is a valid expression, or -1 if it is not.

sample

5 3
2*3+5
2 1 5
1 3 *
2 1 5

11
-1

</p>