Problem: Let S(n) denote the number that represents the digits of n in sorted order. For example, S(1) = 1, S(5) = 5, S(50394) = 3459, S(353535) = 333555.

Given a number X, compute <image> modulo 109 + 7.

Input

The first line of input will contain the integer X (1 ≤ X ≤ 10700).

Output

Print a single integer, the answer to the question.

Examples

Input

21


Output

195


Input

345342


Output

390548434

Note

The first few values of S are 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 12. The sum of these values is 195. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long int lg = 22;
const long long int N = 1e5 + 5;
const long long int M = 162;
const long long int INF = 1e9 + 5;
const long long int mod = 1e9 + 7;
const double PI = 3.14159265358979323846;
template <typename T>
T power(T x, T y) {
  T ans = 1;
  while (y > 0) {
    if (y & 1LL) ans = (ans * x) % mod;
    y >>= 1LL;
    x = (x * x) % mod;
  }
  return ans % mod;
}
inline long long int mul(long long int a, long long int b) {
  return (a * 1ll * b) % mod;
}
inline long long int sub(long long int a, long long int b) {
  long long int c = a - b;
  if (c < 0) c += mod;
  return c;
}
inline long long int add(long long int a, long long int b) {
  long long int c = a + b;
  if (c > mod) c -= mod;
  return c;
}
inline long long int inv(long long int a) { return power(a, mod - 2); }
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long int n;
string r;
long long int powx[705], dp[705][2][11][705];
long long int Get(long long int idx, long long int val, long long int checker) {
  long long int valatIdx = r[idx] - '0';
  if (checker) {
    if (val > valatIdx) {
      return -1;
    }
    if (val == valatIdx) {
      return 1;
    }
    return 0;
  } else {
    return 0;
  }
}
long long int F(long long int idx, long long int checker, long long int dig,
                long long int pos) {
  long long int res = 0;
  if (idx == n) {
    return pos == 0;
  }
  if (dp[idx][checker][dig][pos] != -1) {
    return dp[idx][checker][dig][pos];
  }
  for (long long int i = 0; i <= 9; i++) {
    long long int newchecker = Get(idx, i, checker);
    if (newchecker == -1) {
      continue;
    }
    res = add(res, F(idx + 1, newchecker, dig, max(0LL, pos - (i >= dig))));
  }
  return dp[idx][checker][dig][pos] = res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> r;
  long long int res = 0;
  memset(dp, -1, sizeof(dp));
  n = r.length();
  powx[n - 1] = 1;
  for (long long int i = n - 2; i >= 0; i--) {
    powx[i] = mul(powx[i + 1], 10LL);
  }
  for (long long int i = 1; i <= n; i++) {
    for (long long int j = 0; j <= 9; j++) {
      long long int cnt = sub(F(0, 1, j, n - i + 1), F(0, 1, j + 1, n - i + 1));
      res = add(res, mul(mul(powx[i - 1], j), cnt));
    }
  }
  cout << res << endl;
}