CF730L Expression Queries

一个正确的算术表达式，允许包含括号、数字（可能带有前导零）、乘法和加法。例如表达式 “$(0+01)$”，“$0$” 和 “$1*(0)$” 是简化的算术表达式，但是表达式 “$2-1$”，“$+1$” 和 “$1+2)$” 不是。 给定一个字符串 $s_1s_2...s_{\left\vert{s}\right\vert}$，表示一个简化算术表达式；$s_i$ 表示字符串的第 $i$ 个字符，它可以是数字 $('0'-'9')$，加号 $('+')$，乘号 $('*')$，左括号 $(\ '(' \ )$ 或右括号 $( \ ')' \ )$。 一个字符串的部分 $s_{l}s_{l+1}...s_{r}$ 被称为子表达式，当且仅当它是一个 $SAE$ (简化算术表达式)。 你的任务是回答 $m$ 个查询，每个查询都是一对整数 $l_i$ 和 $r_i$ $(1\le l_i\le r_i\le \left\vert{s}\right\vert)$。对于每个查询，确定给定字符串的相应部分是否为子表达式，并在它是子表达式的情况下计算它的值模 $1000000007$ $(10^9+7)$。应使用标准运算符优先级计算值。

输入的第一行包含非空字符串 $s$ $(1\le \left\vert{s}\right\vert \le 4\cdot 10^5)$，表示一个正确的 $SAE$。字符串的每个字符可以是以下字符之一：$'*'$，$'+'$，$'('$，$')'$ 或数字 $('0'\sim '9')$。表达式可能包含极大的数字。 第二行包含一个整数 $m$ $(1\le m\le 4·10^{5})$，表示查询的数量。接下来的 $m$ 行中，每行包含两个以空格分隔的整数 $l_i$ 和 $r_i$ $(1\le l_{i}\le r_{i}\le\left\vert{s}\right\vert)$，表示第 $i$ 个查询的区间。

对于每个询问单独输出一行。如果第 $i$ 个询问对应一个有效的子表达式，则输出子表达式的值对 $1000000007$ $( 1 0 ^9 + 7 )$ 取模的结果。否则，对于查询输出 $-1$。