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 N = 500010;
const int mod = 1e9 + 7;
int Pow(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, x = (long long)x * x % mod)
    if (y & 1) res = (long long)res * x % mod;
  return res;
}
int match[N];
char s[N];
int ncnt, L[N], R[N], val[N];
vector<vector<int>> p[N];
vector<int> sum[N];
struct Int {
  int x, y;
  Int(int v = 0) {
    if (v)
      x = v, y = 0;
    else
      x = 1, y = 1;
  }
  Int(int x, int y) : x(x), y(y) {}
  Int operator*(Int b) { return Int((long long)x * b.x % mod, y + b.y); }
  Int operator/(Int b) {
    return Int((long long)x * Pow(b.x, mod - 2) % mod, y - b.y);
  }
  int get() { return y ? 0 : x; }
};
vector<vector<Int>> pre[N];
int ed[N], st[N], fuck[N], num[N], pw[N];
int calc(int l, int r) {
  int res = (num[r] - (long long)num[l - 1] * pw[r - l + 1]) % mod;
  return (res + mod) % mod;
}
int build(int l, int r) {
  if (match[l] == r) return build(l + 1, r - 1);
  int rt = ++ncnt;
  L[rt] = l, R[rt] = r;
  if (s[l] != '(' && ed[l] == r) {
    val[rt] = calc(l, r), fuck[rt] = 1;
    return rt;
  }
  p[rt].resize(1), pre[rt].resize(1);
  Int cur(1);
  for (int i = l, j; i <= r; i++) {
    if (s[i] == '(' || isdigit(s[i])) {
      j = s[i] == '(' ? match[i] : ed[i];
      int t = build(i, j);
      p[rt].back().push_back(t), i = j, cur = cur * Int(val[t]);
      pre[rt].back().push_back(cur);
    } else if (s[i] == '+') {
      p[rt].push_back({}), val[rt] = (val[rt] + cur.get()) % mod;
      sum[rt].push_back(cur.get()), cur = Int(1);
      pre[rt].push_back({});
    }
  }
  val[rt] = (val[rt] + cur.get()) % mod;
  sum[rt].push_back(cur.get());
  for (int i = 1; i < sum[rt].size(); i++)
    sum[rt][i] = (sum[rt][i] + sum[rt][i - 1]) % mod;
  return rt;
}
long long hsh[N];
bool check(int l, int r) {
  if (hsh[l - 1] != hsh[r]) return false;
  if (s[l] == '+' || s[l] == '*' || s[r] == '+' || s[r] == '*') return false;
  return true;
}
int work1(int rt, int pos, int l, int r) {
  int base = 1;
  if (l >= 1 && isdigit(s[l]))
    base = (long long)base * calc(l, ed[l]) % mod, l = ed[l] + 2;
  if (r <= N && isdigit(s[r]))
    base = (long long)base * calc(st[r], r) % mod, r = st[r] - 2;
  if (l > r || l > R[p[rt][pos].back()] || r < L[p[rt][pos][0]]) return base;
  int l1 = 0, r1 = (int)p[rt][pos].size() - 1;
  int tl = 0, tr = r1;
  while (tl <= tr) {
    int mid = (tl + tr) >> 1;
    if (R[p[rt][pos][mid]] < l)
      l1 = mid + 1, tl = mid + 1;
    else
      tr = mid - 1;
  }
  tl = 0, tr = r1;
  while (tl <= tr) {
    int mid = (tl + tr) >> 1;
    if (L[p[rt][pos][mid]] > r)
      r1 = mid - 1, tr = mid - 1;
    else
      tl = mid + 1;
  }
  assert(l1 <= r1);
  if (l1 == 0) return (long long)base * pre[rt][pos][r1].get() % mod;
  return (long long)base * (pre[rt][pos][r1] / pre[rt][pos][l1 - 1]).get() %
         mod;
}
int query(int rt, int l, int r) {
  if (ed[l] >= r) return calc(l, r);
  int l1 = 0, r1 = (int)p[rt].size() - 1;
  int tl = 0, tr = r1;
  while (tl <= tr) {
    int mid = (tl + tr) >> 1;
    if (R[p[rt][mid].back()] < l)
      l1 = mid + 1, tl = mid + 1;
    else
      tr = mid - 1;
  }
  tl = 0, tr = r1;
  while (tl <= tr) {
    int mid = (tl + tr) >> 1;
    if (L[p[rt][mid][0]] > r)
      r1 = mid - 1, tr = mid - 1;
    else
      tl = mid + 1;
  }
  if (l1 == r1) {
    return work1(rt, l1, l, r);
  } else {
    int res = sum[rt][r1 - 1] - sum[rt][l1];
    if (res < 0) res += mod;
    return (res + (long long)work1(rt, l1, l, 1e9) + work1(rt, r1, -1e9, r)) %
           mod;
  }
}
long long wkr[N];
mt19937 rnd((long long)new char + time(0));
int ct[N], ans[N], ban[N];
struct event {
  int l, r, id, tp;
};
int main() {
  int n, q;
  scanf("%s%d", s + 1, &q), n = strlen(s + 1);
  pw[0] = 1;
  for (int i = 1; i <= n; i++) pw[i] = (long long)pw[i - 1] * 10 % mod;
  for (int i = 1; i <= n; i++) {
    num[i] = ((long long)num[i - 1] * 10 + s[i] - '0') % mod;
    if (!isdigit(s[i])) num[i] = 0;
  }
  for (int i = 1; i <= n; i++) wkr[i] = rnd();
  static int stk[N], top = 0;
  for (int i = 1; i <= n; i++) {
    if (isdigit(s[i])) st[i] = st[i - 1] ? st[i - 1] : i;
  }
  for (int i = n; i >= 1; i--) {
    if (isdigit(s[i])) ed[i] = ed[i + 1] ? ed[i + 1] : i;
  }
  int cur = 0;
  for (int i = 1; i <= n; i++) {
    if (s[i] == '(') {
      stk[++top] = i, cur ^= wkr[i];
    } else if (s[i] == ')') {
      cur ^= wkr[stk[top]], match[stk[top]] = i, top--;
    }
    hsh[i] = cur;
    ct[i] = ct[i - 1] + (s[i] == '(');
  }
  vector<event> zjk;
  for (int i = 1; i <= q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    if (!check(l, r))
      ban[i] = 1;
    else {
      int tl = 0, tr = r - l, mid, hh = -1;
      while (tl <= tr) {
        mid = (tl + tr) >> 1;
        if (ct[l + mid] - ct[l - 1] != mid + 1 || match[l + mid] != r - mid) {
          tr = mid - 1;
        } else {
          hh = mid, tl = mid + 1;
        }
      }
      hh++, l += hh, r -= hh;
      zjk.push_back({l, r, i, 1});
    }
  }
  build(1, n);
  for (int i = 1; i <= ncnt; i++) {
    zjk.push_back({L[i], R[i], i, 0});
  }
  sort(zjk.begin(), zjk.end(), [&](event a, event b) {
    if (a.l != b.l) return a.l < b.l;
    return a.tp < b.tp;
  });
  set<pair<int, int>> s;
  for (auto t : zjk) {
    if (t.tp == 0) {
      s.insert(pair<int, int>(t.r, t.id));
    } else {
      auto pos = s.lower_bound(pair<int, int>(t.r, -1e9));
      assert(pos != s.end());
      ans[t.id] = query(pos->second, t.l, t.r);
    }
  }
  for (int i = 1; i <= q; i++)
    if (ban[i])
      puts("-1");
    else
      printf("%d\n", (ans[i] + mod) % mod);
}