#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int MOD = 1000000007;
char op[N];
char ggggg[N], loooo[N];
struct Cons {
  int x, y;
  Cons() {}
  Cons(int _x, int _y) : x(_x), y(_y) {}
  Cons &operator+=(const Cons &b) {
    y = (1ll * y * b.x + b.y) % MOD;
    x = (1ll * x * b.x) % MOD;
    return *this;
  }
} sum[N];
int a[N];
Cons operator+(const Cons &a, const Cons &b) {
  return Cons(1ll * a.x * b.x % MOD, (1ll * a.y * b.x + b.y) % MOD);
}
int Pow(int a, int x) {
  int s = 1;
  if (x < 0) x += MOD - 1;
  for (; x; x >>= 1, a = 1ll * a * a % MOD)
    if (x & 1) s = 1ll * s * a % MOD;
  return s;
}
int Num(char *l, char *r, int mod) {
  long long s = 0;
  for (; l != r; l++) s = (s * 10 + *l - '0') % mod;
  return s;
}
void init() {
  for (int i = 0; i <= N - 10; i++) ggggg[i] = '9';
  loooo[0] = '1';
  for (int i = 1; i <= N - 10; i++) loooo[i] = '0';
  sum[0] = Cons(1, 0);
  a[0] = 1;
  int A = 1, B = 9, c = 10;
  int dA = 1, dB = 9;
  for (int i = 1; i <= N - 10; i++) {
    int tc = Pow(c, (dB - dA + 1) % (MOD - 1));
    int dc = Pow(c - 1, MOD - 2);
    long long S = 1ll * (B + 1) * (tc - 1) % MOD * dc % MOD,
              S2 = (1ll * (B - A + 1) * tc % MOD * c % MOD -
                    1ll * (B - A + 2) * tc % MOD + 1) *
                   dc % MOD * dc % MOD;
    sum[i] = sum[i - 1] + Cons(tc, (S + MOD - S2) % MOD);
    a[i] = 1ll * a[i - 1] * tc % MOD;
    A = 10ll * A % MOD, B = (10ll * B + 9) % MOD, c = 10ll * c % MOD;
    dA = 10ll * dA % (MOD - 1), dB = (10ll * dB + 9) % (MOD - 1);
  }
}
Cons getCons(int l1, int l2) {
  long long d = 1ll * a[l2 - 1] * Pow(a[l1], MOD - 2) % MOD;
  return Cons(d, (sum[l2 - 1].y - sum[l1].y * d) % MOD);
}
namespace Proc {
Cons Number(char *l, char *r) {
  long long x = 1, y = 0;
  for (; l != r; l++) x = x * 10 % MOD, y = (y * 10 + *l - '0') % MOD;
  return Cons(x, y);
}
Cons Bracket(char *l, char *r, Cons ex) {
  if (ex.x == 0)
    return ex;
  else if (ex.x == 1)
    return Cons(ex.x, (1ll * Num(l, r, MOD) * ex.y) % MOD);
  else {
    int z = Num(l, r, MOD - 1);
    return Cons(Pow(ex.x, z), 1ll * ex.y * (Pow(ex.x, z) - 1) % MOD *
                                  Pow(ex.x - 1, MOD - 2) % MOD);
  }
}
Cons Hyphen(char *l, char *r, char *ll, char *rr) {
  if ((r - l) == (rr - ll)) {
    int A = Num(l, r, MOD), B = Num(ll, rr, MOD);
    int dA = Num(l, r, MOD - 1), dB = Num(ll, rr, MOD - 1);
    int c = Pow(10, r - l), tc = Pow(c, (dB - dA + 1) % (MOD - 1));
    int dc = Pow(c - 1, MOD - 2);
    long long S = 1ll * (B + 1) * (tc - 1) % MOD * dc % MOD,
              S2 = (1ll * (B - A + 1) * tc % MOD * c % MOD -
                    1ll * (B - A + 2) * tc % MOD + 1) *
                   dc % MOD * dc % MOD;
    return Cons(tc, (S + MOD - S2) % MOD);
  } else {
    return Hyphen(l, r, ggggg, ggggg + (r - l)) + getCons(r - l, rr - ll) +
           Hyphen(loooo, loooo + (rr - ll), ll, rr);
  }
}
};  // namespace Proc
namespace Parser {
Cons term(char *&);
Cons expr(char *&cp) {
  Cons cc(1, 0);
  while (1) {
    cc += term(cp);
    if (!*cp || *cp == ')') break;
    cp++;
  }
  return cc;
}
Cons term(char *&cp) {
  char *p = cp, *q, *cq;
  for (; isdigit(*cp); cp++)
    ;
  if (*cp == '(') {
    q = cp++;
    Cons t = expr(cp);
    cp++;
    return Proc::Bracket(p, q, t);
  } else if (*cp == '-') {
    q = cp++;
    cq = cp;
    for (; isdigit(*cp); cp++)
      ;
    return Proc::Hyphen(p, q, cq, cp);
  } else
    return Proc::Number(p, cp);
}
};  // namespace Parser
int main() {
  scanf("%s", op);
  init();
  char *p = op;
  printf("%d\n", (Parser::expr(p).y + MOD) % MOD);
  return 0;
}

### Prompt

