#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
long long MOD = 1e9 + 7, pw[MAXN], pw1[MAXN];
int jsum[MAXN], jmin[MAXN], jpar[MAXN], topar[MAXN];
string s;
long long fpow(long long base, long long exp) {
  long long result = 1;
  while (exp) {
    if (exp & 1) result = (result * base) % MOD;
    exp >>= 1;
    base = (base * base) % MOD;
  }
  return result;
}
long long sum(long long x, long long y, long long mod = MOD) {
  return (x + y) % mod;
}
long long sub(long long x, long long y, long long mod = MOD) {
  return (x - y + mod) % mod;
}
long long mul(long long x, long long y, long long mod = MOD) {
  return x * y % mod;
}
long long divv(long long x, long long y, long long mod = MOD) {
  return x * fpow(y, mod - 2) % mod;
}
struct num {
  long long len, val, val1;
  num(long long len, long long val, long long val1)
      : len(len), val(val), val1(val1) {}
  num() {}
  num concat(num x) {
    long long nw = sum(mul(val, x.len, MOD - 1), x.val, MOD - 1);
    return num(mul(len, x.len), sum(mul(val, x.len), x.val), nw);
  }
};
num ran[MAXN];
void preproc() {
  for (int i = 0, ThxDem = int(s.size()); i < ThxDem; ++i)
    jsum[i] = jmin[i] = jpar[i] = topar[i] = int(s.size());
  int dep = 0;
  stack<pair<int, int> > sum, mn, open;
  stack<int> par;
  for (int i = int(s.size()) - 1; i >= 0; i--) {
    if (s[i] == ')') par.push(i), dep++;
    if (s[i] == '(') {
      while (int(sum.size()) && sum.top().second == dep) sum.pop();
      while (int(mn.size()) && mn.top().second == dep) mn.pop();
      topar[i] = par.top();
      par.pop();
      dep--;
      open.push({i, dep});
    }
    if (int(open.size()) && open.top().second == dep)
      jpar[i] = open.top().first;
    if (int(sum.size()) && sum.top().second == dep) jsum[i] = sum.top().first;
    if (int(mn.size()) && mn.top().second == dep) jmin[i] = mn.top().first;
    if (s[i] == '+') sum.push({i, dep});
    if (s[i] == '-') mn.push({i, dep});
  }
}
num getnum(int l, int r) {
  num ans(pw[r - l + 1], 0, 0);
  for (int i = l, ThxDem = r + 1; i < ThxDem; ++i) {
    ans.val = sum(mul(ans.val, 10), s[i] - '0');
    ans.val1 = sum(mul(ans.val1, 10, MOD - 1), s[i] - '0', MOD - 1);
  }
  return ans;
}
num range(num x, num y) {
  long long rl1 = sum(sub(y.val, x.val), 1);
  long long rl2 = sum(sub(y.val, x.val), 2);
  long long rl11 = sum(sub(y.val1, x.val1, MOD - 1), 1, MOD - 1);
  long long rl21 = sum(sub(y.val1, x.val1, MOD - 1), 2, MOD - 1);
  num ans(fpow(x.len, rl11), 0, 0);
  long long v = sub(fpow(x.len, rl11), 1);
  v = mul(sum(y.val, 1), v);
  v = divv(v, sub(x.len, 1));
  long long v2 = mul(rl1, fpow(x.len, rl21));
  long long v3 = mul(rl2, fpow(x.len, rl11));
  v2 = divv(sum(sub(v2, v3), 1), fpow(sub(x.len, 1), 2));
  v = sub(v, v2);
  ans.val = v;
  ans.val1 = v;
  return ans;
}
num get_ran(int l1, int r1, int l2, int r2) {
  int lle = r1 - l1 + 1, lri = r2 - l2 + 1;
  num x = getnum(l1, r1), y = getnum(l2, r2);
  if (lle == lri) return range(x, y);
  num fir(pw[lle], sub(pw[lle], 1), sub(pw1[lle], 1, MOD - 1));
  num sec(pw[lri], pw[lri - 1], pw1[lri - 1]);
  num ans = range(x, fir);
  num lst = range(sec, y);
  for (int i = lle + 1, ThxDem = lri; i < ThxDem; ++i) ans = ans.concat(ran[i]);
  ans = ans.concat(lst);
  return ans;
}
num copy(num x, num y) {
  num ans(fpow(y.len, x.val1), 0, 0);
  if (y.len % MOD == 1)
    ans.val = x.val, ans.val1 = x.val1;
  else {
    ans.val = divv(sub(fpow(y.len, x.val1), 1), sub(y.len, 1));
    ans.val1 = ans.val % (MOD - 1);
  }
  ans.val = mul(ans.val, y.val);
  ans.val1 = mul(ans.val1, y.val1, MOD - 1);
  return ans;
}
num solve(int l, int r) {
  if (l > r) return num(1, 0, 0);
  if (jsum[l] <= r) {
    num lef = solve(l, jsum[l] - 1), rig = solve(jsum[l] + 1, r);
    return lef.concat(rig);
  }
  if (jmin[l] <= r) {
    num lef = solve(l, jmin[l] - 1), rig = solve(jmin[l] + 1, r);
    return get_ran(l, jmin[l] - 1, jmin[l] + 1, r);
  }
  if (jpar[l] <= r) {
    num lef = solve(l, jpar[l] - 1), rig = solve(jpar[l] + 1, r - 1);
    return copy(lef, rig);
  }
  return getnum(l, r);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  pw[0] = 1;
  for (int i = 1, ThxDem = MAXN; i < ThxDem; ++i) pw[i] = mul(10, pw[i - 1]);
  pw1[0] = 1;
  for (int i = 1, ThxDem = MAXN; i < ThxDem; ++i)
    pw1[i] = mul(10, pw1[i - 1], MOD - 1);
  cin >> s;
  for (int i = 2, ThxDem = int(s.size()) + 1; i < ThxDem; ++i) {
    num l(pw[i], pw[i - 1], pw1[i - 1]);
    num r(pw[i], sub(pw[i], 1), sub(pw1[i], 1, MOD - 1));
    ran[i] = range(l, r);
  }
  preproc();
  num ans = solve(0, int(s.size()) - 1);
  cout << ans.val << "\n";
}

