#include <bits/stdc++.h>
using namespace std;
template <int mod = 1000000007, int ph = mod - 1>
class modint {
 public:
  int vl;
  modint() { vl = 0; }
  modint(int x) { vl = x; }
  void set(long long x) { vl = x % mod; }
  modint operator+(const modint &t) const {
    int c = vl + t.vl;
    if (c >= mod) c -= mod;
    return c;
  }
  modint &operator+=(const modint &t) {
    if ((vl += t.vl) >= mod) vl -= mod;
    return *this;
  }
  modint operator-(const modint &t) const {
    int c = vl - t.vl;
    if (c < 0) c += mod;
    return c;
  }
  modint &operator-=(const modint &t) {
    if ((vl -= t.vl) < 0) vl += mod;
    return *this;
  }
  modint operator*(const modint &t) const {
    long long cv = (long long)vl * t.vl;
    if (cv >= mod) cv %= mod;
    return cv;
  }
  modint &operator*=(const modint &t) {
    *this = (*this) * t;
    return *this;
  }
  modint operator^(long long t) const {
    modint ret(1), c(*this);
    while (t) {
      if (t & 1) ret = ret * c;
      c = c * c;
      t >>= 1;
    }
    return ret;
  }
  modint operator~() const { return (*this) ^ (ph - 1); }
  modint operator/(const modint &t) const { return (*this) * (~t); }
  bool operator<(const modint &t) const { return vl < t.vl; }
};
class DS {
 public:
  modint<> lenx, x;
  DS() {}
  DS(modint<> _lenx, modint<> _x) : lenx(_lenx), x(_x) {}
  DS operator+(const DS &t) const {
    return DS(lenx * t.lenx, x * t.lenx + t.x);
  }
};
string s;
int match[100010], l;
modint<> readnumber(int &it, int R) {
  modint<> ret(0);
  while (it <= R && (s[it] >= '0' && s[it] <= '9')) {
    ret = ret * 10 + (s[it] - '0');
    it++;
  }
  return ret;
}
modint<1000000006> readnumbere(int l, int r) {
  modint<1000000006> ret(0);
  for (int i = l; i <= r; i++) ret = ret * 10 + (s[i] - '0');
  return ret;
}
DS catenate(int len, modint<> l, modint<> r, modint<1000000006> el,
            modint<1000000006> er) {
  modint<> bas = modint<>(10) ^ len, iv = ~(bas - 1);
  modint<> f1 = bas ^ ((er - el + 1).vl);
  modint<> f2 =
      (bas ^ (1000000006 - el.vl)) *
      ((l + r) * ((bas ^ (el.vl)) * iv * ((bas ^ (er - el + 1).vl) - 1)) -
       iv * ((bas ^ (er + 1).vl) * r -
             iv * (bas ^ (el + 1).vl) * ((bas ^ (er - el).vl) - 1) -
             (bas ^ el.vl) * l));
  return DS(f1, f2);
}
DS solve(int l, int r) {
  DS ret(1, 0);
  for (int i = l, j; i <= r; i = j + 1) {
    j = i;
    modint<> a = readnumber(j, r);
    modint<1000000006> ea = readnumbere(i, j - 1);
    int l1 = j - i;
    DS cur;
    if (j == r + 1 || s[j] == '+')
      cur = DS(modint<>(10) ^ (j - i), a);
    else if (s[j] == '-') {
      j++;
      int l2 = j;
      modint<> b = readnumber(j, r);
      modint<1000000006> eb = readnumbere(l2, j - 1);
      l2 = j - l2;
      if (l1 == l2)
        cur = catenate(l1, a, b, ea, eb);
      else {
        cur = catenate(l1, a, (modint<>(10) ^ l1) - 1, ea,
                       (modint<1000000006>(10) ^ l1) - 1);
        for (int i = l1 + 1; i < l2; i++)
          cur =
              cur + catenate(i, modint<>(10) ^ (i - 1), (modint<>(10) ^ i) - 1,
                             modint<1000000006>(10) ^ (i - 1),
                             (modint<1000000006>(10) ^ i) - 1);
        cur = cur + catenate(l2, modint<>(10) ^ (l2 - 1), b,
                             modint<1000000006>(10) ^ (l2 - 1), eb);
      }
    } else {
      int cr = match[j];
      auto tmp = solve(j + 1, cr - 1);
      j = cr + 1;
      if (tmp.lenx.vl == 1)
        cur = DS(1, tmp.x * a);
      else
        cur = DS(tmp.lenx ^ ea.vl, tmp.x * (modint<>(1) - (tmp.lenx ^ ea.vl)) *
                                       (~(modint<>(1) - tmp.lenx)));
    }
    ret = ret + cur;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(0);
  cin >> s;
  l = s.size();
  vector<int> stk;
  for (int i = 0; i < l; i++) {
    if (s[i] == '(')
      stk.push_back(i);
    else if (s[i] == ')') {
      match[stk.back()] = i;
      match[i] = stk.back();
      stk.pop_back();
    }
  }
  auto c = solve(0, l - 1);
  cout << c.x.vl;
  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 <int mod = 1000000007, int ph = mod - 1>
class modint {
 public:
  int vl;
  modint() { vl = 0; }
  modint(int x) { vl = x; }
  void set(long long x) { vl = x % mod; }
  modint operator+(const modint &t) const {
    int c = vl + t.vl;
    if (c >= mod) c -= mod;
    return c;
  }
  modint &operator+=(const modint &t) {
    if ((vl += t.vl) >= mod) vl -= mod;
    return *this;
  }
  modint operator-(const modint &t) const {
    int c = vl - t.vl;
    if (c < 0) c += mod;
    return c;
  }
  modint &operator-=(const modint &t) {
    if ((vl -= t.vl) < 0) vl += mod;
    return *this;
  }
  modint operator*(const modint &t) const {
    long long cv = (long long)vl * t.vl;
    if (cv >= mod) cv %= mod;
    return cv;
  }
  modint &operator*=(const modint &t) {
    *this = (*this) * t;
    return *this;
  }
  modint operator^(long long t) const {
    modint ret(1), c(*this);
    while (t) {
      if (t & 1) ret = ret * c;
      c = c * c;
      t >>= 1;
    }
    return ret;
  }
  modint operator~() const { return (*this) ^ (ph - 1); }
  modint operator/(const modint &t) const { return (*this) * (~t); }
  bool operator<(const modint &t) const { return vl < t.vl; }
};
class DS {
 public:
  modint<> lenx, x;
  DS() {}
  DS(modint<> _lenx, modint<> _x) : lenx(_lenx), x(_x) {}
  DS operator+(const DS &t) const {
    return DS(lenx * t.lenx, x * t.lenx + t.x);
  }
};
string s;
int match[100010], l;
modint<> readnumber(int &it, int R) {
  modint<> ret(0);
  while (it <= R && (s[it] >= '0' && s[it] <= '9')) {
    ret = ret * 10 + (s[it] - '0');
    it++;
  }
  return ret;
}
modint<1000000006> readnumbere(int l, int r) {
  modint<1000000006> ret(0);
  for (int i = l; i <= r; i++) ret = ret * 10 + (s[i] - '0');
  return ret;
}
DS catenate(int len, modint<> l, modint<> r, modint<1000000006> el,
            modint<1000000006> er) {
  modint<> bas = modint<>(10) ^ len, iv = ~(bas - 1);
  modint<> f1 = bas ^ ((er - el + 1).vl);
  modint<> f2 =
      (bas ^ (1000000006 - el.vl)) *
      ((l + r) * ((bas ^ (el.vl)) * iv * ((bas ^ (er - el + 1).vl) - 1)) -
       iv * ((bas ^ (er + 1).vl) * r -
             iv * (bas ^ (el + 1).vl) * ((bas ^ (er - el).vl) - 1) -
             (bas ^ el.vl) * l));
  return DS(f1, f2);
}
DS solve(int l, int r) {
  DS ret(1, 0);
  for (int i = l, j; i <= r; i = j + 1) {
    j = i;
    modint<> a = readnumber(j, r);
    modint<1000000006> ea = readnumbere(i, j - 1);
    int l1 = j - i;
    DS cur;
    if (j == r + 1 || s[j] == '+')
      cur = DS(modint<>(10) ^ (j - i), a);
    else if (s[j] == '-') {
      j++;
      int l2 = j;
      modint<> b = readnumber(j, r);
      modint<1000000006> eb = readnumbere(l2, j - 1);
      l2 = j - l2;
      if (l1 == l2)
        cur = catenate(l1, a, b, ea, eb);
      else {
        cur = catenate(l1, a, (modint<>(10) ^ l1) - 1, ea,
                       (modint<1000000006>(10) ^ l1) - 1);
        for (int i = l1 + 1; i < l2; i++)
          cur =
              cur + catenate(i, modint<>(10) ^ (i - 1), (modint<>(10) ^ i) - 1,
                             modint<1000000006>(10) ^ (i - 1),
                             (modint<1000000006>(10) ^ i) - 1);
        cur = cur + catenate(l2, modint<>(10) ^ (l2 - 1), b,
                             modint<1000000006>(10) ^ (l2 - 1), eb);
      }
    } else {
      int cr = match[j];
      auto tmp = solve(j + 1, cr - 1);
      j = cr + 1;
      if (tmp.lenx.vl == 1)
        cur = DS(1, tmp.x * a);
      else
        cur = DS(tmp.lenx ^ ea.vl, tmp.x * (modint<>(1) - (tmp.lenx ^ ea.vl)) *
                                       (~(modint<>(1) - tmp.lenx)));
    }
    ret = ret + cur;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(0);
  cin >> s;
  l = s.size();
  vector<int> stk;
  for (int i = 0; i < l; i++) {
    if (s[i] == '(')
      stk.push_back(i);
    else if (s[i] == ')') {
      match[stk.back()] = i;
      match[i] = stk.back();
      stk.pop_back();
    }
  }
  auto c = solve(0, l - 1);
  cout << c.x.vl;
  return 0;
}

```