#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
const long long mod2 = 998244353;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
vector<int> pos[10];
int cnt;
long long pw[15], s[15];
long long cnt2, n;
int ans;
int query(int fixpre, long long val) {
  long long ans = 0;
  for (int d = 0; d < 7; d++) {
    long long offset = (val - fixpre * pw[d]) % mod2;
    if (offset < 0) offset += mod2;
    int p = lower_bound((pos[d]).begin(), (pos[d]).end(), mod2 - offset) -
            pos[d].begin();
    ans = (ans + s[d] + offset * ((int)(pos[d]).size()) -
           mod2 * (((int)(pos[d]).size()) - p)) %
          mod;
  }
  return ans;
}
void dfs(int val, int d) {
  int x = (cnt - val + mod2) % mod2;
  pos[d].push_back(x);
  cnt++;
  s[d] += x;
  if (d == 6) return;
  for (int i = 0; i < 10; i++) dfs(val * 10 + i, d + 1);
}
void dfs2(long long val) {
  if (val * 1000000 + 999999 <= n && val * 10000000 > n) {
    ans = (ans + query(val, cnt2 + 1)) % mod;
    cnt2 += cnt;
  } else {
    cnt2++;
    ans = (ans + ((cnt2 - val) % mod2 + mod2) % mod2) % mod;
    for (int i = val ? 0 : 1; i < 10; i++) {
      if (val * 10 + i <= n) dfs2(val * 10 + i);
    }
  }
}
int main() {
  dfs(0, 0);
  for (int i = 0; i < 7; i++) sort((pos[i]).begin(), (pos[i]).end());
  pw[0] = 1;
  for (int i = 1; i < 13; i++) pw[i] = pw[i - 1] * 10;
  scanf("%lld", &n);
  cnt2 = -1;
  dfs2(0);
  printf("%d\n", ans);
}

### Prompt

Please create a solution in CPP 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 mod = 1000000007;
const long long mod2 = 998244353;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
vector<int> pos[10];
int cnt;
long long pw[15], s[15];
long long cnt2, n;
int ans;
int query(int fixpre, long long val) {
  long long ans = 0;
  for (int d = 0; d < 7; d++) {
    long long offset = (val - fixpre * pw[d]) % mod2;
    if (offset < 0) offset += mod2;
    int p = lower_bound((pos[d]).begin(), (pos[d]).end(), mod2 - offset) -
            pos[d].begin();
    ans = (ans + s[d] + offset * ((int)(pos[d]).size()) -
           mod2 * (((int)(pos[d]).size()) - p)) %
          mod;
  }
  return ans;
}
void dfs(int val, int d) {
  int x = (cnt - val + mod2) % mod2;
  pos[d].push_back(x);
  cnt++;
  s[d] += x;
  if (d == 6) return;
  for (int i = 0; i < 10; i++) dfs(val * 10 + i, d + 1);
}
void dfs2(long long val) {
  if (val * 1000000 + 999999 <= n && val * 10000000 > n) {
    ans = (ans + query(val, cnt2 + 1)) % mod;
    cnt2 += cnt;
  } else {
    cnt2++;
    ans = (ans + ((cnt2 - val) % mod2 + mod2) % mod2) % mod;
    for (int i = val ? 0 : 1; i < 10; i++) {
      if (val * 10 + i <= n) dfs2(val * 10 + i);
    }
  }
}
int main() {
  dfs(0, 0);
  for (int i = 0; i < 7; i++) sort((pos[i]).begin(), (pos[i]).end());
  pw[0] = 1;
  for (int i = 1; i < 13; i++) pw[i] = pw[i - 1] * 10;
  scanf("%lld", &n);
  cnt2 = -1;
  dfs2(0);
  printf("%d\n", ans);
}

```