問題文

(, ), +, -, *, 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$ は整数

入力

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

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

出力

$Q$ 行出力せよ。 $i$ 行目 ($1 ≤ i ≤ Q$) には、$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