#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &f) {
  f = 0;
  T fu = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') {
      fu = -1;
    }
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    f = (f << 3) + (f << 1) + (c & 15);
    c = getchar();
  }
  f *= fu;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + 48);
  else
    print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
  print(x);
  putchar(t);
}
const int md = 1e9 + 7, mod = 998244353;
inline int add(int x, int y) {
  if (x + y >= md) return x + y - md;
  return x + y;
}
inline void addx(int &x, int y) {
  x += y;
  if (x >= md) x -= md;
}
inline int sub(int x, int y) {
  if (x < y) return x - y + md;
  return x - y;
}
inline void subx(int &x, int y) {
  x -= y;
  if (x < 0) x += md;
}
inline int mul(int x, int y) { return 1ull * x * y % md; }
inline int fpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    y >>= 1;
    x = mul(x, x);
  }
  return ans;
}
int norm(int x) { return x >= mod ? x - mod : x; }
int reduce(int x) { return x < 0 ? x + mod : x; }
const int N = 1e6 + 5;
vector<int> rk[10];
int all[10], kr[N];
long long n, pw = 1;
int ans;
int tot;
void dfs1(int now) {
  if (now > n) return;
  if (now) kr[now] = ++tot;
  for (int i = (now == 0); i <= 9; i++) dfs1(now * 10 + i);
}
void dfs2(int u, int now, int len) {
  if (u != 1) {
    ++tot;
    rk[u - 1].push_back(reduce(tot - now));
  }
  if (u == len + 1) return;
  for (int i = 0; i <= 9; i++) dfs2(u + 1, now * 10 + i, len);
}
void ini(int len) {
  if (!len) return;
  tot = 0;
  for (int i = 1; i <= len; i++) rk[i].clear(), all[i] = 0;
  dfs2(1, 0, len);
  for (int i = 1; i <= len; i++) {
    sort(rk[i].begin(), rk[i].end());
    for (int j = 0; j < (int)rk[i].size(); j++) all[i] = add(all[i], rk[i][j]);
  }
}
int sum;
void dfs4(long long now) {
  if (now > n) return;
  if (now != n / pw / 10) {
    sum = norm(sum + 1);
    ans = add(ans, reduce(sum - now % mod));
  }
  for (int i = 0; i <= 9; i++) dfs4(now * 10 + i);
}
int len;
void dfs3(int u, int now) {
  if (now) {
    sum = norm(sum + 1);
    ans = add(ans, reduce(sum - now));
  }
  if (u == 7) {
    if (now == n / pw / 10) {
      dfs4(now);
      --len;
      ini(len);
    } else {
      int pw = 1, nsum = sum;
      for (int i = 1; i <= len; i++) {
        pw *= 10;
        int tem = reduce(sum - 1ll * now * pw % mod);
        int pos =
            lower_bound(rk[i].begin(), rk[i].end(), mod - tem) - rk[i].begin();
        int cnt = (int)rk[i].size() - pos;
        ans = add(ans, all[i]);
        ans = add(ans, mul((int)rk[i].size(), tem));
        ans = sub(ans, mul(mod, cnt));
        nsum = norm(nsum + (int)rk[i].size());
      }
      sum = nsum;
    }
    return;
  }
  for (int i = (now == 0); i <= 9; i++) dfs3(u + 1, now * 10 + i);
}
int main() {
  read(n);
  if (n < 1000000) {
    dfs1(0);
    for (int i = 1; i <= n; i++) {
      if (kr[i] < i)
        ans = add(ans, kr[i] - i + mod);
      else
        ans = add(ans, kr[i] - i);
    }
    print(ans, '\n');
    return 0;
  }
  while (n >= pw * 10) pw *= 10;
  pw /= 1000000;
  {
    len = 1;
    int tmp = pw;
    while (tmp != 1) {
      ++len;
      tmp /= 10;
    }
  }
  ini(len);
  dfs3(1, 0);
  print(ans, '\n');
  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;
template <typename T>
inline void read(T &f) {
  f = 0;
  T fu = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') {
      fu = -1;
    }
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    f = (f << 3) + (f << 1) + (c & 15);
    c = getchar();
  }
  f *= fu;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + 48);
  else
    print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
  print(x);
  putchar(t);
}
const int md = 1e9 + 7, mod = 998244353;
inline int add(int x, int y) {
  if (x + y >= md) return x + y - md;
  return x + y;
}
inline void addx(int &x, int y) {
  x += y;
  if (x >= md) x -= md;
}
inline int sub(int x, int y) {
  if (x < y) return x - y + md;
  return x - y;
}
inline void subx(int &x, int y) {
  x -= y;
  if (x < 0) x += md;
}
inline int mul(int x, int y) { return 1ull * x * y % md; }
inline int fpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    y >>= 1;
    x = mul(x, x);
  }
  return ans;
}
int norm(int x) { return x >= mod ? x - mod : x; }
int reduce(int x) { return x < 0 ? x + mod : x; }
const int N = 1e6 + 5;
vector<int> rk[10];
int all[10], kr[N];
long long n, pw = 1;
int ans;
int tot;
void dfs1(int now) {
  if (now > n) return;
  if (now) kr[now] = ++tot;
  for (int i = (now == 0); i <= 9; i++) dfs1(now * 10 + i);
}
void dfs2(int u, int now, int len) {
  if (u != 1) {
    ++tot;
    rk[u - 1].push_back(reduce(tot - now));
  }
  if (u == len + 1) return;
  for (int i = 0; i <= 9; i++) dfs2(u + 1, now * 10 + i, len);
}
void ini(int len) {
  if (!len) return;
  tot = 0;
  for (int i = 1; i <= len; i++) rk[i].clear(), all[i] = 0;
  dfs2(1, 0, len);
  for (int i = 1; i <= len; i++) {
    sort(rk[i].begin(), rk[i].end());
    for (int j = 0; j < (int)rk[i].size(); j++) all[i] = add(all[i], rk[i][j]);
  }
}
int sum;
void dfs4(long long now) {
  if (now > n) return;
  if (now != n / pw / 10) {
    sum = norm(sum + 1);
    ans = add(ans, reduce(sum - now % mod));
  }
  for (int i = 0; i <= 9; i++) dfs4(now * 10 + i);
}
int len;
void dfs3(int u, int now) {
  if (now) {
    sum = norm(sum + 1);
    ans = add(ans, reduce(sum - now));
  }
  if (u == 7) {
    if (now == n / pw / 10) {
      dfs4(now);
      --len;
      ini(len);
    } else {
      int pw = 1, nsum = sum;
      for (int i = 1; i <= len; i++) {
        pw *= 10;
        int tem = reduce(sum - 1ll * now * pw % mod);
        int pos =
            lower_bound(rk[i].begin(), rk[i].end(), mod - tem) - rk[i].begin();
        int cnt = (int)rk[i].size() - pos;
        ans = add(ans, all[i]);
        ans = add(ans, mul((int)rk[i].size(), tem));
        ans = sub(ans, mul(mod, cnt));
        nsum = norm(nsum + (int)rk[i].size());
      }
      sum = nsum;
    }
    return;
  }
  for (int i = (now == 0); i <= 9; i++) dfs3(u + 1, now * 10 + i);
}
int main() {
  read(n);
  if (n < 1000000) {
    dfs1(0);
    for (int i = 1; i <= n; i++) {
      if (kr[i] < i)
        ans = add(ans, kr[i] - i + mod);
      else
        ans = add(ans, kr[i] - i);
    }
    print(ans, '\n');
    return 0;
  }
  while (n >= pw * 10) pw *= 10;
  pw /= 1000000;
  {
    len = 1;
    int tmp = pw;
    while (tmp != 1) {
      ++len;
      tmp /= 10;
    }
  }
  ini(len);
  dfs3(1, 0);
  print(ans, '\n');
  return 0;
}

```