問題文

(, ), +, -, *, a のみからなる数式 S が与えられます(詳細は問題文の後半を参照してください)。S に含まれる a の個数を N とします。

N 個の整数 a_1, ..., a_N と 2 個の整数 (b_i, x_i) からなる Q 個のクエリが与えられるので、これらのクエリを処理してください。

クエリ: 与えられた数式中の左から b_i 番目の a を x_i に、左から 1, ..., b_i-1, b_i+1, ..., N 番目の a をそれぞれ a_1, ..., a_{b_i-1}, a_{b_i+1}, ..., a_N に置き換えた数式の値と 10^9+7 を法として合同な 0 以上 10^9+6 以下の整数を出力する。

この問題で与えられる数式 S は、以下のような BNF 表記の <expr> シンボルで表されます。

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

制約

与えられる数式に含まれる a の個数を N とします。

• S の長さは 200\,000 以下
• S は問題文中の BNF 表記の <expr> シンボルとして表せる
• 0 ≤ a_i < 10^9+7
• 1 ≤ Q ≤ 10^5
• 1 ≤ b_i ≤ N
• 0 ≤ x_i < 10^9+7
• x_i は整数

入力例 1

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

出力例 1

0
2
1000000005
6

例えば最初のクエリでは、左から 1 番目の a には x_1 = 1 が、左から 2 番目の a には a_2 = 1 が、左から 3 番目の a には a_3 = 2 を代入し、計算すると、 (1-(1))*2 = 0 となり、0 が答えです。

3 番目ののクエリでは、左から 1 番目の a には a_1 = 0 が、左から 2 番目の a には x_3 = 1 が、左から 3 番目の a には a_3 = 2 を代入し、計算すると、 (0-(1))*2 = -2 となり、10^9+7 を法として -2 と合同な 0 以上 10^9+6 以下の整数である、10^9+5 が答えです。

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

出力例 2

552
597
642
579
282
1002
570
354
318
462