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 = 400500;
const int LOG_N = 19;
const int MOD = (int)1e9 + 7;
int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
int sub(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  return a;
}
int mul(int a, int b) { return (long long)a * b % MOD; }
int n;
char s[N];
struct BracketManager {
  int pref[N];
  int st[LOG_N][N];
  int pw2[N];
  int open_pair[N], close_pair[N];
  BracketManager() : pref(), st(), pw2(), open_pair(), close_pair() {}
  void init(char s[], int n) {
    vector<int> stack;
    int bal = 0;
    for (int i = 0; i < n; i++) {
      if (s[i] == '(') {
        bal++;
        stack.push_back(i);
      } else if (s[i] == ')') {
        bal--;
        open_pair[stack.back()] = i;
        close_pair[i] = stack.back();
        stack.pop_back();
      }
      pref[i] = bal;
      st[0][i] = bal;
    }
    pw2[1] = 0;
    for (int i = 2; i <= n; i++) {
      pw2[i] = pw2[i - 1];
      if ((1 << (pw2[i] + 1)) <= i) pw2[i]++;
    }
    for (int s = 1; s < LOG_N; s++)
      for (int i = 0; i + (1 << s) <= n; i++)
        st[s][i] = min(st[s - 1][i], st[s - 1][i + (1 << (s - 1))]);
  }
  bool is_good(int l, int r) {
    int k = pw2[r - l + 1];
    int min_bal = min(st[k][l], st[k][r - (1 << k) + 1]);
    int last = 0;
    if (l > 0) last = pref[l - 1];
    if (min_bal < last) return false;
    int s = pref[r];
    if (l > 0) s -= pref[l - 1];
    return s == 0;
  }
};
struct NumSegTree {
  int sz;
  vector<int> pw10;
  vector<int> t;
  int combine(int a, int b, int suf) { return add(mul(a, pw10[suf]), b); }
  void build(int l, int r) {
    int len = r - l + 1;
    sz = 1;
    while (sz < len) sz *= 2;
    t.resize(2 * sz);
    pw10.resize(2 * sz);
    pw10[0] = 1;
    for (int i = 1; i < 2 * sz; i++) pw10[i] = mul(pw10[i - 1], 10);
    for (int i = 0; i < len; i++) t[sz + i] = s[i + l] - '0';
    int suf = 1;
    for (int i = sz - 1; i > 0; i--) {
      int j = i + 1;
      if (i != sz - 1 && !(j & (j - 1))) suf *= 2;
      t[i] = combine(t[2 * i], t[2 * i + 1], suf);
    }
  }
  int get(int v, int l, int r, int a, int b) {
    if (a > r || b < l) return 0;
    if (a <= l && r <= b) return t[v];
    int m = (l + r) / 2;
    int suf = max(0, min(r, b) - max(m + 1, a) + 1);
    return combine(get(2 * v, l, m, a, b), get(2 * v + 1, m + 1, r, a, b), suf);
  }
  int get(int a, int b) { return get(1, 0, sz - 1, a, b); }
};
struct NumBlock {
  int l, r, val;
  NumSegTree tree;
  NumBlock() : l(), r(), val() {}
  int eval(int ql, int qr) {
    ql = max(ql, l);
    qr = min(qr, r);
    if (l == ql && r == qr) return val;
    return tree.get(ql - l, qr - l);
  }
};
struct MultSegTree {
  int sz;
  vector<int> t;
  void build(const vector<NumBlock> &seq) {
    sz = 1;
    while (sz < (int)seq.size()) sz *= 2;
    t.resize(2 * sz);
    for (int i = 0; i < (int)seq.size(); i++) t[sz + i] = seq[i].val;
    for (int i = sz - 1; i > 0; i--) t[i] = mul(t[2 * i], t[2 * i + 1]);
  }
  int get(int v, int l, int r, int a, int b) {
    if (a > r || b < l) return 1;
    if (a <= l && r <= b) return t[v];
    int m = (l + r) / 2;
    return mul(get(2 * v, l, m, a, b), get(2 * v + 1, m + 1, r, a, b));
  }
  int get(int a, int b) { return get(1, 0, sz - 1, a, b); }
};
struct MultBlock {
  int l, r, val;
  MultSegTree tree;
  vector<NumBlock> nums;
  MultBlock() : l(), r(), val() {}
  int eval(int ql, int qr) {
    ql = max(ql, l);
    qr = min(qr, r);
    NumBlock me;
    me.l = ql;
    int left = upper_bound(nums.begin(), nums.end(), me,
                           [&](const NumBlock &a, const NumBlock &b) {
                             return a.l < b.l;
                           }) -
               nums.begin() - 1;
    me.l = qr;
    int right = upper_bound(nums.begin(), nums.end(), me,
                            [&](const NumBlock &a, const NumBlock &b) {
                              return a.l < b.l;
                            }) -
                nums.begin() - 1;
    if (left == right) return nums[left].eval(ql, qr);
    int res = nums[left].eval(ql, qr);
    res = mul(res, nums[right].eval(ql, qr));
    left++;
    right--;
    res = mul(res, tree.get(left, right));
    return res;
  }
};
struct SumBlock {
  int l, r;
  vector<int> pref_sum;
  vector<MultBlock> mults;
  SumBlock() : l(), r() {}
  int eval(int ql, int qr) {
    MultBlock me;
    me.l = ql;
    int left = upper_bound(mults.begin(), mults.end(), me,
                           [&](const MultBlock &a, const MultBlock &b) {
                             return a.l < b.l;
                           }) -
               mults.begin() - 1;
    me.l = qr;
    int right = upper_bound(mults.begin(), mults.end(), me,
                            [&](const MultBlock &a, const MultBlock &b) {
                              return a.l < b.l;
                            }) -
                mults.begin() - 1;
    if (left == right) return mults[left].eval(ql, qr);
    int res = mults[left].eval(ql, qr);
    res = add(res, mults[right].eval(ql, qr));
    left++;
    right--;
    res = add(res, pref_sum[right]);
    res = sub(res, pref_sum[left - 1]);
    return res;
  }
};
BracketManager brackets;
vector<SumBlock> blocks[N];
int max_depth;
int parse_sum(int, int, int);
NumBlock parse_num(int l, int r, int d) {
  NumBlock block;
  block.l = l;
  block.r = r;
  if (s[l] == '(') {
    int res = parse_sum(l + 1, r - 1, d + 1);
    block.val = res;
  } else {
    block.tree.build(l, r);
    block.val = block.tree.get(0, r - l);
  }
  return block;
}
MultBlock parse_mult(int l, int r, int d) {
  MultBlock block;
  block.l = l;
  block.r = r;
  int p = l - 1;
  for (int i = l; i <= r + 1; i++) {
    if (i <= r && s[i] == '(') {
      i = brackets.open_pair[i];
      continue;
    }
    if (i <= r && s[i] != '*') continue;
    NumBlock inner = parse_num(p + 1, i - 1, d);
    block.nums.push_back(inner);
    p = i;
  }
  block.tree.build(block.nums);
  block.val = block.tree.get(0, (int)block.nums.size() - 1);
  return block;
}
int parse_sum(int l, int r, int d) {
  max_depth = max(max_depth, d);
  SumBlock block;
  block.l = l;
  block.r = r;
  int p = l - 1;
  for (int i = l; i <= r + 1; i++) {
    if (i <= r && s[i] == '(') {
      i = brackets.open_pair[i];
      continue;
    }
    if (i <= r && s[i] != '+') continue;
    MultBlock inner = parse_mult(p + 1, i - 1, d);
    block.pref_sum.push_back(inner.val);
    block.mults.push_back(inner);
    p = i;
  }
  for (int i = 1; i < (int)block.pref_sum.size(); i++)
    block.pref_sum[i] = add(block.pref_sum[i], block.pref_sum[i - 1]);
  blocks[d].push_back(block);
  return block.pref_sum.back();
}
int find_in_depth(int l, int r, int d) {
  SumBlock me;
  me.l = l;
  int pos = upper_bound(blocks[d].begin(), blocks[d].end(), me,
                        [&](const SumBlock &a, const SumBlock &b) {
                          return a.l < b.l;
                        }) -
            blocks[d].begin() - 1;
  if (pos >= 0 && r <= blocks[d][pos].r) return pos;
  return -1;
}
SumBlock &find_deepest_block(int l, int r) {
  int left = 0, right = max_depth + 1;
  while (right - left > 1) {
    int mid = (left + right) / 2;
    if (find_in_depth(l, r, mid) != -1)
      left = mid;
    else
      right = mid;
  }
  return blocks[left][find_in_depth(l, r, left)];
}
void solve() {
  scanf("%s", s);
  n = strlen(s);
  brackets.init(s, n);
  parse_sum(0, n - 1, 0);
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    l--;
    r--;
    if (!brackets.is_good(l, r) || s[l] == '+' || s[l] == '*' || s[r] == '+' ||
        s[r] == '*') {
      puts("-1");
      continue;
    }
    SumBlock &block = find_deepest_block(l, r);
    printf("%d\n", block.eval(l, r));
  }
}
int main() {
  solve();
  (void)0;
  return 0;
}