#include <bits/stdc++.h>
constexpr int Block = 1e6;
constexpr int Mod[] = {998244353, 1000000007};
long long n, cnt;
std::vector<int> val[7];
int res, sum[7];
void DFS1(int d, int v) {
  val[d].emplace_back((++cnt - v + Mod[0]) % Mod[0]);
  if (d == 6) return;
  for (int c = 0; c < 10; ++c) DFS1(d + 1, v * 10 + c);
}
void DFS2(int d, long long v) {
  if (v > n) return;
  if (d != 0) {
    if (v * Block > n / 10 && (v + 1) * Block - 1 <= n) {
      for (int i = 0, p = 1; i <= 6; ++i, p *= 10) {
        int coef = (cnt - v * p % Mod[0] + Mod[0]) % Mod[0];
        auto iter =
            std::lower_bound(val[i].begin(), val[i].end(), Mod[0] - coef);
        res = (res + 1LL * coef * val[i].size() + sum[i]) % Mod[1];
        res = (res - 1LL * Mod[0] * (val[i].end() - iter) % Mod[1] + Mod[1]) %
              Mod[1];
      }
      for (int i = 0; i <= 6; ++i) cnt += val[i].size();
      return;
    }
    res = (res + (++cnt - v % Mod[0] + Mod[0]) % Mod[0]) % Mod[1];
  }
  for (int c = !d; c < 10; ++c) DFS2(d + 1, v * 10 + c);
}
int main() {
  scanf("%lld", &n);
  DFS1(0, 0);
  for (int d = 0; d <= 6; ++d) {
    std::sort(val[d].begin(), val[d].end());
    for (int x : val[d]) sum[d] = (sum[d] + x) % Mod[1];
  }
  cnt = 0;
  DFS2(0, 0);
  printf("%d\n", res);
}

### Prompt

In Cpp, your task is to solve 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>
constexpr int Block = 1e6;
constexpr int Mod[] = {998244353, 1000000007};
long long n, cnt;
std::vector<int> val[7];
int res, sum[7];
void DFS1(int d, int v) {
  val[d].emplace_back((++cnt - v + Mod[0]) % Mod[0]);
  if (d == 6) return;
  for (int c = 0; c < 10; ++c) DFS1(d + 1, v * 10 + c);
}
void DFS2(int d, long long v) {
  if (v > n) return;
  if (d != 0) {
    if (v * Block > n / 10 && (v + 1) * Block - 1 <= n) {
      for (int i = 0, p = 1; i <= 6; ++i, p *= 10) {
        int coef = (cnt - v * p % Mod[0] + Mod[0]) % Mod[0];
        auto iter =
            std::lower_bound(val[i].begin(), val[i].end(), Mod[0] - coef);
        res = (res + 1LL * coef * val[i].size() + sum[i]) % Mod[1];
        res = (res - 1LL * Mod[0] * (val[i].end() - iter) % Mod[1] + Mod[1]) %
              Mod[1];
      }
      for (int i = 0; i <= 6; ++i) cnt += val[i].size();
      return;
    }
    res = (res + (++cnt - v % Mod[0] + Mod[0]) % Mod[0]) % Mod[1];
  }
  for (int c = !d; c < 10; ++c) DFS2(d + 1, v * 10 + c);
}
int main() {
  scanf("%lld", &n);
  DFS1(0, 0);
  for (int d = 0; d <= 6; ++d) {
    std::sort(val[d].begin(), val[d].end());
    for (int x : val[d]) sum[d] = (sum[d] + x) % Mod[1];
  }
  cnt = 0;
  DFS2(0, 0);
  printf("%d\n", res);
}

```