#include <bits/stdc++.h>
using namespace std;
const int N = 1e6, M = N * 2 + 10, K = 6, P1 = 998244353, P2 = 1e9 + 7;
long long n;
int ans = 0;
int del[K + 1][M], sum[K + 1][M], tot[K + 1];
void Add(int &first, int second) {
  if ((first += second) >= P2) first -= P2;
}
void Sub(int &first, int second) {
  if ((first -= second) < 0) first += P2;
}
string To_string(int first, int second) {
  string num;
  for (int i = 0; i < second; i++, first /= 10) {
    num.push_back(first % 10);
  }
  reverse(num.begin(), num.end());
  return num;
}
void dfs1(int now, int len, int &rank) {
  if (len > K) return;
  rank++;
  del[len][++tot[len]] = (rank - now + P1) % P1;
  for (int i = 0; i < 10; i++) dfs1(now * 10 + i, len + 1, rank);
  return;
}
void dfs2(long long now, int &rank) {
  if (now > n) return;
  if (now * N * 10 > n && now * N + N - 1 <= n) {
    int p10 = 1, res = rank;
    for (int i = 0; i <= K; i++) {
      int d = (rank - 1ll * now * p10 % P1 + P1) % P1;
      int p = lower_bound(del[i] + 1, del[i] + tot[i] + 1, P1 - d) - del[i];
      Add(ans, 1ll * tot[i] * d % P2);
      Add(ans, sum[i][tot[i]]);
      Sub(ans, 1ll * (tot[i] - p + 1) * P1 % P2);
      (res += p10) %= P1;
      p10 *= 10;
    }
    rank = res;
  } else {
    rank = (rank + 1) % P1;
    Add(ans, (rank - now % P1 + P1) % P1);
    for (int i = 0; i < 10; i++) dfs2(now * 10 + i, rank);
  }
  return;
}
int main() {
  scanf("%lld", &n);
  int cnt = 0;
  dfs1(0, 0, cnt);
  for (int i = 0; i <= K; i++) {
    sort(del[i] + 1, del[i] + tot[i] + 1);
    for (int j = 1; j <= tot[i]; j++)
      sum[i][j] = (sum[i][j - 1] + del[i][j]) % P2;
  }
  cnt = 0;
  for (int i = 1; i < 10; i++) dfs2(i, cnt);
  printf("%d\n", ans);
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;
const int N = 1e6, M = N * 2 + 10, K = 6, P1 = 998244353, P2 = 1e9 + 7;
long long n;
int ans = 0;
int del[K + 1][M], sum[K + 1][M], tot[K + 1];
void Add(int &first, int second) {
  if ((first += second) >= P2) first -= P2;
}
void Sub(int &first, int second) {
  if ((first -= second) < 0) first += P2;
}
string To_string(int first, int second) {
  string num;
  for (int i = 0; i < second; i++, first /= 10) {
    num.push_back(first % 10);
  }
  reverse(num.begin(), num.end());
  return num;
}
void dfs1(int now, int len, int &rank) {
  if (len > K) return;
  rank++;
  del[len][++tot[len]] = (rank - now + P1) % P1;
  for (int i = 0; i < 10; i++) dfs1(now * 10 + i, len + 1, rank);
  return;
}
void dfs2(long long now, int &rank) {
  if (now > n) return;
  if (now * N * 10 > n && now * N + N - 1 <= n) {
    int p10 = 1, res = rank;
    for (int i = 0; i <= K; i++) {
      int d = (rank - 1ll * now * p10 % P1 + P1) % P1;
      int p = lower_bound(del[i] + 1, del[i] + tot[i] + 1, P1 - d) - del[i];
      Add(ans, 1ll * tot[i] * d % P2);
      Add(ans, sum[i][tot[i]]);
      Sub(ans, 1ll * (tot[i] - p + 1) * P1 % P2);
      (res += p10) %= P1;
      p10 *= 10;
    }
    rank = res;
  } else {
    rank = (rank + 1) % P1;
    Add(ans, (rank - now % P1 + P1) % P1);
    for (int i = 0; i < 10; i++) dfs2(now * 10 + i, rank);
  }
  return;
}
int main() {
  scanf("%lld", &n);
  int cnt = 0;
  dfs1(0, 0, cnt);
  for (int i = 0; i <= K; i++) {
    sort(del[i] + 1, del[i] + tot[i] + 1);
    for (int j = 1; j <= tot[i]; j++)
      sum[i][j] = (sum[i][j - 1] + del[i][j]) % P2;
  }
  cnt = 0;
  for (int i = 1; i < 10; i++) dfs2(i, cnt);
  printf("%d\n", ans);
  return 0;
}

```