#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, mod = 1e9 + 7;
const long long inf = 1e18;
int aft[maxn], tn1[maxn], tn2[maxn];
vector<pair<int, pair<int, int> > > vec;
int Pow(int a, int b) {
  b = ((b % (mod - 1)) + mod - 1) % (mod - 1);
  a = ((a % mod) + mod) % mod;
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) ans = 1ll * ans * a % mod;
  return ans;
}
pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
  return {(1ll * Pow(10, b.second) * a.first + b.first) % mod,
          (a.second + b.second) % (mod - 1)};
}
int ff(pair<int, int> a, int dig) {
  int R1 = (a.first + 1) % mod, R2 = (a.second + 1) % (mod - 1);
  int num = Pow(Pow(10, dig) - 1, mod - 2), ANS = 0;
  if (num == 0)
    ANS = 1ll * R1 * (R1 - 1) % mod * Pow(2, mod - 2) % mod;
  else
    ANS = 1ll *
          ((1ll * (Pow(10, 1ll * dig * R2 % (mod - 1)) - 1) * num - R1) % mod) *
          num % mod;
  return ANS;
}
pair<int, int> f(pair<int, int> a, pair<int, int> b, int dig) {
  int A = (1ll * ff(b, dig) -
           1ll * Pow(10, 1ll * dig * (b.second - a.second + 1) % (mod - 1)) *
               ff({a.first - 1, a.second - 1}, dig)) %
          mod;
  int B = 1ll * dig * (b.second - a.second + 1) % (mod - 1);
  return {A, B};
}
pair<int, int> operator-(pair<int, pair<int, int> > a,
                         pair<int, pair<int, int> > b) {
  pair<int, int> Ans = {0, 0}, nw = a.second;
  for (int i = a.first; i < b.first; i++) {
    pair<int, int> x = {tn1[i], tn2[i]};
    Ans =
        Ans +
        f(nw, {(x.first + mod - 1) % mod, (x.second + mod - 2) % (mod - 1)}, i);
    nw = x;
  }
  Ans = Ans + f(nw, b.second, b.first);
  return Ans;
}
pair<int, int> operator*(pair<int, pair<int, int> > a, pair<int, int> b) {
  int x = b.first, dig = b.second, Num1 = a.second.first,
      Num2 = a.second.second, Ans = 0;
  if (Pow(10, dig) == 1) {
    Ans = 1ll * Num1 * x % mod;
  } else {
    Ans = 1ll * (Pow(10, 1ll * dig * Num2 % (mod - 1)) - 1) *
          (Pow(Pow(10, dig) - 1, mod - 2)) % mod * x % mod;
  }
  return {Ans, 1ll * Num2 * dig % (mod - 1)};
}
pair<int, int> solve(int l, int r) {
  pair<int, int> Ans = {0, 0};
  for (int i = l; i < r; i++) {
    if (vec[i].first >= 0 && i + 1 != r && vec[i + 1].first < 0) continue;
    if (vec[i].first >= 0)
      Ans = Ans + (pair<int, int>){vec[i].second.first, vec[i].first};
    else if (vec[i].first == -1)
      Ans = Ans + (vec[i - 1] * solve(i + 1, aft[i])), i = aft[i];
    else if (vec[i].first == -3)
      Ans = Ans + (vec[i - 1] - vec[i + 1]), ++i;
  }
  return Ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  tn1[0] = tn2[0] = 1;
  for (int i = 1; i < maxn; i++)
    tn1[i] = 10ll * tn1[i - 1] % mod, tn2[i] = 10ll * tn2[i - 1] % (mod - 1);
  string str;
  cin >> str;
  for (int i = 0; i < int((str).size()); i++) {
    if (str[i] == '(') {
      vec.push_back({-1, {0, 0}});
    } else if (str[i] == ')') {
      vec.push_back({-2, {0, 0}});
    } else if (str[i] == '-') {
      vec.push_back({-3, {0, 0}});
    } else if (str[i] != '+') {
      int A = 0, B = 0, C = 0;
      while (i < int((str).size()) && '0' <= str[i] && str[i] <= '9') {
        A = (1ll * 10 * A + (str[i] - '0')) % mod;
        B = (1ll * 10 * B + (str[i] - '0')) % (mod - 1);
        C++, i++;
      }
      vec.push_back({C, {A, B}});
      --i;
    }
  }
  memset(aft, -1, sizeof aft);
  vector<int> vec2;
  for (int i = 0; i < int((vec).size()); i++) {
    if (vec[i].first == -1) vec2.push_back(i);
    if (vec[i].first == -2) aft[vec2.back()] = i, vec2.pop_back();
  }
  int Ans = solve(0, int((vec).size())).first;
  if (Ans < 0) Ans += mod;
  return cout << Ans << endl, 0;
}

### Prompt

