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>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
void sleep(double sec = 1021) {
  clock_t s = clock();
  while (clock() - s < CLOCKS_PER_SEC * sec)
    ;
}
int __ = 1, _cs;
int dp[702][10];
int fac[702 + 702], inv[702 + 702];
inline int C(int a, int b) { return mul(fac[a], mul(inv[b], inv[a - b])); }
int pp[702], ten[702 + 702];
int sv[702][10][702];
int sv2[702][10][702];
int iten[702 + 702];
int dpw[10][702];
void build() {
  ten[0] = fac[0] = inv[0] = 1;
  iten[0] = 1;
  int inv10 = mypow(10, 1000000007LL - 2, 1000000007LL);
  for (int i = 1; i < 702 + 702; i++) {
    fac[i] = mul(fac[i - 1], i);
    inv[i] = mypow(fac[i], 1000000007LL - 2, 1000000007LL);
    ten[i] = mul(ten[i - 1], 10);
    iten[i] = mul(iten[i - 1], inv10);
  }
  int inv9 = mypow(9, 1000000007LL - 2, 1000000007LL);
  for (int i = 1; i < 702; i++) pp[i] = mul(sub(ten[i], 1), inv9);
  for (int i = 1; i < 10; i++) {
    dpw[i][0] = 1;
    for (int j = 1; j < 702; j++) dpw[i][j] = mul(dpw[i][j - 1], i);
  }
  for (int k = 0; k < 702; k++)
    for (int dgt = 1; dgt < 10; dgt++)
      for (int i = 0; i <= k; i++) {
        int tmp = 1;
        tmp = mul(tmp, C(k, i));
        tmp = mul(tmp, dpw[dgt][i]);
        if (9 - dgt > 0) tmp = mul(tmp, dpw[9 - dgt][k - i]);
        tmp = mul(tmp, ten[k - i]);
        sv[k][dgt][i] = tmp;
        if (i) sv[k][dgt][i] = add(sv[k][dgt][i], sv[k][dgt][i - 1]);
      }
  for (int k = 1; k < 702; k++)
    for (int dgt = 1; dgt < 10; dgt++) {
      if (dgt == 9) {
        for (int i = 0; i < k; i++) {
          int j = k - i;
          if (dgt == 9 and i + j < k) continue;
          int way = C(k, j);
          way = mul(way, C(k - j, i));
          way = mul(way, dpw[dgt][i]);
          if (9 - dgt > 0) way = mul(way, dpw[9 - dgt][k - i - j]);
          way = mul(way, ten[k - i - j]);
          way = mul(way, pp[j]);
          dp[k][dgt] = add(dp[k][dgt], mul(way, dgt));
        }
        continue;
      }
      for (int j = 1; j <= k; j++) {
        int way = C(k, j);
        way = mul(way, sv[k - j][dgt][k - j]);
        way = mul(way, pp[j]);
        dp[k][dgt] = add(dp[k][dgt], mul(way, dgt));
      }
    }
}
char c[702];
int ans, len;
void init() {
  scanf("%s", c);
  len = strlen(c);
}
int cnt[10];
void go(int bt, bool bnd) {
  if (bt == len or not bnd) {
    int res = len - bt;
    if (res) {
      int ps = 0;
      for (int i = 9; i; i--) {
        ans = add(ans, mul(dp[res][i], ten[ps]));
        ps += cnt[i];
      }
    }
    int ps = 0;
    for (int i = 0; i < 10; i++) {
      if (i) {
        for (int j = 0; j <= res; j++) {
          int way = sv2[res][i][j];
          way = mul(way, ten[len - (ps + j) - cnt[i]]);
          way = mul(way, pp[cnt[i]]);
          ans = add(ans, mul(i, way));
        }
      }
      ps += cnt[i];
    }
    return;
  }
  for (int i = 0; i <= c[bt] - '0'; i++) {
    if (bt == 0 and i == 0) continue;
    cnt[i]++;
    go(bt + 1, i == c[bt] - '0');
    cnt[i]--;
  }
}
void solve() {
  for (int res = 0; res < 702; res++)
    for (int i = 1; i < 10; i++) {
      for (int j = 0; j <= res; j++) {
        int way = C(res, j);
        way = mul(way, dpw[i][j]);
        way = mul(way, dpw[10 - i][res - j]);
        sv2[res][i][j] = way;
      }
    }
  if (len > 1) {
    for (int i = 1; i < 10; i++) ans = add(ans, dp[len - 1][i]);
  }
  go(0, true);
  cout << ans << endl;
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}