Expression Queries

题目描述

A simplified arithmetic expression (SAE) is an arithmetic expression defined by the following grammar: - <SAE> ::= <Number> | <SAE>+<SAE> | <SAE>\*<SAE> | (<SAE>) - <Number> ::= <Digit> | <Digit><Number> - <Digit> ::= 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 (10^{9}+7) $ . The values should be calculated using standard operator priorities.

输入输出格式

输入格式

The first line of the input contains non-empty string $ s $ $ (1<=|s|<=4·10^{5}) $ 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·10^{5}) $ 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.

输出格式

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 (10^{9}+7) $ . Otherwise output -1 as an answer for the query. Print numbers on separate lines.

输入输出样例

输入样例 #1

((1+2)*3+101*2)
6
8 14
1 6
2 10
11 14
5 5
4 5

输出样例 #1

205
-1
10
2
2
-1

输入样例 #2

(01)
1
1 4

输出样例 #2

1