問題文

青木さんは高橋君と遊ぶ約束をしていましたが、待てど暮らせど高橋君が来ないので、次のような遊びをすることにしました。

• N 枚の赤いカードと N-1 枚の青いカードを、一列に交互に並べておく。つまり、まず赤いカードを一列に並べ、隣り合う赤いカードの間に青いカードを置く。
• 左から i 番目の赤いカードには、はじめ非負整数 A_i が書いてある。
• 左から i 番目の青いカードには、片方の面に + が、他方の面に × が書いてある。S_i が + のとき + の面が、S_i が * のとき × の面がはじめ表向きである。
• 青木さんは、Q 個のクエリを番号順に実行する。i 番目のクエリの内容は 3 つの非負整数 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 について、以下の 3 つのいずれかが成り立つ
  • 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

入力例 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

1行目には、1\times2\times3+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

解説

解説