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₁s₂...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_ls_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⁹ + 7). The values should be calculated using standard operator priorities.