#include <bits/stdc++.h>
const int maxn = 100001, mod = 1000000007;
int mod_inv(int x) {
  return x <= 1 ? x : (int)(mod - mod / x * (long long)mod_inv(mod % x) % mod);
}
int mod_pow(int x, int k) {
  int ret = 1;
  for (; k > 0; k >>= 1, x = (long long)x * x % mod)
    if (k & 1) ret = (long long)ret * x % mod;
  return ret;
}
std::pair<int, int> merge(std::pair<int, int> a, std::pair<int, int> b) {
  return (std::pair<int, int>){
      (int)(((long long)a.first * b.second + b.first) % mod),
      (int)(((long long)a.second * b.second) % mod)};
}
std::pair<int, int> pow(std::pair<int, int> x, int k) {
  std::pair<int, int> ret = (std::pair<int, int>){0, 1},
                      tmp = (std::pair<int, int>){1, x.second};
  for (; k > 0; k >>= 1, tmp = merge(tmp, tmp))
    if (k & 1) ret = merge(ret, tmp);
  return (std::pair<int, int>){(int)((long long)x.first * ret.first % mod),
                               ret.second};
}
std::pair<int, int> gen(int L, int R, int L1, int R1, int pw) {
  if (pw == 1)
    return (std::pair<int, int>){(int)((((L + R - 1LL) * (R - L)) >> 1) % mod),
                                 1};
  int ivs = mod_inv(pw - 1),
      ppw = mod_pow(pw, L1 < R1 ? R1 - L1 : R1 - L1 + mod - 1);
  int ret = ((long long)L * ppw - R + (ppw - 1LL) * ivs) % mod * ivs % mod;
  if (ret < 0) ret += mod;
  return (std::pair<int, int>){ret, ppw};
}
struct Number {
  int val, val1, pw;
} num;
int typ;
char str[maxn], *ptr = str;
void nxtSym() {
  switch (*ptr) {
    case '\0':
      typ = 0;
      break;
    case '+':
      typ = 1;
      ++ptr;
      break;
    case '-':
      typ = 2;
      ++ptr;
      break;
    case '(':
      typ = 3;
      ++ptr;
      break;
    case ')':
      typ = 4;
      ++ptr;
      break;
    default:
      typ = 5;
      num.val = num.val1 = 0;
      num.pw = 1;
      for (; *ptr >= '0' && *ptr <= '9'; ++ptr) {
        num.val = (10LL * num.val + (*ptr - '0')) % mod;
        num.val1 = (10LL * num.val1 + (*ptr - '0')) % (mod - 1);
        num.pw = 10LL * num.pw % mod;
      }
  }
}
std::pair<int, int> expression();
std::pair<int, int> term() {
  assert(typ == 5);
  Number cur = num;
  nxtSym();
  if (typ == 2) {
    nxtSym();
    assert(typ == 5);
    Number nxt = num;
    nxtSym();
    if (cur.pw == nxt.pw) {
      if ((++nxt.val) >= mod) nxt.val -= mod;
      if ((++nxt.val1) >= mod - 1) nxt.val1 -= mod - 1;
      return gen(cur.val, nxt.val, cur.val1, nxt.val1, cur.pw);
    }
    int dig = 1, dig1 = 1;
    while (dig != cur.pw) {
      dig = 10LL * dig % mod;
      dig1 = 10LL * dig1 % (mod - 1);
    }
    std::pair<int, int> ret = gen(cur.val, dig, cur.val1, dig1, cur.pw);
    while (dig != nxt.pw) {
      int nxtdig = 10LL * dig % mod, nxtdig1 = 10LL * dig1 % (mod - 1);
      if (nxtdig == nxt.pw) {
        if ((++nxt.val) >= mod) nxt.val -= mod;
        if ((++nxt.val1) >= mod - 1) nxt.val1 -= mod - 1;
        ret = merge(ret, gen(dig, nxt.val, dig1, nxt.val1, nxtdig));
      } else
        ret = merge(ret, gen(dig, nxtdig, dig1, nxtdig1, nxtdig));
      dig = nxtdig;
      dig1 = nxtdig1;
    }
    return ret;
  }
  if (typ == 3) {
    nxtSym();
    std::pair<int, int> ret = expression();
    assert(typ == 4);
    nxtSym();
    return pow(ret, cur.val1);
  }
  return (std::pair<int, int>){cur.val, cur.pw};
}
std::pair<int, int> expression() {
  std::pair<int, int> ret = term();
  while (typ == 1) {
    nxtSym();
    ret = merge(ret, term());
  }
  return ret;
}
int main() {
  scanf("%s", str);
  nxtSym();
  std::pair<int, int> ret = expression();
  printf("%d\n", ret.first);
  return 0;
}

