#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && (c != '-')) c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int N = 1e6 + 10, mod1 = 998244353, mod2 = 1e9 + 7;
long long n, pw[15];
int len, B, p[15];
long long rk;
vector<int> c[4][15];
int s[4][15];
inline void init_dfs1(int k, int x) {
  ++rk, c[1][k - 1].push_back((rk + mod1 - x) % mod1);
  if (k > len - B) return;
  for (int i = (0); i <= (9); i++) init_dfs1(k + 1, x * 10 + i);
}
inline void init_dfs2(int k, int x, int op) {
  if (k <= len - B || (k > len - B && op != 1))
    ++rk, c[2][k - 1].push_back((rk + mod1 - x) % mod1);
  if (k > len - B) return;
  int num = p[len - B - k + 1];
  for (int i = (0); i <= (9); i++)
    init_dfs2(k + 1, x * 10 + i, op != -1 ? op : (i == num ? -1 : i > num));
}
inline void init_dfs3(int k, int x) {
  ++rk, c[3][k - 1].push_back((rk + mod1 - x) % mod1);
  if (k == len - B) return;
  for (int i = (0); i <= (9); i++) init_dfs3(k + 1, x * 10 + i);
}
int ans;
inline int calc(int b, int k) {
  int ret = 0;
  for (int i = (0); i <= (len - B); i++) {
    if (c[k][i].empty()) continue;
    int t = (rk + 1ll * (mod1 - b) * pw[i]) % mod1;
    ret = (ret + s[k][i] + 1ll * t * ((int)(c[k][i]).size())) % mod2;
    int tmp = lower_bound((c[k][i]).begin(), (c[k][i]).end(), mod1 - t) -
              c[k][i].begin();
    ret = (ret + 1ll * (mod2 - mod1) * (((int)(c[k][i]).size()) - tmp)) % mod2;
  }
  for (int i = (0); i <= (len - B); i++) rk += ((int)(c[k][i]).size());
  return ret;
}
inline void dfs(int k, int x, int op) {
  if (k > B) {
    if (op == 0)
      ans = (ans + calc(x, 1)) % mod2;
    else if (op == 1)
      ans = (ans + calc(x, 3)) % mod2;
    else
      ans = (ans + calc(x, 2)) % mod2;
    return;
  }
  if (k > 1) ++rk, ans = (ans + (rk + mod1 - x) % mod1) % mod2;
  int num = p[len - k + 1];
  for (int i = (k == 1); i <= (9); i++)
    dfs(k + 1, x * 10 + i, op != -1 ? op : (i == num ? -1 : i > num));
}
int main() {
  n = read();
  if (n <= 9) return puts("0"), 0;
  for (long long i = n; i; i /= 10) p[++len] = i % 10;
  B = (len + 1) / 2;
  rk = 0, init_dfs1(1, 0);
  rk = 0, init_dfs2(1, 0, -1);
  rk = 0, init_dfs3(1, 0);
  for (int i = (0); i <= (len - B); i++)
    for (int j = (1); j <= (3); j++) {
      sort((c[j][i]).begin(), (c[j][i]).end());
      for (auto k : c[j][i]) s[j][i] = (s[j][i] + k) % mod2;
    }
  pw[0] = 1;
  for (int i = (1); i <= (len); i++) pw[i] = 10 * pw[i - 1];
  rk = 0, dfs(1, 0, -1), printf("%d\n", ans);
}

### 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>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && (c != '-')) c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int N = 1e6 + 10, mod1 = 998244353, mod2 = 1e9 + 7;
long long n, pw[15];
int len, B, p[15];
long long rk;
vector<int> c[4][15];
int s[4][15];
inline void init_dfs1(int k, int x) {
  ++rk, c[1][k - 1].push_back((rk + mod1 - x) % mod1);
  if (k > len - B) return;
  for (int i = (0); i <= (9); i++) init_dfs1(k + 1, x * 10 + i);
}
inline void init_dfs2(int k, int x, int op) {
  if (k <= len - B || (k > len - B && op != 1))
    ++rk, c[2][k - 1].push_back((rk + mod1 - x) % mod1);
  if (k > len - B) return;
  int num = p[len - B - k + 1];
  for (int i = (0); i <= (9); i++)
    init_dfs2(k + 1, x * 10 + i, op != -1 ? op : (i == num ? -1 : i > num));
}
inline void init_dfs3(int k, int x) {
  ++rk, c[3][k - 1].push_back((rk + mod1 - x) % mod1);
  if (k == len - B) return;
  for (int i = (0); i <= (9); i++) init_dfs3(k + 1, x * 10 + i);
}
int ans;
inline int calc(int b, int k) {
  int ret = 0;
  for (int i = (0); i <= (len - B); i++) {
    if (c[k][i].empty()) continue;
    int t = (rk + 1ll * (mod1 - b) * pw[i]) % mod1;
    ret = (ret + s[k][i] + 1ll * t * ((int)(c[k][i]).size())) % mod2;
    int tmp = lower_bound((c[k][i]).begin(), (c[k][i]).end(), mod1 - t) -
              c[k][i].begin();
    ret = (ret + 1ll * (mod2 - mod1) * (((int)(c[k][i]).size()) - tmp)) % mod2;
  }
  for (int i = (0); i <= (len - B); i++) rk += ((int)(c[k][i]).size());
  return ret;
}
inline void dfs(int k, int x, int op) {
  if (k > B) {
    if (op == 0)
      ans = (ans + calc(x, 1)) % mod2;
    else if (op == 1)
      ans = (ans + calc(x, 3)) % mod2;
    else
      ans = (ans + calc(x, 2)) % mod2;
    return;
  }
  if (k > 1) ++rk, ans = (ans + (rk + mod1 - x) % mod1) % mod2;
  int num = p[len - k + 1];
  for (int i = (k == 1); i <= (9); i++)
    dfs(k + 1, x * 10 + i, op != -1 ? op : (i == num ? -1 : i > num));
}
int main() {
  n = read();
  if (n <= 9) return puts("0"), 0;
  for (long long i = n; i; i /= 10) p[++len] = i % 10;
  B = (len + 1) / 2;
  rk = 0, init_dfs1(1, 0);
  rk = 0, init_dfs2(1, 0, -1);
  rk = 0, init_dfs3(1, 0);
  for (int i = (0); i <= (len - B); i++)
    for (int j = (1); j <= (3); j++) {
      sort((c[j][i]).begin(), (c[j][i]).end());
      for (auto k : c[j][i]) s[j][i] = (s[j][i] + k) % mod2;
    }
  pw[0] = 1;
  for (int i = (1); i <= (len); i++) pw[i] = 10 * pw[i - 1];
  rk = 0, dfs(1, 0, -1), printf("%d\n", ans);
}

```