Add or Multiply

Your younger sister is playing with a wooden math toy made of number blocks and operator blocks. Each number block shows a single digit from 1 to 9. Each operator block is double-sided, and each side shows + or ×.

She has 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 whether you can find the value of the expression.

She then 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 ×.
• a (all flip): Flips all the operator blocks in the expression.

After each move, you must quickly answer the updated value, which may be the same as the previous one. Remember that multiplication is performed before addition.

The first line 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 contains the initial expression of $2N - 1$ characters. Single digits from 1 to 9 are at odd positions, and operators + or * are at even positions.

Each of the next $M$ lines describes one move.

• The swap move is given as s $i$ $j$, with $1 \leq i, j \leq N$. If $i = j$, no blocks are swapped.
• The flip move is given as f $i$, with $1 \leq i \leq N-1$, meaning the $i$th operator is flipped.
• The all-flip move is given as a, with no other parameters.

On the first line, print the value of the initial expression. Then print $M$ more lines, one for each move, containing the value after that move. Print each value modulo $10^9 + 7$.