Please create a solution in Cpp 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 = 100010;
const int MOD = 1000000007;
char op[N];
char ggggg[N], loooo[N];
struct Cons {
  int x, y;
  Cons() {}
  Cons(int _x, int _y) : x(_x), y(_y) {}
  Cons &operator+=(const Cons &b) {
    y = (1ll * y * b.x + b.y) % MOD;
    x = (1ll * x * b.x) % MOD;
    return *this;
  }
} sum[N];
int a[N];
Cons operator+(const Cons &a, const Cons &b) {
  return Cons(1ll * a.x * b.x % MOD, (1ll * a.y * b.x + b.y) % MOD);
}
int Pow(int a, int x) {
  int s = 1;
  if (x < 0) x += MOD - 1;
  for (; x; x >>= 1, a = 1ll * a * a % MOD)
    if (x & 1) s = 1ll * s * a % MOD;
  return s;
}
int Num(char *l, char *r, int mod) {
  long long s = 0;
  for (; l != r; l++) s = (s * 10 + *l - '0') % mod;
  return s;
}
void init() {
  for (int i = 0; i <= N - 10; i++) ggggg[i] = '9';
  loooo[0] = '1';
  for (int i = 1; i <= N - 10; i++) loooo[i] = '0';
  sum[0] = Cons(1, 0);
  a[0] = 1;
  int A = 1, B = 9, c = 10;
  int dA = 1, dB = 9;
  for (int i = 1; i <= N - 10; i++) {
    int tc = Pow(c, (dB - dA + 1) % (MOD - 1));
    int dc = Pow(c - 1, MOD - 2);
    long long S = 1ll * (B + 1) * (tc - 1) % MOD * dc % MOD,
              S2 = (1ll * (B - A + 1) * tc % MOD * c % MOD -
                    1ll * (B - A + 2) * tc % MOD + 1) *
                   dc % MOD * dc % MOD;
    sum[i] = sum[i - 1] + Cons(tc, (S + MOD - S2) % MOD);
    a[i] = 1ll * a[i - 1] * tc % MOD;
    A = 10ll * A % MOD, B = (10ll * B + 9) % MOD, c = 10ll * c % MOD;
    dA = 10ll * dA % (MOD - 1), dB = (10ll * dB + 9) % (MOD - 1);
  }
}
Cons getCons(int l1, int l2) {
  long long d = 1ll * a[l2 - 1] * Pow(a[l1], MOD - 2) % MOD;
  return Cons(d, (sum[l2 - 1].y - sum[l1].y * d) % MOD);
}
namespace Proc {
Cons Number(char *l, char *r) {
  long long x = 1, y = 0;
  for (; l != r; l++) x = x * 10 % MOD, y = (y * 10 + *l - '0') % MOD;
  return Cons(x, y);
}
Cons Bracket(char *l, char *r, Cons ex) {
  if (ex.x == 0)
    return ex;
  else if (ex.x == 1)
    return Cons(ex.x, (1ll * Num(l, r, MOD) * ex.y) % MOD);
  else {
    int z = Num(l, r, MOD - 1);
    return Cons(Pow(ex.x, z), 1ll * ex.y * (Pow(ex.x, z) - 1) % MOD *
                                  Pow(ex.x - 1, MOD - 2) % MOD);
  }
}
Cons Hyphen(char *l, char *r, char *ll, char *rr) {
  if ((r - l) == (rr - ll)) {
    int A = Num(l, r, MOD), B = Num(ll, rr, MOD);
    int dA = Num(l, r, MOD - 1), dB = Num(ll, rr, MOD - 1);
    int c = Pow(10, r - l), tc = Pow(c, (dB - dA + 1) % (MOD - 1));
    int dc = Pow(c - 1, MOD - 2);
    long long S = 1ll * (B + 1) * (tc - 1) % MOD * dc % MOD,
              S2 = (1ll * (B - A + 1) * tc % MOD * c % MOD -
                    1ll * (B - A + 2) * tc % MOD + 1) *
                   dc % MOD * dc % MOD;
    return Cons(tc, (S + MOD - S2) % MOD);
  } else {
    return Hyphen(l, r, ggggg, ggggg + (r - l)) + getCons(r - l, rr - ll) +
           Hyphen(loooo, loooo + (rr - ll), ll, rr);
  }
}
};  // namespace Proc
namespace Parser {
Cons term(char *&);
Cons expr(char *&cp) {
  Cons cc(1, 0);
  while (1) {
    cc += term(cp);
    if (!*cp || *cp == ')') break;
    cp++;
  }
  return cc;
}
Cons term(char *&cp) {
  char *p = cp, *q, *cq;
  for (; isdigit(*cp); cp++)
    ;
  if (*cp == '(') {
    q = cp++;
    Cons t = expr(cp);
    cp++;
    return Proc::Bracket(p, q, t);
  } else if (*cp == '-') {
    q = cp++;
    cq = cp;
    for (; isdigit(*cp); cp++)
      ;
    return Proc::Hyphen(p, q, cq, cp);
  } else
    return Proc::Number(p, cp);
}
};  // namespace Parser
int main() {
  scanf("%s", op);
  init();
  char *p = op;
  printf("%d\n", (Parser::expr(p).y + MOD) % MOD);
  return 0;
}

```