#include <bits/stdc++.h>
using namespace std;
inline long long readint() {
  long long x = 0;
  bool f = 0;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') {
    f = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return f ? -x : x;
}
const int maxl = 12 + 5;
char n[maxl];
int l;
const long long mod1 = 998244353, mod2 = 1e9 + 7;
long long pw[maxl], p2[maxl];
vector<long long> vec;
void dfs1(int u, long long res, int v, int l2, bool tp) {
  if (u > v) {
    vec.push_back(res);
    return;
  }
  for (int i = 0; i < 10; i++)
    dfs1(u + 1,
         (res + (p2[l - u - tp] - pw[l2 - u] + mod1) % mod1 * i % mod1) % mod1,
         v, l2, tp);
}
long long s, ans = 0;
void dfs2(int u, long long res, int l2, bool tp) {
  if (u > l2) {
    ans = (ans + res * vec.size() % mod2 + s -
           mod1 *
               (upper_bound(vec.begin(), vec.end(), mod1 - res,
                            greater<long long>()) -
                vec.begin()) %
               mod2 +
           mod2) %
          mod2;
    return;
  }
  for (int i = 0; i < 10; i++)
    dfs2(u + 1,
         (res + (p2[l - u - tp] - pw[l2 - u] + mod1) % mod1 * i % mod1) % mod1,
         l2, tp);
}
int main() {
  scanf("%s", n + 1);
  l = strlen(n + 1);
  if (l == 1) {
    printf("0\n");
    return 0;
  }
  pw[0] = 1;
  for (int i = 1; i <= l; i++) pw[i] = pw[i - 1] * 10 % mod1;
  p2[0] = 1;
  for (int i = 1; i <= l; i++) p2[i] = (p2[i - 1] * 10 % mod1 + 1) % mod1;
  for (int i = 1; i <= l; i++) {
    for (int j = 1; j <= i; j++)
      for (int k = j > 1 ? 0 : 1; k < (i < l ? 10 : n[j] - '0'); k++) {
        if (k == n[j] - '0') continue;
        bool tp = k > n[j] - '0';
        long long res = i + tp;
        if (j > 1) {
          res = (res + p2[l - 1 - tp] * (n[1] - '0' - 1) % mod1 -
                 pw[i - 1] * (n[1] - '0') % mod1 + mod1) %
                mod1;
          for (int x = 2; x < j; x++)
            res = (res + (p2[l - x - tp] - pw[i - x] + mod1) % mod1 *
                             (n[x] - '0') % mod1) %
                  mod1;
          res = (res + (p2[l - j - tp] - pw[i - j] + mod1) % mod1 * k % mod1) %
                mod1;
        } else
          res = (res + p2[l - 1 - tp] * (k - 1) % mod1 - pw[i - 1] * k % mod1 +
                 mod1) %
                mod1;
        if (tp)
          for (int x = 1; x <= l; x++)
            res = (res + (n[x] - '0' - (x == 1)) * pw[l - x] % mod1) % mod1;
        int mid = (i + j + 1) / 2;
        vec = {};
        dfs1(j + 1, 0, mid, i, tp);
        s = 0;
        for (long long i : vec) s = (s + i) % mod2;
        sort(vec.begin(), vec.end(), greater<long long>());
        dfs2(mid + 1, res, i, tp);
      }
    long long res = i;
    res = (res + p2[l - 1] * (n[1] - '0' - 1) % mod1 -
           pw[i - 1] * (n[1] - '0') % mod1 + mod1) %
          mod1;
    for (int j = 2; j <= i; j++)
      res =
          (res + (p2[l - j] - pw[i - j] + mod1) % mod1 * (n[j] - '0') % mod1) %
          mod1;
    ans = (ans + res) % mod2;
  }
  printf("%lld\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;
inline long long readint() {
  long long x = 0;
  bool f = 0;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') {
    f = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return f ? -x : x;
}
const int maxl = 12 + 5;
char n[maxl];
int l;
const long long mod1 = 998244353, mod2 = 1e9 + 7;
long long pw[maxl], p2[maxl];
vector<long long> vec;
void dfs1(int u, long long res, int v, int l2, bool tp) {
  if (u > v) {
    vec.push_back(res);
    return;
  }
  for (int i = 0; i < 10; i++)
    dfs1(u + 1,
         (res + (p2[l - u - tp] - pw[l2 - u] + mod1) % mod1 * i % mod1) % mod1,
         v, l2, tp);
}
long long s, ans = 0;
void dfs2(int u, long long res, int l2, bool tp) {
  if (u > l2) {
    ans = (ans + res * vec.size() % mod2 + s -
           mod1 *
               (upper_bound(vec.begin(), vec.end(), mod1 - res,
                            greater<long long>()) -
                vec.begin()) %
               mod2 +
           mod2) %
          mod2;
    return;
  }
  for (int i = 0; i < 10; i++)
    dfs2(u + 1,
         (res + (p2[l - u - tp] - pw[l2 - u] + mod1) % mod1 * i % mod1) % mod1,
         l2, tp);
}
int main() {
  scanf("%s", n + 1);
  l = strlen(n + 1);
  if (l == 1) {
    printf("0\n");
    return 0;
  }
  pw[0] = 1;
  for (int i = 1; i <= l; i++) pw[i] = pw[i - 1] * 10 % mod1;
  p2[0] = 1;
  for (int i = 1; i <= l; i++) p2[i] = (p2[i - 1] * 10 % mod1 + 1) % mod1;
  for (int i = 1; i <= l; i++) {
    for (int j = 1; j <= i; j++)
      for (int k = j > 1 ? 0 : 1; k < (i < l ? 10 : n[j] - '0'); k++) {
        if (k == n[j] - '0') continue;
        bool tp = k > n[j] - '0';
        long long res = i + tp;
        if (j > 1) {
          res = (res + p2[l - 1 - tp] * (n[1] - '0' - 1) % mod1 -
                 pw[i - 1] * (n[1] - '0') % mod1 + mod1) %
                mod1;
          for (int x = 2; x < j; x++)
            res = (res + (p2[l - x - tp] - pw[i - x] + mod1) % mod1 *
                             (n[x] - '0') % mod1) %
                  mod1;
          res = (res + (p2[l - j - tp] - pw[i - j] + mod1) % mod1 * k % mod1) %
                mod1;
        } else
          res = (res + p2[l - 1 - tp] * (k - 1) % mod1 - pw[i - 1] * k % mod1 +
                 mod1) %
                mod1;
        if (tp)
          for (int x = 1; x <= l; x++)
            res = (res + (n[x] - '0' - (x == 1)) * pw[l - x] % mod1) % mod1;
        int mid = (i + j + 1) / 2;
        vec = {};
        dfs1(j + 1, 0, mid, i, tp);
        s = 0;
        for (long long i : vec) s = (s + i) % mod2;
        sort(vec.begin(), vec.end(), greater<long long>());
        dfs2(mid + 1, res, i, tp);
      }
    long long res = i;
    res = (res + p2[l - 1] * (n[1] - '0' - 1) % mod1 -
           pw[i - 1] * (n[1] - '0') % mod1 + mod1) %
          mod1;
    for (int j = 2; j <= i; j++)
      res =
          (res + (p2[l - j] - pw[i - j] + mod1) % mod1 * (n[j] - '0') % mod1) %
          mod1;
    ans = (ans + res) % mod2;
  }
  printf("%lld\n", ans);
  return 0;
}

```