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>
const int xn = 400008;
const long long MOD = 1000000007;
int N, Q, D, pb[xn], pp[xn], pm[xn], sb[xn], sp[xn], sm[xn], Lb[xn], Lp[xn],
    Lm[xn];
char a[xn];
long long P10[xn], iP10[xn], Ab[xn], Ap[xn], Az[xn], Am[xn], ab[xn], ap[xn],
    az[xn], am[xn], hb[xn], hp[xn], hz[xn], hm[xn], tb[xn], tp[xn], tz[xn],
    tm[xn];
long long INV(long long x) {
  long long r = 1;
  for (long long b = MOD - 2; b; b >>= 1) {
    if (b & 1) r = r * x % MOD;
    x = x * x % MOD;
  }
  return r;
}
long long F(int l, int r) {
  if (a[l] == '+' || a[l] == '*' || a[l] == ')') return -1;
  if (a[r] == '+' || a[r] == '*' || a[r] == '(') return -1;
  if (sb[pb[l]] != sb[r]) return -1;
  int lep = pp[l], rip = sp[r];
  if (sp[lep] != rip)
    return (hb[r] + tb[l] - ab[pb[l]] + MOD) % MOD;
  else {
    int lem = pm[l], rim = sm[r];
    if (sm[lem] != rim)
      return hz[r] + tz[l] == az[pp[l]]
                 ? hp[r] * tp[l] % MOD * INV(ap[pp[l]]) % MOD
                 : 0;
    else
      return (hm[r] + (tm[l] - am[pm[l]] + MOD) * iP10[rim - r - 1]) % MOD;
  }
  return 0;
}
int main() {
  scanf("%s", a + 2);
  while (a[N + 2]) N++;
  N += 2;
  a[1] = '(', a[N] = ')';
  iP10[0] = P10[0] = 1;
  for (int i = 1; i <= N; i++) {
    P10[i] = P10[i - 1] * 10 % MOD;
    iP10[i] = iP10[i - 1] * 700000005 % MOD;
  }
  for (int i = 1; i <= N; i++) {
    if (a[i] == '(') {
      pb[i] = Lb[D];
      pp[i] = Lp[D];
      pm[i] = Lm[D];
      D++;
      Lb[D] = Lp[D] = Lm[D] = i;
      Az[D] = Ab[D] = Am[D] = 0;
      Ap[D] = 1;
    } else if (a[i] == '+') {
      pb[i] = Lb[D];
      pp[i] = Lp[D];
      pm[i] = Lm[D];
      ap[Lp[D]] = Ap[D] * (Am[D] ? Am[D] : 1) % MOD;
      az[Lp[D]] = Az[D] + !Am[D];
      am[Lm[D]] = Am[D];
      Lp[D] = Lm[D] = i;
      Ab[D] = (Ab[D] + (Az[D] ? 0 : Ap[D]) * Am[D]) % MOD;
      Ap[D] = 1;
      Az[D] = 0;
      Am[D] = 0;
    } else if (a[i] == '*') {
      pb[i] = Lb[D];
      pp[i] = Lp[D];
      pm[i] = Lm[D];
      am[Lm[D]] = Am[D];
      Lm[D] = i;
      Ap[D] = Ap[D] * (Am[D] ? Am[D] : 1) % MOD;
      Az[D] = Az[D] + !Am[D];
      Am[D] = 0;
    } else if (a[i] >= '0' && a[i] <= '9') {
      pb[i] = Lb[D];
      pp[i] = Lp[D];
      pm[i] = Lm[D];
      Am[D] = (Am[D] * 10 + a[i] - 48) % MOD;
      hb[i] = (Ab[D] + (Az[D] ? 0 : Ap[D]) * Am[D]) % MOD;
      hp[i] = Ap[D] * (Am[D] ? Am[D] : 1) % MOD;
      hz[i] = Az[D] + !Am[D];
      hm[i] = Am[D];
    } else {
      ab[Lb[D]] = (Ab[D] + (Az[D] ? 0 : Ap[D]) * Am[D]) % MOD;
      ap[Lp[D]] = Ap[D] * (Am[D] ? Am[D] : 1) % MOD;
      az[Lp[D]] = Az[D] + !Am[D];
      am[Lm[D]] = Am[D];
      pb[i] = Lb[D];
      pp[i] = Lp[D];
      pm[i] = Lm[D];
      Am[D - 1] = (Ab[D] + (Az[D] ? 0 : Ap[D]) * Am[D]) % MOD;
      D--;
      hb[i] = (Ab[D] + (Az[D] ? 0 : Ap[D]) * Am[D]) % MOD;
      hp[i] = Ap[D] * (Am[D] ? Am[D] : 1) % MOD;
      hz[i] = Az[D] + !Am[D];
      hm[i] = Am[D];
    }
  }
  for (int i = N, l = -1; i; i--) {
    if (a[i] >= '0' && a[i] <= '9')
      l++;
    else
      l = -1;
    if (a[i] == ')') {
      sb[i] = Lb[D];
      sp[i] = Lp[D];
      sm[i] = Lm[D];
      D++;
      Lb[D] = Lp[D] = Lm[D] = i;
      Az[D] = Ab[D] = Am[D] = 0;
      Ap[D] = 1;
    } else if (a[i] == '+') {
      sb[i] = Lb[D];
      sp[i] = Lp[D];
      sm[i] = Lm[D];
      Lp[D] = Lm[D] = i;
      Ab[D] = (Ab[D] + (Az[D] ? 0 : Ap[D]) * Am[D]) % MOD;
      Ap[D] = 1;
      Az[D] = 0;
      Am[D] = 0;
    } else if (a[i] == '*') {
      sb[i] = Lb[D];
      sp[i] = Lp[D];
      sm[i] = Lm[D];
      Lm[D] = i;
      Ap[D] = Ap[D] * (Am[D] ? Am[D] : 1) % MOD;
      Az[D] = Az[D] + !Am[D];
      Am[D] = 0;
    } else if (a[i] >= '0' && a[i] <= '9') {
      sb[i] = Lb[D];
      sp[i] = Lp[D];
      sm[i] = Lm[D];
      Am[D] = (Am[D] + P10[l] * (a[i] - 48)) % MOD;
      tb[i] = (Ab[D] + (Az[D] ? 0 : Ap[D]) * Am[D]) % MOD;
      tp[i] = Ap[D] * (Am[D] ? Am[D] : 1) % MOD;
      tz[i] = Az[D] + !Am[D];
      tm[i] = Am[D];
    } else {
      sb[i] = Lb[D];
      sp[i] = Lp[D];
      sm[i] = Lm[D];
      Am[D - 1] = (Ab[D] + (Az[D] ? 0 : Ap[D]) * Am[D]) % MOD;
      D--;
      tb[i] = (Ab[D] + (Az[D] ? 0 : Ap[D]) * Am[D]) % MOD;
      tp[i] = Ap[D] * (Am[D] ? Am[D] : 1) % MOD;
      tz[i] = Az[D] + !Am[D];
      tm[i] = Am[D];
    }
  }
  for (scanf("%d", &Q); Q--;) {
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%I64d\n", F(l + 1, r + 1));
  }
  return 0;
}