#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int MOD = 1e9 + 7;
const int DEBUG = false;
vector<int> PLUS[N], MINUS[N];
int power10[N][2];
int match[N];
char s[N];
int n;
int power(int a, int b, int mod = MOD) {
  int ret = 1;
  for (; b; b >>= 1) {
    if (b & 1) {
      ret = 1LL * ret * a % mod;
    }
    a = 1LL * a * a % mod;
  }
  return ret;
}
pair<int, int> concat(pair<int, int> a, pair<int, int> b) {
  return {(1LL * a.first * b.second % MOD + b.first) % MOD,
          1LL * a.second * b.second % MOD};
}
pair<int, int> parse_exp(int dep, int l, int r);
int parse_number(int l, int r, int mod) {
  if (DEBUG) cout << "parse number " << string(s + l, s + r + 1) << endl;
  int ret = 0;
  for (int i = l; i <= r; i++) {
    ret = (ret * 10LL + s[i] - '0') % mod;
  }
  return ret;
}
int sum(int a, int b[2]) {
  if (a == 1) {
    return b[0] % MOD;
  }
  int upper = power(a, b[1], MOD) + MOD - 1;
  int lower = a + MOD - 1;
  return 1LL * upper % MOD * power(lower % MOD, MOD - 2, MOD) % MOD;
}
pair<int, int> brute_force(int x) {
  pair<int, int> ret = {0, 1};
  for (int i = 1; i <= x; i++) {
    int p = 1, t = i;
    while (t) {
      (p *= 10) %= MOD;
      t /= 10;
    }
    ret = concat(ret, {i, p});
  }
  return ret;
}
pair<int, int> get_val(int r, long long number[2], int l) {
  int p = power10[l][0];
  if (DEBUG) cout << r << " " << number[1] << " " << p << endl;
  assert(p != 1);
  int ret = 0;
  if (p == 1) {
    ret = 1LL * r * (number[0] + 1) % MOD;
    ret -= 1LL * number[0] * (number[0] + 1) / 2 % MOD;
  } else {
    int n = number[1];
    ret = 1LL * r * (power(p, n + 1) + MOD - 1) % MOD * power(p - 1, MOD - 2) %
          MOD;
    int ms = 1LL * number[0] * power(p, n + 1) % MOD;
    ms -= 1LL * (power(p, n + 1) - 1) * power(p - 1, MOD - 2) % MOD;
    ms++;
    ms = 1LL * (ms % MOD + MOD) % MOD * power(p - 1, MOD - 2) % MOD;
    ret -= ms;
  }
  if (ret < 0) ret += MOD;
  return {ret, power(10, 1LL * (number[1] + 1) * l % (MOD - 1))};
}
pair<int, int> calc(string s, int op = 0) {
  if (DEBUG) cout << "parse calc " << s << " op = " << op << endl;
  static int a[N];
  int m = s.size();
  for (int i = 0; i < m; i++) {
    a[i] = s[m - i - 1] - '0';
  }
  if (s == "0" || (s == "1" && op == 1)) {
    return {0, 1};
  }
  if (op) {
    a[0]--;
    for (int i = 0; i < m; i++) {
      if (a[i] < 0) {
        a[i] += 10;
        a[i + 1]--;
      }
    }
    while (m > 1 && a[m - 1] == 0) m--;
  }
  pair<int, int> ret = {0, 1};
  for (int i = 1; i < m; i++) {
    long long number[2] = {
        (power10[i][0] - 1 - power10[i - 1][0] + MOD) % MOD,
        (power10[i][1] - 1 - power10[i - 1][1] + MOD - 1) % (MOD - 1)};
    ret = concat(ret, get_val((power10[i][0] + MOD - 1) % MOD, number, i));
  }
  int r[2] = {0};
  for (int i = m - 1; i >= 0; i--) {
    for (int j = 0; j < 2; j++) {
      int mod = (MOD - j);
      r[j] = (r[j] * 10LL + a[i]) % mod;
    }
  }
  long long number[2] = {(r[0] - power10[m - 1][0] + MOD) % MOD,
                         (r[1] - power10[m - 1][1] + MOD - 1) % (MOD - 1)};
  ret = concat(ret, get_val(r[0], number, m));
  if (DEBUG) cout << "result = " << ret.first << " " << ret.second << endl;
  return ret;
}
pair<int, int> parse_term(int dep, int l, int r) {
  if (DEBUG) cout << "parse term " << string(s + l, s + r + 1) << endl;
  if (s[r] == ')') {
    int p = match[r];
    auto e = parse_exp(dep + 1, p + 1, r - 1);
    int number[2] = {parse_number(l, p - 1, MOD),
                     parse_number(l, p - 1, MOD - 1)};
    return {1LL * e.first * sum(e.second, number) % MOD,
            power(e.second, number[1])};
  } else {
    int i = upper_bound(MINUS[dep].begin(), MINUS[dep].end(), r) -
            MINUS[dep].begin() - 1;
    if (i < 0 || MINUS[dep][i] < l)
      return {parse_number(l, r, MOD), power10[r - l + 1][0]};
    int p = MINUS[dep][i];
    auto eval_l = calc(string(s + l, s + p), 1);
    auto eval_r = calc(string(s + p + 1, s + r + 1));
    int second = 1LL * eval_r.second * power(eval_l.second, MOD - 2) % MOD;
    int first = eval_r.first - 1LL * eval_l.first * second % MOD;
    if (first < 0) first += MOD;
    return {first, second};
  }
}
pair<int, int> parse_exp(int dep, int l, int r) {
  if (DEBUG) cout << "parse exp " << string(s + l, s + r + 1) << endl;
  int i = upper_bound(PLUS[dep].begin(), PLUS[dep].end(), r) -
          PLUS[dep].begin() - 1;
  if (i < 0 || PLUS[dep][i] < l) return parse_term(dep, l, r);
  int p = PLUS[dep][i];
  auto a = parse_exp(dep, l, p - 1), b = parse_term(dep, p + 1, r);
  return concat(a, b);
}
void prepare() {
  power10[0][0] = power10[0][1] = 1;
  for (int i = 0; i < n; i++) {
    power10[i + 1][0] = power10[i][0] * 10LL % MOD;
    power10[i + 1][1] = power10[i][1] * 10LL % (MOD - 1);
  }
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  prepare();
  vector<int> stack;
  for (int i = 0, cur = 0; i < n; i++) {
    switch (s[i]) {
      case '(':
        cur++;
        stack.push_back(i);
        break;
      case ')':
        cur--;
        match[stack.back()] = i, match[i] = stack.back();
        stack.pop_back();
        break;
      case '+':
        PLUS[cur].push_back(i);
        break;
      case '-':
        MINUS[cur].push_back(i);
        break;
    }
  }
  cout << parse_exp(0, 0, n - 1).first << endl;
  return 0;
}

