AT_bitflyer2018_final_e 数式とクエリ

现有一个仅由字符 `(`, `)`, `+`, `-`, `*`, `a` 组成的数学表达式 $ S $（具体定义参见下文 BNF 描述）。假设表达式中的字符 `a` 总共有 $ N $ 个。 接下来有 $ Q $ 个查询，每个查询提供 $ N $ 个整数 $ a_1, \ldots, a_N $ 和一对整数 $(b_i, x_i)$。你的任务是处理这些查询。 **处理查询**：对于每个查询，将表达式中从左到右第 $ b_i $ 个 `a` 替换为 $ x_i $，其他位置的 `a` 替换为 $ a_1, \ldots, a_{b_i-1}, a_{b_i+1}, \ldots, a_N $，然后计算替换后表达式的值。最后，输出该值对 $ 10^9+7 $ 取模后的结果，结果应在 $ 0 $ 到 $ 10^9+6 $ 之间。 本题中，表达式 $ S $ 符合以下 BNF 表达式定义： ``` ::= | '+' | '-' ::= | '*' ::= 'a' | '(' ')' ```

输入包含以下内容： > $ S $ $ Q $ $ a_1 $ ... $ a_N $ $ b_1 $ $ x_1 $ : $ b_Q $ $ x_Q $

输出共 $ Q $ 行，每行对应一个查询的答案。对于第 $ i $ 个查询（$ 1 \le i \le Q $），输出结果。

- $ S $ 的长度不超过 $ 200,000 $。 - $ S $ 可被 BNF 表达式定义的规则解析。 - $ 0 \le a_i < 10^9+7 $。 - $ 1 \le Q \le 10^5 $。 - $ 1 \le b_i \le N $。 - $ 0 \le x_i < 10^9+7 $。 - $ x_i $ 为整数。 ### 示例解释 比如，在第一个查询中，将第一个 `a` 替换为 $ x_1 = 1 $，第二个 `a` 替换为 $ a_2 = 1 $，第三个 `a` 替换为 $ a_3 = 2 $，表达式 $(1 - (1)) * 2 = 0$ 计算结果是 $ 0 $。在第三个查询中，替换第一个 `a` 为 $ a_1 = 0 $，第二个 `a` 替换为 $ x_3 = 1 $，第三个 `a` 替换为 $ a_3 = 2 $，结果 $(0 - (1)) * 2 = -2$，取模之后得到 $ 10^9+5 $。 **本翻译由 AI 自动生成**