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 = 500000;
const int mod = 1000000007;
char s[N];
struct block;
block *bl[N];
int poww[N];
stack<block *> blocks;
void next(int &it) {
  if (blocks.empty())
    it++;
  else
    bl[it++] = blocks.top();
}
int power(int a, int b) {
  if (b == 0) return 1;
  if (b & 1) return 1LL * a * power(a, b - 1) % mod;
  return power(1LL * a * a % mod, b / 2);
}
int inv(int a) { return power(a, mod - 2); }
struct expr {
  int a, b;
  int val;
  virtual int _get(int A, int B) { return 0; };
  int get(int A, int B) {
    A = max(a, A);
    B = min(b, B);
    if (a == A && b == B) {
      return val;
    }
    return _get(A, B);
  }
  expr(int A, int B) : a(A), b(B) {}
  expr() = default;
};
struct num : expr {
  vector<int> pref;
  num(int &it) {
    a = it;
    val = 0;
    pref.push_back(0);
    while (isdigit(s[it])) {
      val = (1LL * val * 10 + s[it] - '0') % mod;
      next(it);
      pref.push_back(val);
    }
    b = it;
  }
  int _get(int A, int B) {
    int ans = (pref[B - a] - 1LL * pref[A - a] * poww[B - A]) % mod;
    if (ans < 0) ans += mod;
    return ans;
  }
};
struct prod : expr {
  vector<expr *> vec;
  vector<int> res;
  prod(int &it);
  int _get(int A, int B) {
    auto e = new expr(A, B);
    auto it1 = upper_bound(vec.begin(), vec.end(), e,
                           [](expr *a, expr *b) { return a->a < b->a; });
    auto it2 = lower_bound(vec.begin(), vec.end(), e,
                           [](expr *a, expr *b) { return a->b < b->b; });
    delete e;
    int ans = 1;
    if (it2 > it1)
      ans = 1LL * res[it2 - vec.begin()] * inv(res[it1 - vec.begin()]) % mod;
    if (it2 != vec.end()) ans = 1LL * ans * (*it2)->get(A, B) % mod;
    if (it1 != vec.begin() && --it1 != it2)
      ans = 1LL * ans * (*it1)->get(A, B) % mod;
    return ans;
  }
};
struct block : expr {
  vector<expr *> vec;
  vector<int> res;
  block(int &it) {
    val = 0;
    a = it;
    assert(s[it] == '(');
    next(it);
    blocks.push(this);
    res.push_back(0);
    while (true) {
      vec.push_back(new prod(it));
      val = (val + vec.back()->val) % mod;
      res.push_back(val);
      if (s[it] != '+')
        break;
      else
        next(it);
    }
    blocks.pop();
    assert(s[it] = ')');
    next(it);
    b = it;
  }
  int _get(int A, int B) {
    if (a == A || b == B) return -1;
    auto e = new expr(A, B);
    auto it1 = upper_bound(vec.begin(), vec.end(), e,
                           [](expr *a, expr *b) { return a->a < b->a; });
    auto it2 = lower_bound(vec.begin(), vec.end(), e,
                           [](expr *a, expr *b) { return a->b < b->b; });
    delete e;
    int ans = 0;
    if (it2 > it1) ans = res[it2 - vec.begin()] - res[it1 - vec.begin()];
    if (ans < 0) ans += mod;
    if (it2 != vec.end()) ans = (ans + (*it2)->get(A, B)) % mod;
    if (it1 != vec.begin() && --it1 != it2)
      ans = (ans + (*it1)->get(A, B)) % mod;
    return ans;
  }
};
prod::prod(int &it) {
  val = 1;
  a = it;
  res.push_back(1);
  while (true) {
    if (s[it] == '(')
      vec.push_back(new block(it));
    else
      vec.push_back(new num(it));
    val = 1LL * val * vec.back()->val % mod;
    res.push_back(val);
    if (s[it] != '*')
      break;
    else
      next(it);
  }
  b = it;
}
int main() {
  poww[0] = 1;
  for (int i = 1; i < N; i++) poww[i] = poww[i - 1] * 10LL % mod;
  scanf("%s", s + 1);
  s[0] = '(';
  s[strlen(s)] = ')';
  int i = 0;
  new block(i);
  int n;
  scanf("%d", &n);
  while (n--) {
    int a, b;
    scanf("%d %d", &a, &b);
    if ((!isdigit(s[a]) && s[a] != '(') || (!isdigit(s[b]) && s[b] != ')') ||
        bl[a] != bl[b]) {
      puts("-1");
      continue;
    }
    printf("%d\n", bl[a]->get(a, b + 1));
  }
}