### Prompt

Please formulate a cpp solution to the following problem:

Consider the following grammar:

  * <expression> ::= <term> | <expression> '+' <term>
  * <term> ::= <number> | <number> '-' <number> | <number> '(' <expression> ')'
  * <number> ::= <pos_digit> | <number> <digit>
  * <digit> ::= '0' | <pos_digit>
  * <pos_digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'



This grammar describes a number in decimal system using the following rules:

  * <number> describes itself,
  * <number>-<number> (l-r, l ≤ r) describes integer which is concatenation of all integers from l to r, written without leading zeros. For example, 8-11 describes 891011,
  * <number>(<expression>) describes integer which is concatenation of <number> copies of integer described by <expression>,
  * <expression>+<term> describes integer which is concatenation of integers described by <expression> and <term>.



For example, 2(2-4+1)+2(2(17)) describes the integer 2341234117171717.

You are given an expression in the given grammar. Print the integer described by it modulo 109 + 7.

Input

The only line contains a non-empty string at most 105 characters long which is valid according to the given grammar. In particular, it means that in terms l-r l ≤ r holds.

Output

Print single integer — the number described by the expression modulo 109 + 7.

Examples

Input

8-11


Output

891011


Input

2(2-4+1)+2(2(17))


Output

100783079


Input

1234-5678


Output

745428774


Input

1+2+3+4-5+6+7-9


Output