### Prompt

Generate 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 = 100010;
long long MOD = 1e9 + 7, pw[MAXN], pw1[MAXN];
int jsum[MAXN], jmin[MAXN], jpar[MAXN], topar[MAXN];
string s;
long long fpow(long long base, long long exp) {
  long long result = 1;
  while (exp) {
    if (exp & 1) result = (result * base) % MOD;
    exp >>= 1;
    base = (base * base) % MOD;
  }
  return result;
}
long long sum(long long x, long long y, long long mod = MOD) {
  return (x + y) % mod;
}
long long sub(long long x, long long y, long long mod = MOD) {
  return (x - y + mod) % mod;
}
long long mul(long long x, long long y, long long mod = MOD) {
  return x * y % mod;
}
long long divv(long long x, long long y, long long mod = MOD) {
  return x * fpow(y, mod - 2) % mod;
}
struct num {
  long long len, val, val1;
  num(long long len, long long val, long long val1)
      : len(len), val(val), val1(val1) {}
  num() {}
  num concat(num x) {
    long long nw = sum(mul(val, x.len, MOD - 1), x.val, MOD - 1);
    return num(mul(len, x.len), sum(mul(val, x.len), x.val), nw);
  }
};
num ran[MAXN];
void preproc() {
  for (int i = 0, ThxDem = int(s.size()); i < ThxDem; ++i)
    jsum[i] = jmin[i] = jpar[i] = topar[i] = int(s.size());
  int dep = 0;
  stack<pair<int, int> > sum, mn, open;
  stack<int> par;
  for (int i = int(s.size()) - 1; i >= 0; i--) {
    if (s[i] == ')') par.push(i), dep++;
    if (s[i] == '(') {
      while (int(sum.size()) && sum.top().second == dep) sum.pop();
      while (int(mn.size()) && mn.top().second == dep) mn.pop();
      topar[i] = par.top();
      par.pop();
      dep--;
      open.push({i, dep});
    }
    if (int(open.size()) && open.top().second == dep)
      jpar[i] = open.top().first;
    if (int(sum.size()) && sum.top().second == dep) jsum[i] = sum.top().first;
    if (int(mn.size()) && mn.top().second == dep) jmin[i] = mn.top().first;
    if (s[i] == '+') sum.push({i, dep});
    if (s[i] == '-') mn.push({i, dep});
  }
}
num getnum(int l, int r) {
  num ans(pw[r - l + 1], 0, 0);
  for (int i = l, ThxDem = r + 1; i < ThxDem; ++i) {
    ans.val = sum(mul(ans.val, 10), s[i] - '0');
    ans.val1 = sum(mul(ans.val1, 10, MOD - 1), s[i] - '0', MOD - 1);
  }
  return ans;
}
num range(num x, num y) {
  long long rl1 = sum(sub(y.val, x.val), 1);
  long long rl2 = sum(sub(y.val, x.val), 2);
  long long rl11 = sum(sub(y.val1, x.val1, MOD - 1), 1, MOD - 1);
  long long rl21 = sum(sub(y.val1, x.val1, MOD - 1), 2, MOD - 1);
  num ans(fpow(x.len, rl11), 0, 0);
  long long v = sub(fpow(x.len, rl11), 1);
  v = mul(sum(y.val, 1), v);
  v = divv(v, sub(x.len, 1));
  long long v2 = mul(rl1, fpow(x.len, rl21));
  long long v3 = mul(rl2, fpow(x.len, rl11));
  v2 = divv(sum(sub(v2, v3), 1), fpow(sub(x.len, 1), 2));
  v = sub(v, v2);
  ans.val = v;
  ans.val1 = v;
  return ans;
}
num get_ran(int l1, int r1, int l2, int r2) {
  int lle = r1 - l1 + 1, lri = r2 - l2 + 1;
  num x = getnum(l1, r1), y = getnum(l2, r2);
  if (lle == lri) return range(x, y);
  num fir(pw[lle], sub(pw[lle], 1), sub(pw1[lle], 1, MOD - 1));
  num sec(pw[lri], pw[lri - 1], pw1[lri - 1]);
  num ans = range(x, fir);
  num lst = range(sec, y);
  for (int i = lle + 1, ThxDem = lri; i < ThxDem; ++i) ans = ans.concat(ran[i]);
  ans = ans.concat(lst);
  return ans;
}
num copy(num x, num y) {
  num ans(fpow(y.len, x.val1), 0, 0);
  if (y.len % MOD == 1)
    ans.val = x.val, ans.val1 = x.val1;
  else {
    ans.val = divv(sub(fpow(y.len, x.val1), 1), sub(y.len, 1));
    ans.val1 = ans.val % (MOD - 1);
  }
  ans.val = mul(ans.val, y.val);
  ans.val1 = mul(ans.val1, y.val1, MOD - 1);
  return ans;
}
num solve(int l, int r) {
  if (l > r) return num(1, 0, 0);
  if (jsum[l] <= r) {
    num lef = solve(l, jsum[l] - 1), rig = solve(jsum[l] + 1, r);
    return lef.concat(rig);
  }
  if (jmin[l] <= r) {
    num lef = solve(l, jmin[l] - 1), rig = solve(jmin[l] + 1, r);
    return get_ran(l, jmin[l] - 1, jmin[l] + 1, r);
  }
  if (jpar[l] <= r) {
    num lef = solve(l, jpar[l] - 1), rig = solve(jpar[l] + 1, r - 1);
    return copy(lef, rig);
  }
  return getnum(l, r);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  pw[0] = 1;
  for (int i = 1, ThxDem = MAXN; i < ThxDem; ++i) pw[i] = mul(10, pw[i - 1]);
  pw1[0] = 1;
  for (int i = 1, ThxDem = MAXN; i < ThxDem; ++i)
    pw1[i] = mul(10, pw1[i - 1], MOD - 1);
  cin >> s;
  for (int i = 2, ThxDem = int(s.size()) + 1; i < ThxDem; ++i) {
    num l(pw[i], pw[i - 1], pw1[i - 1]);
    num r(pw[i], sub(pw[i], 1), sub(pw1[i], 1, MOD - 1));
    ran[i] = range(l, r);
  }
  preproc();
  num ans = solve(0, int(s.size()) - 1);
  cout << ans.val << "\n";
}

```