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>
inline int read() {
  int x = 0, w = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') ch = getchar(), w = -1;
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + ch - 48, ch = getchar();
  return x * w;
}
const int N = 5e5 + 5;
const int MOD = 1e9 + 7;
char s[N];
inline void add(int &a, int b) { a = a + b >= MOD ? a + b - MOD : a + b; }
inline int madd(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
inline int get_id(char ch) {
  if (ch >= '0' && ch <= '9') return 0;
  if (ch == '+' || ch == '*') return 1;
  return 2;
}
int pow_10[N];
inline int fpow(int x, int p) {
  int res = 1;
  while (p) {
    if (p & 1) res = 1ll * x * res % MOD;
    x = 1ll * x * x % MOD;
    p >>= 1;
  }
  return res;
}
int n, Q;
int left[N], right[N], num[N];
int dep[N], val[N];
int nval[N], nid[N], cnt1;
int osum[N], oid[N], opl[N], opr[N], cnt2;
int zero[N], prod[N], inv_prod[N];
inline int get_num(int l, int r) {
  if (s[r] == ')') return val[r];
  return madd(num[r], MOD - 1ll * num[l - 1] * pow_10[r - l + 1] % MOD);
}
inline int get_opt(int l, int r) {
  if (nid[l] == nid[r]) return get_num(l, r);
  int res = 1ll * get_num(l, right[l]) * get_num(left[r], r) % MOD;
  l = right[l] + 2, r = left[r] - 2;
  if (l > r || !res) return res;
  l = nid[l], r = nid[r];
  if (zero[r] - zero[l - 1] > 0) return 0;
  return 1ll * res * prod[r] % MOD * inv_prod[l - 1] % MOD;
}
inline int build(int l, int r, int cur_dep) {
  std::vector<int> id, seg_num, opts;
  for (int i = l; i <= r; i = right[i] + 2) {
    id.push_back(i);
    if (s[i] == '(') {
      dep[i] = dep[right[i]] = cur_dep;
      val[i] = val[right[i]] = build(i + 1, right[i] - 1, i);
    } else
      for (int j = i; j <= right[i]; j++) dep[j] = cur_dep;
    seg_num.push_back(get_num(i, right[i]));
  }
  opts.push_back(0);
  for (int i = 1; i < (int)id.size(); i++)
    if (s[id[i] - 1] == '+') opts.push_back(i);
  opts.push_back((int)id.size());
  for (int i = 0; i < (int)id.size(); i++) {
    int nl = id[i];
    int nr = right[nl];
    nval[++cnt1] = seg_num[i];
    if (s[nl] == '(')
      nid[nl] = nid[nr] = cnt1;
    else
      for (int j = nl; j <= nr; j++) nid[j] = cnt1;
  }
  int res = 0;
  for (int i = 0; i < (int)opts.size() - 1; i++) {
    int nl = opts[i];
    int nr = opts[i + 1] - 1;
    int sum = 1;
    ++cnt2;
    opl[cnt2] = id[nl];
    opr[cnt2] = right[id[nr]];
    for (int j = nl; j <= nr; j++) {
      sum = 1ll * sum * seg_num[j] % MOD;
      int ml = id[j];
      int mr = right[ml];
      if (s[ml] == '(')
        oid[ml] = oid[mr] = cnt2;
      else
        for (int k = ml; k <= mr; k++) oid[k] = cnt2;
    }
    osum[cnt2] = sum;
    add(res, sum);
  }
  return res;
}
inline void init() {
  scanf("%s", s + 2);
  Q = read();
  n = strlen(s + 2) + 2;
  s[1] = '(';
  s[n] = ')';
  pow_10[0] = 1;
  for (int i = 1; i <= n; i++) pow_10[i] = 1ll * pow_10[i - 1] * 10 % MOD;
  std::stack<int> stk;
  for (int i = n; i >= 1; i--) {
    int id = get_id(s[i]);
    if (!id)
      right[i] = get_id(s[i + 1]) ? i : right[i + 1];
    else if (s[i] == ')')
      right[i] = i, stk.push(i);
    else if (s[i] == '(')
      right[i] = stk.top(), stk.pop();
  }
  for (int i = 1; i <= n; i++) {
    int id = get_id(s[i]);
    if (!id)
      left[i] = get_id(s[i - 1]) ? i : left[i - 1];
    else if (s[i] == '(')
      left[i] = i, stk.push(i);
    else if (s[i] == ')')
      left[i] = stk.top(), stk.pop();
  }
  for (int i = 1; i <= n; i++)
    if (!get_id(s[i])) num[i] = (1ll * num[i - 1] * 10 + s[i] - 48) % MOD;
  val[1] = val[n] = build(2, n - 1, 1);
  for (int i = 1; i <= cnt2; i++) add(osum[i], osum[i - 1]);
  prod[0] = 1;
  for (int i = 1; i <= cnt1; i++) {
    if (!nval[i])
      zero[i] = zero[i - 1] + 1;
    else
      zero[i] = zero[i - 1];
    prod[i] = 1ll * prod[i - 1] * (std::max(1, nval[i])) % MOD;
    inv_prod[i] = fpow(prod[i], MOD - 2);
  }
}
int main() {
  init();
  while (Q--) {
    int l = read() + 1, r = read() + 1;
    if (s[l] == '*' || s[r] == '+' || s[l] == '+' || s[r] == '*' ||
        s[l] == ')' || s[r] == '(' || dep[l] != dep[r]) {
      puts("-1");
      continue;
    }
    if (nid[l] == nid[r]) {
      printf("%d\n", get_num(l, r));
    } else if (oid[l] == oid[r]) {
      printf("%d\n", get_opt(l, r));
    } else {
      int res = madd(get_opt(l, opr[oid[l]]), get_opt(opl[oid[r]], r));
      l = oid[l] + 1, r = oid[r] - 1;
      if (l <= r) add(res, (osum[r] + MOD - osum[l - 1]) % MOD);
      printf("%d\n", (res % MOD + MOD) % MOD);
    }
  }
  return 0;
}