Broken Calculator Game

You find a suspicious calculator on the road. As you pick it up, a murderer appears behind you. You run as hard as you can, but you end up at a dead end. From behind you hear 'Let's start the game,' and a formula appears on the calculator. A life-or-death game begins.

The game is to evaluate the formula on the calculator. Following the rules of this broken calculator is not easy.

1. The formula has length N and consists of the digits 0 to 9 and the operators '+' and '*'.
2. When evaluating the formula, ignore every operator that is at the start of the formula or directly follows another operator. Then, if the last character of the formula is an operator, ignore that operator too.
3. When evaluating the formula, '*' is computed before '+'.
4. The value of the formula is always taken modulo $10^9+7$.
5. A formula that contains only operators has the value -1.

For example, '**11+*3*+5++' is read as '11+3*5', so the answer is 26. '**+++**+++' gives -1.

You planned to evaluate the formula once and end the game. However, participants with suspiciously high ratings kept pressuring the setters to add query problems, so the formula on the calculator changes Q times.

Each change is written as l r x. It adds x to every digit from the l-th to the r-th character of the formula. Only when processing queries, '+' and '*' are also treated as numbers, with values 10 and 11. If the sum is 12 or more, apply the remainder modulo 12.

Compute the values of all Q+1 formulas shown on the calculator and survive the game!

The first line contains N and Q, where $1 \le N \le 100{,}000$ and $1 \le Q \le 100{,}000$.

The second line contains the formula of length N.

From the third line on, each of the Q lines contains one query, where $1 \le l \le r \le N$ and $1 \le x < 12$.

The first line prints the value of the given formula modulo $10^9+7$. If the formula consists only of operators, print -1.

From line 2 to line Q+1, line i prints the value of the formula after applying the (i-1)-th query, modulo $10^9+7$. If the formula consists only of operators, print -1.