Please formulate 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>
using namespace std;
const int maxn = 1e5 + 10, mod = 1e9 + 7;
const long long inf = 1e18;
int aft[maxn], tn1[maxn], tn2[maxn];
vector<pair<int, pair<int, int> > > vec;
int Pow(int a, int b) {
  b = ((b % (mod - 1)) + mod - 1) % (mod - 1);
  a = ((a % mod) + mod) % mod;
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) ans = 1ll * ans * a % mod;
  return ans;
}
pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
  return {(1ll * Pow(10, b.second) * a.first + b.first) % mod,
          (a.second + b.second) % (mod - 1)};
}
int ff(pair<int, int> a, int dig) {
  int R1 = (a.first + 1) % mod, R2 = (a.second + 1) % (mod - 1);
  int num = Pow(Pow(10, dig) - 1, mod - 2), ANS = 0;
  if (num == 0)
    ANS = 1ll * R1 * (R1 - 1) % mod * Pow(2, mod - 2) % mod;
  else
    ANS = 1ll *
          ((1ll * (Pow(10, 1ll * dig * R2 % (mod - 1)) - 1) * num - R1) % mod) *
          num % mod;
  return ANS;
}
pair<int, int> f(pair<int, int> a, pair<int, int> b, int dig) {
  int A = (1ll * ff(b, dig) -
           1ll * Pow(10, 1ll * dig * (b.second - a.second + 1) % (mod - 1)) *
               ff({a.first - 1, a.second - 1}, dig)) %
          mod;
  int B = 1ll * dig * (b.second - a.second + 1) % (mod - 1);
  return {A, B};
}
pair<int, int> operator-(pair<int, pair<int, int> > a,
                         pair<int, pair<int, int> > b) {
  pair<int, int> Ans = {0, 0}, nw = a.second;
  for (int i = a.first; i < b.first; i++) {
    pair<int, int> x = {tn1[i], tn2[i]};
    Ans =
        Ans +
        f(nw, {(x.first + mod - 1) % mod, (x.second + mod - 2) % (mod - 1)}, i);
    nw = x;
  }
  Ans = Ans + f(nw, b.second, b.first);
  return Ans;
}
pair<int, int> operator*(pair<int, pair<int, int> > a, pair<int, int> b) {
  int x = b.first, dig = b.second, Num1 = a.second.first,
      Num2 = a.second.second, Ans = 0;
  if (Pow(10, dig) == 1) {
    Ans = 1ll * Num1 * x % mod;
  } else {
    Ans = 1ll * (Pow(10, 1ll * dig * Num2 % (mod - 1)) - 1) *
          (Pow(Pow(10, dig) - 1, mod - 2)) % mod * x % mod;
  }
  return {Ans, 1ll * Num2 * dig % (mod - 1)};
}
pair<int, int> solve(int l, int r) {
  pair<int, int> Ans = {0, 0};
  for (int i = l; i < r; i++) {
    if (vec[i].first >= 0 && i + 1 != r && vec[i + 1].first < 0) continue;
    if (vec[i].first >= 0)
      Ans = Ans + (pair<int, int>){vec[i].second.first, vec[i].first};
    else if (vec[i].first == -1)
      Ans = Ans + (vec[i - 1] * solve(i + 1, aft[i])), i = aft[i];
    else if (vec[i].first == -3)
      Ans = Ans + (vec[i - 1] - vec[i + 1]), ++i;
  }
  return Ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  tn1[0] = tn2[0] = 1;
  for (int i = 1; i < maxn; i++)
    tn1[i] = 10ll * tn1[i - 1] % mod, tn2[i] = 10ll * tn2[i - 1] % (mod - 1);
  string str;
  cin >> str;
  for (int i = 0; i < int((str).size()); i++) {
    if (str[i] == '(') {
      vec.push_back({-1, {0, 0}});
    } else if (str[i] == ')') {
      vec.push_back({-2, {0, 0}});
    } else if (str[i] == '-') {
      vec.push_back({-3, {0, 0}});
    } else if (str[i] != '+') {
      int A = 0, B = 0, C = 0;
      while (i < int((str).size()) && '0' <= str[i] && str[i] <= '9') {
        A = (1ll * 10 * A + (str[i] - '0')) % mod;
        B = (1ll * 10 * B + (str[i] - '0')) % (mod - 1);
        C++, i++;
      }
      vec.push_back({C, {A, B}});
      --i;
    }
  }
  memset(aft, -1, sizeof aft);
  vector<int> vec2;
  for (int i = 0; i < int((vec).size()); i++) {
    if (vec[i].first == -1) vec2.push_back(i);
    if (vec[i].first == -2) aft[vec2.back()] = i, vec2.pop_back();
  }
  int Ans = solve(0, int((vec).size())).first;
  if (Ans < 0) Ans += mod;
  return cout << Ans << endl, 0;
}

```