#include <bits/stdc++.h>
namespace sash {
using namespace std;
template <class T>
using v = vector<T>;
template <class T>
using vv = vector<v<T>>;
template <class T>
using pri = priority_queue<T>;
template <class T>
using rpi = priority_queue<T, v<T>, greater<T>>;
using vvb = v<vector<bool>>;
using vs = v<string>;
using vvi = v<vector<long long>>;
using vc = v<char>;
template <class T>
inline void rd(T& a) {
  cin >> a;
}
template <class T>
inline void rd(v<T>& a, long long n) {
  T x;
  for (long long i = (long long)0; i < (long long)n; i++) {
    cin >> x;
    a[i] = x;
  }
}
template <class T>
inline void rd(vv<T>& a, long long n, long long m) {
  for (long long i = (long long)0; i < (long long)n; i++) {
    rd(a[i], m);
  }
}
template <class T, class... Args>
inline void rd(T& a, Args&... args) {
  cin >> a;
  rd(args...);
}
template <class T>
inline void print(T a) {
  cout << (a) << '\n';
}
template <class T>
inline void print(v<T> a) {
  for (auto x : a) cout << (x) << ' ';
  cout << '\n';
}
template <class T>
inline void print(vv<T> a) {
  for (auto x : a) print(x);
}
inline long long mintwo(long long n) { return __builtin_ctzll(n); }
inline long long maxtwo(long long n) { return (long long)log2(n); }
inline long long onebits(long long n) { return __builtin_popcountll(n); }
inline long double pdiv(long long a, long long b) {
  return (1.0 * (a)) / (1.0 * (b));
}
inline void chxor(long long& a, long long b) { a = a ^ b; }
inline void mangekyo();
inline void subl() {}
long double _c;
using i32 = int32_t;
template <class T>
inline long long sum(v<T> a) {
  long long s = 0;
  for (auto x : a) s += x;
  return s;
}
template <class T>
inline T min(v<T> a) {
  return *min_element(a.begin(), a.end());
}
template <class T>
inline T max(v<T> a) {
  return *max_element(a.begin(), a.end());
}
template <class T, class U>
inline void chmax(T& a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
inline void chmin(T& a, U b) {
  if (a > b) a = b;
}
template <class T, class U>
inline T max(T a, U b) {
  return a > b ? a : b;
}
template <class T, class U>
inline T min(T a, U b) {
  return a < b ? a : b;
}
template <class T>
long long POW(T& a, long long b) {
  long long r = 1, p = a;
  for (long long e = b; e > 0; e >>= 1, p *= p) r *= (e & 1) ? p : 1;
  return r;
}
template <class T>
v<T> pre_sum(v<T> a) {
  for (long long i = (long long)1; i < (long long)a.size(); i++)
    a[i] += a[i - 1];
  return a;
}
template <class T>
v<T> suf_sum(v<T> a) {
  for (long long i = (long long)a.size() - 1 - 1; i > (long long)0 - 1; i--)
    a[i] += a[i + 1];
  return a;
}
void factfill(vector<long long>& fact, long long n) {
  fact.resize(n + 1, 1);
  for (long long i = (long long)1; i < (long long)n + 1; i++)
    fact[i] = fact[i - 1] * i;
}
void yes() { print("YES"); }
void no() { print("NO"); }
const long long inf = 1e9, mod = 1e9 + 7;
}  // namespace sash
using namespace sash;
i32 main() {
  mangekyo();
  string s;
  rd(s);
  long long n = s.size();
  reverse((s).begin(), (s).end());
  long long pw = 1, su = 0, ans = 0;
  for (long long i = (long long)0; i < (long long)n; i++) {
    ans =
        (ans + (n - i - 1) * (n - i) / 2 % mod * pw % mod * (s[i] - '0')) % mod;
    ans = (ans + (s[i] - '0') * su) % mod;
    su = (su + pw * (i + 1)) % mod;
    pw = pw * 10 % mod;
  }
  print(ans);
  cerr << "Time: " << ((clock() - _c) / CLOCKS_PER_SEC);
  return 0;
}
void sash::mangekyo() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  srand(time(NULL));
  _c = clock();
}

### Prompt

Generate a Cpp solution to the following problem:

Sometimes it is not easy to come to an agreement in a bargain. Right now Sasha and Vova can't come to an agreement: Sasha names a price as high as possible, then Vova wants to remove as many digits from the price as possible. In more details, Sasha names some integer price n, Vova removes a non-empty substring of (consecutive) digits from the price, the remaining digits close the gap, and the resulting integer is the price.

For example, is Sasha names 1213121, Vova can remove the substring 1312, and the result is 121.

It is allowed for result to contain leading zeros. If Vova removes all digits, the price is considered to be 0.

