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;
const int N = 4e5 + 7;
const int LOG = 20;
int n;
int match[N], dep[N];
vector<int> PLUS[N], times[N];
char s[N];
int f[N][LOG], g[N][LOG], go[N][LOG];
int suffix[N], prefix[N], nxt_opt[N], bv[N];
void add(int &a, int b) {
  if ((a += b) >= MOD) a -= MOD;
}
void mul(int &a, int b) { a = 1LL * a * b % MOD; }
bool is_digit(char c) { return '0' <= c && c <= '9'; }
int power(int a, int n) {
  int ret = 1;
  for (int i = 1; i <= n; i <<= 1) {
    if (n & i) {
      mul(ret, a);
    }
    mul(a, a);
  }
  return ret;
}
int dfs(int l, int r, int cur) {
  if (s[l] == '(' && s[r] == ')' && match[l] == r) {
    return bv[l] = bv[r] = dfs(l + 1, r - 1, cur + 1);
  } else {
    int ret = 0;
    int pos =
        lower_bound(PLUS[cur].begin(), PLUS[cur].end(), l) - PLUS[cur].begin();
    if (pos < PLUS[cur].size() && PLUS[cur][pos] < r) {
      ret = 0;
      vector<int> tmp;
      for (int i = pos; i < PLUS[cur].size() && PLUS[cur][i] < r; i++) {
        tmp.push_back(PLUS[cur][i]);
      }
      assert(tmp.size() > 0);
      add(ret, dfs(l, tmp[0] - 1, cur));
      for (int i = 0; i + 1 < tmp.size(); i++) {
        add(ret, f[tmp[i]][0] = dfs(tmp[i] + 1, tmp[i + 1] - 1, cur));
        go[tmp[i]][0] = tmp[i + 1];
      }
      add(ret, dfs(tmp.back() + 1, r, cur));
      return ret;
    }
    pos = lower_bound(times[cur].begin(), times[cur].end(), l) -
          times[cur].begin();
    if (pos < times[cur].size() && times[cur][pos] < r) {
      ret = 1;
      vector<int> tmp;
      for (int i = pos; i < times[cur].size() && times[cur][i] < r; i++) {
        tmp.push_back(times[cur][i]);
      }
      assert(tmp.size() > 0);
      mul(ret, dfs(l, tmp[0] - 1, cur));
      for (int i = 0; i + 1 < tmp.size(); i++) {
        mul(ret, g[tmp[i]][0] = dfs(tmp[i] + 1, tmp[i + 1] - 1, cur));
        go[tmp[i]][0] = tmp[i + 1];
      }
      mul(ret, dfs(tmp.back() + 1, r, cur));
      return ret;
    }
    for (int i = l; i <= r; i++) {
      assert(is_digit(s[i]));
      prefix[i] = (prefix[i - 1] * 10LL + s[i] - '0') % MOD;
      nxt_opt[i] = r + 1;
    }
    for (int i = r, base = 1; i >= l; i--) {
      suffix[i] = (suffix[i + 1] + 1LL * (s[i] - '0') * base) % MOD;
      base = base * 10LL % MOD;
    }
    return prefix[r];
  }
}
void prepare() {
  vector<int> lb;
  for (int i = 1, cur_dep = 0; i <= n; i++) {
    if (s[i] == '(') {
      cur_dep++;
      lb.push_back(i);
    } else if (s[i] == ')') {
      cur_dep--;
      match[i] = lb.back();
      match[lb.back()] = i;
      lb.pop_back();
    } else if (s[i] == '+') {
      PLUS[cur_dep].push_back(i);
    } else if (s[i] == '*') {
      times[cur_dep].push_back(i);
    }
  }
  for (int i = 1; i <= n; i++) {
    go[i][0] = 0;
  }
  dfs(1, n, 0);
}
int get_number(int l, int r) {
  return 1LL * (suffix[l] + MOD - suffix[r + 1]) % MOD *
         power(power(10, nxt_opt[l] - r - 1), MOD - 2) % MOD;
}
int get_first_number(int &l, int r) {
  int ret;
  if (s[l] == '(') {
    ret = bv[l];
    l = match[l] + 1;
  } else {
    assert(is_digit(s[l]));
    if (nxt_opt[l] == nxt_opt[r]) {
      ret = get_number(l, r);
      l = r + 1;
      return ret;
    }
    ret = suffix[l];
    l = nxt_opt[l];
  }
  return ret;
}
int solve(int l, int r) {
  if (l > r || l < 1 || r > n) return -1;
  if (s[l] == '+' || s[r] == '+' || s[l] == '*' || s[r] == '*' || s[l] == ')') {
    return -1;
  }
  int first = get_first_number(l, r);
  if (l == r + 1) return first;
  if (l > r || s[l] == ')') return -1;
  assert(s[l] != '(');
  if (s[l] == '*') {
    for (int i = LOG - 1; i >= 0; i--) {
      if (go[l][i] != 0 && go[l][i] <= r) {
        mul(first, g[l][i]);
        l = go[l][i];
      }
    }
    l++;
    int second = get_first_number(l, r);
    mul(first, second);
    if (l == r + 1) {
      return first;
    }
  }
  if (l > r || s[l] == ')') return -1;
  assert(s[l] == '+');
  for (int i = LOG - 1; i >= 0; i--) {
    if (go[l][i] != 0 && go[l][i] <= r) {
      add(first, f[l][i]);
      l = go[l][i];
    }
  }
  l++;
  int second = get_first_number(l, r);
  if (l == r + 1) return (first + second) % MOD;
  if (l > r || s[l] == ')') return -1;
  assert(s[l] == '*');
  for (int i = LOG - 1; i >= 0; i--) {
    if (go[l][i] != 0 && go[l][i] <= r) {
      mul(second, g[l][i]);
      l = go[l][i];
    }
  }
  l++;
  int third = get_first_number(l, r);
  mul(second, third);
  if (l == r + 1) return (first + second) % MOD;
  return -1;
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  prepare();
  for (int i = 0; i + 1 < LOG; i++) {
    for (int j = 1; j <= n; j++) {
      go[j][i + 1] = go[go[j][i]][i];
      f[j][i + 1] = (f[j][i] + f[go[j][i]][i]) % MOD;
      g[j][i + 1] = 1LL * g[j][i] * g[go[j][i]][i] % MOD;
    }
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    printf("%d\n", solve(l, r));
  }
  return 0;
}