Problem Description

You are given a formula $ S $ consisting of (, ), +, -, *, and a (see the later part of the problem statement for details). Let $ N $ be the number of as in $ S $.

You are given $ N $ integers $ a_1, ..., a_N $ and $ Q $ queries consisting of two integers $ (b_i, x_i) $. Process these queries.

Query: Replace the $ b_i $-th a in the given formula with $ x_i $, and replace the $ 1, ..., b_i-1, b_i+1, ..., N $-th as with $ a_1, ..., a_{b_i-1}, a_{b_i+1}, ..., a_N $ respectively. Output the value of the modified formula modulo $ 10^9+7 $ as an integer between $ 0 $ and $ 10^9+6 $.

The given formula $ S $ can be represented by the <expr> symbol in the following BNF notation:

<expr> ::= <term> | <expr> '+' <term> | <expr> '-' <term>
<term> ::= <value> | <term> '*' <value>
<value> ::= 'a' | '(' <expr> ')' 

Input Format

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

$ S $ $ Q $ $ a_1 $ ... $ a_N $ $ b_1 $ $ x_1 $ : $ b_Q $ $ x_Q $

Output Format

Output $ Q $ lines. The $ i $-th line ($1 \leq i \leq Q$) should contain the answer for the $ i $-th query.

Sample Input and Output

Sample Input #1

(a-(a))*a
4
0 1 2
1 1
1 2
2 1
1 4

Sample Output #1

0
2
1000000005
6

Sample Input #2

(a)*a+((a+(a*(a))-(a)*a+a*a))*a
10
8 6 6 4 8 1 4 3 8 9
3 4
3 9
8 4
3 7
4 0
8 9
3 6
9 0
6 8
9 4

Sample Output #2

552
597
642
579
282
1002
570
354
318
462

Notes/Hints

Constraints

Let $ N $ be the number of as in the given formula.

• The length of $ S $ is at most $ 200,000 $
• $ S $ can be represented by the <expr> symbol in the BNF notation given in the problem
• $0 \leq a_i < 10^9+7$
• $1 \leq Q \leq 10^5$
• $1 \leq b_i \leq N$
• $0 \leq x_i < 10^9+7$
• $ x_i $ is an integer

Sample Explanation 1

For example, in the first query, the $ 1 $-st a is replaced with $ x_1 = 1 $, the $ 2 $-nd a with $ a_2 = 1 $, and the $ 3 $-rd a with $ a_3 = 2 $. The calculation results in $ (1-(1))*2 = 0 $, so the answer is $ 0 $. In the third query, the $ 1 $-st a is replaced with $ a_1 = 0 $, the $ 2 $-nd a with $ x_3 = 1 $, and the $ 3 $-rd a with $ a_3 = 2 $. The calculation results in $ (0-(1))*2 = -2 $, so the answer is $ 10^9+5 $ modulo $ 10^9+7 $.

见题面 Input 部分

见题面 Output 部分