Problem: 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 s1s2...s|s| that represents a SAE; si 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 slsl + 1...sr 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 li, ri (1 ≤ li ≤ ri ≤ |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.

Input

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 li, ri (1 ≤ li ≤ ri ≤ |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 (109 + 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 400000;
const int MOD = 1000000007;
int mypow(int x, int n) {
  int ret = 1;
  while (true) {
    if (n & 1) ret = (long long)ret * x % MOD;
    if ((n >>= 1) == 0) break;
    x = (long long)x * x % MOD;
  }
  return ret;
}
int inv(int x) {
  assert(x != 0);
  return mypow(x, MOD - 2);
}
int n, nq;
char s[MAXN + 1];
int match[MAXN];
int stck[MAXN], nstck;
int numb[MAXN], nnumb, numbval[MAXN], numbstart[MAXN], numbend[MAXN];
int term[MAXN], nterm, termval[MAXN], termstart[MAXN], termend[MAXN];
int expr[MAXN], nexpr, exprval[MAXN];
int p10[MAXN + 1];
int digsum[MAXN + 1];
int zerosum[MAXN + 1], numbprod[MAXN + 1];
int termsum[MAXN + 1];
int parsenumb(int &at) {
  numbstart[nnumb] = at;
  if (s[at] == '(') {
    numbval[nnumb] = exprval[expr[at + 1]];
    numb[at] = nnumb, term[at] = nterm, expr[at] = nexpr;
    at = match[at];
    numb[at] = nnumb, term[at] = nterm, expr[at] = nexpr;
    ++at;
  } else if (isdigit(s[at])) {
    numbval[nnumb] = 0;
    while (isdigit(s[at])) {
      numb[at] = nnumb, term[at] = nterm, expr[at] = nexpr;
      numbval[nnumb] = ((long long)numbval[nnumb] * 10 + s[at] - '0') % MOD;
      ++at;
    }
  } else
    assert(false);
  numbend[nnumb] = at - 1;
  return numbval[nnumb++];
}
int parseterm(int &at) {
  termstart[nterm] = nnumb;
  termval[nterm] = parsenumb(at);
  while (s[at] == '*') {
    ++at;
    termval[nterm] = (long long)termval[nterm] * parsenumb(at) % MOD;
  }
  termend[nterm] = nnumb - 1;
  return termval[nterm++];
}
int parseexpr(int &at) {
  exprval[nexpr] = parseterm(at);
  while (s[at] == '+') {
    ++at;
    exprval[nexpr] = (exprval[nexpr] + parseterm(at)) % MOD;
  }
  return exprval[nexpr++];
}
int solvesamenumb(int l, int r) {
  if (s[l] == '(') return numbval[numb[l]];
  return (digsum[r + 1] + MOD - (long long)p10[r - l + 1] * digsum[l] % MOD) %
         MOD;
}
int solvesameterm(int l, int r) {
  int nzero = zerosum[r + 1] - zerosum[l];
  if (nzero != 0) return 0;
  return (long long)numbprod[r + 1] * inv(numbprod[l]) % MOD;
}
int solvesameexpr(int l, int r) {
  return (termsum[r + 1] + MOD - termsum[l]) % MOD;
}
int solve(int l, int r) {
  if (!isdigit(s[l]) && s[l] != '(') return -1;
  if (!isdigit(s[r]) && s[r] != ')') return -1;
  if (numb[l] == numb[r]) return solvesamenumb(l, r);
  if (term[l] == term[r]) {
    int a = solvesamenumb(l, numbend[numb[l]]);
    int b = solvesameterm(numb[l] + 1, numb[r] - 1);
    int c = solvesamenumb(numbstart[numb[r]], r);
    return (long long)a * b % MOD * c % MOD;
  }
  if (expr[l] == expr[r]) {
    int a = solvesamenumb(l, numbend[numb[l]]);
    int b = solvesameterm(numb[l] + 1, termend[term[l]]);
    int c = solvesameexpr(term[l] + 1, term[r] - 1);
    int d = solvesameterm(termstart[term[r]], numb[r] - 1);
    int e = solvesamenumb(numbstart[numb[r]], r);
    return ((long long)a * b + c + (long long)d * e) % MOD;
  }
  return -1;
}
void run() {
  scanf("%s", s);
  n = strlen(s);
  memset(match, -1, sizeof(match));
  nstck = 0;
  for (int i = (0); i < (n); ++i)
    if (s[i] == '(')
      stck[nstck++] = i;
    else if (s[i] == ')')
      assert(nstck > 0), match[i] = stck[nstck - 1], match[stck[nstck - 1]] = i,
                         --nstck;
  assert(nstck == 0);
  memset(numb, -1, sizeof(numb));
  memset(term, -1, sizeof(term));
  memset(expr, -1, sizeof(expr));
  nnumb = nterm = nexpr = 0;
  for (int i = n - 1; i >= 0; --i)
    if (s[i] == '(') {
      int at = i + 1;
      parseexpr(at);
      assert(at == match[i]);
    }
  {
    int at = 0;
    parseexpr(at);
    assert(at == n);
  }
  p10[0] = 1;
  for (int i = (0); i < (n); ++i) p10[i + 1] = (long long)10 * p10[i] % MOD;
  digsum[0] = 0;
  for (int i = (0); i < (n); ++i)
    digsum[i + 1] =
        ((long long)10 * digsum[i] + (isdigit(s[i]) ? s[i] - '0' : 0)) % MOD;
  zerosum[0] = 0;
  for (int i = (0); i < (nnumb); ++i)
    zerosum[i + 1] = zerosum[i] + (numbval[i] == 0 ? 1 : 0);
  numbprod[0] = 1;
  for (int i = (0); i < (nnumb); ++i)
    numbprod[i + 1] =
        (long long)numbprod[i] * (numbval[i] == 0 ? 1 : numbval[i]) % MOD;
  termsum[0] = 0;
  for (int i = (0); i < (nterm); ++i)
    termsum[i + 1] = (termsum[i] + termval[i]) % MOD;
  scanf("%d", &nq);
  for (int qi = (0); qi < (nq); ++qi) {
    int l, r;
    scanf("%d%d", &l, &r);
    --l, --r;
    printf("%d\n", solve(l, r));
  }
}
int main() {
  run();
  return 0;
}