Sasha wants to come up with some constraints so that Vova can't just remove all digits, but he needs some arguments supporting the constraints. To start with, he wants to compute the sum of all possible resulting prices after Vova's move.

Help Sasha to compute this sum. Since the answer can be very large, print it modulo 10^9 + 7.

Input

The first and only line contains a single integer n (1 ≤ n < 10^{10^5}).

Output

In the only line print the required sum modulo 10^9 + 7.

Examples

Input


107


Output


42


Input


100500100500


Output


428101984

Note

Consider the first example.

Vova can choose to remove 1, 0, 7, 10, 07, or 107. The results are 07, 17, 10, 7, 1, 0. Their sum is 42.

### Response

```cpp
#include <bits/stdc++.h>
namespace sash {
using namespace std;
template <class T>
using v = vector<T>;
template <class T>
using vv = vector<v<T>>;
template <class T>
using pri = priority_queue<T>;
template <class T>
using rpi = priority_queue<T, v<T>, greater<T>>;
using vvb = v<vector<bool>>;
using vs = v<string>;
using vvi = v<vector<long long>>;
using vc = v<char>;
template <class T>
inline void rd(T& a) {
  cin >> a;
}
template <class T>
inline void rd(v<T>& a, long long n) {
  T x;
  for (long long i = (long long)0; i < (long long)n; i++) {
    cin >> x;
    a[i] = x;
  }
}
template <class T>
inline void rd(vv<T>& a, long long n, long long m) {
  for (long long i = (long long)0; i < (long long)n; i++) {
    rd(a[i], m);
  }
}
template <class T, class... Args>
inline void rd(T& a, Args&... args) {
  cin >> a;
  rd(args...);
}
template <class T>
inline void print(T a) {
  cout << (a) << '\n';
}
template <class T>
inline void print(v<T> a) {
  for (auto x : a) cout << (x) << ' ';
  cout << '\n';
}
template <class T>
inline void print(vv<T> a) {
  for (auto x : a) print(x);
}
inline long long mintwo(long long n) { return __builtin_ctzll(n); }
inline long long maxtwo(long long n) { return (long long)log2(n); }
inline long long onebits(long long n) { return __builtin_popcountll(n); }
inline long double pdiv(long long a, long long b) {
  return (1.0 * (a)) / (1.0 * (b));
}
inline void chxor(long long& a, long long b) { a = a ^ b; }
inline void mangekyo();
inline void subl() {}
long double _c;
using i32 = int32_t;
template <class T>
inline long long sum(v<T> a) {
  long long s = 0;
  for (auto x : a) s += x;
  return s;
}
template <class T>
inline T min(v<T> a) {
  return *min_element(a.begin(), a.end());
}
template <class T>
inline T max(v<T> a) {
  return *max_element(a.begin(), a.end());
}
template <class T, class U>
inline void chmax(T& a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
inline void chmin(T& a, U b) {
  if (a > b) a = b;
}
template <class T, class U>
inline T max(T a, U b) {
  return a > b ? a : b;
}
template <class T, class U>
inline T min(T a, U b) {
  return a < b ? a : b;
}
template <class T>
long long POW(T& a, long long b) {
  long long r = 1, p = a;
  for (long long e = b; e > 0; e >>= 1, p *= p) r *= (e & 1) ? p : 1;
  return r;
}
template <class T>
v<T> pre_sum(v<T> a) {
  for (long long i = (long long)1; i < (long long)a.size(); i++)
    a[i] += a[i - 1];
  return a;
}
template <class T>
v<T> suf_sum(v<T> a) {
  for (long long i = (long long)a.size() - 1 - 1; i > (long long)0 - 1; i--)
    a[i] += a[i + 1];
  return a;
}
void factfill(vector<long long>& fact, long long n) {
  fact.resize(n + 1, 1);
  for (long long i = (long long)1; i < (long long)n + 1; i++)
    fact[i] = fact[i - 1] * i;
}
void yes() { print("YES"); }
void no() { print("NO"); }
const long long inf = 1e9, mod = 1e9 + 7;
}  // namespace sash
using namespace sash;
i32 main() {
  mangekyo();
  string s;
  rd(s);
  long long n = s.size();
  reverse((s).begin(), (s).end());
  long long pw = 1, su = 0, ans = 0;
  for (long long i = (long long)0; i < (long long)n; i++) {
    ans =
        (ans + (n - i - 1) * (n - i) / 2 % mod * pw % mod * (s[i] - '0')) % mod;
    ans = (ans + (s[i] - '0') * su) % mod;
    su = (su + pw * (i + 1)) % mod;
    pw = pw * 10 % mod;
  }
  print(ans);
  cerr << "Time: " << ((clock() - _c) / CLOCKS_PER_SEC);
  return 0;
}
void sash::mangekyo() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  srand(time(NULL));
  _c = clock();
}

```