Problem Description

Aoki had made plans to play with Takahashi, but as Takahashi did not show up, Aoki decided to play the following game:

• Arrange $ N $ red cards and $ N-1 $ blue cards alternately in a row. That is, first arrange the red cards in a row, and then place a blue card between each pair of adjacent red cards.
• The $ i $-th red card from the left initially has a non-negative integer $ A_i $ written on it.
• The $ i $-th blue card from the left has a + on one side and a × on the other. Initially, the side with + is face up if $ S_i $ is +, and the side with × is face up if $ S_i $ is *.
• Aoki will execute $ Q $ queries in order. Each query is represented by three non-negative integers $ T_i, X_i, Y_i $ and is interpreted as follows:
• If $ T_i = 1 $, replace the integer on the $ X_i $-th red card from the left with $ Y_i $.
• If $ T_i = 2 $, flip the $ X_i $-th blue card from the left. In this query, $ Y_i = 0 $ is guaranteed.
• If $ T_i = 3 $ (response query), consider the subsequence of cards from the $ X_i $-th red card to the $ Y_i $-th red card as an expression and answer the result of the calculation. Since Aoki cannot calculate large numbers without paper or pen, answer the result modulo $ 10^9+7 $.

Iroha decided to write a program to simulate this game to verify if Aoki's answers are correct.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the correct answer for each response query in order, each on a new line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

10
20
27

Sample Input #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

Sample Output #2

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

Notes/Hints

Constraints

• $ S $ is a string of length $ N-1 $ consisting only of + and *, and all other inputs are integers.
• $2 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^9$
• $1 \leq Q \leq 10^5$
• For each query $ T_i, X_i, Y_i $, one of the following three conditions holds:
• $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$

Sample Explanation 1

In the first line, output $1 \times 2 \times 3 + 4 = 10$. The + and × are calculated as in normal arithmetic.

见题面 Input 部分

见题面 Output 部分