#include <bits/stdc++.h>
long long n, count;
const long long mod = 998244353;
const int M = 1e9 + 7;
long long power[15] = {1};
inline long long div(long long x) {
  if (x >= 0)
    return x / mod;
  else
    return -((-x + mod - 1) / mod);
}
inline long long start_with(long long x) {
  long long sum = 0;
  for (int add = 0; add <= 12; ++add) {
    if (x * power[add] > n) break;
    sum += std::min(power[add], n - x * power[add] + 1);
  }
  return sum;
}
inline long long bit(long long x) {
  int len = 1;
  for (; x > 9;) x /= 10, len += 1;
  return len;
}
inline long long rank(long long x) {
  int b = bit(x);
  long long r = 1;
  for (int lcp = 0; lcp < b; ++lcp) {
    long long pre = x / power[b - lcp], z = x / power[b - lcp - 1] % 10;
    for (int j = !lcp; j < z; ++j) {
      r += start_with(pre * 10 + j);
    }
  }
  return r + b - 1;
}
inline void dfs0(long long pre, int len) {
  const long long min = pre * power[len];
  const long long max = (pre + 1) * power[len] - 1;
  if (min > n) return;
  if (max <= n) {
    const long long rmin = rank(min);
    const long long rmax = rank(max);
    if (div(rmin - max) == div(rmax - min)) {
      count -= div(rmin - max) * power[len];
      count %= M;
      return;
    }
  }
  for (int i = 0; i <= 9; ++i) {
    dfs0(pre * 10 + i, len - 1);
  }
}
int main() {
  std::cin >> n;
  for (int i = 1; i < 15; ++i) power[i] = power[i - 1] * 10;
  for (int o = 0; o <= 12; ++o) {
    for (int i = 1; i <= 9; ++i) {
      dfs0(i, o);
    }
  }
  std::cout << (count * mod % M + M) % M << '\n';
}

### Prompt

Create a solution in Cpp for 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>
long long n, count;
const long long mod = 998244353;
const int M = 1e9 + 7;
long long power[15] = {1};
inline long long div(long long x) {
  if (x >= 0)
    return x / mod;
  else
    return -((-x + mod - 1) / mod);
}
inline long long start_with(long long x) {
  long long sum = 0;
  for (int add = 0; add <= 12; ++add) {
    if (x * power[add] > n) break;
    sum += std::min(power[add], n - x * power[add] + 1);
  }
  return sum;
}
inline long long bit(long long x) {
  int len = 1;
  for (; x > 9;) x /= 10, len += 1;
  return len;
}
inline long long rank(long long x) {
  int b = bit(x);
  long long r = 1;
  for (int lcp = 0; lcp < b; ++lcp) {
    long long pre = x / power[b - lcp], z = x / power[b - lcp - 1] % 10;
    for (int j = !lcp; j < z; ++j) {
      r += start_with(pre * 10 + j);
    }
  }
  return r + b - 1;
}
inline void dfs0(long long pre, int len) {
  const long long min = pre * power[len];
  const long long max = (pre + 1) * power[len] - 1;
  if (min > n) return;
  if (max <= n) {
    const long long rmin = rank(min);
    const long long rmax = rank(max);
    if (div(rmin - max) == div(rmax - min)) {
      count -= div(rmin - max) * power[len];
      count %= M;
      return;
    }
  }
  for (int i = 0; i <= 9; ++i) {
    dfs0(pre * 10 + i, len - 1);
  }
}
int main() {
  std::cin >> n;
  for (int i = 1; i < 15; ++i) power[i] = power[i - 1] * 10;
  for (int o = 0; o <= 12; ++o) {
    for (int i = 1; i <= 9; ++i) {
      dfs0(i, o);
    }
  }
  std::cout << (count * mod % M + M) % M << '\n';
}

```