#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
int pw(int x, int n, int mod) {
  int ret = 1;
  while (true) {
    if (n & 1) ret = (long long)ret * x % mod;
    if ((n >>= 1) == 0) return ret;
    x = (long long)x * x % mod;
  }
}
int inv(int x, int mod) {
  int phi = mod == 1000000007 ? mod - 1 : mod == 1000000006 ? 500000002 : -1;
  assert(phi != -1 && x >= 1 && gcd(x, mod) == 1);
  int ret = pw(x, phi - 1, mod);
  assert((long long)ret * x % mod == 1);
  return ret;
}
int F(int a, int b, int bb, int r, int mod) {
  if (r == 1) return ((long long)b + mod - a + 1) % mod;
  return (long long)(pw(r, bb + 1, mod) - pw(r, a, mod) + mod) *
         inv(r - 1, mod) % mod;
}
int G(int a, int b, int bb, int r, int mod) {
  return (((long long)b * pw(r, bb + 1, mod) - (long long)a * pw(r, a, mod) -
           F(a + 1, b, bb, r, mod)) %
              mod +
          mod) %
         mod * inv(r - 1, mod) % mod;
}
int sval(char *s, int slen, int mod) {
  int ret = 0;
  for (int i = (0); i < (slen); ++i)
    ret = ((long long)10 * ret + s[i] - '0') % mod;
  return ret;
}
const int MAXLEN = 1000000;
const int MOD = 1000000007;
int calc(char *s, int slen) {
  int ret = 0;
  int s0 = sval(s, slen, MOD), s1 = sval(s, slen, MOD - 1);
  for (int len = (1); len <= (slen); ++len) {
    int o1, o2, e1 = 0, e2 = 0, t, a, b, bb, r = pw(10, len, MOD);
    if (len != slen) {
      e1 =
          ((long long)s1 + MOD - 1 - pw(10, slen - 1, MOD - 1) + 1) % (MOD - 1);
      e2 = len == slen - 1
               ? 0
               : ((long long)9 * G(len, slen - 2, slen - 2, 10, MOD - 1) +
                  (long long)9 * F(len, slen - 2, slen - 2, 10, MOD - 1)) %
                     (MOD - 1);
      o1 = pw(10, (long long)e1 * slen % (MOD - 1), MOD);
      o2 = pw(10, e2, MOD);
      t = r - 1;
      if (t < 0) t += MOD;
      a = 0;
      b = (long long)9 * pw(10, len - 1, MOD) % MOD - 1;
      if (b < 0) b += MOD;
      bb = (long long)9 * pw(10, len - 1, MOD - 1) % (MOD - 1) - 1;
      if (bb < 0) bb += MOD;
    } else {
      o1 = o2 = 1;
      t = s0;
      a = 0;
      b = s0 - pw(10, len - 1, MOD);
      if (b < 0) b += MOD;
      bb = s1 - pw(10, len - 1, MOD - 1);
      if (bb < 0) bb += MOD - 1;
    }
    int z =
        ((long long)t * F(a, b, bb, r, MOD) - G(a, b, bb, r, MOD) + MOD) % MOD;
    int cur = (long long)o1 * o2 % MOD * z % MOD;
    ret += cur;
    if (ret >= MOD) ret -= MOD;
  }
  return ret;
}
int calclen(char *s, int slen) {
  int ret = 0;
  int s1 = sval(s, slen, MOD - 1);
  for (int len = (1); len <= (slen); ++len) {
    int cnt;
    if (len != slen) {
      cnt = (long long)9 * pw(10, len - 1, MOD - 1) % (MOD - 1);
    } else {
      cnt = (s1 + MOD - 1 - pw(10, len - 1, MOD - 1) + 1) % (MOD - 1);
    }
    int cur = (long long)cnt * len % (MOD - 1);
    ret += cur;
    if (ret >= MOD - 1) ret -= MOD - 1;
  }
  return ret;
}
void dec(char *s, int &slen) {
  for (int i = slen - 1; i >= 0; --i)
    if (s[i] != '0') {
      --s[i];
      break;
    } else
      s[i] = '9';
  if (s[0] == '0') {
    for (int i = (0); i < (slen); ++i) s[i] = s[i + 1];
    --slen;
  }
}
typedef struct R {
  int len, val;
} R;
char *nrstart[MAXLEN], *nrend[MAXLEN];
int nnr;
int termtype[MAXLEN], terma[MAXLEN], termb[MAXLEN], nterm;
vector<int> expr[MAXLEN];
int nexpr;
int parsenumber(char *&s) {
  assert(isdigit(*s));
  int ret = nnr++;
  nrstart[ret] = s;
  while (isdigit(*s)) ++s;
  nrend[ret] = s;
  return ret;
}
int parseexpr(char *&s);
int parseterm(char *&s) {
  int ret = nterm++;
  terma[ret] = parsenumber(s);
  if (*s == '-') {
    ++s;
    termtype[ret] = 1;
    termb[ret] = parsenumber(s);
  } else if (*s == '(') {
    ++s;
    termtype[ret] = 2;
    termb[ret] = parseexpr(s);
    assert(*s == ')');
    ++s;
  } else
    termtype[ret] = 0;
  return ret;
}
int parseexpr(char *&s) {
  int ret = nexpr++;
  expr[ret].push_back(parseterm(s));
  while (*s == '+') {
    ++s;
    expr[ret].push_back(parseterm(s));
  }
  return ret;
}
int parse(char *ss, int slen) {
  nexpr = nterm = nnr = 0;
  char *s = ss;
  int expr = parseexpr(s);
  assert(s == ss + slen);
  return expr;
}
void printexpr(int e);
void printnumber(int x) {
  for (char *c = nrstart[x]; c != nrend[x]; ++c) printf("%c", *c);
}
void printterm(int t) {
  printnumber(terma[t]);
  if (termtype[t] == 1) {
    printf("-");
    printnumber(termb[t]);
  }
  if (termtype[t] == 2) {
    printf("(");
    printexpr(termb[t]);
    printf(")");
  }
}
void printexpr(int e) {
  for (int i = (0); i < (((int)(expr[e]).size())); ++i) {
    if (i != 0) printf("+");
    printterm(expr[e][i]);
  }
}
R concat(const R &a, const R &b) {
  R ret;
  ret.len = a.len + b.len;
  if (ret.len >= MOD - 1) ret.len -= MOD - 1;
  ret.val = ((long long)a.val * pw(10, b.len, MOD) + b.val) % MOD;
  return ret;
}
R repeat(const R &b, char *s, int slen) {
  int s0 = sval(s, slen, MOD), s1 = sval(s, slen, MOD - 1);
  R ret;
  ret.len = (long long)b.len * s1 % (MOD - 1);
  ret.val = (long long)b.val *
            F(0, s0 == 0 ? MOD - 1 : s0 - 1, s1 == 0 ? MOD - 2 : s1 - 1,
              pw(10, b.len, MOD), MOD) %
            MOD;
  return ret;
}
R calcnumber(int x) {
  R ret;
  ret.len = 0, ret.val = 0;
  for (char *c = nrstart[x]; c != nrend[x]; ++c)
    ++ret.len, ret.val = ((long long)10 * ret.val + *c - '0') % MOD;
  return ret;
}
R calcexpr(int e);
R calcterm(int t) {
  if (termtype[t] == 0) {
    return calcnumber(terma[t]);
  }
  if (termtype[t] == 1) {
    char *a = nrstart[terma[t]];
    int alen = nrend[terma[t]] - nrstart[terma[t]];
    char *b = nrstart[termb[t]];
    int blen = nrend[termb[t]] - nrstart[termb[t]];
    dec(a, alen);
    int A = calclen(a, alen), B = calclen(b, blen), D = B - A;
    if (D < 0) D += MOD - 1;
    int val = calc(b, blen) - (long long)pw(10, D, MOD) * calc(a, alen) % MOD;
    if (val < 0) val += MOD;
    R ret;
    ret.len = D, ret.val = val;
    return ret;
  }
  if (termtype[t] == 2) {
    R x = calcexpr(termb[t]);
    char *a = nrstart[terma[t]];
    int alen = nrend[terma[t]] - nrstart[terma[t]];
    return repeat(x, a, alen);
  }
}
R calcexpr(int e) {
  R ret;
  ret.len = 0, ret.val = 0;
  for (int i = (0); i < (((int)(expr[e]).size())); ++i) {
    R cur = calcterm(expr[e][i]);
    ret = concat(ret, cur);
  }
  return ret;
}
char s[MAXLEN + 1];
int slen;
void run() {
  scanf("%s", s);
  slen = strlen(s);
  int rt = parse(s, slen);
  R res = calcexpr(rt);
  printf("%d\n", res.val);
}
int main() {
  run();
  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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
int pw(int x, int n, int mod) {
  int ret = 1;
  while (true) {
    if (n & 1) ret = (long long)ret * x % mod;
    if ((n >>= 1) == 0) return ret;
    x = (long long)x * x % mod;
  }
}
int inv(int x, int mod) {
  int phi = mod == 1000000007 ? mod - 1 : mod == 1000000006 ? 500000002 : -1;
  assert(phi != -1 && x >= 1 && gcd(x, mod) == 1);
  int ret = pw(x, phi - 1, mod);
  assert((long long)ret * x % mod == 1);
  return ret;
}
int F(int a, int b, int bb, int r, int mod) {
  if (r == 1) return ((long long)b + mod - a + 1) % mod;
  return (long long)(pw(r, bb + 1, mod) - pw(r, a, mod) + mod) *
         inv(r - 1, mod) % mod;
}
int G(int a, int b, int bb, int r, int mod) {
  return (((long long)b * pw(r, bb + 1, mod) - (long long)a * pw(r, a, mod) -
           F(a + 1, b, bb, r, mod)) %
              mod +
          mod) %
         mod * inv(r - 1, mod) % mod;
}
int sval(char *s, int slen, int mod) {
  int ret = 0;
  for (int i = (0); i < (slen); ++i)
    ret = ((long long)10 * ret + s[i] - '0') % mod;
  return ret;
}
const int MAXLEN = 1000000;
const int MOD = 1000000007;
int calc(char *s, int slen) {
  int ret = 0;
  int s0 = sval(s, slen, MOD), s1 = sval(s, slen, MOD - 1);
  for (int len = (1); len <= (slen); ++len) {
    int o1, o2, e1 = 0, e2 = 0, t, a, b, bb, r = pw(10, len, MOD);
    if (len != slen) {
      e1 =
          ((long long)s1 + MOD - 1 - pw(10, slen - 1, MOD - 1) + 1) % (MOD - 1);
      e2 = len == slen - 1
               ? 0
               : ((long long)9 * G(len, slen - 2, slen - 2, 10, MOD - 1) +
                  (long long)9 * F(len, slen - 2, slen - 2, 10, MOD - 1)) %
                     (MOD - 1);
      o1 = pw(10, (long long)e1 * slen % (MOD - 1), MOD);
      o2 = pw(10, e2, MOD);
      t = r - 1;
      if (t < 0) t += MOD;
      a = 0;
      b = (long long)9 * pw(10, len - 1, MOD) % MOD - 1;
      if (b < 0) b += MOD;
      bb = (long long)9 * pw(10, len - 1, MOD - 1) % (MOD - 1) - 1;
      if (bb < 0) bb += MOD;
    } else {
      o1 = o2 = 1;
      t = s0;
      a = 0;
      b = s0 - pw(10, len - 1, MOD);
      if (b < 0) b += MOD;
      bb = s1 - pw(10, len - 1, MOD - 1);
      if (bb < 0) bb += MOD - 1;
    }
    int z =
        ((long long)t * F(a, b, bb, r, MOD) - G(a, b, bb, r, MOD) + MOD) % MOD;
    int cur = (long long)o1 * o2 % MOD * z % MOD;
    ret += cur;
    if (ret >= MOD) ret -= MOD;
  }
  return ret;
}
int calclen(char *s, int slen) {
  int ret = 0;
  int s1 = sval(s, slen, MOD - 1);
  for (int len = (1); len <= (slen); ++len) {
    int cnt;
    if (len != slen) {
      cnt = (long long)9 * pw(10, len - 1, MOD - 1) % (MOD - 1);
    } else {
      cnt = (s1 + MOD - 1 - pw(10, len - 1, MOD - 1) + 1) % (MOD - 1);
    }
    int cur = (long long)cnt * len % (MOD - 1);
    ret += cur;
    if (ret >= MOD - 1) ret -= MOD - 1;
  }
  return ret;
}
void dec(char *s, int &slen) {
  for (int i = slen - 1; i >= 0; --i)
    if (s[i] != '0') {
      --s[i];
      break;
    } else
      s[i] = '9';
  if (s[0] == '0') {
    for (int i = (0); i < (slen); ++i) s[i] = s[i + 1];
    --slen;
  }
}
typedef struct R {
  int len, val;
} R;
char *nrstart[MAXLEN], *nrend[MAXLEN];
int nnr;
int termtype[MAXLEN], terma[MAXLEN], termb[MAXLEN], nterm;
vector<int> expr[MAXLEN];
int nexpr;
int parsenumber(char *&s) {
  assert(isdigit(*s));
  int ret = nnr++;
  nrstart[ret] = s;
  while (isdigit(*s)) ++s;
  nrend[ret] = s;
  return ret;
}
int parseexpr(char *&s);
int parseterm(char *&s) {
  int ret = nterm++;
  terma[ret] = parsenumber(s);
  if (*s == '-') {
    ++s;
    termtype[ret] = 1;
    termb[ret] = parsenumber(s);
  } else if (*s == '(') {
    ++s;
    termtype[ret] = 2;
    termb[ret] = parseexpr(s);
    assert(*s == ')');
    ++s;
  } else
    termtype[ret] = 0;
  return ret;
}
int parseexpr(char *&s) {
  int ret = nexpr++;
  expr[ret].push_back(parseterm(s));
  while (*s == '+') {
    ++s;
    expr[ret].push_back(parseterm(s));
  }
  return ret;
}
int parse(char *ss, int slen) {
  nexpr = nterm = nnr = 0;
  char *s = ss;
  int expr = parseexpr(s);
  assert(s == ss + slen);
  return expr;
}
void printexpr(int e);
void printnumber(int x) {
  for (char *c = nrstart[x]; c != nrend[x]; ++c) printf("%c", *c);
}
void printterm(int t) {
  printnumber(terma[t]);
  if (termtype[t] == 1) {
    printf("-");
    printnumber(termb[t]);
  }
  if (termtype[t] == 2) {
    printf("(");
    printexpr(termb[t]);
    printf(")");
  }
}
void printexpr(int e) {
  for (int i = (0); i < (((int)(expr[e]).size())); ++i) {
    if (i != 0) printf("+");
    printterm(expr[e][i]);
  }
}
R concat(const R &a, const R &b) {
  R ret;
  ret.len = a.len + b.len;
  if (ret.len >= MOD - 1) ret.len -= MOD - 1;
  ret.val = ((long long)a.val * pw(10, b.len, MOD) + b.val) % MOD;
  return ret;
}
R repeat(const R &b, char *s, int slen) {
  int s0 = sval(s, slen, MOD), s1 = sval(s, slen, MOD - 1);
  R ret;
  ret.len = (long long)b.len * s1 % (MOD - 1);
  ret.val = (long long)b.val *
            F(0, s0 == 0 ? MOD - 1 : s0 - 1, s1 == 0 ? MOD - 2 : s1 - 1,
              pw(10, b.len, MOD), MOD) %
            MOD;
  return ret;
}
R calcnumber(int x) {
  R ret;
  ret.len = 0, ret.val = 0;
  for (char *c = nrstart[x]; c != nrend[x]; ++c)
    ++ret.len, ret.val = ((long long)10 * ret.val + *c - '0') % MOD;
  return ret;
}
R calcexpr(int e);
R calcterm(int t) {
  if (termtype[t] == 0) {
    return calcnumber(terma[t]);
  }
  if (termtype[t] == 1) {
    char *a = nrstart[terma[t]];
    int alen = nrend[terma[t]] - nrstart[terma[t]];
    char *b = nrstart[termb[t]];
    int blen = nrend[termb[t]] - nrstart[termb[t]];
    dec(a, alen);
    int A = calclen(a, alen), B = calclen(b, blen), D = B - A;
    if (D < 0) D += MOD - 1;
    int val = calc(b, blen) - (long long)pw(10, D, MOD) * calc(a, alen) % MOD;
    if (val < 0) val += MOD;
    R ret;
    ret.len = D, ret.val = val;
    return ret;
  }
  if (termtype[t] == 2) {
    R x = calcexpr(termb[t]);
    char *a = nrstart[terma[t]];
    int alen = nrend[terma[t]] - nrstart[terma[t]];
    return repeat(x, a, alen);
  }
}
R calcexpr(int e) {
  R ret;
  ret.len = 0, ret.val = 0;
  for (int i = (0); i < (((int)(expr[e]).size())); ++i) {
    R cur = calcterm(expr[e][i]);
    ret = concat(ret, cur);
  }
  return ret;
}
char s[MAXLEN + 1];
int slen;
void run() {
  scanf("%s", s);
  slen = strlen(s);
  int rt = parse(s, slen);
  R res = calcexpr(rt);
  printf("%d\n", res.val);
}
int main() {
  run();
  return 0;
}

```