123456789

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int MOD = 1e9 + 7;
const int DEBUG = false;
vector<int> PLUS[N], MINUS[N];
int power10[N][2];
int match[N];
char s[N];
int n;
int power(int a, int b, int mod = MOD) {
  int ret = 1;
  for (; b; b >>= 1) {
    if (b & 1) {
      ret = 1LL * ret * a % mod;
    }
    a = 1LL * a * a % mod;
  }
  return ret;
}
pair<int, int> concat(pair<int, int> a, pair<int, int> b) {
  return {(1LL * a.first * b.second % MOD + b.first) % MOD,
          1LL * a.second * b.second % MOD};
}
pair<int, int> parse_exp(int dep, int l, int r);
int parse_number(int l, int r, int mod) {
  if (DEBUG) cout << "parse number " << string(s + l, s + r + 1) << endl;
  int ret = 0;
  for (int i = l; i <= r; i++) {
    ret = (ret * 10LL + s[i] - '0') % mod;
  }
  return ret;
}
int sum(int a, int b[2]) {
  if (a == 1) {
    return b[0] % MOD;
  }
  int upper = power(a, b[1], MOD) + MOD - 1;
  int lower = a + MOD - 1;
  return 1LL * upper % MOD * power(lower % MOD, MOD - 2, MOD) % MOD;
}
pair<int, int> brute_force(int x) {
  pair<int, int> ret = {0, 1};
  for (int i = 1; i <= x; i++) {
    int p = 1, t = i;
    while (t) {
      (p *= 10) %= MOD;
      t /= 10;
    }
    ret = concat(ret, {i, p});
  }
  return ret;
}
pair<int, int> get_val(int r, long long number[2], int l) {
  int p = power10[l][0];
  if (DEBUG) cout << r << " " << number[1] << " " << p << endl;
  assert(p != 1);
  int ret = 0;
  if (p == 1) {
    ret = 1LL * r * (number[0] + 1) % MOD;
    ret -= 1LL * number[0] * (number[0] + 1) / 2 % MOD;
  } else {
    int n = number[1];
    ret = 1LL * r * (power(p, n + 1) + MOD - 1) % MOD * power(p - 1, MOD - 2) %
          MOD;
    int ms = 1LL * number[0] * power(p, n + 1) % MOD;
    ms -= 1LL * (power(p, n + 1) - 1) * power(p - 1, MOD - 2) % MOD;
    ms++;
    ms = 1LL * (ms % MOD + MOD) % MOD * power(p - 1, MOD - 2) % MOD;
    ret -= ms;
  }
  if (ret < 0) ret += MOD;
  return {ret, power(10, 1LL * (number[1] + 1) * l % (MOD - 1))};
}
pair<int, int> calc(string s, int op = 0) {
  if (DEBUG) cout << "parse calc " << s << " op = " << op << endl;
  static int a[N];
  int m = s.size();
  for (int i = 0; i < m; i++) {
    a[i] = s[m - i - 1] - '0';
  }
  if (s == "0" || (s == "1" && op == 1)) {
    return {0, 1};
  }
  if (op) {
    a[0]--;
    for (int i = 0; i < m; i++) {
      if (a[i] < 0) {
        a[i] += 10;
        a[i + 1]--;
      }
    }
    while (m > 1 && a[m - 1] == 0) m--;
  }
  pair<int, int> ret = {0, 1};
  for (int i = 1; i < m; i++) {
    long long number[2] = {
        (power10[i][0] - 1 - power10[i - 1][0] + MOD) % MOD,
        (power10[i][1] - 1 - power10[i - 1][1] + MOD - 1) % (MOD - 1)};
    ret = concat(ret, get_val((power10[i][0] + MOD - 1) % MOD, number, i));
  }
  int r[2] = {0};
  for (int i = m - 1; i >= 0; i--) {
    for (int j = 0; j < 2; j++) {
      int mod = (MOD - j);
      r[j] = (r[j] * 10LL + a[i]) % mod;
    }
  }
  long long number[2] = {(r[0] - power10[m - 1][0] + MOD) % MOD,
                         (r[1] - power10[m - 1][1] + MOD - 1) % (MOD - 1)};
  ret = concat(ret, get_val(r[0], number, m));
  if (DEBUG) cout << "result = " << ret.first << " " << ret.second << endl;
  return ret;
}
pair<int, int> parse_term(int dep, int l, int r) {
  if (DEBUG) cout << "parse term " << string(s + l, s + r + 1) << endl;
  if (s[r] == ')') {
    int p = match[r];
    auto e = parse_exp(dep + 1, p + 1, r - 1);
    int number[2] = {parse_number(l, p - 1, MOD),
                     parse_number(l, p - 1, MOD - 1)};
    return {1LL * e.first * sum(e.second, number) % MOD,
            power(e.second, number[1])};
  } else {
    int i = upper_bound(MINUS[dep].begin(), MINUS[dep].end(), r) -
            MINUS[dep].begin() - 1;
    if (i < 0 || MINUS[dep][i] < l)
      return {parse_number(l, r, MOD), power10[r - l + 1][0]};
    int p = MINUS[dep][i];
    auto eval_l = calc(string(s + l, s + p), 1);
    auto eval_r = calc(string(s + p + 1, s + r + 1));
    int second = 1LL * eval_r.second * power(eval_l.second, MOD - 2) % MOD;
    int first = eval_r.first - 1LL * eval_l.first * second % MOD;
    if (first < 0) first += MOD;
    return {first, second};
  }
}
pair<int, int> parse_exp(int dep, int l, int r) {
  if (DEBUG) cout << "parse exp " << string(s + l, s + r + 1) << endl;
  int i = upper_bound(PLUS[dep].begin(), PLUS[dep].end(), r) -
          PLUS[dep].begin() - 1;
  if (i < 0 || PLUS[dep][i] < l) return parse_term(dep, l, r);
  int p = PLUS[dep][i];
  auto a = parse_exp(dep, l, p - 1), b = parse_term(dep, p + 1, r);
  return concat(a, b);
}
void prepare() {
  power10[0][0] = power10[0][1] = 1;
  for (int i = 0; i < n; i++) {
    power10[i + 1][0] = power10[i][0] * 10LL % MOD;
    power10[i + 1][1] = power10[i][1] * 10LL % (MOD - 1);
  }
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  prepare();
  vector<int> stack;
  for (int i = 0, cur = 0; i < n; i++) {
    switch (s[i]) {
      case '(':
        cur++;
        stack.push_back(i);
        break;
      case ')':
        cur--;
        match[stack.back()] = i, match[i] = stack.back();
        stack.pop_back();
        break;
      case '+':
        PLUS[cur].push_back(i);
        break;
      case '-':
        MINUS[cur].push_back(i);
        break;
    }
  }
  cout << parse_exp(0, 0, n - 1).first << endl;
  return 0;
}

```