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>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
mt19937 ggen;
const int MOD = 1000000007;
int add(int a, int b) {
  int res = a + b;
  if (res >= MOD) res -= MOD;
  return res;
}
int mul(int a, int b) { return (long long)a * b % MOD; }
int blen[500010];
void precalc() {
  for (int i = 0; i < 500010; i++) {
    int ti = i;
    while (ti) {
      blen[i]++;
      ti >>= 1;
    }
  }
}
struct sparse {
  vector<pair<int, int> > a;
  vector<pair<int, int> > mn[20];
  void build() {
    int n = a.size();
    mn[0].resize(n);
    for (int i = 0; i < n; i++) {
      mn[0][i] = a[i];
    }
    for (int i = 1; i < 20; i++) {
      mn[i].resize(n);
      for (int j = 0; j < n; j++) {
        mn[i][j] = mn[i - 1][j];
        if (j + (1 << (i - 1)) < n)
          mn[i][j] = min(mn[i][j], mn[i - 1][j + (1 << (i - 1))]);
      }
    }
  }
  pair<int, int> get(int l, int r) {
    int dt = r - l + 1;
    return min(mn[blen[dt] - 1][l],
               mn[blen[dt] - 1][r + 1 - (1 << (blen[dt] - 1))]);
  }
};
int n;
string s;
int sb[500010];
sparse st[3];
struct node {
  node *l, *r;
  int type;
  int val;
  int ev;
  int id;
  node() : l(NULL), r(NULL), val(-1), ev(-1) {}
};
node tr[800000];
int ts;
node *root;
node *ptr[500010];
typedef node *nodeptr;
bool right(int l, int r) {
  int mb = st[2].get(l, r + 1).first;
  return (sb[l] == sb[r + 1] && sb[l] == mb);
}
void parse(nodeptr &v, int l, int r) {
  v = &tr[ts];
  tr[ts].id = ts;
  ts++;
  if (l == r) {
    v->val = s[l] - '0';
    ptr[l] = v;
    return;
  }
  if (s[l] == '(' && s[r] == ')' && right(l + 1, r - 1)) {
    v->type = -1;
    parse(v->l, l + 1, r - 1);
    ptr[l] = ptr[r] = v;
  } else {
    auto t = st[0].get(l, r);
    if (t.first == sb[l]) {
      v->type = 0;
      parse(v->l, l, t.second - 1);
      parse(v->r, t.second + 1, r);
    } else {
      t = st[1].get(l, r);
      if (t.first == sb[l]) {
        v->type = 1;
        parse(v->l, l, t.second - 1);
        parse(v->r, t.second + 1, r);
      } else {
        v->type = 2;
        parse(v->l, l, r - 1);
        parse(v->r, r, r);
      }
    }
  }
}
int tin[800000];
int tout[800000];
int timer;
int p[20][800000];
pair<int, int> L[20][800000];
pair<int, int> apply(pair<int, int> a, pair<int, int> b) {
  a.first = mul(a.first, b.first);
  a.second = add(mul(a.second, b.first), b.second);
  return a;
}
int eval(nodeptr v, nodeptr pt) {
  tin[v->id] = ++timer;
  p[0][v->id] = pt->id;
  if (v->val != -1) {
    v->ev = v->val;
  } else {
    if (v->type == -1)
      v->ev = eval(v->l, v);
    else {
      int a = eval(v->l, v);
      int b = eval(v->r, v);
      if (v->type == 0)
        v->ev = add(a, b);
      else if (v->type == 1)
        v->ev = mul(a, b);
      else
        v->ev = add(mul(a, 10), b);
    }
  }
  tout[v->id] = ++timer;
  return v->ev;
}
bool upper(int a, int b) { return tin[a] <= tin[b] && tin[b] <= tout[a]; }
int lca(int a, int b) {
  if (upper(a, b))
    return a;
  else if (upper(b, a))
    return b;
  for (int i = 19; i >= 0; i--) {
    if (!upper(p[i][a], b)) a = p[i][a];
  }
  return p[0][a];
}
int get(pair<int, int> arr[][800000], int val, int a, int b) {
  if (a == b) return val;
  for (int i = 19; i >= 0; i--) {
    if (!upper(p[i][a], b)) {
      val = add(mul(val, arr[i][a].first), arr[i][a].second);
      a = p[i][a];
    }
  }
  return val;
}
int ql[500010];
int qr[500010];
int ansa[500010];
int ansb[500010];
void solve_l(int m) {
  for (int i = 0; i < ts; i++) {
    nodeptr cur = &tr[i];
    nodeptr p = &tr[::p[0][i]];
    if (i == 0) {
      L[0][i].first = 1;
      L[0][i].second = 0;
    } else if (p->type == -1) {
      L[0][i].first = 1;
      L[0][i].second = 0;
    } else if (p->type == 0) {
      if (p->l == cur) {
        L[0][i].first = 1;
        L[0][i].second = p->r->ev;
      } else {
        L[0][i].first = 1;
        L[0][i].second = 0;
      }
    } else if (p->type == 1) {
      if (p->l == cur) {
        L[0][i].first = p->r->ev;
        L[0][i].second = 0;
      } else {
        L[0][i].first = 1;
        L[0][i].second = 0;
      }
    } else {
      if (p->l == cur) {
        L[0][i].first = 10;
        L[0][i].second = p->r->ev;
      } else {
        L[0][i].first = 1;
        L[0][i].second = 0;
      }
    }
  }
  for (int pw = 1; pw < 20; pw++) {
    for (int i = 0; i < ts; i++) {
      L[pw][i] = apply(L[pw - 1][i], L[pw - 1][p[pw - 1][i]]);
    }
  }
  for (int i = 0; i < m; i++) {
    int l = ql[i], r = qr[i];
    if (s[l] == '+' || s[l] == '*' || s[l] == ')' || s[r] == '+' ||
        s[r] == '*' || s[r] == '(' || !right(l, r)) {
      continue;
    }
    l = ptr[l]->id;
    r = ptr[r]->id;
    if (l == r) {
      continue;
    }
    int lc = lca(l, r);
    ansa[i] = get(L, tr[l].ev, l, lc);
  }
}
void solve_r(int m) {
  for (int i = 0; i < ts; i++) {
    nodeptr cur = &tr[i];
    nodeptr p = &tr[::p[0][i]];
    if (i == 0) {
      L[0][i].first = 1;
      L[0][i].second = 0;
    } else if (p->type == -1) {
      L[0][i].first = 1;
      L[0][i].second = 0;
    } else if (p->type == 0) {
      if (p->l == cur) {
        L[0][i].first = 1;
        L[0][i].second = 0;
      } else {
        L[0][i].first = 1;
        L[0][i].second = p->l->ev;
      }
    } else if (p->type == 1) {
      if (p->l == cur) {
        L[0][i].first = 1;
        L[0][i].second = 0;
      } else {
        L[0][i].first = p->l->ev;
        L[0][i].second = 0;
      }
    } else {
      if (p->l == cur) {
        L[0][i].first = 1;
        L[0][i].second = 0;
      } else {
        L[0][i].first = 1;
        L[0][i].second = mul(p->l->ev, 10);
      }
    }
  }
  for (int pw = 1; pw < 20; pw++) {
    for (int i = 0; i < ts; i++) {
      L[pw][i] = apply(L[pw - 1][i], L[pw - 1][p[pw - 1][i]]);
    }
  }
  for (int i = 0; i < m; i++) {
    int l = ql[i], r = qr[i];
    if (s[l] == '+' || s[l] == '*' || s[l] == ')' || s[r] == '+' ||
        s[r] == '*' || s[r] == '(' || !right(l, r)) {
      continue;
    }
    l = ptr[l]->id;
    r = ptr[r]->id;
    if (l == r) {
      continue;
    }
    int lc = lca(l, r);
    ansb[i] = get(L, tr[r].ev, r, lc);
  }
}
void solve() {
  cin >> s;
  n = s.size();
  int bal = 0;
  for (int i = 0; i < n; i++) {
    sb[i] = bal;
    if (s[i] == '(')
      bal++;
    else if (s[i] == ')')
      bal--;
  }
  for (int i = 0; i < n; i++) {
    st[2].a.push_back(pair<int, int>(sb[i], i));
    if (s[i] == '+')
      st[0].a.push_back(pair<int, int>(sb[i], i));
    else
      st[0].a.push_back(pair<int, int>(((int)(1e9) + 1337), i));
    if (s[i] == '*')
      st[1].a.push_back(pair<int, int>(sb[i], i));
    else
      st[1].a.push_back(pair<int, int>(((int)(1e9) + 1337), i));
  }
  st[0].build();
  st[1].build();
  st[2].build();
  parse(root, 0, n - 1);
  eval(root, root);
  for (int pw = 1; pw < 20; pw++) {
    for (int i = 0; i < ts; i++) {
      p[pw][i] = p[pw - 1][p[pw - 1][i]];
    }
  }
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    ql[i] = l;
    qr[i] = r;
  }
  solve_l(m);
  solve_r(m);
  for (int i = 0; i < m; i++) {
    int l = ql[i], r = qr[i];
    if (s[l] == '+' || s[l] == '*' || s[l] == ')' || s[r] == '+' ||
        s[r] == '*' || s[r] == '(' || !right(l, r)) {
      cout << "-1\n";
      continue;
    }
    l = ptr[l]->id;
    r = ptr[r]->id;
    if (l == r) {
      cout << tr[l].ev << '\n';
      continue;
    }
    int lc = lca(l, r);
    int a = ansa[i];
    int b = ansb[i];
    if (tr[lc].type == 0)
      cout << add(a, b);
    else if (tr[lc].type == 1)
      cout << mul(a, b);
    else if (tr[lc].type == 2)
      cout << add(mul(a, 10), b);
    cout << '\n';
  }
}
void testgen(int n) {
  ofstream ofs("input.txt", ios_base::out | ios_base::trunc);
  mt19937 gen(1337);
  uniform_int_distribution<int> distr(0, 9);
  for (int i = 0; i < n; i++) ofs << (char)('0' + distr(gen));
  ofs << "\n1\n1 " << n;
  ofs.close();
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ggen = mt19937(13);
  precalc();
  solve();
  return 0;
}