#include <bits/stdc++.h>
using namespace std;
int expo(int a, int b) {
  if (!b) return 1;
  if (b & 1)
    return 1LL * a * expo(1LL * a * a % 1000000007, b >> 1) % 1000000007;
  return expo(1LL * a * a % 1000000007, b >> 1);
}
int inv_mod(int x) { return expo(x, 1000000007 - 2); }
int i2 = inv_mod(2), i10 = inv_mod(10);
struct number {
  int v, p;
  number(int v, int p) : v(v), p(p) {}
};
number concat(number a, number b) {
  return number((1LL * a.v * b.p + b.v) % 1000000007,
                1LL * a.p * b.p % 1000000007);
}
int remainder(string& str, int mod) {
  int rem = 0;
  for (char c : str) {
    assert(c >= '0' && c <= '9');
    rem = (10LL * rem + (c - '0')) % mod;
  }
  return rem;
}
number parse(string& str, int& pos);
number c(int l, int r, int k, int p10eL, int rem_l, int rem_r) {
  int prod = expo(p10eL, (rem_r - 1 + 1000000007 - 1) % (1000000007 - 1));
  int FR, FL;
  if (k == 1) {
    FR = 1LL * r * (r + 1) % 1000000007 * i2 % 1000000007;
    FL = 1LL * l * (l - 1 + 1000000007) % 1000000007 * i2 % 1000000007;
  } else {
    int kr = expo(k, rem_r),
        kl1 = expo(k, (rem_l - 1 + 1000000007 - 1) % (1000000007 - 1)),
        ik1 = inv_mod((k - 1 + 1000000007) % 1000000007);
    FR = (1LL * r * kr % 1000000007 * ik1 % 1000000007 -
          1LL * kr * ik1 % 1000000007 * ik1 % 1000000007 + 1000000007) %
         1000000007;
    FL = (1LL * (l - 1 + 1000000007) * kl1 % 1000000007 * ik1 % 1000000007 -
          1LL * kl1 * ik1 % 1000000007 * ik1 % 1000000007 + 1000000007) %
         1000000007;
  }
  return number(
      1LL * prod * (FR - FL + 1000000007) % 1000000007,
      expo(p10eL, (rem_r - rem_l + 1 + 1000000007 - 1) % (1000000007 - 1)));
}
number C(number l, number r, string& str_l, string& str_r) {
  if (str_l.size() == str_r.size()) {
    return c(l.v, r.v, inv_mod(l.p), l.p, remainder(str_l, 1000000007 - 1),
             remainder(str_r, 1000000007 - 1));
  } else {
    int mid = 0, mid_rem = 0, rem_l = remainder(str_l, 1000000007 - 1),
        rem_r = remainder(str_r, 1000000007 - 1);
    for (char c : str_l) {
      mid = (10LL * mid + 9) % 1000000007;
      mid_rem = (10LL * mid_rem + 9) % (1000000007 - 1);
    }
    int k = inv_mod(l.p), p10eL = l.p;
    number ret = c(l.v, mid, k, p10eL, rem_l, mid_rem);
    for (int i = str_l.size() + 1; i < str_r.size(); i++) {
      k = 1LL * k * i10 % 1000000007;
      p10eL = 10LL * p10eL % 1000000007;
      l.v = (mid + 1) % 1000000007;
      rem_l = (mid_rem + 1) % (1000000007 - 1);
      mid = (10LL * mid + 9) % 1000000007;
      mid_rem = (10LL * mid_rem + 9) % (1000000007 - 1);
      ret = concat(ret, c(l.v, mid, k, p10eL, rem_l, mid_rem));
    }
    k = 1LL * k * i10 % 1000000007;
    p10eL = 10LL * p10eL % 1000000007;
    l.v = (mid + 1) % 1000000007;
    rem_l = (mid_rem + 1) % (1000000007 - 1);
    ret = concat(ret, c(l.v, r.v, k, p10eL, rem_l, rem_r));
    return ret;
  }
}
number rep(number x, number y, string& str_x) {
  if (y.p == 1) {
    return number(1LL * x.v * y.v % 1000000007, 1);
  } else {
    int rem = remainder(str_x, 1000000007 - 1);
    int new_pot = expo(y.p, rem);
    return number(1LL * y.v * ((new_pot - 1 + 1000000007) % 1000000007) %
                      1000000007 *
                      inv_mod((y.p - 1 + 1000000007) % 1000000007) % 1000000007,
                  new_pot);
  }
}
number parse_term(string& str) {
  number a1(0, 1), a2(0, 1);
  int which = 0;
  string t1, t2;
  for (char c : str) {
    if (which == 0) {
      if (c == '-')
        which = 1;
      else if (c == '(')
        which = 2;
      else {
        assert(c >= '0' && c <= '9');
        a1 = concat(a1, number(c - '0', 10));
        t1 += c;
      }
    } else if (which == 1) {
      assert(c >= '0' && c <= '9');
      a2 = concat(a2, number(c - '0', 10));
      t2 += c;
    } else {
      t2 += c;
    }
  }
  if (which == 0)
    return a1;
  else if (which == 1)
    return C(a1, a2, t1, t2);
  else {
    assert(false);
  }
}
number parse(string& str, int& pos) {
  string tmp;
  number ret(0, 1), a1(0, 1), a2(0, 1);
  int brackets = 0;
  for (; pos < str.size();) {
    char c = str[pos];
    if (c == '+' && brackets == 0) {
      ret = concat(ret, parse_term(tmp));
      tmp = "";
      pos++;
    } else {
      if (c == '(') {
        a1 = parse_term(tmp);
        a2 = parse(str, ++pos);
        ret = concat(ret, rep(a1, a2, tmp));
        tmp = "";
      } else if (c == ')') {
        pos++;
        break;
      } else {
        tmp += c;
        pos++;
      }
    }
  }
  ret = concat(ret, parse_term(tmp));
  return ret;
}
char s[100010];
string str;
int main() {
  scanf("%s", s);
  str = s;
  int pos = 0;
  number ans = parse(str, pos);
  printf("%d\n", ans.v);
  return 0;
}

