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 maxN = 5e5 + 10, mod = 1e9 + 7;
int n, q, cnt;
int nxt[maxN + 1], res[maxN + 1], ans[maxN + 1];
int pw[maxN + 1], id[maxN + 1], tp[maxN + 1];
int L[maxN + 1], R[maxN + 1], S[maxN + 1];
int stk[maxN + 1], top;
int sum[maxN + 1], mn[maxN + 1][21], lg[maxN + 1];
char s[maxN + 1];
vector<int> pm[maxN + 1], pa[maxN + 1];
vector<int> son[maxN + 1], pre[maxN + 1], p0[maxN + 1];
inline int read() {
  int num = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) num = (num << 3) + (num << 1) + (ch ^ 48), ch = getchar();
  return num * f;
}
inline void update(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
inline int mpow(int a, int x) {
  int ans = 1;
  while (x) {
    if (x & 1) ans = 1ll * ans * a % mod;
    a = 1ll * a * a % mod;
    x >>= 1;
  }
  return ans;
}
inline int get_mn(int l, int r) {
  int k = lg[r - l + 1];
  return min(mn[l][k], mn[r - (1 << k) + 1][k]);
}
inline bool check(int l, int r) {
  if (sum[r] != sum[l - 1]) return false;
  if (s[l] == '*' || s[l] == '+') return false;
  if (s[r] == '*' || s[r] == '+') return false;
  return get_mn(l, r) >= sum[r];
}
inline int get_Mul(int l, int r) {
  int id = sum[r];
  int x = lower_bound(pm[id].begin(), pm[id].end(), l) - pm[id].begin();
  if (x == pm[id].size() || pm[id][x] > r) return -1;
  return pm[id][x];
}
inline int get_Add(int l, int r) {
  int id = sum[r];
  int x = lower_bound(pa[id].begin(), pa[id].end(), l) - pa[id].begin();
  if (x == pa[id].size() || pa[id][x] > r) return -1;
  return pa[id][x];
}
inline int build(int l, int r) {
  int node = ++cnt;
  L[node] = l, R[node] = r;
  while (s[l] == '(' && nxt[l] == r) id[l++] = node, r--;
  int mid = get_Add(l, r);
  if (mid != -1) {
    tp[node] = 0;
    int x = l;
    while (mid != -1) {
      id[mid] = node;
      son[node].push_back(build(x, mid - 1));
      x = mid + 1;
      mid = get_Add(x, r);
    }
    son[node].push_back(build(x, r));
    int sum = 0;
    for (int i = 0; i < son[node].size(); i++) {
      update(sum, res[son[node][i]]);
      pre[node].push_back(sum);
    }
    return res[node] = sum, node;
  }
  mid = get_Mul(l, r);
  if (mid != -1) {
    tp[node] = 1;
    int x = l;
    while (mid != -1) {
      id[mid] = node;
      son[node].push_back(build(x, mid - 1));
      x = mid + 1;
      mid = get_Mul(x, r);
    }
    son[node].push_back(build(x, r));
    int sum = 1, tot = 0;
    for (int i = 0; i < son[node].size(); i++) {
      if (!res[son[node][i]])
        tot++;
      else
        sum = 1ll * sum * res[son[node][i]] % mod;
      pre[node].push_back(sum);
      p0[node].push_back(tot);
    }
    return res[node] = tot ? 0 : sum, node;
  }
  tp[node] = 2;
  for (int i = l; i <= r; i++)
    res[node] = (10ll * res[node] % mod + s[i] - '0') % mod;
  return node;
}
inline int get(int l, int r) {
  int ans = S[r];
  update(ans, mod - 1ll * S[l - 1] * pw[r - l + 1] % mod);
  return ans;
}
inline int findl(int node, int x) {
  int l = 0, r = son[node].size() - 1, ans = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (L[son[node][mid]] < x)
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return ans;
}
inline int findr(int node, int x) {
  int l = 0, r = son[node].size() - 1, ans = son[node].size();
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (R[son[node][mid]] > x)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return ans;
}
inline int query3(int node, int l, int r) {
  l = max(l, L[node]), r = min(r, R[node]);
  if (l > r) return 0;
  return get(l, r);
}
inline int query2(int node, int l, int r) {
  if (tp[node] == 2) return query3(node, l, r);
  l = max(l, L[node]), r = min(r, R[node]);
  if (l > r) return 0;
  int x = findl(node, l), y = findr(node, r);
  int ans = (y ? pre[node][y - 1] : 1), tot = (y ? p0[node][y - 1] : 0);
  if (x != -1)
    ans = 1ll * ans * mpow(pre[node][x], mod - 2) % mod, tot -= p0[node][x];
  if (x != -1 && R[son[node][x]] >= l)
    ans = 1ll * ans * query3(son[node][x], l, r) % mod;
  if (y != son[node].size() && L[son[node][y]] <= r)
    ans = 1ll * ans * query3(son[node][y], l, r) % mod;
  return tot ? 0 : ans;
}
inline int query1(int node, int l, int r) {
  int x = findl(node, l), y = findr(node, r);
  int ans = (y ? pre[node][y - 1] : 0);
  if (x != -1) update(ans, mod - pre[node][x]);
  if (x != -1 && R[son[node][x]] >= l) update(ans, query2(son[node][x], l, r));
  if (y != son[node].size() && L[son[node][y]] <= r)
    update(ans, query2(son[node][y], l, r));
  return ans;
}
inline int solve(int l, int r) {
  if (s[l] == '(' && nxt[l] == r) return res[id[l]];
  int mid = get_Add(l, r);
  if (mid != -1) return query1(id[mid], l, r);
  mid = get_Mul(l, r);
  if (mid != -1) return query2(id[mid], l, r);
  return get(l, r);
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1];
    if (s[i] == '(') sum[i]++, stk[++top] = i;
    if (s[i] == ')') sum[i]--, nxt[stk[top--]] = i;
  }
  for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; i++) mn[i][0] = sum[i];
  for (int j = 1; (1 << j) <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
  for (int i = 1; i <= n; i++) {
    if (s[i] == '+') pa[sum[i]].push_back(i);
    if (s[i] == '*') pm[sum[i]].push_back(i);
  }
  pw[0] = 1;
  for (int i = 1; i <= n; i++) pw[i] = 10ll * pw[i - 1] % mod;
  for (int i = 1; i <= n; i++) {
    S[i] = 10ll * S[i - 1] % mod;
    if (isdigit(s[i])) update(S[i], s[i] - '0');
  }
  build(1, n);
  q = read();
  while (q--) {
    int l = read(), r = read();
    if (!check(l, r)) {
      puts("-1");
      continue;
    }
    printf("%d\n", solve(l, r));
  }
  return 0;
}