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;
template <class T>
inline void in(T &x) {
  x = 0;
  short f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
  x *= f;
}
template <class T>
inline void out(T x, const char c = '\n') {
  static short st[30];
  short m = 0;
  if (x < 0) putchar('-'), x = -x;
  do st[++m] = x % 10, x /= 10;
  while (x);
  while (m) putchar(st[m--] | '0');
  putchar(c);
}
template <class T, class... Args>
inline void in(T &x, Args &...args) {
  in(x);
  in(args...);
}
template <class T, class... Args>
inline void out(const T &x, const Args &...args) {
  out(x, ' ');
  out(args...);
}
template <class T>
inline void prt(T a[], int n) {
  for (register int i = 0; i < n; ++i) out(a[i], ' ');
  putchar('\n');
}
template <class T>
inline void clr(T a[], int n) {
  memset(a, 0, sizeof(T) * n);
}
template <class T>
inline void clr(T *a, T *b) {
  memset(a, 0, sizeof(T) * (b - a));
}
template <class T>
inline bool ckmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
inline bool ckmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
namespace MOD_CALC {
const int md = 1e9 + 7;
inline int add(const int a, const int b) {
  return a + b >= md ? a + b - md : a + b;
}
inline int sub(const int a, const int b) {
  return a - b < 0 ? a - b + md : a - b;
}
inline int mul(const int a, const int b) { return (long long)a * b % md; }
inline void inc(int &a, const int b) { (a += b) >= md ? a -= md : 0; }
inline void dec(int &a, const int b) { (a -= b) < 0 ? a += md : 0; }
inline int qpow(int a, int b) {
  int r = 1;
  for (; b; b >>= 1, a = mul(a, a))
    if (b & 1) r = mul(r, a);
  return r;
}
inline int mdinv(const int a) { return qpow(a, md - 2); }
}  // namespace MOD_CALC
using namespace MOD_CALC;
namespace i207M {
int len;
char s[705];
int f[705][10][705];
int dp(int p, int m, int c, bool jud) {
  if (p > len) return c == 0;
  if (!jud && f[p][m][c] != -1) return f[p][m][c];
  int r = 0, mx = jud ? s[p] - '0' : 9;
  for (register int i = 0; i <= mx; ++i)
    inc(r, dp(p + 1, m, c - (i >= m), jud && (i == mx)));
  if (!jud) f[p][m][c] = r;
  return r;
}
int wei[705];
signed main() {
  memset(f, -1, sizeof(f));
  scanf("%s", s + 1);
  len = strlen(s + 1);
  wei[1] = 1;
  for (register int i = 1; i <= len; ++i) wei[i] = mul(wei[i - 1], 10) + 1;
  int ans = 0;
  for (register int i = 1; i <= 9; ++i)
    for (register int j = 1; j <= len; ++j)
      inc(ans, mul(wei[j], dp(1, i, j, 1)));
  out(ans);
  return 0;
}
}  // namespace i207M
signed main() {
  i207M::main();
  return 0;
}