No tags yet

No tag edit access

L. Expression Queries

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputA 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.

Input

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.

Output

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.

Examples

Input

((1+2)*3+101*2)

6

8 14

1 6

2 10

11 14

5 5

4 5

Output

205

-1

10

2

2

-1

Input

(01)

1

1 4

Output

1

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/24/2017 07:57:00 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|