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 MOD = int(1e9) + 7;
using lint = long long;
struct modint {
  int v;
  modint(int v_ = 0) : v(v_ % MOD) {}
  modint operator+(const modint &m) const { return modint(v + m.v); }
  modint operator-(const modint &m) const { return modint(v - m.v + MOD); }
  modint operator*(const modint &m) const {
    return modint((lint)v * m.v % MOD);
  }
  modint operator+=(const modint m) {
    v = (v + m.v) % MOD;
    return *this;
  }
  modint operator*=(const modint m) {
    v = (lint(v) * m.v) % MOD;
    return *this;
  }
  modint inv() const {
    modint ret = 1, base = v;
    int ex = MOD - 2;
    while (ex > 0) {
      if (ex & 1) ret *= base;
      base *= base;
      ex >>= 1;
    }
    return ret;
  }
};
const int N_ = int(4.1e5);
char S[N_];
int IDX;
void print_spaces(int n) {
  while (n--) putchar(' ');
}
struct Expression {
  int l, r;
  modint value;
  vector<Expression *> ch;
  vector<modint> pref;
  virtual modint calc(int s, int e) { return 0; };
  int left_bound(int x) {
    int low = 0, high = int(ch.size()) - 1;
    int pos = ch.size();
    x += 1;
    while (low <= high) {
      int mid = (low + high) >> 1;
      if (x <= ch[mid]->l) {
        pos = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return pos;
  }
  int right_bound(int x) {
    int low = 0, high = int(ch.size()) - 1;
    int pos = -1;
    while (low <= high) {
      int mid = (low + high) >> 1;
      if (ch[mid]->r >= x) {
        high = mid - 1;
        pos = mid;
      } else {
        low = mid + 1;
      }
    }
    return pos;
  }
  modint get(int s, int e) {
    if (0) printf("s=%d e=%d l=%d r=%d\n", s, e, l, r);
    return (max(l, s) == l && min(r, e) == r) ? value
                                              : calc(max(l, s), min(r, e));
  }
  virtual void print(int){};
};
vector<Expression *> stk;
Expression *wh[N_];
void adv() { wh[IDX++] = stk.empty() ? NULL : stk.back(); }
modint pw10[N_];
modint pwinv10[N_];
const modint INV10 = modint(10).inv();
struct Number : Expression {
  Number() {
    value = 0;
    pref.push_back(0);
    l = IDX;
    for (; isdigit(S[IDX]); adv()) {
      value = value * 10 + (S[IDX] - '0');
      pref.push_back(value);
      r = IDX;
    }
  }
  modint calc(int s, int e) {
    if (0) printf(" Number calc %d %d\n", s, e);
    e -= l - 1;
    s -= l - 1;
    return (pref[e] - pref[s - 1] * pw10[e - s + 1]);
  }
  void print(int indent) {}
};
struct Hang : Expression {
  Hang();
  void print(int indent) {}
  modint calc(int s, int e) {
    int i = left_bound(s);
    int j = right_bound(e);
    if (0) printf(" Hang calc %d %d [%d, %d]\n", s, e, i, j);
    for (Expression *xx : ch) {
      if (0) printf("  (%d, %d) ", xx->l, xx->r);
    }
    if (0) printf("\n");
    for (modint v : pref) {
      if (0) printf("  %d ", v.v);
    }
    if (0) printf("\n");
    modint ret = 1;
    if (i < j) {
      ret *= pref[j] * pref[i].inv();
    }
    i -= 1;
    if (i >= 0) {
      ret *= ch[i]->get(s, e);
    }
    if (i != j && j < ch.size()) {
      ret *= ch[j]->get(s, e);
    }
    if (0) printf(" HANG calc %d %d returned %d\n", s, e, ret.v);
    return ret;
  }
};
struct SAE : Expression {
  SAE() {
    value = 0;
    pref.push_back(0);
    l = IDX;
    assert(S[IDX] == '(');
    adv();
    stk.push_back(this);
    while (true) {
      ch.push_back(new Hang());
      value += ch.back()->value;
      pref.push_back(value);
      if (S[IDX] != '+') {
        break;
      }
      adv();
    }
    r = IDX;
    stk.pop_back();
    assert(S[IDX] == ')');
    adv();
  }
  modint calc(int s, int e) {
    int i = left_bound(s);
    int j = right_bound(e);
    if (0) printf(" SAE calc %d %d [%d, %d]\n", s, e, i, j);
    for (Expression *xx : ch) {
      if (0) printf("  (%d, %d) ", xx->l, xx->r);
    }
    if (0) printf("\n");
    for (modint v : pref) {
      if (0) printf("  %d ", v.v);
    }
    if (0) printf("\n");
    modint ret = 0;
    if (i < j) {
      ret += pref[j] - pref[i];
    }
    i -= 1;
    if (i >= 0) {
      ret += ch[i]->get(s, e);
    }
    if (i != j && j < ch.size()) {
      ret += ch[j]->get(s, e);
    }
    if (0) printf(" SAE calc %d %d returned %d\n", s, e, ret.v);
    return ret;
  }
  void print(int indent) {
    if (0) printf(" value = %d\n", value.v);
  }
};
Hang::Hang() {
  value = 1;
  pref.push_back(1);
  l = IDX;
  while (true) {
    if (S[IDX] == '(') {
      ch.push_back(new SAE());
    } else {
      ch.push_back(new Number());
    }
    value *= ch.back()->value;
    pref.push_back(value);
    if (S[IDX] != '*') break;
    adv();
  }
  r = IDX - 1;
}
int N;
int main() {
  pwinv10[0] = 1;
  pw10[0] = 1;
  assert((INV10 * 10).v == 1);
  for (int i = 1; i < N_; i++) {
    pw10[i] = pw10[i - 1] * 10;
    pwinv10[i] = pwinv10[i - 1] * INV10;
  }
  S[0] = '(';
  scanf("%s", S + 1);
  S[strlen(S + 1) + 1] = ')';
  N = strlen(S);
  new SAE();
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    bool good = true;
    good &= isdigit(S[l]) || (S[l] == '(');
    good &= isdigit(S[r]) || (S[r] == ')');
    good &= (wh[l] == wh[r]);
    if (good) {
      printf("%d\n", wh[l]->get(l, r).v);
    } else {
      printf("-1\n");
    }
  }
  return 0;
}