#include <bits/stdc++.h>
#pragma GCC optimize(2, 3, "Ofast")
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
const int B = 1000000;
const int mod1 = 998244353;
const int mod2 = 1e9 + 7;
vector<int> va[7];
long long sum[7];
long long cnt, n, ans;
int calc(long long x) { return (x % mod1 + mod1) % mod1; }
void dfs1(int dep, int val) {
  ++cnt;
  va[dep].push_back(calc(cnt - val));
  if (dep == 6) return;
  for (int i = 0; i < 10; i++) dfs1(dep + 1, 10 * val + i);
}
void dfs2(int dep, long long val) {
  if (val > n) return;
  if (dep >= 1) {
    if (val * B > n / 10 && (val + 1) * B - 1 <= n) {
      int tmp = 1;
      for (int i = 0; i < 7; i++) {
        int coef = calc(cnt - val * tmp);
        int pos = lower_bound(va[i].begin(), va[i].end(), mod1 - coef) -
                  va[i].begin();
        ans = (ans + 1ll * coef * (int(va[i].size())) % mod2 + sum[i] -
               1ll * mod1 * ((int(va[i].size())) - pos) % mod2) %
              mod2;
        tmp *= 10;
      }
      for (int i = 0; i < 7; i++) cnt += (int(va[i].size()));
      return;
    }
    ++cnt;
    ans = (ans + calc(cnt - val)) % mod2;
  }
  for (int i = !dep; i < 10; i++) dfs2(dep + 1, 10 * val + i);
}
int main() {
  cin >> n;
  dfs1(0, 0);
  for (int dep = 0; dep < 7; dep++) {
    sort(va[dep].begin(), va[dep].end());
    for (auto v : va[dep]) sum[dep] += v;
  }
  cnt = 0;
  dfs2(0, 0);
  cout << (ans + mod2) % mod2 << '\n';
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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>
#pragma GCC optimize(2, 3, "Ofast")
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
const int B = 1000000;
const int mod1 = 998244353;
const int mod2 = 1e9 + 7;
vector<int> va[7];
long long sum[7];
long long cnt, n, ans;
int calc(long long x) { return (x % mod1 + mod1) % mod1; }
void dfs1(int dep, int val) {
  ++cnt;
  va[dep].push_back(calc(cnt - val));
  if (dep == 6) return;
  for (int i = 0; i < 10; i++) dfs1(dep + 1, 10 * val + i);
}
void dfs2(int dep, long long val) {
  if (val > n) return;
  if (dep >= 1) {
    if (val * B > n / 10 && (val + 1) * B - 1 <= n) {
      int tmp = 1;
      for (int i = 0; i < 7; i++) {
        int coef = calc(cnt - val * tmp);
        int pos = lower_bound(va[i].begin(), va[i].end(), mod1 - coef) -
                  va[i].begin();
        ans = (ans + 1ll * coef * (int(va[i].size())) % mod2 + sum[i] -
               1ll * mod1 * ((int(va[i].size())) - pos) % mod2) %
              mod2;
        tmp *= 10;
      }
      for (int i = 0; i < 7; i++) cnt += (int(va[i].size()));
      return;
    }
    ++cnt;
    ans = (ans + calc(cnt - val)) % mod2;
  }
  for (int i = !dep; i < 10; i++) dfs2(dep + 1, 10 * val + i);
}
int main() {
  cin >> n;
  dfs1(0, 0);
  for (int dep = 0; dep < 7; dep++) {
    sort(va[dep].begin(), va[dep].end());
    for (auto v : va[dep]) sum[dep] += v;
  }
  cnt = 0;
  dfs2(0, 0);
  cout << (ans + mod2) % mod2 << '\n';
  return 0;
}

```