Problem K
Add or Multiply

Initial input of Sample 1.

Your younger sister is playing with a wooden math toy consisting of number and operator blocks. Each number block is printed with a single digit from $1$ to $9$, and operator blocks are double-sided; $+$ and $\times $ are printed on each side. She has just built a math expression by alternating number and operator blocks. The first block is a number, the second is an operator, the third is a number, and so on. She asks, "can you answer the value of the expression?"

Further, she repeatedly makes one of the following moves.

• s $i$ $j$ (swap): Swaps the $i$th and $j$th number blocks.

• f $i$ (flip): Flips the $i$th operator block. Its operator alternates between $+$ and $\times $.

• a (all flip): Flips all the operator blocks in the entire math expression.

After her move, you have to quickly answer the updated value (possibly the same as the previous one). Remember that you must perform multiplications earlier than additions.

Input

The first line of input contains two integers $N$ ($2 \leq N \leq 2 \times 10^5$) and $M$ ($1 \leq M \leq 2 \times 10^5$), where $N$ is the number of integers and $M$ is the number of queries. The second line represents the initial input of $2N - 1$ characters. Single digits between $1$ and $9$ are at odd positions, and operators $+$ (“+”) or $\times $ (“*”) are at even positions. Each of the next $M$ lines represents your sister’s move. The swap move is described as “s $i$ $j$” with $1 \leq i, j \leq N$, where $i$ and $j$ are the 1-indexed positions to swap. If $i=j$, then no blocks are swapped. The flip move is described as “f $i$” with $1 \leq i \leq N-1$, meaning your sister flips the $i$th operator. Finally, the all-flip move is described as “a”, without additional parameters.

Output

The first line of output should be the value of the initial expression. Then, output $M$ more lines, one for each move. Since values can be large, print the value modulo $10^9 + 7$ ($=1\, 000\, 000\, 007$).

Explanation of Sample 1

• $2 + 3 \times 4 = 14$ : initial expression.

• $3 + 2 \times 4 = 11$ : swaps the first number ($2$) and the second number ($3$).

• $3 \times 2 + 4 = 10$ : flips all the operators.

• $3 \times 2 \times 4 = 24$ : flips the second operator ($+$).

• $3 + 2 + 4 = 9$ : again, flips all the operators.

3 4
2+3*4
s 1 2
a
f 2
a

14
11
10
24
9