CF730L.Expression Queries

A simplified arithmetic expression (SAE) is an arithmetic expression defined by the following grammar:

• ::= | + | * | ()
• ::= |
• ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

In other words it's a correct arithmetic expression that is allowed to contain brackets, numbers (possibly with leading zeros), multiplications and additions. For example expressions "(0+01)", "0" and "1*(0)" are simplified arithmetic expressions, but expressions "2-1", "+1" and "1+2)" are not.

Given a string _s_1_s_2...s|s| that represents a SAE; s__i denotes the i-th character of the string which can be either a digit ('0'-'9'), a plus sign ('+'), a multiplication sign ('*'), an opening round bracket '(' or a closing round bracket ')'.

A part s__l__s__l + 1...s__r of this string is called a sub-expression if and only if it is a SAE.

You task is to answer m queries, each of which is a pair of integers l__i, r__i (1 ≤ l__i ≤ r__i ≤ |s|). For each query determine whether the corresponding part of the given string is a sub-expression and in case it's a sub-expression calculate its value modulo 1000000007 (109 + 7). The values should be calculated using standard operator priorities.

简化算术表达式（SAE）是一种由如下文法定义的算术表达式：

• <SAE> ::= <Number> | <SAE>+<SAE> | <SAE>*<SAE> | (<SAE>)
• <Number> ::= <Digit> | <Digit><Number>
• <Digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

换言之，它是一个合法的算术表达式，允许包含括号、数字（数字可能含有前导零）、乘法和加法运算。例如，表达式 "(0+01)"、"0" 和 "1*(0)" 均为简化算术表达式；但表达式 "2-1"、"+1" 和 "1+2)" 则不是。

给定一个字符串 $s_1s_2\ldots s_{|s|}$，它表示一个 SAE；其中 $s_i$ 表示该字符串的第 $i$ 个字符，可以是数字（'0'–'9'）、加号（'+'）、乘号（'*'）、左圆括号 '(' 或右圆括号 ')'。

该字符串的一个子串 $s_ls_{l+1}\ldots s_r$ 被称为子表达式，当且仅当它本身是一个 SAE。

你的任务是回答 $m$ 个查询，每个查询由一对整数 $l_i, r_i$ 组成（满足 $1 \le l_i \le r_i \le |s|$）。对每个查询，请判断该字符串对应区间是否构成一个子表达式；若是子表达式，则计算其值对 $1000000007$（即 $10^9 + 7$）取模的结果。计算时需遵循标准的运算符优先级规则。

The first line of the input contains non-empty string s (1 ≤ |s| ≤ 4·105) which represents a correct SAE. Each character of the string can be one of the following characters: '*', '+', '(', ')' or a digit ('0'-'9'). The expression might contain extra-huge numbers.

The second line contains an integer m (1 ≤ m ≤ 4·105) which is the number of queries. Each of the next m lines contains two space-separated integers l__i, r__i (1 ≤ l__i ≤ r__i ≤ |s|) — the i-th query.

输入的第一行包含一个非空字符串 $s$（$1 ≤ |s| ≤ 4·10^5$），表示一个合法的 SAE（简单算术表达式）。字符串中的每个字符可以是以下字符之一：\*、+、(、) 或一个数字（'0'–'9'）。该表达式可能包含极大数值。

第二行包含一个整数 $m$（$1 ≤ m ≤ 4·10^5$），表示查询次数。接下来的 $m$ 行中，每行包含两个以空格分隔的整数 $l_i$、$r_i$（$1 ≤ l_i ≤ r_i ≤ |s|$），表示第 $i$ 个查询。

The i-th number of output should be the answer for the i-th query. If the i-th query corresponds to a valid sub-expression output the value of the sub-expression modulo 1000000007 (109 + 7). Otherwise output -1 as an answer for the query. Print numbers on separate lines.

第 $i$ 个输出数字应为第 $i$ 个查询的答案。若第 $i$ 个查询对应一个有效的子表达式，则输出该子表达式的值对 $1000000007$（即 $10^9 + 7$）取模的结果；否则，输出 $-1$ 作为该查询的答案。每个数字单独占一行。