Background

【She kept the promise...】
【From a battlefield where no one could possibly survive】
【Only thinking of meeting the technician officer... wanting to act cute to the technician officer...】
【That was why she managed to preserve just a tiny bit of lifespan... and came back safely...】
That’s right... she kept the promise...
But I couldn’t say anything to her.
I couldn’t do anything for her.
Nothing...

......
Chtholly......

In the past, whenever I ran into helpless things like other people’s tragedies or misfortunes,
I always tried to change something.
But my power has always been far too small...

In the end, I couldn’t help at all...
I should have already understood that deeply...
I want Chtholly to be happy...
I really can’t stand that guy...
A man like me, what on earth is there that she could fall for...

【You can’t even figure out something this simple?】
【Because you... are the person who let me experience so, so many firsts...】
【On the open-air street stalls, you saved me for the first time】
【You were the first to take me to a place with a wide view to look at the scenery】
【You made me feel all kinds of emotions for the first time】
【You were the first person I relied on, and also the first opponent who defeated me】

【Ah... if I really start counting, I can’t even finish counting...】
【So, it’s only natural that the first person I fell in love with was you】

【At least you should have noticed something this small, you i-di-ot】
【I... what is wrong with me?】
【I remember I went back to the warehouse, and had a strange dream】

【You didn’t come back for a long time...】
【What’s wrong, why are you making that face?】
Welcome back... Chtholly.

Welcome back...

Problem 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