#include <bits/stdc++.h>
template <typename T>
struct xgcd_s {
  T m, n, gcd;
};
template <typename T>
xgcd_s<T> xgcd(T a, T b) {
  T m[] = {1, 0}, n[] = {0, 1}, q[] = {0, 0};
  for (int i = 0;; i ^= 1) {
    m[i] -= m[i ^ 1] * q[i];
    n[i] -= n[i ^ 1] * q[i];
    if (!b) return xgcd_s<T>{m[i], n[i], a};
    q[i] = a / b;
    a %= b;
    std::swap(a, b);
  }
}
template <unsigned M()>
struct _intmod {
 private:
  struct _p {
    unsigned x;
  };
  _intmod(_p x) { n = x.x; }

 public:
  unsigned n;
  _intmod() { n = 0; }
  _intmod(int x) { n = x < 0 ? M() + x % (int)M() : x % M(); }
  _intmod(unsigned x) { n = x % M(); }
  _intmod(long x) { n = unsigned(x < 0 ? M() + x % (long)M() : x % M()); }
  _intmod(unsigned long x) { n = x % M(); }
  _intmod(long long x) {
    n = unsigned(x < 0 ? M() + x % (long long)M() : x % M());
  }
  _intmod(unsigned long long x) { n = x % M(); }
  _intmod operator+(_intmod b) const { return {n + b.n}; }
  _intmod operator*(_intmod b) const {
    return {_p{unsigned((unsigned long long)n * b.n % M())}};
  }
  _intmod operator-(_intmod b) const {
    return {_p{n >= b.n ? n - b.n : M() + n - b.n}};
  }
  _intmod operator-() const { return {_p{n ? M() - n : 0U}}; }
  _intmod& operator+=(_intmod b) { return (*this = *this + b); }
  _intmod& operator-=(_intmod b) { return (*this = *this - b); }
  _intmod& operator/=(_intmod b) { return (*this = *this / b); }
  _intmod& operator*=(_intmod b) { return (*this = *this * b); }
  static _intmod mulinv(_intmod n) {
    xgcd_s<signed> x = xgcd<signed>(n.n, M());
    assert(x.gcd == 1);
    return x.m;
  }
  _intmod operator/(_intmod b) const { return *this * mulinv(b); }
  bool operator==(_intmod b) const { return n == b.n; }
  bool operator!=(_intmod b) const { return n != b.n; }
  explicit operator int() const { return n; }
};
template <unsigned M()>
std::ostream& operator<<(std::ostream& o, _intmod<M> n) {
  return o << n.n;
}
template <unsigned M()>
std::istream& operator>>(std::istream& i, _intmod<M>& n) {
  long long x;
  i >> x;
  n = x;
  return i;
}
template <unsigned M>
unsigned intmod_unsignedconst() {
  static_assert(M > 0 && M < (1U << 31), "modulus bad");
  return M;
}
template <unsigned* M>
unsigned intmod_unsignedptr() {
  return *M;
}
template <unsigned M>
using intmod = _intmod<intmod_unsignedconst<M> >;
template <unsigned* M>
using intmodv = _intmod<intmod_unsignedptr<M> >;
static_assert(std::is_trivially_copyable<intmod<3> >::value, "");
template <typename T, typename X>
T bpow(T b, X x) {
  T r = 1, p = b;
  while (x) {
    if (x & 1) r = r * p;
    if (x >>= 1) p = p * p;
  }
  return r;
}
using I = intmod<1000000007>;
using XI = intmod<1000000007 - 1>;
struct expr {
  I m;
  XI xm, len;
};
I ten(XI x) { return bpow(I(10), x.n); }
expr operator+(expr a, expr b) {
  expr o;
  o.len = a.len + b.len;
  o.m = a.m * ten(b.len) + b.m;
  return o;
}
expr rangeSameLen(expr a, expr b) {
  I L = ten(a.len);
  expr o;
  if (L == 1) {
    o.m = (b.m * (b.m + 1) - (a.m - 1) * a.m) / 2;
  } else {
    I ilm1 = I::mulinv(L - 1);
    I Lpow = bpow(L, int(b.xm - a.xm + 1));
    o.m = ((Lpow - L) * ilm1 - b.m + a.m * Lpow) * ilm1;
  }
  o.len = a.len * (b.xm - a.xm + 1);
  return o;
}
expr operator-(expr a, expr b) {
  expr o{};
  while (a.len.n < b.len.n) {
    I m10 = ten(a.len.n);
    XI xm10 = bpow(XI(10), a.len.n);
    o = o + rangeSameLen(a, expr{m10 - 1, xm10 - 1, a.len.n});
    ++a.len.n;
    a.m = m10;
    a.xm = xm10;
  }
  return o + rangeSameLen(a, b);
}
expr operator*(expr a, expr b) {
  I x = ten(b.len);
  expr o;
  I xsum = x == 1 ? a.m : (I(1) - bpow(x, a.xm.n)) / (I(1) - x);
  o.m = b.m * xsum;
  o.len = a.xm * b.len;
  return o;
}
expr parseNumber(const char*& p) {
  expr o{};
  while (*p >= '0' && *p <= '9') {
    int d = *p++ - '0';
    o.m = o.m * 10 + d;
    o.xm = o.xm * 10 + d;
    ++o.len.n;
  }
  return o;
}
expr parseExpression(const char*& p);
expr parseTerm(const char*& p) {
  expr a = parseNumber(p);
  if (*p == '-') {
    ++p;
    expr b = parseNumber(p);
    return a - b;
  }
  if (*p == '(') {
    ++p;
    expr b = parseExpression(p);
    assert(*p == ')');
    ++p;
    return a * b;
  }
  return a;
}
expr parseExpression(const char*& p) {
  expr a = parseTerm(p);
  if (*p == '+') {
    ++p;
    expr b = parseExpression(p);
    return a + b;
  }
  return a;
}
using namespace std;
int main(int argc, char** argv) {
  if (argc == 2) freopen(argv[1], "r", stdin);
  ios_base::sync_with_stdio(0);
  string s;
  cin >> s;
  const char* p = s.data();
  expr ans = parseExpression(p);
  assert(p == s.data() + s.size());
  cout << ans.m;
  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>
template <typename T>
struct xgcd_s {
  T m, n, gcd;
};
template <typename T>
xgcd_s<T> xgcd(T a, T b) {
  T m[] = {1, 0}, n[] = {0, 1}, q[] = {0, 0};
  for (int i = 0;; i ^= 1) {
    m[i] -= m[i ^ 1] * q[i];
    n[i] -= n[i ^ 1] * q[i];
    if (!b) return xgcd_s<T>{m[i], n[i], a};
    q[i] = a / b;
    a %= b;
    std::swap(a, b);
  }
}
template <unsigned M()>
struct _intmod {
 private:
  struct _p {
    unsigned x;
  };
  _intmod(_p x) { n = x.x; }

 public:
  unsigned n;
  _intmod() { n = 0; }
  _intmod(int x) { n = x < 0 ? M() + x % (int)M() : x % M(); }
  _intmod(unsigned x) { n = x % M(); }
  _intmod(long x) { n = unsigned(x < 0 ? M() + x % (long)M() : x % M()); }
  _intmod(unsigned long x) { n = x % M(); }
  _intmod(long long x) {
    n = unsigned(x < 0 ? M() + x % (long long)M() : x % M());
  }
  _intmod(unsigned long long x) { n = x % M(); }
  _intmod operator+(_intmod b) const { return {n + b.n}; }
  _intmod operator*(_intmod b) const {
    return {_p{unsigned((unsigned long long)n * b.n % M())}};
  }
  _intmod operator-(_intmod b) const {
    return {_p{n >= b.n ? n - b.n : M() + n - b.n}};
  }
  _intmod operator-() const { return {_p{n ? M() - n : 0U}}; }
  _intmod& operator+=(_intmod b) { return (*this = *this + b); }
  _intmod& operator-=(_intmod b) { return (*this = *this - b); }
  _intmod& operator/=(_intmod b) { return (*this = *this / b); }
  _intmod& operator*=(_intmod b) { return (*this = *this * b); }
  static _intmod mulinv(_intmod n) {
    xgcd_s<signed> x = xgcd<signed>(n.n, M());
    assert(x.gcd == 1);
    return x.m;
  }
  _intmod operator/(_intmod b) const { return *this * mulinv(b); }
  bool operator==(_intmod b) const { return n == b.n; }
  bool operator!=(_intmod b) const { return n != b.n; }
  explicit operator int() const { return n; }
};
template <unsigned M()>
std::ostream& operator<<(std::ostream& o, _intmod<M> n) {
  return o << n.n;
}
template <unsigned M()>
std::istream& operator>>(std::istream& i, _intmod<M>& n) {
  long long x;
  i >> x;
  n = x;
  return i;
}
template <unsigned M>
unsigned intmod_unsignedconst() {
  static_assert(M > 0 && M < (1U << 31), "modulus bad");
  return M;
}
template <unsigned* M>
unsigned intmod_unsignedptr() {
  return *M;
}
template <unsigned M>
using intmod = _intmod<intmod_unsignedconst<M> >;
template <unsigned* M>
using intmodv = _intmod<intmod_unsignedptr<M> >;
static_assert(std::is_trivially_copyable<intmod<3> >::value, "");
template <typename T, typename X>
T bpow(T b, X x) {
  T r = 1, p = b;
  while (x) {
    if (x & 1) r = r * p;
    if (x >>= 1) p = p * p;
  }
  return r;
}
using I = intmod<1000000007>;
using XI = intmod<1000000007 - 1>;
struct expr {
  I m;
  XI xm, len;
};
I ten(XI x) { return bpow(I(10), x.n); }
expr operator+(expr a, expr b) {
  expr o;
  o.len = a.len + b.len;
  o.m = a.m * ten(b.len) + b.m;
  return o;
}
expr rangeSameLen(expr a, expr b) {
  I L = ten(a.len);
  expr o;
  if (L == 1) {
    o.m = (b.m * (b.m + 1) - (a.m - 1) * a.m) / 2;
  } else {
    I ilm1 = I::mulinv(L - 1);
    I Lpow = bpow(L, int(b.xm - a.xm + 1));
    o.m = ((Lpow - L) * ilm1 - b.m + a.m * Lpow) * ilm1;
  }
  o.len = a.len * (b.xm - a.xm + 1);
  return o;
}
expr operator-(expr a, expr b) {
  expr o{};
  while (a.len.n < b.len.n) {
    I m10 = ten(a.len.n);
    XI xm10 = bpow(XI(10), a.len.n);
    o = o + rangeSameLen(a, expr{m10 - 1, xm10 - 1, a.len.n});
    ++a.len.n;
    a.m = m10;
    a.xm = xm10;
  }
  return o + rangeSameLen(a, b);
}
expr operator*(expr a, expr b) {
  I x = ten(b.len);
  expr o;
  I xsum = x == 1 ? a.m : (I(1) - bpow(x, a.xm.n)) / (I(1) - x);
  o.m = b.m * xsum;
  o.len = a.xm * b.len;
  return o;
}
expr parseNumber(const char*& p) {
  expr o{};
  while (*p >= '0' && *p <= '9') {
    int d = *p++ - '0';
    o.m = o.m * 10 + d;
    o.xm = o.xm * 10 + d;
    ++o.len.n;
  }
  return o;
}
expr parseExpression(const char*& p);
expr parseTerm(const char*& p) {
  expr a = parseNumber(p);
  if (*p == '-') {
    ++p;
    expr b = parseNumber(p);
    return a - b;
  }
  if (*p == '(') {
    ++p;
    expr b = parseExpression(p);
    assert(*p == ')');
    ++p;
    return a * b;
  }
  return a;
}
expr parseExpression(const char*& p) {
  expr a = parseTerm(p);
  if (*p == '+') {
    ++p;
    expr b = parseExpression(p);
    return a + b;
  }
  return a;
}
using namespace std;
int main(int argc, char** argv) {
  if (argc == 2) freopen(argv[1], "r", stdin);
  ios_base::sync_with_stdio(0);
  string s;
  cin >> s;
  const char* p = s.data();
  expr ans = parseExpression(p);
  assert(p == s.data() + s.size());
  cout << ans.m;
  return 0;
}

```