Add or Multiply

문제

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 $11$ to $99$, and operator blocks are double-sided; $++$ and $\times \backslash 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 $ii$ $jj$ (swap): Swaps the $ii$th and $jj$th number blocks.
• f $ii$ (flip): Flips the $ii$th operator block. Its operator alternates between $++$ and $\times \backslash 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.

입력

The first line of input contains two integers $NN$ ($2\le N\le 2\times {10}^{5}2\; \backslash leq\; N\; \backslash leq\; 2\; \backslash times\; 10^5$) and $MM$ ($1\le M\le 2\times {10}^{5}1\; \backslash leq\; M\; \backslash leq\; 2\; \backslash times\; 10^5$), where $NN$ is the number of integers and $MM$ is the number of queries.

The second line represents the initial input of $2N-12N\; -\; 1$ characters. Single digits between $11$ and $99$ are at odd positions, and operators $++$ ("+") or $\times \backslash times$ ("*") are at even positions.

Each of the next $MM$ lines represents your sister's move.

The swap move is described as "s $ii$ $jj$" with $1\le i,j\le N1\; \backslash leq\; i,\; j\; \backslash leq\; N$, where $ii$ and $jj$ are the 1-indexed positions to swap. If $i=ji=j$, then no blocks are swapped.

The flip move is described as "f $ii$" with $1\le i\le N-11\; \backslash leq\; i\; \backslash leq\; N-1$, meaning your sister flips the $ii$th operator.

Finally, the all-flip move is described as "a", without additional parameters.

출력

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

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

14
11
10
24
9