#include <bits/stdc++.h>
using namespace std;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
}
template <typename T>
static T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
static T mod(T a, T m) {
  a %= m;
  if (a < 0) a += m;
  return a;
}
template <typename T>
static T inverse(T a, T m) {
  a = mod(a, m);
  if (a <= 1) return a;
  return mod((1 - inverse(m, a) * m) / a, m);
}
template <typename T, typename C, T Modulus>
class MR {
 private:
  struct tag_plus {};
  struct tag_minus {};
  struct tag_good {};
  T value;
  static_assert(std::numeric_limits<C>::max() / Modulus / Modulus > 0,
                "compute type is too small");
  static_assert(Modulus < std::numeric_limits<T>::max() / 2,
                "storage type is too small");
  void reduce(tag_plus) {
    if (value >= Modulus) value -= Modulus;
  }
  void reduce(tag_minus) {
    if (value < 0) value += Modulus;
  }
  void reduce(tag_good) {}

 public:
  static const T modulus = Modulus;
  MR() : value(0) {}
  MR(C value) : value(value % Modulus) { reduce(tag_minus()); }
  template <typename tag_t>
  MR(T value, tag_t tag) : value(value) {
    reduce(tag);
  }
  MR &operator=(C value) {
    this->value = value % Modulus;
    reduce(tag_minus());
    return *this;
  }
  MR operator+(MR b) const { return MR(value + b.value, tag_plus()); }
  MR operator-(MR b) const { return MR(value - b.value, tag_minus()); }
  MR operator*(MR b) const {
    return MR(C(value) * C(b.value) % Modulus, tag_good());
  }
  MR operator-() const { return MR(-value, tag_minus()); }
  MR &operator+=(MR b) {
    value += b.value;
    reduce(tag_plus());
    return *this;
  }
  MR &operator-=(MR b) {
    value -= b.value;
    reduce(tag_minus());
    return *this;
  }
  MR &operator*=(MR b) {
    value = C(value) * C(b.value) % Modulus;
    return *this;
  }
  bool operator==(MR b) const { return value == b.value; }
  bool operator!=(MR b) const { return value != b.value; }
  T get() const { return value; }
  MR inverse() const {
    assert(value);
    return MR(::inverse(C(value), C(Modulus)), tag_good());
  }
  MR operator/(MR b) const { return *this * b.inverse(); }
  MR &operator/=(MR b) { return *this *= b.inverse(); }
};
template <typename T, typename C, T Modulus>
static inline std::ostream &operator<<(std::ostream &o, MR<T, C, Modulus> mr) {
  return o << mr.get();
}
template <typename T>
static T power(const T &a, long long b) {
  if (b == 0)
    return T(1);
  else if (b & 1)
    return power(a, b - 1) * a;
  else {
    T tmp = power(a, b / 2);
    return tmp * tmp;
  }
}
template <typename T, typename U>
static T sumag(T a, T b, T s, U apow, U bpow) {
  if (s == 1)
    return (a + b - 1) * (b - a) / 2;
  else {
    auto inv = (s - 1).inverse();
    T part = (b - 1) * power(s, bpow.get()) - a * power(s, apow.get()) +
             inv * (power(s, apow.get() + 1) - power(s, bpow.get()));
    return part * inv;
  }
}
struct value {
  MR<int, long long, 1000000007> base;
  MR<int, long long, 1000000007> step;
};
static string line;
static int pos;
static value concat(const value &a, const value &b) {
  return value{a.base * b.step + b.base, a.step * b.step};
}
static string parse_number() {
  int stop = pos;
  while (line[stop] >= '0' && line[stop] <= '9') stop++;
  string out = line.substr(pos, stop - pos);
  pos = stop;
  return out;
}
template <typename T>
static T simple(const string &number) {
  T out = 0;
  for (char c : number) out = out * 10 + (c - '0');
  return out;
}
static value value_of(const string &number) {
  value out{0, 1};
  for (char c : number) {
    int d = c - '0';
    out.base *= 10;
    out.base += d;
    out.step *= 10;
  }
  return out;
}
static value repeat(const string &r, const value &a) {
  MR<int, long long, 1000000006> rv =
      simple<MR<int, long long, 1000000006> >(r);
  MR<int, long long, 1000000007> rm =
      simple<MR<int, long long, 1000000007> >(r);
  value out;
  out.step = power(a.step, rv.get());
  if (a.step.get() == 1)
    out.base = rm * a.base;
  else
    out.base = (out.step - 1) / (a.step - 1) * a.base;
  return out;
}
static value make_range1(long long d, const MR<int, long long, 1000000007> &a,
                         const MR<int, long long, 1000000007> &b,
                         const MR<int, long long, 1000000006> &ap,
                         const MR<int, long long, 1000000006> &bp) {
  MR<int, long long, 1000000007> scale =
      power(MR<int, long long, 1000000007>(10), ((bp - 1) * d).get());
  MR<int, long long, 1000000007> s =
      power(MR<int, long long, 1000000007>(10), d).inverse();
  value out;
  out.base = sumag(a, b, s, ap, bp) * scale;
  MR<int, long long, 1000000006> digits = (bp - ap) * d;
  out.step = power(MR<int, long long, 1000000007>(10), digits.get());
  return out;
}
static value make_range(const string &a, const string &b) {
  if (a.size() == b.size()) {
    return make_range1(a.size(), simple<MR<int, long long, 1000000007> >(a),
                       simple<MR<int, long long, 1000000007> >(b) + 1,
                       simple<MR<int, long long, 1000000006> >(a),
                       simple<MR<int, long long, 1000000006> >(b) + 1);
  } else {
    value out =
        make_range1(a.size(), simple<MR<int, long long, 1000000007> >(a),
                    power(MR<int, long long, 1000000007>(10), a.size()),
                    simple<MR<int, long long, 1000000006> >(a),
                    power(MR<int, long long, 1000000006>(10), a.size()));
    for (int d = ((long long)(a).size()) + 1; d < ((long long)(b).size());
         d++) {
      value cur =
          make_range1(d, power(MR<int, long long, 1000000007>(10), d - 1),
                      power(MR<int, long long, 1000000007>(10), d),
                      power(MR<int, long long, 1000000006>(10), d - 1),
                      power(MR<int, long long, 1000000006>(10), d));
      out = concat(out, cur);
    }
    value last = make_range1(
        b.size(),
        power(MR<int, long long, 1000000007>(10), ((long long)(b).size()) - 1),
        simple<MR<int, long long, 1000000007> >(b) + 1,
        power(MR<int, long long, 1000000006>(10), ((long long)(b).size()) - 1),
        simple<MR<int, long long, 1000000006> >(b) + 1);
    out = concat(out, last);
    return out;
  }
}
static value parse_expression();
static value parse_term() {
  string left = parse_number();
  if (line[pos] == '-') {
    pos++;
    string right = parse_number();
    return make_range(left, right);
  } else if (line[pos] == '(') {
    pos++;
    value right = parse_expression();
    assert(line[pos] == ')');
    pos++;
    return repeat(left, right);
  } else
    return value_of(left);
}
static value parse_expression() {
  value left = parse_term();
  if (line[pos] == '+') {
    pos++;
    value right = parse_expression();
    return concat(left, right);
  } else
    return left;
};
int main(int argc, const char **argv) {
  redirect(argc, argv);
  cin >> line;
  line += '$';
  pos = 0;
  value ans = parse_expression();
  cout << ans.base << '\n';
  return 0;
}

