#include <bits/stdc++.h>
using namespace std;
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et() {
  puts("-1");
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
int tn1[100005], tn2[100005];
struct mb {
  int val, val1, len;
  mb() {}
  mb(int val, int len) : val(val), len(len) {}
  mb(int val, int val1, int len) : val(val), val1(val1), len(len) {}
  mb operator+(const mb &b) const {
    return mb((fastPow(10, b.len) * val + b.val) % 1000000007,
              (len + b.len) % (1000000007 - 1));
  }
  mb operator*(const mb &b) const {
    int f = 0;
    if (fastPow(10, b.len) == 1) {
      f = (long long)b.val * val % 1000000007;
    } else {
      f = (long long)(fastPow(10, (long long)b.len * val1 % (1000000007 - 1)) +
                      1000000007 - 1) %
          1000000007 *
          fastPow(fastPow(10, b.len) + 1000000007 - 1, 1000000007 - 2) %
          1000000007 * b.val % 1000000007;
    }
    return mb(f, (long long)b.len * val1 % (1000000007 - 1));
  }
  int ff(pair<int, int> a, int dig) const {
    int R1 = (a.first + 1) % 1000000007, R2 = (a.second + 1) % (1000000007 - 1);
    int num = fastPow((fastPow(10, dig) - 1 + 1000000007) % 1000000007,
                      1000000007 - 2),
        ANS = 0;
    if (num == 0)
      ANS = 1ll * R1 * (R1 - 1 + 1000000007) % 1000000007 *
            fastPow(2, 1000000007 - 2) % 1000000007;
    else
      ANS = 1ll *
            ((1ll * (fastPow(10, 1ll * dig * R2 % (1000000007 - 1)) - 1) * num -
              R1) %
             1000000007) *
            num % 1000000007;
    return ANS;
  }
  pair<int, int> f(pair<int, int> a, pair<int, int> b, int dig) const {
    int A = (1ll * ff(b, dig) -
             1ll *
                 fastPow(10, 1ll * dig *
                                 (b.second - a.second + 1 + 1000000007 - 1) %
                                 (1000000007 - 1)) *
                 ff({a.first - 1 + 1000000007, a.second - 1 + 1000000007 - 1},
                    dig)) %
            1000000007;
    int B = 1ll * dig * (b.second - a.second + 1 + 1000000007 - 1) %
            (1000000007 - 1);
    return {A, B};
  }
  mb operator-(const mb &b) const {
    mb Ans = {0, 0};
    pair<int, int> nw = {val, val1};
    for (int i = len; i < b.len; i++) {
      pair<int, int> x = {tn1[i], tn2[i]};
      pair<int, int> zz = f(nw,
                            {(x.first + 1000000007 - 1) % 1000000007,
                             (x.second + 1000000007 - 2) % (1000000007 - 1)},
                            i);
      Ans = Ans + mb(zz.first, zz.second);
      nw = x;
    }
    pair<int, int> zz = f(nw, {b.val, b.val1}, b.len);
    Ans = Ans + mb(zz.first, zz.second);
    return Ans;
  }
};
char S[100005];
int st = 1;
bool isd(char x) { return '0' <= x && x <= '9'; }
vector<int> bs;
int ed;
mb dfs(bool fg = 0) {
  mb ret;
  assert(isd(S[st]));
  int a = 0, b = 0, c = 0;
  while (st <= n && isd(S[st])) {
    int num = S[st] - '0';
    c++;
    a = ((long long)a * 10 + num) % 1000000007;
    b = ((long long)b * 10 + num) % (1000000007 - 1);
    st++;
  }
  ret = mb(a, b, c);
  if (fg) return ret;
  int cur = st;
  while (st <= n) {
    if (S[st] == ')') {
      ed = st;
      st++;
      return ret;
    }
    if (S[st] == '+') {
      st++;
      ret = ret + dfs();
    } else if (S[st] == '-') {
      st++;
      ret = ret - dfs(1);
    } else if (S[st] == '(') {
      bs.push_back(st);
      st++;
      ret = ret * dfs();
    }
    if (ed != 0) {
      if (bs.back() < cur) return ret;
      bs.pop_back();
      ed = 0;
    }
  }
  return ret;
}
void fmain(int tid) {
  scanf("%s", S + 1);
  tn1[0] = tn2[0] = 1;
  n = strlen(S + 1);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    tn1[i] = (long long)tn1[i - 1] * 10 % 1000000007;
    tn2[i] = (long long)tn2[i - 1] * 10 % (1000000007 - 1);
  }
  mb ret = dfs();
  int ans = ret.val;
  addmod(ans, 1000000007);
  printf("%d\n", ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et() {
  puts("-1");
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
int tn1[100005], tn2[100005];
struct mb {
  int val, val1, len;
  mb() {}
  mb(int val, int len) : val(val), len(len) {}
  mb(int val, int val1, int len) : val(val), val1(val1), len(len) {}
  mb operator+(const mb &b) const {
    return mb((fastPow(10, b.len) * val + b.val) % 1000000007,
              (len + b.len) % (1000000007 - 1));
  }
  mb operator*(const mb &b) const {
    int f = 0;
    if (fastPow(10, b.len) == 1) {
      f = (long long)b.val * val % 1000000007;
    } else {
      f = (long long)(fastPow(10, (long long)b.len * val1 % (1000000007 - 1)) +
                      1000000007 - 1) %
          1000000007 *
          fastPow(fastPow(10, b.len) + 1000000007 - 1, 1000000007 - 2) %
          1000000007 * b.val % 1000000007;
    }
    return mb(f, (long long)b.len * val1 % (1000000007 - 1));
  }
  int ff(pair<int, int> a, int dig) const {
    int R1 = (a.first + 1) % 1000000007, R2 = (a.second + 1) % (1000000007 - 1);
    int num = fastPow((fastPow(10, dig) - 1 + 1000000007) % 1000000007,
                      1000000007 - 2),
        ANS = 0;
    if (num == 0)
      ANS = 1ll * R1 * (R1 - 1 + 1000000007) % 1000000007 *
            fastPow(2, 1000000007 - 2) % 1000000007;
    else
      ANS = 1ll *
            ((1ll * (fastPow(10, 1ll * dig * R2 % (1000000007 - 1)) - 1) * num -
              R1) %
             1000000007) *
            num % 1000000007;
    return ANS;
  }
  pair<int, int> f(pair<int, int> a, pair<int, int> b, int dig) const {
    int A = (1ll * ff(b, dig) -
             1ll *
                 fastPow(10, 1ll * dig *
                                 (b.second - a.second + 1 + 1000000007 - 1) %
                                 (1000000007 - 1)) *
                 ff({a.first - 1 + 1000000007, a.second - 1 + 1000000007 - 1},
                    dig)) %
            1000000007;
    int B = 1ll * dig * (b.second - a.second + 1 + 1000000007 - 1) %
            (1000000007 - 1);
    return {A, B};
  }
  mb operator-(const mb &b) const {
    mb Ans = {0, 0};
    pair<int, int> nw = {val, val1};
    for (int i = len; i < b.len; i++) {
      pair<int, int> x = {tn1[i], tn2[i]};
      pair<int, int> zz = f(nw,
                            {(x.first + 1000000007 - 1) % 1000000007,
                             (x.second + 1000000007 - 2) % (1000000007 - 1)},
                            i);
      Ans = Ans + mb(zz.first, zz.second);
      nw = x;
    }
    pair<int, int> zz = f(nw, {b.val, b.val1}, b.len);
    Ans = Ans + mb(zz.first, zz.second);
    return Ans;
  }
};
char S[100005];
int st = 1;
bool isd(char x) { return '0' <= x && x <= '9'; }
vector<int> bs;
int ed;
mb dfs(bool fg = 0) {
  mb ret;
  assert(isd(S[st]));
  int a = 0, b = 0, c = 0;
  while (st <= n && isd(S[st])) {
    int num = S[st] - '0';
    c++;
    a = ((long long)a * 10 + num) % 1000000007;
    b = ((long long)b * 10 + num) % (1000000007 - 1);
    st++;
  }
  ret = mb(a, b, c);
  if (fg) return ret;
  int cur = st;
  while (st <= n) {
    if (S[st] == ')') {
      ed = st;
      st++;
      return ret;
    }
    if (S[st] == '+') {
      st++;
      ret = ret + dfs();
    } else if (S[st] == '-') {
      st++;
      ret = ret - dfs(1);
    } else if (S[st] == '(') {
      bs.push_back(st);
      st++;
      ret = ret * dfs();
    }
    if (ed != 0) {
      if (bs.back() < cur) return ret;
      bs.pop_back();
      ed = 0;
    }
  }
  return ret;
}
void fmain(int tid) {
  scanf("%s", S + 1);
  tn1[0] = tn2[0] = 1;
  n = strlen(S + 1);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    tn1[i] = (long long)tn1[i - 1] * 10 % 1000000007;
    tn2[i] = (long long)tn2[i - 1] * 10 % (1000000007 - 1);
  }
  mb ret = dfs();
  int ans = ret.val;
  addmod(ans, 1000000007);
  printf("%d\n", ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

```