你的妹妹正在玩一套木制数学玩具，由数字块和运算符块组成。每个数字块上印有一个 1 到 9 之间的数字，运算符块是双面的，两面分别印有 $+$ 和 $\times$。她刚刚用交替排列的数字块和运算符块搭建了一个数学表达式。第一个块是数字，第二个是运算符，第三个是数字，以此类推。她问你：“你能算出这个表达式的值吗？”

此外，她会重复进行以下操作之一：

• $s\ i\ j$ (交换)：交换第 $i$ 个和第 $j$ 个数字块。
• $f\ i$ (翻转)：翻转第 $i$ 个运算符块。其运算符在 $+$ 和 $\times$ 之间切换。
• $a$ (全部翻转)：翻转整个数学表达式中的所有运算符块。

在每次操作后，你都需要快速回答更新后的表达式的值（可能与上一次相同）。请记住，乘法运算的优先级高于加法。

输入格式

第一行包含两个整数 $N$ ($2 \le N \le 2 \times 10^5$) 和 $M$ ($1 \le M \le 2 \times 10^5$)，其中 $N$ 是数字的个数，$M$ 是操作的次数。第二行表示初始输入的 $2N - 1$ 个字符。奇数位置是 1 到 9 之间的单个数字，偶数位置是运算符 $+$（“+”）或 $\times$（“*”）。接下来的 $M$ 行，每行代表你妹妹的一次操作。交换操作描述为 “$s\ i\ j$”，其中 $1 \le i, j \le N$，$i$ 和 $j$ 是要交换的 1-索引位置。如果 $i = j$，则不交换任何块。翻转操作描述为 “$f\ i$”，其中 $1 \le i \le N - 1$，表示你妹妹翻转了第 $i$ 个运算符。最后，全部翻转操作描述为 “$a$”，没有额外参数。

输出格式

第一行输出应为初始表达式的值。然后，输出 $M$ 行，每行对应一次操作后的结果。由于数值可能很大，请将结果对 $10^9 + 7$ ($= 1\,000\,000\,007$) 取模。

说明

样例 1 的初始输入。

样例 1 的解释：

• $2 + 3 \times 4 = 14$：初始表达式。
• $3 + 2 \times 4 = 11$：交换第一个数字 (2) 和第二个数字 (3)。
• $3 \times 2 + 4 = 10$：翻转所有运算符。
• $3 \times 2 \times 4 = 24$：翻转第二个运算符 (+)。
• $3 + 2 + 4 = 9$：再次翻转所有运算符。

样例

输入 1

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

输出 1

14
11
10
24
9