#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005, mo = int(1e9) + 7;
int pw[maxn], pw2[maxn];
int fpm(int a, int b) {
  int tmp = 1;
  for (; b; b >>= 1, a = a * 1ll * a % mo)
    if (b & 1) tmp = tmp * 1ll * a % mo;
  return tmp;
}
int mod_int(const string &a, const int &mo) {
  int tmp = 0;
  for (int i = 0; i < a.length(); i++) tmp = (tmp * 10ll + a[i] - 48) % mo;
  return tmp;
}
struct node {
  int l, v;
  node(void) {}
  node(int a, int b) : l(a), v(b) {}
  node(const string &a) {
    l = pw[a.size()];
    v = mod_int(a, mo);
  }
  node operator+(const node &a) {
    return node(l * 1ll * a.l % mo, (v * 1ll * a.l + a.v) % mo);
  }
  node operator^(const string &a) {
    if (a == "") return node(l, v);
    int up = fpm(l, mod_int(a, mo - 1));
    if (l == 1) return node(up, v * 1ll * mod_int(a, mo) % mo);
    return node(up, (v * 1ll * (up - 1) % mo) * fpm(l - 1, mo - 2) % mo);
  }
};
string operator-(const string &a, const string &b) {
  static int va[1000005];
  int len = a.length();
  for (int i = 0; i < len; i++) va[i] = a[len - i - 1] - 48;
  for (int i = 0; i < b.length(); i++)
    va[i] = va[i] - (b[b.length() - i - 1] - 48);
  for (int i = 0; i < len; i++)
    if (va[i] < 0) va[i] += 10, va[i + 1]--;
  for (; len > 1 && !va[len - 1]; len--)
    ;
  string tmp = string(len, '0');
  for (int i = len - 1; i >= 0; i--) tmp[len - i - 1] = char('0' + va[i]);
  return tmp;
}
string s;
int iter;
string get_int() {
  int fiter = iter;
  for (; iter < s.length() && s[iter] >= '0' && s[iter] <= '9'; iter++)
    ;
  return s.substr(fiter, iter - fiter);
}
node get_sum(const string &l, const string &r) {
  int la = l.length(), lb = r.length();
  if (la == lb) {
    string m = r - l;
    int v = mod_int(m, mo - 1);
    int base = pw[la],
        ps = (fpm(base, v + 1) - 1) * 1ll * fpm(base - 1, mo - 2) % mo;
    int val = (mod_int(m, mo) * 1ll * fpm(base, v + 1) % mo - (ps - 1)) *
              fpm(base - 1, mo - 2) % mo;
    return node(fpm(base, v + 1), (mod_int(r, mo) * 1ll * ps - val) % mo);
  } else {
    node ans = get_sum(l, string(la, '9'));
    for (++la; la < lb; la++) {
      int v = ((pw2[la] - 1 - pw2[la - 1]) % (mo - 1) + (mo - 1)) % (mo - 1);
      int base = pw[la],
          ps = (fpm(base, v + 1) - 1) * 1ll * fpm(base - 1, mo - 2) % mo;
      int mod_mo = ((pw[la] - 1 - pw[la - 1]) % mo + mo) % mo;
      int val = (mod_mo * 1ll * fpm(base, v + 1) % mo - (ps - 1)) *
                fpm(base - 1, mo - 2) % mo;
      ans = ans + node(fpm(base, v + 1), ((pw[la] - 1) * 1ll * ps - val) % mo);
    }
    return ans + get_sum('1' + string(lb - 1, '0'), r);
  }
}
node solve() {
  string num = "";
  node tmp = node(num);
  for (; iter < s.length();) {
    if (isdigit(s[iter])) num = get_int();
    char ch = s[iter++];
    if (ch == '(') tmp = tmp + (solve() ^ num);
    if (ch == ')') return tmp + node(num);
    if (ch == '+') tmp = tmp + node(num);
    if (ch == '-') {
      string num1 = get_int();
      tmp = tmp + get_sum(num, num1);
    }
    num = "";
  }
  return tmp + node(num);
}
int main() {
  cin >> s;
  s = "(" + s + ")";
  pw[0] = pw2[0] = 1;
  for (int i = 1; i <= s.length(); i++)
    pw[i] = pw[i - 1] * 10ll % mo, pw2[i] = pw2[i - 1] * 10ll % (mo - 1);
  iter = 0;
  cout << (solve().v + mo) % mo << endl;
  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;
const int maxn = 100005, mo = int(1e9) + 7;
int pw[maxn], pw2[maxn];
int fpm(int a, int b) {
  int tmp = 1;
  for (; b; b >>= 1, a = a * 1ll * a % mo)
    if (b & 1) tmp = tmp * 1ll * a % mo;
  return tmp;
}
int mod_int(const string &a, const int &mo) {
  int tmp = 0;
  for (int i = 0; i < a.length(); i++) tmp = (tmp * 10ll + a[i] - 48) % mo;
  return tmp;
}
struct node {
  int l, v;
  node(void) {}
  node(int a, int b) : l(a), v(b) {}
  node(const string &a) {
    l = pw[a.size()];
    v = mod_int(a, mo);
  }
  node operator+(const node &a) {
    return node(l * 1ll * a.l % mo, (v * 1ll * a.l + a.v) % mo);
  }
  node operator^(const string &a) {
    if (a == "") return node(l, v);
    int up = fpm(l, mod_int(a, mo - 1));
    if (l == 1) return node(up, v * 1ll * mod_int(a, mo) % mo);
    return node(up, (v * 1ll * (up - 1) % mo) * fpm(l - 1, mo - 2) % mo);
  }
};
string operator-(const string &a, const string &b) {
  static int va[1000005];
  int len = a.length();
  for (int i = 0; i < len; i++) va[i] = a[len - i - 1] - 48;
  for (int i = 0; i < b.length(); i++)
    va[i] = va[i] - (b[b.length() - i - 1] - 48);
  for (int i = 0; i < len; i++)
    if (va[i] < 0) va[i] += 10, va[i + 1]--;
  for (; len > 1 && !va[len - 1]; len--)
    ;
  string tmp = string(len, '0');
  for (int i = len - 1; i >= 0; i--) tmp[len - i - 1] = char('0' + va[i]);
  return tmp;
}
string s;
int iter;
string get_int() {
  int fiter = iter;
  for (; iter < s.length() && s[iter] >= '0' && s[iter] <= '9'; iter++)
    ;
  return s.substr(fiter, iter - fiter);
}
node get_sum(const string &l, const string &r) {
  int la = l.length(), lb = r.length();
  if (la == lb) {
    string m = r - l;
    int v = mod_int(m, mo - 1);
    int base = pw[la],
        ps = (fpm(base, v + 1) - 1) * 1ll * fpm(base - 1, mo - 2) % mo;
    int val = (mod_int(m, mo) * 1ll * fpm(base, v + 1) % mo - (ps - 1)) *
              fpm(base - 1, mo - 2) % mo;
    return node(fpm(base, v + 1), (mod_int(r, mo) * 1ll * ps - val) % mo);
  } else {
    node ans = get_sum(l, string(la, '9'));
    for (++la; la < lb; la++) {
      int v = ((pw2[la] - 1 - pw2[la - 1]) % (mo - 1) + (mo - 1)) % (mo - 1);
      int base = pw[la],
          ps = (fpm(base, v + 1) - 1) * 1ll * fpm(base - 1, mo - 2) % mo;
      int mod_mo = ((pw[la] - 1 - pw[la - 1]) % mo + mo) % mo;
      int val = (mod_mo * 1ll * fpm(base, v + 1) % mo - (ps - 1)) *
                fpm(base - 1, mo - 2) % mo;
      ans = ans + node(fpm(base, v + 1), ((pw[la] - 1) * 1ll * ps - val) % mo);
    }
    return ans + get_sum('1' + string(lb - 1, '0'), r);
  }
}
node solve() {
  string num = "";
  node tmp = node(num);
  for (; iter < s.length();) {
    if (isdigit(s[iter])) num = get_int();
    char ch = s[iter++];
    if (ch == '(') tmp = tmp + (solve() ^ num);
    if (ch == ')') return tmp + node(num);
    if (ch == '+') tmp = tmp + node(num);
    if (ch == '-') {
      string num1 = get_int();
      tmp = tmp + get_sum(num, num1);
    }
    num = "";
  }
  return tmp + node(num);
}
int main() {
  cin >> s;
  s = "(" + s + ")";
  pw[0] = pw2[0] = 1;
  for (int i = 1; i <= s.length(); i++)
    pw[i] = pw[i - 1] * 10ll % mo, pw2[i] = pw2[i - 1] * 10ll % (mo - 1);
  iter = 0;
  cout << (solve().v + mo) % mo << endl;
  return 0;
}

```