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;
inline long long mod(long long n, long long m) {
  long long ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}
long long gcd(long long a, long long b) {
  return (b == 0LL ? a : gcd(b, a % b));
}
long long exp(long long a, long long b, long long m) {
  if (b == 0LL) return 1LL;
  if (b == 1LL) return mod(a, m);
  long long k = mod(exp(a, b / 2, m), m);
  if (b & 1LL) {
    return mod(a * mod(k * k, m), m);
  } else
    return mod(k * k, m);
}
string X;
int j;
int n;
const int N = 720;
long long dp[N][N][2];
const int M = 1e9 + 7;
long long solve(int id, int num, int f1) {
  if (id == n) {
    return num == 0;
  }
  long long& x = dp[id][num][f1];
  if (x != -1) return x;
  x = 0;
  for (int k = 0; k < 10; k++) {
    if (f1 == 0 and k > X[id] - '0') break;
    int nf = f1;
    if (k < X[id] - '0') nf = 1;
    int num2 = num - (k >= j);
    if (num2 < 0) {
      continue;
    }
    x = (x + solve(id + 1, num2, nf)) % M;
  }
  return x;
}
long long pwr[N];
long long pre[N];
int to_int(string s) {
  int r = 0;
  for (int i = 0; i < s.size(); i++) {
    r = 10 * r + s[i] - '0';
  }
  return r;
}
int S(int x) {
  vector<int> vec;
  while (x > 0) {
    vec.push_back(x % 10);
    x /= 10;
  }
  int r = 0;
  sort(vec.begin(), vec.end());
  string s = "";
  for (int x : vec) {
    s += char(x + '0');
  }
  return to_int(s);
}
int brute() {
  int x = to_int(X);
  int res = 0;
  for (int i = 1; i <= x; i++) {
    res += S(i);
    res %= M;
  }
  return res;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> X;
  n = (int)X.size();
  long long res = 0;
  pwr[0] = 1;
  for (int i = 1; i <= n; i++) {
    pwr[i] = pwr[i - 1] * 10ll % M;
  }
  for (j = 1; j <= 9; j++) {
    memset(dp, -1, sizeof(dp));
    long long cur = 0;
    pre[0] = 0;
    for (int qtd = 1; qtd <= n; qtd++) {
      pre[qtd] = pre[qtd - 1] + solve(0, qtd, 0);
      if (pre[qtd] >= M) pre[qtd] -= M;
    }
    for (int qtd = 1; qtd <= n; qtd++) {
      cur = (cur + 1ll * mod(pre[n] - pre[qtd - 1], M) * pwr[qtd - 1]) % M;
    }
    res = (res + cur) % M;
  }
  res = mod(res, M);
  cout << res << "\n";
}