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;
const int inf = 1.01e9;
const double eps = 1e-9;
const int N = 4e5 + 10;
const int mod = 1e9 + 7;
int rev(int a, int m) {
  if (a == 1) return 1;
  return (1 - rev(m % a, a) * (long long)m) / a + m;
}
struct number {
  int val, len;
  int st, en;
  vector<int> pref, suf;
};
char s[N];
int pos = 0;
inline number parse_number() {
  int en = pos;
  while ('0' <= s[en] && s[en] <= '9') en++;
  assert(pos < en);
  number res;
  res.len = en - pos;
  res.pref = vector<int>(res.len + 1);
  res.suf = vector<int>(res.len + 1);
  for (int i = 0; (i) < (res.len); ++i)
    res.pref[i + 1] = (res.pref[i] * 10LL + s[pos + i] - '0') % mod;
  int pn = 1;
  for (int i = res.len - 1; i >= 0; --i) {
    res.suf[i] = (res.suf[i + 1] + pn * (long long)(s[pos + i] - '0')) % mod;
    pn = pn * 10LL % mod;
  }
  res.st = pos, res.en = en;
  res.val = res.pref[res.len];
  pos = en;
  return res;
}
struct brackets {
  int val;
  int st, en;
  brackets() {}
  brackets(int vval, int sst, int een) : val(vval), st(sst), en(een) {}
};
inline int getVal(pair<brackets, number> &a) {
  if (a.first.val != -1) return a.first.val;
  return a.second.val;
}
struct mul {
  vector<pair<brackets, number>> v;
  vector<int> pref, suf;
  vector<int> mid, cnt;
  int val;
  int st, en;
  void calc() {
    int len = ((int)(v).size());
    pref = vector<int>(len + 1);
    suf = vector<int>(len + 1);
    pref[0] = 1;
    for (int i = 0; i < len; ++i)
      pref[i + 1] = pref[i] * (long long)getVal(v[i]) % mod;
    suf[len] = 1;
    for (int i = len - 1; i >= 0; --i)
      suf[i] = suf[i + 1] * (long long)getVal(v[i]) % mod;
    val = pref[len];
    mid = vector<int>(len + 1);
    cnt = vector<int>(len + 1);
    mid[0] = 1;
    for (int i = 0; i < len; ++i) {
      int VAL = getVal(v[i]);
      mid[i + 1] = mid[i];
      cnt[i + 1] = cnt[i];
      if (VAL == 0)
        cnt[i + 1]++;
      else
        mid[i + 1] = mid[i + 1] * (long long)VAL % mod;
    }
  }
  int getMid(int l, int r) {
    if (l >= r) return 1;
    int dcnt = cnt[r] - cnt[l];
    if (dcnt) return 0;
    return mid[r] * (long long)rev(mid[l], mod) % mod;
  }
};
struct add {
  vector<mul> v;
  vector<int> pref, suf;
  int val;
  int st, en;
  void calc() {
    int len = ((int)(v).size());
    pref = vector<int>(len + 1);
    suf = vector<int>(len + 1);
    pref[0] = 0;
    for (int i = 0; i < len; ++i) pref[i + 1] = (pref[i] + v[i].val) % mod;
    suf[len] = 0;
    for (int i = len - 1; i >= 0; --i) suf[i] = (suf[i + 1] + v[i].val) % mod;
    val = pref[len];
  }
};
add parse_add();
brackets parse_brackets() {
  brackets b;
  b.st = pos;
  assert(s[pos] == '(');
  pos++;
  b.val = parse_add().val;
  assert(s[pos] == ')');
  pos++;
  b.en = pos;
  return b;
}
pair<brackets, number> parse_brackets_or_number() {
  pair<brackets, number> a;
  if (s[pos] == '(') {
    a.first = parse_brackets();
    return a;
  }
  a.first = brackets(-1, -1, -1);
  a.second = parse_number();
  return a;
}
mul parse_mul() {
  mul m;
  m.st = pos;
  while (1) {
    m.v.push_back(parse_brackets_or_number());
    if (s[pos] == ')' || s[pos] == 0 || s[pos] == '+') {
      break;
    }
    assert(s[pos] == '*');
    pos++;
  }
  m.en = pos;
  m.calc();
  return m;
}
int res[N];
vector<pair<int, int>> q[N];
int u[N];
int uc = 0;
pair<int, int> POS[N];
int p10[N];
int GIMME_PREF(pair<brackets, number> &a, int k) {
  if (a.first.val == -1) {
    return a.second.pref[k - a.second.st];
  } else {
    return a.first.val;
  }
}
int GIMME_SUF(pair<brackets, number> &a, int k) {
  if (a.first.val == -1) {
    return a.second.suf[k - a.second.st];
  } else {
    return a.first.val;
  }
}
int GET_ME_PREF(mul &M, int j, int k) {
  int X = GIMME_PREF(M.v[j], k);
  return X * (long long)M.pref[j] % mod;
}
int GET_ME_SUF(mul &M, int j, int k) {
  int X = GIMME_SUF(M.v[j], k);
  return X * (long long)M.suf[j + 1] % mod;
}
add parse_add() {
  add a;
  a.st = pos;
  while (1) {
    a.v.push_back(parse_mul());
    if (s[pos] == ')' || s[pos] == 0) break;
    assert(s[pos] == '+');
    pos++;
  }
  a.en = pos;
  a.calc();
  uc++;
  for (int i = 0; i < ((int)(a.v).size()); ++i) {
    for (int j = 0; j < ((int)(a.v[i].v).size()); ++j) {
      pair<brackets, number> z = a.v[i].v[j];
      if (z.first.val == -1) {
        for (int k = z.second.st + 1; k <= z.second.en; ++k) {
          u[k] = uc;
          POS[k] = {i, j};
        }
      } else {
        int k = z.first.en;
        u[k] = uc;
        POS[k] = {i, j};
      }
    }
  }
  for (int i = 0; i < ((int)(a.v).size()); ++i) {
    for (int j = 0; j < ((int)(a.v[i].v).size()); ++j) {
      pair<brackets, number> z = a.v[i].v[j];
      if (z.first.val == -1) {
        for (int k = z.second.st; k < z.second.en; ++k) {
          for (pair<int, int> w : q[k]) {
            int y = w.first;
            if (u[y] != uc) {
              res[w.second] = -1;
              continue;
            }
            int i2 = POS[y].first;
            int j2 = POS[y].second;
            int k2 = y;
            if (i == i2) {
              if (j == j2) {
                number &E = a.v[i].v[j].second;
                res[w.second] =
                    (E.pref[y - E.st] -
                     E.pref[k - E.st] * (long long)p10[y - k] % mod + mod) %
                    mod;
              } else {
                int L = GIMME_SUF(a.v[i].v[j], k);
                int M = a.v[i].getMid(j + 1, j2);
                int R = GIMME_PREF(a.v[i].v[j2], y);
                res[w.second] = (L * (long long)M % mod * R) % mod;
              }
            } else {
              int L = GET_ME_SUF(a.v[i], j, k);
              int M = (a.pref[i2] - a.pref[i + 1] + mod) % mod;
              int R = GET_ME_PREF(a.v[i2], j2, k2);
              res[w.second] = (L + (long long)M + R) % mod;
            }
          }
        }
      } else {
        int k = z.first.st;
        for (pair<int, int> w : q[k]) {
          int y = w.first;
          if (u[y] != uc) {
            res[w.second] = -1;
            continue;
          }
          int i2 = POS[y].first;
          int j2 = POS[y].second;
          int k2 = y;
          if (i == i2) {
            if (j == j2) {
              brackets &B = a.v[i].v[j].first;
              res[w.second] = B.val;
            } else {
              int L = GIMME_SUF(a.v[i].v[j], k);
              int M = a.v[i].getMid(j + 1, j2);
              int R = GIMME_PREF(a.v[i].v[j2], y);
              res[w.second] = (L * (long long)M % mod * R) % mod;
            }
          } else {
            int L = GET_ME_SUF(a.v[i], j, k);
            int M = (a.pref[i2] - a.pref[i + 1] + mod) % mod;
            int R = GET_ME_PREF(a.v[i2], j2, k2);
            res[w.second] = (L + (long long)M + R) % mod;
          }
        }
      }
    }
  }
  return a;
}
int main() {
  p10[0] = 1;
  for (int i = 1; i < N; ++i) p10[i] = p10[i - 1] * 10LL % mod;
  scanf("%s", s);
  int n;
  scanf("%d", &n);
  for (int i = 0; (i) < (n); ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    --l;
    q[l].push_back({r, i});
  }
  for (int i = 0; (i) < (n); ++i) res[i] = -1;
  parse_add();
  for (int i = 0; (i) < (n); ++i) printf("%d\n", res[i]);
  return 0;
}