问题文

青木和高桥约好一起玩，但是高桥迟迟未到，所以青木决定玩以下的游戏。

• 准备 $N$ 张红色卡片和 $N-1$ 张蓝色卡片，交替排列在一列中。也就是说，先排列红色卡片，然后在相邻的红色卡片之间放置蓝色卡片。
• 第 $i$ 张从左数的红色卡片上写着一个非负整数 $A_i$。
• 第 $i$ 张从左数的蓝色卡片有两面，一面写着 +，另一面写着 ×。如果 $S_i$ 是 +，则 + 面朝上；如果 $S_i$ 是 *，则 × 面朝上。
• 青木要执行 $Q$ 个查询，按照编号依次执行。第 $i$ 个查询有三个非负整数 $T_i, X_i, Y_i$，具体解释如下：
  • 如果 $T_i = 1$，将第 $X_i$ 张从左数的红色卡片的数字替换为 $Y_i$。
  • 如果 $T_i = 2$，翻转第 $X_i$ 张从左数的蓝色卡片。注意，在这个查询中有保证 $Y_i = 0$。
  • 如果 $T_i = 3$（回答查询），将从左数第 $X_i$ 张红色卡片到第 $Y_i$ 张红色卡片组成的子序列看作数学表达式，并计算表达式的结果。然而，青木无法在没有纸和笔的情况下计算大数，所以需要取表达式结果除以 $10^9+7$ 的余数作为答案。

为了确认青木的答案是否正确，伊洛哈决定编写一个模拟以上游戏的程序。

制约条件

• 字符串 $S$ 长度为 $N-1$，仅由 + 和 * 组成；其他都是整数。
• $2 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^9$
• $1 \leq Q \leq 10^5$
• 对于每个查询 $T_i, X_i, Y_i$，以下三种情况之一成立：
  • $T_i = 1, 1 \leq X_i \leq N, 0 \leq Y_i \leq 10^9$
  • $T_i = 2, 1 \leq X_i \leq N - 1, Y_i = 0$
  • $T_i = 3, 1 \leq X_i \leq Y_i \leq N$

输入

输入以以下格式从标准输入中给出。

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $S$ $Q$ $T_1$ $X_1$ $Y_1$ $\vdots$ $T_Q$ $X_Q$ $Y_Q$

输出

请逐行按顺序输出每个回答查询的正确答案。

输入示例 1

5
1 2 3 4 100
**+*
5
3 1 4
1 5 5
3 4 5
2 1 0
3 1 5

输出示例 1

10
20
27

第一行输出答案 $10$，因为 $1 \times 2 \times 3 + 4 = 10$。+ 和 * 的计算规则与常规四则运算相同。

输入示例 2

30
141056031 626562406 398984580 302301632 724833823 819260147 433302050 210081 464012738 867417506 592634049 207581070 196502965 201049574 651294024 481261837 785858015 132486153 389688195 704728852 193622905 503147306 35766369 884292216 743597128 172030481 568485269 51112624 850324303 618492623
**+**++++*+***+*++******++*++
30
3 8 9
2 21 0
1 18 32689954
2 27 0
2 28 0
3 5 23
3 3 3
1 19 705926811
3 19 21
2 8 0
2 20 0
3 8 25
2 2 0
1 23 249011956
3 4 17
2 2 0
2 2 0
3 15 23
3 1 16
2 2 0
3 20 28
3 17 21
1 25 300797469
2 14 0
3 6 30
3 4 28
2 10 0
1 5 102545023
1 30 895902786
3 1 30

输出示例 2

464222819
10116361
398984580
494861147
781529391
919851764
726060889
72956646
887945392
641812930
620768060
243676249
751282029

解说

解说