#include <bits/stdc++.h>
char a[100001];
const long long MOD6 = 1000000006, MOD7 = 1000000007;
long long POWER(long long a, long long b, long long c) {
  long long r = 1 % c;
  for (; b; b >>= 1) {
    if (b & 1) r = r * a % c;
    a = a * a % c;
  }
  return r;
}
struct token {
  long long LEN, W;
  inline token operator+(const token &x) const {
    return {LEN * x.LEN % MOD7, (W * x.LEN + x.W) % MOD7};
  }
  inline token operator*(long long time) const {
    if (LEN == 1)
      return {1, W * time % MOD7};
    else {
      long long NL = POWER(LEN, time, MOD7);
      return {NL, W * (NL + MOD7 - 1) % MOD7 * POWER(LEN - 1, MOD7 - 2, MOD7) %
                      MOD7};
    }
  }
  inline void append(int d) {
    LEN = LEN * 10 % MOD7;
    W = (W * 10 + d) % MOD7;
  }
};
token before[100001], cur[100001], af[100001];
long long c6[100001], a6[100001], cl[100001], al[100001];
int D;
token part(long long L7, long long L6, long long R7, long long R6,
           long long L) {
  long long D = POWER(10, L, MOD7);
  if (D == 1)
    return {1, (L7 + R7) * (R7 - L7 + 1) % MOD7 * ((MOD7 + 1) >> 1) % MOD7};
  long long TEN = POWER(10, (R6 - L6 + 1 + MOD6) % MOD6, MOD7),
            DPOW = POWER(TEN, L, MOD7), INVDM1 = POWER(D - 1, MOD7 - 2, MOD7);
  return {DPOW, (L7 * DPOW - R7 + MOD7 + (DPOW - D + MOD7) * INVDM1) % MOD7 *
                    INVDM1 % MOD7};
}
token cont(token L, long long L6, long long LL, token R, long long R6,
           long long RL) {
  if (LL == RL) return part(L.W, L6, R.W, R6, LL);
  token ans =
      part(L.W, L6, POWER(10, LL, MOD7) - 1, POWER(10, LL, MOD6) - 1, LL);
  for (int i = LL + 1; i < RL; i++)
    ans = ans + part(POWER(10, i - 1, MOD7), POWER(10, i - 1, MOD6),
                     POWER(10, i, MOD7) - 1, POWER(10, i, MOD6) - 1, i);
  ans =
      ans + part(POWER(10, RL - 1, MOD7), POWER(10, RL - 1, MOD6), R.W, R6, RL);
  return ans;
}
int main() {
  D = 1;
  before[1] = {1, 0};
  cur[1] = {1, 0};
  af[1] = {-1, 0};
  scanf("%s", a);
  for (char *c = a; *c; c++)
    if (*c >= '0' && *c <= '9') {
      if (~af[D].LEN) {
        af[D].append(*c - 48);
        al[D]++;
        a6[D] = (a6[D] * 10 + *c - 48) % MOD6;
      } else {
        cur[D].append(*c - 48);
        cl[D]++;
        c6[D] = (c6[D] * 10 + *c - 48) % MOD6;
      }
    } else if (*c == '+') {
      before[D] = before[D] +
                  (~af[D].LEN ? cont(cur[D], c6[D], cl[D], af[D], a6[D], al[D])
                              : cur[D]);
      c6[D] = 0;
      cl[D] = 0;
      cur[D] = {1, 0};
      a6[D] = 0;
      al[D] = 0;
      af[D] = {-1, 0};
    } else if (*c == '-') {
      a6[D] = 0;
      al[D] = 0;
      af[D] = {1, 0};
    } else if (*c == '(') {
      before[++D] = {1, 0};
      c6[D] = 0;
      cl[D] = 0;
      cur[D] = {1, 0};
      a6[D] = 0;
      al[D] = 0;
      af[D] = {-1, 0};
    } else if (*c == ')') {
      cur[D - 1] = (before[D] + (~af[D].LEN ? cont(cur[D], c6[D], cl[D], af[D],
                                                   a6[D], al[D])
                                            : cur[D])) *
                   c6[D - 1];
      D--;
    }
  token WHOLE =
      before[1] +
      (~af[1].LEN ? cont(cur[1], c6[1], cl[1], af[1], a6[1], al[1]) : cur[D]);
  printf("%lld\n", WHOLE.W);
  return 0;
}

### Prompt

