#include <bits/stdc++.h>
using namespace std;
vector<char> opers;
int modulo(1e9 + 7);
int pw(int x, int n) {
  int res(1);
  while (n) {
    if (n & 1) res = (long long)res * x % modulo;
    x = (long long)x * x % modulo;
    n /= 2;
  }
  return res;
}
inline bool isDigit(char c) { return c >= '0' && c <= '9'; }
const int N(111111);
char st[N];
struct Opad {
  string str;
  int val, mul;
  Opad() {
    val = 0;
    mul = 1;
  }
};
vector<Opad> opads;
void operate() {
  Opad o1, o2;
  o2 = opads.back();
  opads.pop_back();
  o1 = opads.back();
  opads.pop_back();
  if (opers.back() == '+') {
    Opad res;
    res.val = ((long long)o1.val * o2.mul + o2.val) % modulo;
    res.mul = (long long)o1.mul * o2.mul % modulo;
    opads.push_back(res);
  } else {
    Opad res;
    for (int i((int)o1.str.size() - 1); i >= 0; i--) {
      for (int j(0); j < (int)o1.str[i] - '0'; j++) {
        res.val = ((long long)res.val * o2.mul + o2.val) % modulo;
        res.mul = ((long long)res.mul * o2.mul) % modulo;
      }
      int mul(o2.mul), add(o2.val);
      for (int j(0); j < 9; j++) {
        o2.mul = ((long long)mul * o2.mul) % modulo;
        o2.val = ((long long)mul * o2.val + add) % modulo;
      }
    }
    opads.push_back(res);
  }
  opers.pop_back();
}
Opad calc(const string& a) {
  Opad res;
  res.str = a;
  for (int i(0); i < (int)a.size(); i++) {
    res.mul = res.mul * 10ll % modulo;
    res.val = (res.val * 10ll + a[i] - '0') % modulo;
  }
  return res;
}
Opad calc(const string& le, const string& ri) {
  Opad res;
  Opad a(calc(le)), b(calc(ri));
  int phil(0), phir(0);
  for (int i(0); i < (int)le.size(); i++) {
    phil = ((long long)phil * 10ll + le[i] - '0') % (modulo - 1);
  }
  for (int i(0); i < (int)ri.size(); i++) {
    phir = ((long long)phir * 10ll + ri[i] - '0') % (modulo - 1);
  }
  int cur(1), curphi(1);
  for (int i(1); i < le.size(); i++) {
    cur = cur * 10ll % modulo;
    curphi = curphi * 10ll % (modulo - 1);
  }
  for (int len(le.size()); len <= ri.size(); len++) {
    int leval, rival, lephi, riphi;
    if (len == le.size()) {
      leval = a.val;
      lephi = phil;
    } else {
      leval = cur;
      lephi = curphi;
    }
    if (len == ri.size()) {
      rival = b.val;
      riphi = phir;
    } else {
      rival = (cur * 10ll + modulo - 1) % modulo;
      riphi = (curphi * 10ll + modulo - 2) % (modulo - 1);
    }
    int bs(pw(10, len));
    int val = (((rival + 1ll) *
                    ((pw(bs, (riphi - lephi + modulo) % (modulo - 1)) - 1ll +
                      modulo) *
                     pw(bs - 1, modulo - 2) % modulo) %
                    modulo -
                ((rival - leval + 1ll + modulo) *
                     pw(bs, (riphi - lephi + 1 + modulo) % (modulo - 1)) -
                 (rival - leval + 2ll + modulo) *
                     pw(bs, (riphi - lephi + modulo) % (modulo - 1)) +
                 1) %
                    modulo * pw(bs - 1, modulo - 2) % modulo *
                    pw(bs - 1, modulo - 2) % modulo) +
               modulo) %
              modulo;
    int mul = pw(bs, (riphi - lephi + modulo) % (modulo - 1));
    res.val = ((long long)res.val * mul + val) % modulo;
    res.mul = (long long)res.mul * mul % modulo;
    cur = cur * 10ll % modulo;
    curphi = curphi * 10ll % (modulo - 1);
  }
  return res;
}
int main() {
  scanf("%s", st);
  int len(strlen(st));
  for (int i(0); i < len; i++) {
    if (isDigit(st[i])) {
      string s;
      int j(i);
      for (; isDigit(st[j]); j++) s.push_back(st[j]);
      if (st[j] == '-') {
        string t;
        for (j++; isDigit(st[j]); j++) t.push_back(st[j]);
        opads.push_back(calc(s, t));
      } else {
        opads.push_back(calc(s));
      }
      i = j - 1;
    } else if (st[i] == '(') {
      opers.push_back('(');
    } else if (st[i] == '+') {
      opers.push_back('+');
    } else if (st[i] == ')') {
      while (opers.back() != '(') {
        operate();
      }
      operate();
    }
  }
  while (opers.size()) operate();
  cout << opads.back().val << endl;
}

