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;
int add(int x, int y) { return (x += y) < 1000000007 ? x : x - 1000000007; }
int mul(int x, int y) { return (int)((long long int)x * y % 1000000007); }
int len;
char s[444444];
int p10[444444];
int chk_id[444444];
int nex_para[444444];
int pre_para[444444];
int nex_add[444444], nex_mul[444444];
int pre_add[444444], pre_mul[444444];
int st_pos[444444], st_chk_id[444444];
int top;
int CHK;
int id[444444];
int typ[444444], T;
vector<int> op[444444];
int szz[444444];
int pos[444444];
int val[444444];
vector<int> seg[444444];
int CUR;
void build(int i, int s, int e) {
  if (s == e) {
    seg[CUR][i] = op[CUR][s];
    return;
  }
  int m = (s + e) / 2;
  build(i * 2, s, m);
  build(i * 2 + 1, m + 1, e);
  if (typ[CUR] == 2)
    seg[CUR][i] = add(seg[CUR][i * 2], seg[CUR][i * 2 + 1]);
  else if (typ[CUR] == 3)
    seg[CUR][i] = mul(seg[CUR][i * 2], seg[CUR][i * 2 + 1]);
  else
    seg[CUR][i] = add(mul(seg[CUR][i * 2], p10[e - m]), seg[CUR][i * 2 + 1]);
}
int query(int i, int s, int e, int l, int r) {
  if (s == l && e == r) return seg[CUR][i];
  int m = (s + e) / 2;
  if (r <= m) return query(i * 2, s, m, l, r);
  if (l > m) return query(i * 2 + 1, m + 1, e, l, r);
  int res1 = query(i * 2, s, m, l, m);
  int res2 = query(i * 2 + 1, m + 1, e, m + 1, r);
  if (typ[CUR] == 2)
    return add(res1, res2);
  else if (typ[CUR] == 3)
    return mul(res1, res2);
  else
    return add(mul(res1, p10[r - m]), res2);
}
int analysis(int from, int to) {
  int cur = ++T;
  if (s[from] == '(' && nex_para[from] == to) {
    id[from] = id[to] = cur;
    typ[cur] = 1;
    return val[cur] = analysis(from + 1, to - 1);
  }
  if (nex_add[from] != -1 && nex_add[from] <= to) {
    typ[cur] = 2;
    while (1) {
      int nx = nex_add[from];
      if (nx == -1 || nx > to) break;
      op[cur].push_back(analysis(from, nx - 1));
      id[nx] = cur;
      pos[nx] = op[cur].size();
      from = nx + 1;
    }
    op[cur].push_back(analysis(from, to));
    int sz = szz[cur] = op[cur].size();
    seg[cur].resize(sz * 4);
    CUR = cur;
    build(1, 0, sz - 1);
    return seg[cur][1];
  }
  if (nex_mul[from] != -1 && nex_mul[from] <= to) {
    typ[cur] = 3;
    while (1) {
      int nx = nex_mul[from];
      if (nx == -1 || nx > to) break;
      op[cur].push_back(analysis(from, nx - 1));
      pos[nx] = op[cur].size();
      id[nx] = cur;
      from = nx + 1;
    }
    op[cur].push_back(analysis(from, to));
    int sz = szz[cur] = op[cur].size();
    seg[cur].resize(sz * 4);
    CUR = cur;
    build(1, 0, sz - 1);
    return seg[cur][1];
  }
  typ[cur] = 4;
  for (int i = from; i <= to; i++) {
    id[i] = cur;
    op[cur].push_back(s[i] - '0');
    pos[i] = op[cur].size();
  }
  int sz = szz[cur] = op[cur].size();
  seg[cur].resize(sz * 4);
  CUR = cur;
  build(1, 0, sz - 1);
  return seg[cur][1];
}
int process(int from, int to) {
  if (s[from] == '(' && nex_para[from] == to) {
    return val[id[from]];
  }
  if (nex_add[from] != -1 && nex_add[from] <= to) {
    int A = nex_add[from];
    int B = pre_add[to];
    int cur = id[A];
    int A_id = pos[A], B_id = pos[B];
    CUR = cur;
    int zz = A_id != B_id ? query(1, 0, szz[cur] - 1, A_id, B_id - 1) : 0;
    zz = add(zz, process(from, A - 1));
    zz = add(zz, process(B + 1, to));
    return zz;
  }
  if (nex_mul[from] != -1 && nex_mul[from] <= to) {
    int A = nex_mul[from];
    int B = pre_mul[to];
    int cur = id[A];
    int A_id = pos[A], B_id = pos[B];
    CUR = cur;
    int zz = A_id != B_id ? query(1, 0, szz[cur] - 1, A_id, B_id - 1) : 1;
    zz = mul(zz, process(from, A - 1));
    zz = mul(zz, process(B + 1, to));
    return zz;
  }
  int cur = id[from];
  CUR = cur;
  return query(1, 0, szz[cur] - 1, pos[from] - 1, pos[to] - 1);
}
int main() {
  scanf("%s", s + 1);
  len = strlen(s + 1);
  s[0] = '(';
  s[len + 1] = ')';
  len += 2;
  top = 0;
  for (int i = 0; i < len; i++)
    if (s[i] == '(') {
      st_pos[top] = i;
      st_chk_id[top] = ++CHK;
      top++;
    } else if (s[i] == ')') {
      int from = st_pos[top - 1] + 1, to = i - 1, chk = st_chk_id[top - 1];
      int add = -1, mul = -1;
      for (int j = from; j <= to; j++) {
        pre_add[j] = add;
        pre_mul[j] = mul;
        chk_id[j] = chk;
        if (s[j] == '(') {
          j = nex_para[j];
          pre_add[j] = add;
          pre_mul[j] = mul;
          chk_id[j] = chk;
        } else if (s[j] == '+')
          add = j;
        else if (s[j] == '*')
          mul = j;
      }
      add = mul = -1;
      for (int j = to; j >= from; j--) {
        nex_add[j] = add;
        nex_mul[j] = mul;
        if (s[j] == ')') {
          j = pre_para[j];
          nex_add[j] = add;
          nex_mul[j] = mul;
        } else if (s[j] == '+')
          add = j;
        else if (s[j] == '*')
          mul = j;
      }
      nex_para[st_pos[top - 1]] = i;
      pre_para[i] = st_pos[top - 1];
      --top;
    }
  p10[0] = 1;
  for (int i = 1; i <= len; i++) p10[i] = mul(p10[i - 1], 10);
  analysis(0, len - 1);
  int q, from, to;
  for (scanf("%d", &q); q--;) {
    scanf("%d%d", &from, &to);
    if (chk_id[from] == chk_id[to] && (isdigit(s[from]) || s[from] == '(') &&
        (isdigit(s[to]) || s[to] == ')')) {
      printf("%d\n", process(from, to));
    } else
      puts("-1");
  }
  return 0;
}