問題文

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

• $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$

入力

入力は以下の形式で標準入力から与えられます。

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

出力

各回答クエリの正しい答えをそれぞれ $1$ 行で順に出力してください。

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

解説

解説