#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 1000000007;
struct Mint {
  int val;
  Mint() { val = 0; }
  Mint(ll x) {
    val = (-MOD <= x && x < MOD) ? x : x % MOD;
    if (val < 0) val += MOD;
  }
  template <typename U>
  explicit operator U() const {
    return (U)val;
  }
  friend bool operator==(const Mint& a, const Mint& b) {
    return a.val == b.val;
  }
  friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
  friend bool operator<(const Mint& a, const Mint& b) { return a.val < b.val; }
  Mint& operator+=(const Mint& m) {
    if ((val += m.val) >= MOD) val -= MOD;
    return *this;
  }
  Mint& operator-=(const Mint& m) {
    if ((val -= m.val) < 0) val += MOD;
    return *this;
  }
  Mint& operator*=(const Mint& m) {
    val = (ll)val * m.val % MOD;
    return *this;
  }
  friend Mint modex(Mint a, ll p) {
    assert(p >= 0);
    Mint ans = 1;
    for (; p; p >>= 1, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  Mint& operator/=(const Mint& m) { return *this *= modex(m, MOD - 2); }
  Mint& operator++() { return *this += 1; }
  Mint& operator--() { return *this -= 1; }
  Mint operator++(int) {
    Mint result(*this);
    *this += 1;
    return result;
  }
  Mint operator--(int) {
    Mint result(*this);
    *this -= 1;
    return result;
  }
  Mint operator-() const { return Mint(-val); }
  friend Mint operator+(Mint a, const Mint& b) { return a += b; }
  friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
  friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
  friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
  friend ostream& operator<<(ostream& os, const Mint& x) { return os << x.val; }
  friend string to_string(const Mint& b) { return to_string(b.val); }
};
int main() {
  ll n;
  scanf("%lld", &n);
  const int mod = 998244353;
  int blockCnt = 0;
  array<vector<int>, 7> vals;
  array<Mint, 7> sumVals{};
  function<void(ll, int)> precalc = [&](ll x, int d) {
    int v = (blockCnt - x + mod) % mod;
    vals[d].push_back(v);
    ++blockCnt;
    if (d == 6) return;
    for (int i = 0; i <= 9; ++i) {
      precalc(x * 10 + i, d + 1);
    }
  };
  precalc(0, 0);
  for (int i = 0; i <= 6; ++i) {
    sort(vals[i].begin(), vals[i].end());
    sumVals[i] = accumulate(vals[i].begin(), vals[i].end(), Mint(0));
  }
  Mint ans = 0;
  ll cnt = 0;
  function<void(ll)> go = [&](ll pref) {
    if (pref * 1000000 + 999999 <= n && pref * 10000000 > n) {
      int p10 = 1;
      for (int d = 0; d <= 6; ++d) {
        int add = ((cnt - pref * p10) % mod + mod) % mod;
        ans += sumVals[d];
        if (add > 0) {
          ans += Mint(add) * vals[d].size();
          int pos = lower_bound(vals[d].begin(), vals[d].end(), mod - add) -
                    vals[d].begin();
          ans -= Mint(vals[d].size() - pos) * mod;
        }
        p10 *= 10;
      }
      cnt += blockCnt;
      return;
    }
    ans += ((cnt - pref) % mod + mod) % mod;
    ++cnt;
    for (int d = pref ? 0 : 1; d <= 9; ++d) {
      if (pref * 10 + d <= n) go(pref * 10 + d);
    }
  };
  go(0);
  42;
  printf("%d\n", ans.val);
}

### Prompt

Your task is to create a cpp solution to the following problem:

Integers from 1 to n (inclusive) were sorted lexicographically (considering integers as strings). As a result, array a_1, a_2, ..., a_n was obtained.

Calculate value of (∑_{i = 1}^n ((i - a_i) mod 998244353)) mod 10^9 + 7.

x mod y here means the remainder after division x by y. This remainder is always non-negative and doesn't exceed y - 1. For example, 5 mod 3 = 2, (-1) mod 6 = 5. 

Input

The first line contains the single integer n (1 ≤ n ≤ 10^{12}).

Output

Print one integer — the required sum.

Examples

Input


3


Output


0


Input


12


Output


994733045


Input


21


Output


978932159


Input


1000000000000


Output


289817887

Note

A string a is lexicographically smaller than a string b if and only if one of the following holds:

  * a is a prefix of b, but a ≠ b; 
  * in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b. 



For example, 42 is lexicographically smaller than 6, because they differ in the first digit, and 4 < 6; 42 < 420, because 42 is a prefix of 420.

Let's denote 998244353 as M.

In the first example, array a is equal to [1, 2, 3]. 

  * (1 - 1) mod M = 0 mod M = 0 
  * (2 - 2) mod M = 0 mod M = 0 
  * (3 - 3) mod M = 0 mod M = 0 



As a result, (0 + 0 + 0) mod 10^9 + 7 = 0

In the second example, array a is equal to [1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9]. 

  * (1 - 1) mod M = 0 mod M = 0 
  * (2 - 10) mod M = (-8) mod M = 998244345 
  * (3 - 11) mod M = (-8) mod M = 998244345 
  * (4 - 12) mod M = (-8) mod M = 998244345 
  * (5 - 2) mod M = 3 mod M = 3 
  * (6 - 3) mod M = 3 mod M = 3 
  * (7 - 4) mod M = 3 mod M = 3 
  * (8 - 5) mod M = 3 mod M = 3 
  * (9 - 6) mod M = 3 mod M = 3 
  * (10 - 7) mod M = 3 mod M = 3 
  * (11 - 8) mod M = 3 mod M = 3 
  * (12 - 9) mod M = 3 mod M = 3 



As a result, (0 + 998244345 + 998244345 + 998244345 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) mod 10^9 + 7 = 2994733059 mod 10^9 + 7 = 994733045

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 1000000007;
struct Mint {
  int val;
  Mint() { val = 0; }
  Mint(ll x) {
    val = (-MOD <= x && x < MOD) ? x : x % MOD;
    if (val < 0) val += MOD;
  }
  template <typename U>
  explicit operator U() const {
    return (U)val;
  }
  friend bool operator==(const Mint& a, const Mint& b) {
    return a.val == b.val;
  }
  friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
  friend bool operator<(const Mint& a, const Mint& b) { return a.val < b.val; }
  Mint& operator+=(const Mint& m) {
    if ((val += m.val) >= MOD) val -= MOD;
    return *this;
  }
  Mint& operator-=(const Mint& m) {
    if ((val -= m.val) < 0) val += MOD;
    return *this;
  }
  Mint& operator*=(const Mint& m) {
    val = (ll)val * m.val % MOD;
    return *this;
  }
  friend Mint modex(Mint a, ll p) {
    assert(p >= 0);
    Mint ans = 1;
    for (; p; p >>= 1, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  Mint& operator/=(const Mint& m) { return *this *= modex(m, MOD - 2); }
  Mint& operator++() { return *this += 1; }
  Mint& operator--() { return *this -= 1; }
  Mint operator++(int) {
    Mint result(*this);
    *this += 1;
    return result;
  }
  Mint operator--(int) {
    Mint result(*this);
    *this -= 1;
    return result;
  }
  Mint operator-() const { return Mint(-val); }
  friend Mint operator+(Mint a, const Mint& b) { return a += b; }
  friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
  friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
  friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
  friend ostream& operator<<(ostream& os, const Mint& x) { return os << x.val; }
  friend string to_string(const Mint& b) { return to_string(b.val); }
};
int main() {
  ll n;
  scanf("%lld", &n);
  const int mod = 998244353;
  int blockCnt = 0;
  array<vector<int>, 7> vals;
  array<Mint, 7> sumVals{};
  function<void(ll, int)> precalc = [&](ll x, int d) {
    int v = (blockCnt - x + mod) % mod;
    vals[d].push_back(v);
    ++blockCnt;
    if (d == 6) return;
    for (int i = 0; i <= 9; ++i) {
      precalc(x * 10 + i, d + 1);
    }
  };
  precalc(0, 0);
  for (int i = 0; i <= 6; ++i) {
    sort(vals[i].begin(), vals[i].end());
    sumVals[i] = accumulate(vals[i].begin(), vals[i].end(), Mint(0));
  }
  Mint ans = 0;
  ll cnt = 0;
  function<void(ll)> go = [&](ll pref) {
    if (pref * 1000000 + 999999 <= n && pref * 10000000 > n) {
      int p10 = 1;
      for (int d = 0; d <= 6; ++d) {
        int add = ((cnt - pref * p10) % mod + mod) % mod;
        ans += sumVals[d];
        if (add > 0) {
          ans += Mint(add) * vals[d].size();
          int pos = lower_bound(vals[d].begin(), vals[d].end(), mod - add) -
                    vals[d].begin();
          ans -= Mint(vals[d].size() - pos) * mod;
        }
        p10 *= 10;
      }
      cnt += blockCnt;
      return;
    }
    ans += ((cnt - pref) % mod + mod) % mod;
    ++cnt;
    for (int d = pref ? 0 : 1; d <= 9; ++d) {
      if (pref * 10 + d <= n) go(pref * 10 + d);
    }
  };
  go(0);
  42;
  printf("%d\n", ans.val);
}

```