### Prompt

Your challenge is to write 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;
int expo(int a, int b) {
  if (!b) return 1;
  if (b & 1)
    return 1LL * a * expo(1LL * a * a % 1000000007, b >> 1) % 1000000007;
  return expo(1LL * a * a % 1000000007, b >> 1);
}
int inv_mod(int x) { return expo(x, 1000000007 - 2); }
int i2 = inv_mod(2), i10 = inv_mod(10);
struct number {
  int v, p;
  number(int v, int p) : v(v), p(p) {}
};
number concat(number a, number b) {
  return number((1LL * a.v * b.p + b.v) % 1000000007,
                1LL * a.p * b.p % 1000000007);
}
int remainder(string& str, int mod) {
  int rem = 0;
  for (char c : str) {
    assert(c >= '0' && c <= '9');
    rem = (10LL * rem + (c - '0')) % mod;
  }
  return rem;
}
number parse(string& str, int& pos);
number c(int l, int r, int k, int p10eL, int rem_l, int rem_r) {
  int prod = expo(p10eL, (rem_r - 1 + 1000000007 - 1) % (1000000007 - 1));
  int FR, FL;
  if (k == 1) {
    FR = 1LL * r * (r + 1) % 1000000007 * i2 % 1000000007;
    FL = 1LL * l * (l - 1 + 1000000007) % 1000000007 * i2 % 1000000007;
  } else {
    int kr = expo(k, rem_r),
        kl1 = expo(k, (rem_l - 1 + 1000000007 - 1) % (1000000007 - 1)),
        ik1 = inv_mod((k - 1 + 1000000007) % 1000000007);
    FR = (1LL * r * kr % 1000000007 * ik1 % 1000000007 -
          1LL * kr * ik1 % 1000000007 * ik1 % 1000000007 + 1000000007) %
         1000000007;
    FL = (1LL * (l - 1 + 1000000007) * kl1 % 1000000007 * ik1 % 1000000007 -
          1LL * kl1 * ik1 % 1000000007 * ik1 % 1000000007 + 1000000007) %
         1000000007;
  }
  return number(
      1LL * prod * (FR - FL + 1000000007) % 1000000007,
      expo(p10eL, (rem_r - rem_l + 1 + 1000000007 - 1) % (1000000007 - 1)));
}
number C(number l, number r, string& str_l, string& str_r) {
  if (str_l.size() == str_r.size()) {
    return c(l.v, r.v, inv_mod(l.p), l.p, remainder(str_l, 1000000007 - 1),
             remainder(str_r, 1000000007 - 1));
  } else {
    int mid = 0, mid_rem = 0, rem_l = remainder(str_l, 1000000007 - 1),
        rem_r = remainder(str_r, 1000000007 - 1);
    for (char c : str_l) {
      mid = (10LL * mid + 9) % 1000000007;
      mid_rem = (10LL * mid_rem + 9) % (1000000007 - 1);
    }
    int k = inv_mod(l.p), p10eL = l.p;
    number ret = c(l.v, mid, k, p10eL, rem_l, mid_rem);
    for (int i = str_l.size() + 1; i < str_r.size(); i++) {
      k = 1LL * k * i10 % 1000000007;
      p10eL = 10LL * p10eL % 1000000007;
      l.v = (mid + 1) % 1000000007;
      rem_l = (mid_rem + 1) % (1000000007 - 1);
      mid = (10LL * mid + 9) % 1000000007;
      mid_rem = (10LL * mid_rem + 9) % (1000000007 - 1);
      ret = concat(ret, c(l.v, mid, k, p10eL, rem_l, mid_rem));
    }
    k = 1LL * k * i10 % 1000000007;
    p10eL = 10LL * p10eL % 1000000007;
    l.v = (mid + 1) % 1000000007;
    rem_l = (mid_rem + 1) % (1000000007 - 1);
    ret = concat(ret, c(l.v, r.v, k, p10eL, rem_l, rem_r));
    return ret;
  }
}
number rep(number x, number y, string& str_x) {
  if (y.p == 1) {
    return number(1LL * x.v * y.v % 1000000007, 1);
  } else {
    int rem = remainder(str_x, 1000000007 - 1);
    int new_pot = expo(y.p, rem);
    return number(1LL * y.v * ((new_pot - 1 + 1000000007) % 1000000007) %
                      1000000007 *
                      inv_mod((y.p - 1 + 1000000007) % 1000000007) % 1000000007,
                  new_pot);
  }
}
number parse_term(string& str) {
  number a1(0, 1), a2(0, 1);
  int which = 0;
  string t1, t2;
  for (char c : str) {
    if (which == 0) {
      if (c == '-')
        which = 1;
      else if (c == '(')
        which = 2;
      else {
        assert(c >= '0' && c <= '9');
        a1 = concat(a1, number(c - '0', 10));
        t1 += c;
      }
    } else if (which == 1) {
      assert(c >= '0' && c <= '9');
      a2 = concat(a2, number(c - '0', 10));
      t2 += c;
    } else {
      t2 += c;
    }
  }
  if (which == 0)
    return a1;
  else if (which == 1)
    return C(a1, a2, t1, t2);
  else {
    assert(false);
  }
}
number parse(string& str, int& pos) {
  string tmp;
  number ret(0, 1), a1(0, 1), a2(0, 1);
  int brackets = 0;
  for (; pos < str.size();) {
    char c = str[pos];
    if (c == '+' && brackets == 0) {
      ret = concat(ret, parse_term(tmp));
      tmp = "";
      pos++;
    } else {
      if (c == '(') {
        a1 = parse_term(tmp);
        a2 = parse(str, ++pos);
        ret = concat(ret, rep(a1, a2, tmp));
        tmp = "";
      } else if (c == ')') {
        pos++;
        break;
      } else {
        tmp += c;
        pos++;
      }
    }
  }
  ret = concat(ret, parse_term(tmp));
  return ret;
}
char s[100010];
string str;
int main() {
  scanf("%s", s);
  str = s;
  int pos = 0;
  number ans = parse(str, pos);
  printf("%d\n", ans.v);
  return 0;
}

```