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 Inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
const int jt = 1000000007, maxn = 1 << 19;
void inline add(int &a, int b) {
  a += b - jt;
  a += (a >> 31) & jt;
}
void inline sub(int &a, int b) {
  a -= b;
  a += (a >> 31) & jt;
}
void inline mul(int &a, int b) { a = (long long)a * b % jt; }
int inline Add(int a, int b) { return a + b >= jt ? a + b - jt : a + b; }
int inline Sub(int a, int b) { return a - b < 0 ? a - b + jt : a - b; }
int inline Mul(int a, int b) { return (long long)a * b % jt; }
struct NumberGetter {
  int val[maxn], mii[maxn];
  void inline init(char s[], int n) {
    val[0] = 0;
    mii[0] = 1;
    for (int i = 1; i <= (n); ++i) {
      val[i] = Add(Mul(val[i - 1], 10), isdigit(s[i]) ? s[i] - '0' : 0);
      mii[i] = Mul(mii[i - 1], 10);
    }
  }
  int inline query(int l, int r) {
    return Sub(val[r], Mul(val[l - 1], mii[r - l + 1]));
  }
} Ng;
struct Segtree {
  vector<int> dt;
  int N;
  void init(vector<int> s) {
    N = 1;
    while (N <= ((int)(s).size())) N <<= 1;
    dt.resize(N << 1);
    for (int i = 0; i < (((int)(s).size())); ++i) dt[i + N] = s[i];
    for (int i = (N - 1); (-1) > 0 ? i <= (0) : i >= (0); i += (-1))
      dt[i] = Mul(dt[i << 1], dt[i << 1 | 1]);
  }
  int query(int l, int r) {
    int res = 1;
    for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) mul(res, dt[l++]);
      if (r & 1) mul(res, dt[--r]);
    }
    return res;
  }
};
struct Multiply {
  int l, r;
  vector<int> brs, bgs;
  vector<int> pre, suf;
  Segtree seg;
  int getpre(int);
  int getsuf(int);
  int getval(int, int);
} Ms[maxn];
struct Bracket {
  int l, r;
  bool single;
  vector<int> mls, bgs;
  vector<int> pre;
  int getpre(int);
  int getsuf(int);
  int getval(int, int);
  Bracket(int l = 0, int r = 0, int single = 0) : l(l), r(r), single(single) {}
} Bs[maxn];
int inline Bracket::getpre(int len) {
  if (len < 0) return 1;
  if (single) return Ng.query(l, l + len - 1);
  if (len == r - l + 1) return pre.back();
  return 1;
}
int inline Bracket::getsuf(int len) {
  if (len < 0) return 1;
  if (single) return Ng.query(r - len + 1, r);
  if (len == r - l + 1) return pre.back();
  return 1;
}
int inline Multiply::getpre(int len) {
  if (len < 0) return 0;
  int id =
      upper_bound((bgs).begin(), (bgs).end(), l + len - 1) - bgs.begin() - 1;
  if (Bs[brs[id]].r == l + len - 1) return pre[id + 1];
  return Mul(pre[id], Bs[brs[id]].getpre(l + len - 1 - Bs[brs[id]].l + 1));
}
int inline Multiply::getsuf(int len) {
  if (len < 0) return 0;
  int id =
      upper_bound((bgs).begin(), (bgs).end(), r - len + 1) - bgs.begin() - 1;
  if (Bs[brs[id]].l == r - len + 1) return suf[id];
  return Mul(suf[id + 1],
             Bs[brs[id]].getsuf(Bs[brs[id]].r - (r - len + 1) + 1));
}
int inline Bracket::getval(int l, int r) {
  if (single) return Ng.query(l, r);
  if (l < bgs[0]) ++l;
  if (r == this->r) --r;
  int id1 = lower_bound((bgs).begin(), (bgs).end(), l) - bgs.begin();
  int id2 = upper_bound((bgs).begin(), (bgs).end(), r) - bgs.begin() - 1;
  if (id1 > id2) return Ms[mls[id2]].getval(l, r);
  return Add(Ms[mls[id1]].l == l
                 ? 0
                 : Ms[mls[id1 - 1]].getsuf(Ms[mls[id1 - 1]].r - l + 1),
             Add(Sub(pre[id2], pre[id1]),
                 id2 < ((int)(mls).size())
                     ? Ms[mls[id2]].getpre(r - Ms[mls[id2]].l + 1)
                     : 0));
}
int inline Multiply::getval(int l, int r) {
  int id1 = lower_bound((bgs).begin(), (bgs).end(), l) - bgs.begin();
  int id2 = upper_bound((bgs).begin(), (bgs).end(), r) - bgs.begin() - 1;
  if (id1 > id2) return Bs[brs[id2]].getval(l, r);
  return Mul(Bs[brs[id1]].l == l
                 ? 1
                 : Bs[brs[id1 - 1]].getsuf(Bs[brs[id1 - 1]].r - l + 1),
             Mul(seg.query(id1, id2 - 1),
                 id2 < ((int)(brs).size())
                     ? Bs[brs[id2]].getpre(r - Bs[brs[id2]].l + 1)
                     : 1));
}
struct Segtree3 {
  pair<int, int> dt[maxn << 1];
  void init() {
    for (int i = 0; i < (maxn << 1); ++i) dt[i].first = Inf;
  }
  void set(int a, pair<int, int> x) {
    a += maxn;
    dt[a] = x;
    while (a >>= 1) dt[a] = min(dt[a << 1], dt[a << 1 | 1]);
  }
  pair<int, int> query(int l, int r) {
    pair<int, int> res(Inf, 0);
    for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res = min(res, dt[l++]);
      if (r & 1) res = min(res, dt[--r]);
    }
    return res;
  }
} sgg;
int N, Q;
char s[maxn];
int mcs, bcs;
int parseBracket(int &, int);
int parseMulti(int &ptr, int dep, int uid) {
  int id = ++mcs;
  Ms[id].l = ptr;
  Ms[id].pre.push_back(1);
  vector<int> val;
  while (1) {
    Ms[id].bgs.push_back(ptr);
    sgg.set(ptr, make_pair(dep, uid));
    int nid = parseBracket(ptr, dep + 1);
    Ms[id].brs.push_back(nid);
    Ms[id].pre.push_back(Mul(Ms[id].pre.back(), Bs[nid].pre.back()));
    val.push_back(Bs[nid].pre.back());
    if (s[ptr] != '*') break;
    sgg.set(ptr, make_pair(dep, uid));
    ++ptr;
  }
  Ms[id].suf.resize(((int)(Ms[id].pre).size()));
  Ms[id].suf.back() = 1;
  for (int i = (((int)(Ms[id].brs).size()) - 1); (-1) > 0 ? i <= (0) : i >= (0);
       i += (-1))
    Ms[id].suf[i] = Mul(Ms[id].suf[i + 1], Bs[Ms[id].brs[i]].pre.back());
  Ms[id].seg.init(val);
  Ms[id].r = ptr - 1;
  return id;
}
int parseBracket(int &ptr, int dep) {
  if (s[ptr] != '(') {
    Bs[++bcs].single = 1;
    Bs[bcs].l = ptr;
    while (isdigit(s[ptr])) sgg.set(ptr, make_pair(dep, bcs)), ++ptr;
    Bs[bcs].r = ptr - 1;
    Bs[bcs].pre.push_back(Ng.query(Bs[bcs].l, Bs[bcs].r));
    return bcs;
  }
  int id = ++bcs;
  Bs[id].l = ptr;
  ++ptr;
  Bs[id].pre.push_back(0);
  while (1) {
    Bs[id].bgs.push_back(ptr);
    int nid = parseMulti(ptr, dep, id);
    Bs[id].mls.push_back(nid);
    Bs[id].pre.push_back(Add(Bs[id].pre.back(), Ms[nid].pre.back()));
    if (s[ptr] == ')') break;
    sgg.set(ptr, make_pair(dep, id));
    ++ptr;
  }
  Bs[id].r = ptr++;
  return id;
}
struct Segtree2 {
  pair<int, int> dt[maxn << 1];
  pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
    return make_pair(a.first + b.first, min(a.second, a.first + b.second));
  }
  void set(int a, pair<int, int> x) {
    a += maxn;
    dt[a] = x;
    while (a >>= 1) dt[a] = merge(dt[a << 1], dt[a << 1 | 1]);
  }
  pair<int, int> query(int l, int r) {
    pair<int, int> lres(0, 0), rres(0, 0);
    for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) lres = merge(lres, dt[l++]);
      if (r & 1) rres = merge(dt[--r], rres);
    }
    return merge(lres, rres);
  }
} seg;
int rt;
int main() {
  scanf("%s", s + 1);
  N = strlen(s + 1) + 2;
  scanf("%d", &Q);
  s[0] = '(';
  s[N - 1] = ')';
  Ng.init(s, N - 2);
  int ptr = 0;
  sgg.init();
  rt = parseBracket(ptr, 0);
  for (int i = 1; i <= (N); ++i) {
    if (s[i] == '(') seg.set(i, make_pair(1, 0));
    if (s[i] == ')') seg.set(i, make_pair(-1, -1));
  }
  int tms = 0;
  while (Q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    if (s[l] == '+' || s[l] == '*') {
      puts("-1");
      continue;
    }
    if (s[r] == '+' || s[r] == '*') {
      puts("-1");
      continue;
    }
    auto bbr = seg.query(l, r);
    if (bbr.second < 0 || bbr.first > 0) {
      puts("-1");
      continue;
    }
    int khid = sgg.query(l, r).second;
    tms -= clock();
    printf("%d\n", Bs[khid].getval(l, r));
    tms += clock();
  }
  return 0;
}