### Prompt

Generate 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>
const int maxn = 100001, mod = 1000000007;
int mod_inv(int x) {
  return x <= 1 ? x : (int)(mod - mod / x * (long long)mod_inv(mod % x) % mod);
}
int mod_pow(int x, int k) {
  int ret = 1;
  for (; k > 0; k >>= 1, x = (long long)x * x % mod)
    if (k & 1) ret = (long long)ret * x % mod;
  return ret;
}
std::pair<int, int> merge(std::pair<int, int> a, std::pair<int, int> b) {
  return (std::pair<int, int>){
      (int)(((long long)a.first * b.second + b.first) % mod),
      (int)(((long long)a.second * b.second) % mod)};
}
std::pair<int, int> pow(std::pair<int, int> x, int k) {
  std::pair<int, int> ret = (std::pair<int, int>){0, 1},
                      tmp = (std::pair<int, int>){1, x.second};
  for (; k > 0; k >>= 1, tmp = merge(tmp, tmp))
    if (k & 1) ret = merge(ret, tmp);
  return (std::pair<int, int>){(int)((long long)x.first * ret.first % mod),
                               ret.second};
}
std::pair<int, int> gen(int L, int R, int L1, int R1, int pw) {
  if (pw == 1)
    return (std::pair<int, int>){(int)((((L + R - 1LL) * (R - L)) >> 1) % mod),
                                 1};
  int ivs = mod_inv(pw - 1),
      ppw = mod_pow(pw, L1 < R1 ? R1 - L1 : R1 - L1 + mod - 1);
  int ret = ((long long)L * ppw - R + (ppw - 1LL) * ivs) % mod * ivs % mod;
  if (ret < 0) ret += mod;
  return (std::pair<int, int>){ret, ppw};
}
struct Number {
  int val, val1, pw;
} num;
int typ;
char str[maxn], *ptr = str;
void nxtSym() {
  switch (*ptr) {
    case '\0':
      typ = 0;
      break;
    case '+':
      typ = 1;
      ++ptr;
      break;
    case '-':
      typ = 2;
      ++ptr;
      break;
    case '(':
      typ = 3;
      ++ptr;
      break;
    case ')':
      typ = 4;
      ++ptr;
      break;
    default:
      typ = 5;
      num.val = num.val1 = 0;
      num.pw = 1;
      for (; *ptr >= '0' && *ptr <= '9'; ++ptr) {
        num.val = (10LL * num.val + (*ptr - '0')) % mod;
        num.val1 = (10LL * num.val1 + (*ptr - '0')) % (mod - 1);
        num.pw = 10LL * num.pw % mod;
      }
  }
}
std::pair<int, int> expression();
std::pair<int, int> term() {
  assert(typ == 5);
  Number cur = num;
  nxtSym();
  if (typ == 2) {
    nxtSym();
    assert(typ == 5);
    Number nxt = num;
    nxtSym();
    if (cur.pw == nxt.pw) {
      if ((++nxt.val) >= mod) nxt.val -= mod;
      if ((++nxt.val1) >= mod - 1) nxt.val1 -= mod - 1;
      return gen(cur.val, nxt.val, cur.val1, nxt.val1, cur.pw);
    }
    int dig = 1, dig1 = 1;
    while (dig != cur.pw) {
      dig = 10LL * dig % mod;
      dig1 = 10LL * dig1 % (mod - 1);
    }
    std::pair<int, int> ret = gen(cur.val, dig, cur.val1, dig1, cur.pw);
    while (dig != nxt.pw) {
      int nxtdig = 10LL * dig % mod, nxtdig1 = 10LL * dig1 % (mod - 1);
      if (nxtdig == nxt.pw) {
        if ((++nxt.val) >= mod) nxt.val -= mod;
        if ((++nxt.val1) >= mod - 1) nxt.val1 -= mod - 1;
        ret = merge(ret, gen(dig, nxt.val, dig1, nxt.val1, nxtdig));
      } else
        ret = merge(ret, gen(dig, nxtdig, dig1, nxtdig1, nxtdig));
      dig = nxtdig;
      dig1 = nxtdig1;
    }
    return ret;
  }
  if (typ == 3) {
    nxtSym();
    std::pair<int, int> ret = expression();
    assert(typ == 4);
    nxtSym();
    return pow(ret, cur.val1);
  }
  return (std::pair<int, int>){cur.val, cur.pw};
}
std::pair<int, int> expression() {
  std::pair<int, int> ret = term();
  while (typ == 1) {
    nxtSym();
    ret = merge(ret, term());
  }
  return ret;
}
int main() {
  scanf("%s", str);
  nxtSym();
  std::pair<int, int> ret = expression();
  printf("%d\n", ret.first);
  return 0;
}

```