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 = 1e9 + 7;
int ksm(int x, int y = mod - 2) {
  int z = 1;
  for (; y; y >>= 1, x = 1ll * x * x % mod)
    if (y & 1) z = 1ll * z * x % mod;
  return z;
}
const int inv10 = ksm(10);
int n, m, pos[400100], cnt, lp[1200100], rp[1200100], tp[1200100];
int ten[400100], net[400100];
char s[400100];
vector<int> v[1200100];
vector<int> pre[1200100], zer[1200100];
stack<int> stk;
void dfs(int x) {
  if (tp[x] == 0) pre[x].push_back(0);
  if (tp[x] == 1) pre[x].push_back(1);
  for (auto y : v[x]) {
    dfs(y);
    if (tp[x] == 0)
      pre[x].push_back((pre[x].back() + (zer[y].empty() ? pre[y].back() : 0)) %
                       mod);
    if (tp[x] == 1) {
      if (pre[y].back() == 0)
        zer[x].push_back(pre[x].size()), pre[x].push_back(pre[x].back());
      else
        pre[x].push_back(1ll * pre[x].back() * pre[y].back() % mod);
    }
  }
  if (tp[x] == 2) {
    if (!v[x].empty())
      pre[x].push_back(pre[v[x].back()].back());
    else {
      pre[x].push_back(0);
      for (int i = lp[x]; i <= rp[x]; i++)
        pre[x].push_back((10ll * pre[x].back() + s[i] - '0') % mod);
    }
  }
}
int calc(int x, int l, int r) {
  if (!v[x].empty()) return pre[x].back();
  return (pre[x][r - lp[x] + 1] + mod -
          1ll * pre[x][l - lp[x]] * ten[r - l + 1] % mod) %
         mod;
}
int CALC(int x, int l, int r) {
  auto it = upper_bound(zer[x].begin(), zer[x].end(), l);
  if (it != zer[x].end() && *it <= r) return 0;
  if (!r) return 1;
  if (l == v[x].size() + 1) return 1;
  return 1ll * pre[x][r] * ksm(pre[x][l + 1]) % mod;
}
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  ten[0] = net[0] = 1;
  for (int i = 1; i <= n; i++)
    ten[i] = 10ll * ten[i - 1] % mod, net[i] = 1ll * inv10 * net[i - 1] % mod;
  s[0] = '(', s[n + 1] = ')';
  for (int i = 0; i <= n + 1; i++) {
    if (s[i] == '(') stk.push(++cnt), lp[cnt] = i, tp[cnt] = 0;
    pos[i] = stk.top();
    if (s[i] == ')') rp[stk.top()] = i, stk.pop();
  }
  for (int i = 0; i <= n + 1; i++) {
    if (s[i] == '(') {
      if (!stk.empty()) v[stk.top()].push_back(pos[i]);
      stk.push(pos[i]);
      tp[++cnt] = 1, lp[cnt] = i + 1, stk.push(cnt);
      tp[++cnt] = 2, lp[cnt] = i + 1, stk.push(cnt);
    }
    if (s[i] == '+') {
      int tms = stk.top();
      stk.pop();
      rp[tms] = i - 1;
      int pls = stk.top();
      stk.pop();
      rp[pls] = i - 1;
      int bra = stk.top();
      v[pls].push_back(tms);
      v[bra].push_back(pls);
      tp[++cnt] = 1, lp[cnt] = i + 1, stk.push(cnt);
      tp[++cnt] = 2, lp[cnt] = i + 1, stk.push(cnt);
    }
    if (s[i] == '*') {
      int tms = stk.top();
      stk.pop();
      rp[tms] = i - 1;
      int pls = stk.top();
      v[pls].push_back(tms);
      tp[++cnt] = 2, lp[cnt] = i + 1, stk.push(cnt);
    }
    if (s[i] == ')') {
      int tms = stk.top();
      stk.pop();
      rp[tms] = i - 1;
      int pls = stk.top();
      stk.pop();
      rp[pls] = i - 1;
      int bra = stk.top();
      stk.pop();
      v[pls].push_back(tms);
      v[bra].push_back(pls);
    }
  }
  dfs(1);
  scanf("%d", &m);
  for (int i = 1, l, r; i <= m; i++) {
    scanf("%d%d", &l, &r);
    if (pos[l - 1] != pos[r + 1] || s[l] == '+' || s[l] == '*' || s[r] == '+' ||
        s[r] == '*') {
      puts("-1");
      continue;
    }
    int x = pos[l - 1];
    lp[0] = l;
    int p = upper_bound(v[x].begin(), v[x].end(), 0,
                        [](int a, int b) { return lp[a] < lp[b]; }) -
            v[x].begin() - 1;
    int P = v[x][p];
    int _p = upper_bound(v[P].begin(), v[P].end(), 0,
                         [](int a, int b) { return lp[a] < lp[b]; }) -
             v[P].begin() - 1;
    int _P = v[P][_p];
    rp[0] = r;
    int q = lower_bound(v[x].begin(), v[x].end(), 0,
                        [](int a, int b) { return rp[a] < rp[b]; }) -
            v[x].begin();
    int Q = v[x][q];
    int _q = lower_bound(v[Q].begin(), v[Q].end(), 0,
                         [](int a, int b) { return rp[a] < rp[b]; }) -
             v[Q].begin();
    int _Q = v[Q][_q];
    if (p == q && _p == _q) {
      printf("%d\n", calc(_P, l, r));
      continue;
    }
    int pp = calc(_P, l, rp[_P]);
    int qq = calc(_Q, lp[_Q], r);
    if (p == q) {
      printf("%d\n", 1ll * pp * CALC(P, _p, _q) % mod * qq % mod);
      continue;
    }
    pp = 1ll * pp * CALC(P, _p, v[P].size()) % mod;
    qq = 1ll * qq * CALC(Q, -1, _q) % mod;
    printf("%d\n",
           (0ll + pp + (pre[x][q] + mod - pre[x][p + 1]) % mod + qq) % mod);
  }
  return 0;
}