### 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;
vector<char> opers;
int modulo(1e9 + 7);
int pw(int x, int n) {
  int res(1);
  while (n) {
    if (n & 1) res = (long long)res * x % modulo;
    x = (long long)x * x % modulo;
    n /= 2;
  }
  return res;
}
inline bool isDigit(char c) { return c >= '0' && c <= '9'; }
const int N(111111);
char st[N];
struct Opad {
  string str;
  int val, mul;
  Opad() {
    val = 0;
    mul = 1;
  }
};
vector<Opad> opads;
void operate() {
  Opad o1, o2;
  o2 = opads.back();
  opads.pop_back();
  o1 = opads.back();
  opads.pop_back();
  if (opers.back() == '+') {
    Opad res;
    res.val = ((long long)o1.val * o2.mul + o2.val) % modulo;
    res.mul = (long long)o1.mul * o2.mul % modulo;
    opads.push_back(res);
  } else {
    Opad res;
    for (int i((int)o1.str.size() - 1); i >= 0; i--) {
      for (int j(0); j < (int)o1.str[i] - '0'; j++) {
        res.val = ((long long)res.val * o2.mul + o2.val) % modulo;
        res.mul = ((long long)res.mul * o2.mul) % modulo;
      }
      int mul(o2.mul), add(o2.val);
      for (int j(0); j < 9; j++) {
        o2.mul = ((long long)mul * o2.mul) % modulo;
        o2.val = ((long long)mul * o2.val + add) % modulo;
      }
    }
    opads.push_back(res);
  }
  opers.pop_back();
}
Opad calc(const string& a) {
  Opad res;
  res.str = a;
  for (int i(0); i < (int)a.size(); i++) {
    res.mul = res.mul * 10ll % modulo;
    res.val = (res.val * 10ll + a[i] - '0') % modulo;
  }
  return res;
}
Opad calc(const string& le, const string& ri) {
  Opad res;
  Opad a(calc(le)), b(calc(ri));
  int phil(0), phir(0);
  for (int i(0); i < (int)le.size(); i++) {
    phil = ((long long)phil * 10ll + le[i] - '0') % (modulo - 1);
  }
  for (int i(0); i < (int)ri.size(); i++) {
    phir = ((long long)phir * 10ll + ri[i] - '0') % (modulo - 1);
  }
  int cur(1), curphi(1);
  for (int i(1); i < le.size(); i++) {
    cur = cur * 10ll % modulo;
    curphi = curphi * 10ll % (modulo - 1);
  }
  for (int len(le.size()); len <= ri.size(); len++) {
    int leval, rival, lephi, riphi;
    if (len == le.size()) {
      leval = a.val;
      lephi = phil;
    } else {
      leval = cur;
      lephi = curphi;
    }
    if (len == ri.size()) {
      rival = b.val;
      riphi = phir;
    } else {
      rival = (cur * 10ll + modulo - 1) % modulo;
      riphi = (curphi * 10ll + modulo - 2) % (modulo - 1);
    }
    int bs(pw(10, len));
    int val = (((rival + 1ll) *
                    ((pw(bs, (riphi - lephi + modulo) % (modulo - 1)) - 1ll +
                      modulo) *
                     pw(bs - 1, modulo - 2) % modulo) %
                    modulo -
                ((rival - leval + 1ll + modulo) *
                     pw(bs, (riphi - lephi + 1 + modulo) % (modulo - 1)) -
                 (rival - leval + 2ll + modulo) *
                     pw(bs, (riphi - lephi + modulo) % (modulo - 1)) +
                 1) %
                    modulo * pw(bs - 1, modulo - 2) % modulo *
                    pw(bs - 1, modulo - 2) % modulo) +
               modulo) %
              modulo;
    int mul = pw(bs, (riphi - lephi + modulo) % (modulo - 1));
    res.val = ((long long)res.val * mul + val) % modulo;
    res.mul = (long long)res.mul * mul % modulo;
    cur = cur * 10ll % modulo;
    curphi = curphi * 10ll % (modulo - 1);
  }
  return res;
}
int main() {
  scanf("%s", st);
  int len(strlen(st));
  for (int i(0); i < len; i++) {
    if (isDigit(st[i])) {
      string s;
      int j(i);
      for (; isDigit(st[j]); j++) s.push_back(st[j]);
      if (st[j] == '-') {
        string t;
        for (j++; isDigit(st[j]); j++) t.push_back(st[j]);
        opads.push_back(calc(s, t));
      } else {
        opads.push_back(calc(s));
      }
      i = j - 1;
    } else if (st[i] == '(') {
      opers.push_back('(');
    } else if (st[i] == '+') {
      opers.push_back('+');
    } else if (st[i] == ')') {
      while (opers.back() != '(') {
        operate();
      }
      operate();
    }
  }
  while (opers.size()) operate();
  cout << opads.back().val << endl;
}

```