Create a solution in Cpp for 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>
char a[100001];
const long long MOD6 = 1000000006, MOD7 = 1000000007;
long long POWER(long long a, long long b, long long c) {
  long long r = 1 % c;
  for (; b; b >>= 1) {
    if (b & 1) r = r * a % c;
    a = a * a % c;
  }
  return r;
}
struct token {
  long long LEN, W;
  inline token operator+(const token &x) const {
    return {LEN * x.LEN % MOD7, (W * x.LEN + x.W) % MOD7};
  }
  inline token operator*(long long time) const {
    if (LEN == 1)
      return {1, W * time % MOD7};
    else {
      long long NL = POWER(LEN, time, MOD7);
      return {NL, W * (NL + MOD7 - 1) % MOD7 * POWER(LEN - 1, MOD7 - 2, MOD7) %
                      MOD7};
    }
  }
  inline void append(int d) {
    LEN = LEN * 10 % MOD7;
    W = (W * 10 + d) % MOD7;
  }
};
token before[100001], cur[100001], af[100001];
long long c6[100001], a6[100001], cl[100001], al[100001];
int D;
token part(long long L7, long long L6, long long R7, long long R6,
           long long L) {
  long long D = POWER(10, L, MOD7);
  if (D == 1)
    return {1, (L7 + R7) * (R7 - L7 + 1) % MOD7 * ((MOD7 + 1) >> 1) % MOD7};
  long long TEN = POWER(10, (R6 - L6 + 1 + MOD6) % MOD6, MOD7),
            DPOW = POWER(TEN, L, MOD7), INVDM1 = POWER(D - 1, MOD7 - 2, MOD7);
  return {DPOW, (L7 * DPOW - R7 + MOD7 + (DPOW - D + MOD7) * INVDM1) % MOD7 *
                    INVDM1 % MOD7};
}
token cont(token L, long long L6, long long LL, token R, long long R6,
           long long RL) {
  if (LL == RL) return part(L.W, L6, R.W, R6, LL);
  token ans =
      part(L.W, L6, POWER(10, LL, MOD7) - 1, POWER(10, LL, MOD6) - 1, LL);
  for (int i = LL + 1; i < RL; i++)
    ans = ans + part(POWER(10, i - 1, MOD7), POWER(10, i - 1, MOD6),
                     POWER(10, i, MOD7) - 1, POWER(10, i, MOD6) - 1, i);
  ans =
      ans + part(POWER(10, RL - 1, MOD7), POWER(10, RL - 1, MOD6), R.W, R6, RL);
  return ans;
}
int main() {
  D = 1;
  before[1] = {1, 0};
  cur[1] = {1, 0};
  af[1] = {-1, 0};
  scanf("%s", a);
  for (char *c = a; *c; c++)
    if (*c >= '0' && *c <= '9') {
      if (~af[D].LEN) {
        af[D].append(*c - 48);
        al[D]++;
        a6[D] = (a6[D] * 10 + *c - 48) % MOD6;
      } else {
        cur[D].append(*c - 48);
        cl[D]++;
        c6[D] = (c6[D] * 10 + *c - 48) % MOD6;
      }
    } else if (*c == '+') {
      before[D] = before[D] +
                  (~af[D].LEN ? cont(cur[D], c6[D], cl[D], af[D], a6[D], al[D])
                              : cur[D]);
      c6[D] = 0;
      cl[D] = 0;
      cur[D] = {1, 0};
      a6[D] = 0;
      al[D] = 0;
      af[D] = {-1, 0};
    } else if (*c == '-') {
      a6[D] = 0;
      al[D] = 0;
      af[D] = {1, 0};
    } else if (*c == '(') {
      before[++D] = {1, 0};
      c6[D] = 0;
      cl[D] = 0;
      cur[D] = {1, 0};
      a6[D] = 0;
      al[D] = 0;
      af[D] = {-1, 0};
    } else if (*c == ')') {
      cur[D - 1] = (before[D] + (~af[D].LEN ? cont(cur[D], c6[D], cl[D], af[D],
                                                   a6[D], al[D])
                                            : cur[D])) *
                   c6[D - 1];
      D--;
    }
  token WHOLE =
      before[1] +
      (~af[1].LEN ? cont(cur[1], c6[1], cl[1], af[1], a6[1], al[1]) : cur[D]);
  printf("%lld\n", WHOLE.W);
  return 0;
}

```