#include <bits/stdc++.h>
using namespace std;
int IN() {
  int x = 0, f = 0, ch;
  for (; (ch = getchar()) < '0' || ch > '9';) f = (ch == '-');
  for (; ch >= '0' && ch <= '9'; (ch = getchar())) x = x * 10 + ch - '0';
  return f ? -x : x;
}
int M, N, C, opt[200005], G[200005];
char s[200005];
int Pow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = 1ll * a * a % 1000000007)
    if (b & 1) ret = 1ll * ret * a % 1000000007;
  return ret;
}
struct Nod {
  int x, y, l, p;
  Nod operator+(const Nod& b) const {
    Nod c, a = *this;
    c.x = (1ll * a.x * b.p + b.x) % 1000000007;
    c.y = -1;
    c.l = -1;
    c.p = 1ll * a.p * b.p % 1000000007;
    return c;
  }
  Nod operator*(const Nod& b) const {
    Nod c, a = *this;
    if (b.p == 1)
      c.x = 1ll * a.x * b.x % 1000000007;
    else
      c.x = 1ll * (Pow(b.p, a.y) - 1) * Pow(b.p - 1, 1000000007 - 2) %
            1000000007 * b.x % 1000000007;
    c.y = -1;
    c.l = -1;
    c.p = Pow(b.p, a.y);
    return c;
  }
  Nod operator^(const Nod& b) const {
    Nod c, a = *this;
    int v = Pow(a.p, 1000000007 - 2);
    if (v == 1) {
      c.x = 1ll * (a.x + b.x) * (b.x - a.x + 1) / 2 % 1000000007;
    } else {
      c.x =
          (1ll * b.x * Pow(v, b.y + 1) - 1ll * a.x * Pow(v, a.y)) % 1000000007;
      c.x = (c.x - 1ll * (Pow(v, b.y + 1) - Pow(v, a.y + 1)) *
                       Pow(v - 1, 1000000007 - 2)) %
            1000000007;
      c.x = 1ll * c.x * Pow(v - 1, 1000000007 - 2) % 1000000007;
    }
    c.x = 1ll * c.x * Pow(Pow(v, b.y), 1000000007 - 2) % 1000000007;
    c.x = (c.x + 1000000007) % 1000000007;
    c.y = -1;
    c.l = -1;
    c.p = Pow(p, b.y - a.y + 1 + 1000000007 - 1);
    return c;
  }
} A[200005], L[200005], R[200005];
Nod Func(Nod a, Nod b) {
  if (a.l == b.l) return a ^ b;
  Nod c = a ^ R[a.l];
  for (int i = a.l + 1, lim = b.l - 1; i <= lim; i++) c = c + (L[i] ^ R[i]);
  c = c + (L[b.l] ^ b);
  return c;
}
Nod Add(Nod a, int v) {
  Nod c;
  c.x = (a.x * 10ll + v) % 1000000007;
  c.y = (a.y * 10ll + v) % (1000000007 - 1);
  c.l = a.l + 1;
  c.p = 10ll * a.p % 1000000007;
  return c;
}
Nod Get(int l, int r) {
  Nod c = (Nod){0, 0, 0, 1};
  for (int i = l, lim = r; i <= lim; i++) c = Add(c, s[i] - '0');
  return c;
}
int main(int argc, char* argv[]) {
  scanf("%s", s + 1);
  M = strlen(s + 1);
  L[1] = (Nod){1, 1, 1, 10};
  R[1] = (Nod){9, 9, 1, 10};
  for (int i = 2, lim = M; i <= lim; i++) {
    L[i] = Add(L[i - 1], 0);
    R[i] = Add(R[i - 1], 9);
  }
  for (int i = 1, lim = M; i <= lim; i++) {
    if (s[i] == '(')
      opt[++N] = -1;
    else if (s[i] == ')')
      opt[++N] = -2;
    else if (s[i] == '+')
      opt[++N] = -3;
    else {
      int j = i;
      for (; j <= M && '0' <= s[j] && s[j] <= '9'; j++)
        ;
      if (j > M || s[j] != '-')
        A[++C] = Get(i, j - 1), i = j - 1;
      else {
        int k = j + 1;
        for (; k <= M && '0' <= s[k] && s[k] <= '9'; k++)
          ;
        A[++C] = Func(Get(i, j - 1), Get(j + 1, k - 1));
        i = k - 1;
      }
      opt[++N] = C;
    }
  }
  M = 0;
  for (int i = 1, lim = N; i <= lim; i++) {
    if (opt[i] == -1 || opt[i] == -3 || opt[i] == -4)
      G[++M] = opt[i];
    else if (opt[i] == -2) {
      A[++C] = A[G[M--]];
      for (; G[M] != -1;) {
        M--;
        A[C] = A[G[M--]] + A[C];
      }
      A[C] = A[G[M - 1]] * A[C];
      M -= 2;
      G[++M] = C;
    } else
      G[++M] = opt[i];
  }
  Nod Ans = A[G[1]];
  for (int i = 2, lim = M; i <= lim; i++) i++, Ans = Ans + A[G[i]];
  printf("%d\n", Ans.x);
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
int IN() {
  int x = 0, f = 0, ch;
  for (; (ch = getchar()) < '0' || ch > '9';) f = (ch == '-');
  for (; ch >= '0' && ch <= '9'; (ch = getchar())) x = x * 10 + ch - '0';
  return f ? -x : x;
}
int M, N, C, opt[200005], G[200005];
char s[200005];
int Pow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = 1ll * a * a % 1000000007)
    if (b & 1) ret = 1ll * ret * a % 1000000007;
  return ret;
}
struct Nod {
  int x, y, l, p;
  Nod operator+(const Nod& b) const {
    Nod c, a = *this;
    c.x = (1ll * a.x * b.p + b.x) % 1000000007;
    c.y = -1;
    c.l = -1;
    c.p = 1ll * a.p * b.p % 1000000007;
    return c;
  }
  Nod operator*(const Nod& b) const {
    Nod c, a = *this;
    if (b.p == 1)
      c.x = 1ll * a.x * b.x % 1000000007;
    else
      c.x = 1ll * (Pow(b.p, a.y) - 1) * Pow(b.p - 1, 1000000007 - 2) %
            1000000007 * b.x % 1000000007;
    c.y = -1;
    c.l = -1;
    c.p = Pow(b.p, a.y);
    return c;
  }
  Nod operator^(const Nod& b) const {
    Nod c, a = *this;
    int v = Pow(a.p, 1000000007 - 2);
    if (v == 1) {
      c.x = 1ll * (a.x + b.x) * (b.x - a.x + 1) / 2 % 1000000007;
    } else {
      c.x =
          (1ll * b.x * Pow(v, b.y + 1) - 1ll * a.x * Pow(v, a.y)) % 1000000007;
      c.x = (c.x - 1ll * (Pow(v, b.y + 1) - Pow(v, a.y + 1)) *
                       Pow(v - 1, 1000000007 - 2)) %
            1000000007;
      c.x = 1ll * c.x * Pow(v - 1, 1000000007 - 2) % 1000000007;
    }
    c.x = 1ll * c.x * Pow(Pow(v, b.y), 1000000007 - 2) % 1000000007;
    c.x = (c.x + 1000000007) % 1000000007;
    c.y = -1;
    c.l = -1;
    c.p = Pow(p, b.y - a.y + 1 + 1000000007 - 1);
    return c;
  }
} A[200005], L[200005], R[200005];
Nod Func(Nod a, Nod b) {
  if (a.l == b.l) return a ^ b;
  Nod c = a ^ R[a.l];
  for (int i = a.l + 1, lim = b.l - 1; i <= lim; i++) c = c + (L[i] ^ R[i]);
  c = c + (L[b.l] ^ b);
  return c;
}
Nod Add(Nod a, int v) {
  Nod c;
  c.x = (a.x * 10ll + v) % 1000000007;
  c.y = (a.y * 10ll + v) % (1000000007 - 1);
  c.l = a.l + 1;
  c.p = 10ll * a.p % 1000000007;
  return c;
}
Nod Get(int l, int r) {
  Nod c = (Nod){0, 0, 0, 1};
  for (int i = l, lim = r; i <= lim; i++) c = Add(c, s[i] - '0');
  return c;
}
int main(int argc, char* argv[]) {
  scanf("%s", s + 1);
  M = strlen(s + 1);
  L[1] = (Nod){1, 1, 1, 10};
  R[1] = (Nod){9, 9, 1, 10};
  for (int i = 2, lim = M; i <= lim; i++) {
    L[i] = Add(L[i - 1], 0);
    R[i] = Add(R[i - 1], 9);
  }
  for (int i = 1, lim = M; i <= lim; i++) {
    if (s[i] == '(')
      opt[++N] = -1;
    else if (s[i] == ')')
      opt[++N] = -2;
    else if (s[i] == '+')
      opt[++N] = -3;
    else {
      int j = i;
      for (; j <= M && '0' <= s[j] && s[j] <= '9'; j++)
        ;
      if (j > M || s[j] != '-')
        A[++C] = Get(i, j - 1), i = j - 1;
      else {
        int k = j + 1;
        for (; k <= M && '0' <= s[k] && s[k] <= '9'; k++)
          ;
        A[++C] = Func(Get(i, j - 1), Get(j + 1, k - 1));
        i = k - 1;
      }
      opt[++N] = C;
    }
  }
  M = 0;
  for (int i = 1, lim = N; i <= lim; i++) {
    if (opt[i] == -1 || opt[i] == -3 || opt[i] == -4)
      G[++M] = opt[i];
    else if (opt[i] == -2) {
      A[++C] = A[G[M--]];
      for (; G[M] != -1;) {
        M--;
        A[C] = A[G[M--]] + A[C];
      }
      A[C] = A[G[M - 1]] * A[C];
      M -= 2;
      G[++M] = C;
    } else
      G[++M] = opt[i];
  }
  Nod Ans = A[G[1]];
  for (int i = 2, lim = M; i <= lim; i++) i++, Ans = Ans + A[G[i]];
  printf("%d\n", Ans.x);
  return 0;
}

```