#include <bits/stdc++.h>
using namespace std;
const long long p = 998244353;
const long long mod = 1e9 + 7;
long long read() {
  long long s = 0;
  char c = getchar(), lc = '+';
  while (c < '0' || '9' < c) lc = c, c = getchar();
  while ('0' <= c && c <= '9') s = s * 10 + c - '0', c = getchar();
  return lc == '-' ? -s : s;
}
void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + '0');
  else
    write(x / 10), putchar(x % 10 + '0');
}
void print(long long x, char c = '\n') {
  write(x);
  putchar(c);
}
long long pw[8], sum[7], cnt = 0, ans = 0, n;
vector<long long> v[7];
void dfs0(long long deep, long long val) {
  v[deep].push_back((cnt++ - val + p) % p);
  if (deep < 6)
    for (long long i = 0; i <= 9; i++) dfs0(deep + 1, val * 10 + i);
}
void dfs1(long long deep, long long val) {
  static long long idx = 0;
  if (val > n) return;
  if (val * pw[6] > n / 10 && (val + 1) * pw[6] - 1 <= n) {
    for (long long i = 0; i <= 6; i++) {
      long long now = (idx - val % p * pw[i] % p + p) % p, siz = v[i].size();
      long long tot =
          v[i].end() - lower_bound(v[i].begin(), v[i].end(), p - now);
      ans = (ans + sum[i] + now * siz - p * tot) % mod;
    }
    idx += cnt;
    return;
  }
  ans = (ans + (idx++ - val % p + p) % p) % mod;
  for (long long i = !deep; i <= 9; i++) dfs1(deep + 1, val * 10 + i);
}
void Multi_test_no_horses() {
  n = read();
  dfs0(0, 0);
  for (long long i = pw[0] = 1; i <= 7; i++) pw[i] = pw[i - 1] * 10;
  for (long long i = 0; i <= 6; i++) {
    sort(v[i].begin(), v[i].end());
    for (long long j : v[i]) sum[i] += j;
  }
  dfs1(0, 0);
  print(ans);
}
signed main(signed Hello, char *CodeForces[]) {
  (void)Hello, (void)CodeForces;
  long long T = 1;
  while (T--) Multi_test_no_horses();
  return 0;
}

### Prompt

Generate 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;
const long long p = 998244353;
const long long mod = 1e9 + 7;
long long read() {
  long long s = 0;
  char c = getchar(), lc = '+';
  while (c < '0' || '9' < c) lc = c, c = getchar();
  while ('0' <= c && c <= '9') s = s * 10 + c - '0', c = getchar();
  return lc == '-' ? -s : s;
}
void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + '0');
  else
    write(x / 10), putchar(x % 10 + '0');
}
void print(long long x, char c = '\n') {
  write(x);
  putchar(c);
}
long long pw[8], sum[7], cnt = 0, ans = 0, n;
vector<long long> v[7];
void dfs0(long long deep, long long val) {
  v[deep].push_back((cnt++ - val + p) % p);
  if (deep < 6)
    for (long long i = 0; i <= 9; i++) dfs0(deep + 1, val * 10 + i);
}
void dfs1(long long deep, long long val) {
  static long long idx = 0;
  if (val > n) return;
  if (val * pw[6] > n / 10 && (val + 1) * pw[6] - 1 <= n) {
    for (long long i = 0; i <= 6; i++) {
      long long now = (idx - val % p * pw[i] % p + p) % p, siz = v[i].size();
      long long tot =
          v[i].end() - lower_bound(v[i].begin(), v[i].end(), p - now);
      ans = (ans + sum[i] + now * siz - p * tot) % mod;
    }
    idx += cnt;
    return;
  }
  ans = (ans + (idx++ - val % p + p) % p) % mod;
  for (long long i = !deep; i <= 9; i++) dfs1(deep + 1, val * 10 + i);
}
void Multi_test_no_horses() {
  n = read();
  dfs0(0, 0);
  for (long long i = pw[0] = 1; i <= 7; i++) pw[i] = pw[i - 1] * 10;
  for (long long i = 0; i <= 6; i++) {
    sort(v[i].begin(), v[i].end());
    for (long long j : v[i]) sum[i] += j;
  }
  dfs1(0, 0);
  print(ans);
}
signed main(signed Hello, char *CodeForces[]) {
  (void)Hello, (void)CodeForces;
  long long T = 1;
  while (T--) Multi_test_no_horses();
  return 0;
}

```