问题描述

给定只包含 (, ), +, -, *, a 的数学表达式 $S$（请参考问题描述中的详细说明）。定义 $N$ 为 $S$ 中出现的 a 的个数。

给定 $N$ 个整数 $a_1, ..., a_N$ 和 $Q$ 个由两个整数 $(b_i, x_i)$ 组成的查询，请处理这些查询。

查询：将给定数学表达式中从左到右的第 $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> ')' 

约束条件

令 $N$ 为给定的数学表达式中 a 的个数。

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

在第三个查询中，将从左到右的第 $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$，因此答案为 $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