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 double EPS = 1e-10;
const long long MOD = 1e9 + 7;
const long double PI = 3.1415926535897932384626433832795028841;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= MOD;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
  }
  return res;
}
ostream& operator<<(std::ostream& stream, const long long* arr) {
  int i = 0;
  cout << "{";
  while (arr[i] != INT_MAX) {
    cout << arr[i];
    if (arr[i + 1] != INT_MAX) cout << ",";
    i++;
  }
  cout << "}";
  return stream;
}
ostream& operator<<(std::ostream& stream, const vector<int> vec) {
  cout << "{";
  for (int i = 0; i < vec.size(); i++) {
    cout << vec[i];
    if (i != vec.size() - 1) cout << ",";
  }
  cout << "}";
  return stream;
}
ostream& operator<<(std::ostream& stream,
                    const pair<long long, long long>& vec) {
  cout << "(" << vec.first << ',' << vec.second << ")";
  return stream;
}
template <class T>
struct segtree_t {
  vector<T> t, lazy, flag_equal;
  int st, sz;
  T (*addition_fun)(T, T);
  T invalid_value;
  segtree_t() {}
  segtree_t(int start, int finish, T* arr, T (*add_fun)(T, T), T invalid_val) {
    int size = (finish + 1) * 2;
    int tree_size = 2;
    while (tree_size < size) tree_size *= 2;
    t = vector<T>(tree_size);
    lazy = vector<T>(tree_size);
    flag_equal = vector<T>(tree_size);
    st = start;
    sz = finish;
    addition_fun = add_fun;
    invalid_value = invalid_val;
    build(1, start, finish, arr);
  }
  void build(int i, int l, int r, T* arr) {
    if (l > r) return;
    lazy[i] = 0;
    flag_equal[i] = 0;
    if (l == r) {
      t[i] = arr[l];
    } else {
      build(i * 2, l, (l + r) / 2, arr);
      build(i * 2 + 1, (l + r) / 2 + 1, r, arr);
      t[i] = addition_fun(t[i * 2], t[i * 2 + 1]);
    }
  }
  void inc_range(int l, int r, T value) {
    if (l > r) return;
    inc_range_rec(1, st, sz, l, r, value);
  }
  void set_values(int l, int r, T value) {
    set_values_rec(1, st, sz, l, r, value);
  }
  void inc_range_rec(int i, int l, int r, int tl, int tr, T value) {
    if (lazy[i] != 0) {
      t[i] += lazy[i];
      if (l != r) {
        lazy[i * 2] += lazy[i];
        lazy[i * 2 + 1] += lazy[i];
      }
      lazy[i] = 0;
    }
    if (r < tl or l > tr) return;
    if (l > r) return;
    if (l >= tl and r <= tr) {
      if (l != r) {
        lazy[i * 2] += value;
        lazy[i * 2 + 1] += value;
      }
      t[i] += value;
    } else {
      inc_range_rec(i * 2, l, (l + r) / 2, tl, tr, value);
      inc_range_rec(i * 2 + 1, (l + r) / 2 + 1, r, tl, tr, value);
      t[i] = addition_fun(t[i * 2], t[i * 2 + 1]);
    }
  }
  T query_rec(int i, int l, int r, int tl, int tr) {
    if (flag_equal[i] != 0) {
      if (l != r) {
        t[i * 2] = t[i];
        t[i * 2 + 1] = t[i];
        flag_equal[i * 2] = 1;
        flag_equal[i * 2 + 1] = 1;
      }
      flag_equal[i] = 0;
    }
    if (r < tl or l > tr) return invalid_value;
    if (l > r) return invalid_value;
    if (lazy[i] != 0) {
      t[i] += lazy[i];
      if (l != r) {
        lazy[i * 2] += lazy[i];
        lazy[i * 2 + 1] += lazy[i];
      }
      lazy[i] = 0;
    }
    if (l >= tl and r <= tr) {
      return t[i];
    } else {
      T m1 = query_rec(i * 2, l, (l + r) / 2, tl, tr);
      T m2 = query_rec(i * 2 + 1, (l + r) / 2 + 1, r, tl, tr);
      if (m1 == invalid_value && m2 == invalid_value) return invalid_value;
      if (m1 == invalid_value) return m2;
      if (m2 == invalid_value) return m1;
      return addition_fun(m1, m2);
    }
  }
  T query(int l, int r) { return query_rec(1, st, sz, l, r); }
  void set_values_rec(int i, int l, int r, int tl, int tr, T value) {
    if (flag_equal[i] != 0) {
      if (l != r) {
        t[i * 2] = t[i];
        t[i * 2 + 1] = t[i];
        flag_equal[i * 2] = 1;
        flag_equal[i * 2 + 1] = 1;
      }
      flag_equal[i] = 0;
    }
    if (r < tl || l > tr) return;
    if (l > r) return;
    if (l >= tl and r <= tr) {
      t[i] = value;
      flag_equal[i] = 1;
    } else {
      set_values_rec(i * 2, l, (l + r) / 2, tl, tr, value);
      set_values_rec(i * 2 + 1, (l + r) / 2 + 1, r, tl, tr, value);
      t[i] = addition_fun(t[i * 2], t[i * 2 + 1]);
    }
  }
  ~segtree_t() {}
};
template <class T>
struct fenwick_t {
  vector<T> FW;
  fenwick_t(int n) { FW = vector<T>(n + 1); }
  void inc(int i, T v) {
    while (i <= FW.size() - 1) {
      FW[i] += v;
      i += i & (-i);
    }
  }
  T get(int i) {
    T rta = 0;
    while (i > 0) {
      rta += FW[i];
      i -= i & (-i);
    }
    return rta;
  }
};
struct dsu_t {
  vector<int> p, sz, depth;
  dsu_t() {}
  dsu_t(int n) {
    p = vector<int>(n + 1);
    sz = vector<int>(n + 1);
    depth = vector<int>(n + 1);
    for (int i = 1; i <= n; i++) {
      p[i] = i;
      sz[i] = 1;
      depth[i] = 1;
    }
  }
  int get(int i) {
    int j = i;
    while (p[i] != i) i = p[i];
    while (p[j] != j) {
      int aux = p[j];
      p[j] = i;
      j = aux;
    }
    return i;
  }
  void merge(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) return;
    if (sz[a] > sz[b]) {
      p[b] = a;
      sz[a] += sz[b];
    } else {
      p[a] = b;
      sz[b] += sz[a];
      if (depth[a] == depth[b]) depth[b]++;
    }
  }
  void show() {
    for (int i = 1; i <= p.size() - 1; i++) {
      cout << i << ": " << p[i] << ' ' << sz[i] << ' ' << depth[i] << " \n";
    }
  }
};
const int maxn = 700 + 5;
const int maxm = 1e5 + 5;
const int maxk = 1e5 + 5;
const int maxq = 1e5 + 5;
string A;
vector<long long> X;
long long ways[maxn][11];
long long dp[2][maxn][2];
long long has[2][maxn][2];
void pre_calc(int jj) {
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j <= X.size(); j++) {
      for (int k = 0; k < 2; k++) dp[i][j][k] = 0, has[i][j][k] = 0;
    }
  }
  dp[0][0][0] = 1;
  has[0][0][0] = 1;
  for (long long i = 0; i < X.size(); i++) {
    for (long long j = 0; j <= X.size(); j++)
      for (int k = 0; k < 2; k++)
        dp[(i + 1) % 2][j][k] = 0, has[(i + 1) % 2][j][k] = 0;
    for (long long j = 0; j <= X.size(); j++) {
      for (long long k = 0; k < 2; k++) {
        if (!has[i % 2][j][k]) continue;
        for (long long d = 0; d <= 9; d++) {
          long long new_j = j, new_k = k;
          if (k == 0 && d > X[i]) break;
          if (k == 0 && d < X[i]) new_k = 1;
          if (d >= jj) new_j++;
          dp[(i + 1) % 2][new_j][new_k] =
              (dp[(i + 1) % 2][new_j][new_k] + dp[i % 2][j][k]) % MOD;
          has[(i + 1) % 2][new_j][new_k] = 1;
        }
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin >> A;
  for (long long i = 0; i < A.size(); i++) X.push_back(A[i] - '0');
  for (int i = 1; i <= 9; i++) {
    pre_calc(i);
    long long acc = 0;
    for (long long j = X.size(); j >= 1; j--) {
      long long nxt = (dp[X.size() % 2][j][0] + dp[X.size() % 2][j][1]) % MOD;
      acc = (acc + nxt) % MOD;
      ways[j][i] = acc;
    }
  }
  long long ans = 0;
  long long mult = 1;
  for (long long i = 1; i <= X.size(); i++) {
    for (long long d = 1; d <= 9; d++) {
      long long add = (ways[i][d] - ways[i][d + 1] + MOD) % MOD;
      long long add2 = ((add * mult % MOD) * d) % MOD;
      ans = (ans + add2) % MOD;
    }
    mult = (mult * 10) % MOD;
  }
  cout << ans << '\n';
}