### Prompt

Create a solution in CPP for 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;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
}
template <typename T>
static T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
static T mod(T a, T m) {
  a %= m;
  if (a < 0) a += m;
  return a;
}
template <typename T>
static T inverse(T a, T m) {
  a = mod(a, m);
  if (a <= 1) return a;
  return mod((1 - inverse(m, a) * m) / a, m);
}
template <typename T, typename C, T Modulus>
class MR {
 private:
  struct tag_plus {};
  struct tag_minus {};
  struct tag_good {};
  T value;
  static_assert(std::numeric_limits<C>::max() / Modulus / Modulus > 0,
                "compute type is too small");
  static_assert(Modulus < std::numeric_limits<T>::max() / 2,
                "storage type is too small");
  void reduce(tag_plus) {
    if (value >= Modulus) value -= Modulus;
  }
  void reduce(tag_minus) {
    if (value < 0) value += Modulus;
  }
  void reduce(tag_good) {}

 public:
  static const T modulus = Modulus;
  MR() : value(0) {}
  MR(C value) : value(value % Modulus) { reduce(tag_minus()); }
  template <typename tag_t>
  MR(T value, tag_t tag) : value(value) {
    reduce(tag);
  }
  MR &operator=(C value) {
    this->value = value % Modulus;
    reduce(tag_minus());
    return *this;
  }
  MR operator+(MR b) const { return MR(value + b.value, tag_plus()); }
  MR operator-(MR b) const { return MR(value - b.value, tag_minus()); }
  MR operator*(MR b) const {
    return MR(C(value) * C(b.value) % Modulus, tag_good());
  }
  MR operator-() const { return MR(-value, tag_minus()); }
  MR &operator+=(MR b) {
    value += b.value;
    reduce(tag_plus());
    return *this;
  }
  MR &operator-=(MR b) {
    value -= b.value;
    reduce(tag_minus());
    return *this;
  }
  MR &operator*=(MR b) {
    value = C(value) * C(b.value) % Modulus;
    return *this;
  }
  bool operator==(MR b) const { return value == b.value; }
  bool operator!=(MR b) const { return value != b.value; }
  T get() const { return value; }
  MR inverse() const {
    assert(value);
    return MR(::inverse(C(value), C(Modulus)), tag_good());
  }
  MR operator/(MR b) const { return *this * b.inverse(); }
  MR &operator/=(MR b) { return *this *= b.inverse(); }
};
template <typename T, typename C, T Modulus>
static inline std::ostream &operator<<(std::ostream &o, MR<T, C, Modulus> mr) {
  return o << mr.get();
}
template <typename T>
static T power(const T &a, long long b) {
  if (b == 0)
    return T(1);
  else if (b & 1)
    return power(a, b - 1) * a;
  else {
    T tmp = power(a, b / 2);
    return tmp * tmp;
  }
}
template <typename T, typename U>
static T sumag(T a, T b, T s, U apow, U bpow) {
  if (s == 1)
    return (a + b - 1) * (b - a) / 2;
  else {
    auto inv = (s - 1).inverse();
    T part = (b - 1) * power(s, bpow.get()) - a * power(s, apow.get()) +
             inv * (power(s, apow.get() + 1) - power(s, bpow.get()));
    return part * inv;
  }
}
struct value {
  MR<int, long long, 1000000007> base;
  MR<int, long long, 1000000007> step;
};
static string line;
static int pos;
static value concat(const value &a, const value &b) {
  return value{a.base * b.step + b.base, a.step * b.step};
}
static string parse_number() {
  int stop = pos;
  while (line[stop] >= '0' && line[stop] <= '9') stop++;
  string out = line.substr(pos, stop - pos);
  pos = stop;
  return out;
}
template <typename T>
static T simple(const string &number) {
  T out = 0;
  for (char c : number) out = out * 10 + (c - '0');
  return out;
}
static value value_of(const string &number) {
  value out{0, 1};
  for (char c : number) {
    int d = c - '0';
    out.base *= 10;
    out.base += d;
    out.step *= 10;
  }
  return out;
}
static value repeat(const string &r, const value &a) {
  MR<int, long long, 1000000006> rv =
      simple<MR<int, long long, 1000000006> >(r);
  MR<int, long long, 1000000007> rm =
      simple<MR<int, long long, 1000000007> >(r);
  value out;
  out.step = power(a.step, rv.get());
  if (a.step.get() == 1)
    out.base = rm * a.base;
  else
    out.base = (out.step - 1) / (a.step - 1) * a.base;
  return out;
}
static value make_range1(long long d, const MR<int, long long, 1000000007> &a,
                         const MR<int, long long, 1000000007> &b,
                         const MR<int, long long, 1000000006> &ap,
                         const MR<int, long long, 1000000006> &bp) {
  MR<int, long long, 1000000007> scale =
      power(MR<int, long long, 1000000007>(10), ((bp - 1) * d).get());
  MR<int, long long, 1000000007> s =
      power(MR<int, long long, 1000000007>(10), d).inverse();
  value out;
  out.base = sumag(a, b, s, ap, bp) * scale;
  MR<int, long long, 1000000006> digits = (bp - ap) * d;
  out.step = power(MR<int, long long, 1000000007>(10), digits.get());
  return out;
}
static value make_range(const string &a, const string &b) {
  if (a.size() == b.size()) {
    return make_range1(a.size(), simple<MR<int, long long, 1000000007> >(a),
                       simple<MR<int, long long, 1000000007> >(b) + 1,
                       simple<MR<int, long long, 1000000006> >(a),
                       simple<MR<int, long long, 1000000006> >(b) + 1);
  } else {
    value out =
        make_range1(a.size(), simple<MR<int, long long, 1000000007> >(a),
                    power(MR<int, long long, 1000000007>(10), a.size()),
                    simple<MR<int, long long, 1000000006> >(a),
                    power(MR<int, long long, 1000000006>(10), a.size()));
    for (int d = ((long long)(a).size()) + 1; d < ((long long)(b).size());
         d++) {
      value cur =
          make_range1(d, power(MR<int, long long, 1000000007>(10), d - 1),
                      power(MR<int, long long, 1000000007>(10), d),
                      power(MR<int, long long, 1000000006>(10), d - 1),
                      power(MR<int, long long, 1000000006>(10), d));
      out = concat(out, cur);
    }
    value last = make_range1(
        b.size(),
        power(MR<int, long long, 1000000007>(10), ((long long)(b).size()) - 1),
        simple<MR<int, long long, 1000000007> >(b) + 1,
        power(MR<int, long long, 1000000006>(10), ((long long)(b).size()) - 1),
        simple<MR<int, long long, 1000000006> >(b) + 1);
    out = concat(out, last);
    return out;
  }
}
static value parse_expression();
static value parse_term() {
  string left = parse_number();
  if (line[pos] == '-') {
    pos++;
    string right = parse_number();
    return make_range(left, right);
  } else if (line[pos] == '(') {
    pos++;
    value right = parse_expression();
    assert(line[pos] == ')');
    pos++;
    return repeat(left, right);
  } else
    return value_of(left);
}
static value parse_expression() {
  value left = parse_term();
  if (line[pos] == '+') {
    pos++;
    value right = parse_expression();
    return concat(left, right);
  } else
    return left;
};
int main(int argc, const char **argv) {
  redirect(argc, argv);
  cin >> line;
  line += '$';
  pos = 0;
  value ans = parse_expression();
  cout << ans.base << '\n';
  return 0;
}

```