#include <bits/stdc++.h>
using namespace std;
long long n;
int ans = 0;
int digcnt;
long long pref[20];
long long pwr10[20];
long long count_pref(long long x, int digits) {
  if (digits == 0) return n;
  long long Ans = 0;
  for (int i = digits; i < digcnt; i++) {
    Ans += pwr10[i - digits];
  }
  if (x < pref[digits]) {
    Ans += pwr10[digcnt - digits];
  } else if (x == pref[digits]) {
    Ans += n - x * pwr10[digcnt - digits] + 1;
  }
  return Ans;
}
void dfs(long long x, int digits, int upto, long long presum) {
  if (upto == digcnt) {
    if (x > pref[digits]) return;
    if (x == pref[digits] && digits < upto) {
      long long cursum = presum;
      for (long long nxt = pref[digits] * 10LL; nxt <= pref[digits + 1];
           nxt++) {
        if (digits || nxt) {
          dfs(nxt, digits + 1, upto, cursum + 1);
          cursum += count_pref(nxt, digits + 1);
        }
      }
      return;
    }
  }
  if (digits == upto) {
    ans -= (((presum + 1LL - x) + 1000000LL * 998244353LL) / 998244353LL -
            1000000LL);
    if (ans < 0) ans += 1000000007;
    if (ans >= 1000000007) ans -= 1000000007;
    return;
  }
  if (digits > 0) {
    long long mina = x * pwr10[upto - digits];
    long long maxa = mina + pwr10[upto - digits] - 1;
    long long mini = presum;
    long long maxi = presum + count_pref(x, digits);
    if ((((maxi - mina) + 1000000LL * 998244353LL) / 998244353LL - 1000000LL) ==
        (((mini - maxa) + 1000000LL * 998244353LL) / 998244353LL - 1000000LL)) {
      ans -= (((long long)((((maxi - mina) + 1000000LL * 998244353LL) /
                                998244353LL -
                            1000000LL) +
                           1000000007) *
               (long long)(pwr10[upto - digits] % 1000000007)) %
              1000000007);
      if (ans < 0) ans += 1000000007;
      if (ans >= 1000000007) ans -= 1000000007;
      return;
    }
  }
  long long cursum = presum;
  for (long long nxt = x * 10LL; nxt < (x + 1LL) * 10LL; nxt++) {
    if (digits || nxt) {
      dfs(nxt, digits + 1, upto, cursum + 1);
      cursum += count_pref(nxt, digits + 1);
    }
  }
}
int main() {
  pwr10[0] = 1LL;
  for (int i = 1; i <= 15; i++) {
    pwr10[i] = 10LL * pwr10[i - 1];
  }
  scanf("%lld", &n);
  char tmp[20];
  sprintf(tmp, "%lld", n);
  digcnt = strlen(tmp);
  long long tmp2 = n;
  for (int i = 0; i < digcnt; i++) {
    pref[digcnt - i] = tmp2;
    tmp2 /= 10LL;
  }
  for (int i = 1; i <= digcnt; i++) {
    dfs(0, 0, i, -1);
  }
  ans = (((long long)(ans) * (long long)(998244353)) % 1000000007);
  printf("%d", 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;
long long n;
int ans = 0;
int digcnt;
long long pref[20];
long long pwr10[20];
long long count_pref(long long x, int digits) {
  if (digits == 0) return n;
  long long Ans = 0;
  for (int i = digits; i < digcnt; i++) {
    Ans += pwr10[i - digits];
  }
  if (x < pref[digits]) {
    Ans += pwr10[digcnt - digits];
  } else if (x == pref[digits]) {
    Ans += n - x * pwr10[digcnt - digits] + 1;
  }
  return Ans;
}
void dfs(long long x, int digits, int upto, long long presum) {
  if (upto == digcnt) {
    if (x > pref[digits]) return;
    if (x == pref[digits] && digits < upto) {
      long long cursum = presum;
      for (long long nxt = pref[digits] * 10LL; nxt <= pref[digits + 1];
           nxt++) {
        if (digits || nxt) {
          dfs(nxt, digits + 1, upto, cursum + 1);
          cursum += count_pref(nxt, digits + 1);
        }
      }
      return;
    }
  }
  if (digits == upto) {
    ans -= (((presum + 1LL - x) + 1000000LL * 998244353LL) / 998244353LL -
            1000000LL);
    if (ans < 0) ans += 1000000007;
    if (ans >= 1000000007) ans -= 1000000007;
    return;
  }
  if (digits > 0) {
    long long mina = x * pwr10[upto - digits];
    long long maxa = mina + pwr10[upto - digits] - 1;
    long long mini = presum;
    long long maxi = presum + count_pref(x, digits);
    if ((((maxi - mina) + 1000000LL * 998244353LL) / 998244353LL - 1000000LL) ==
        (((mini - maxa) + 1000000LL * 998244353LL) / 998244353LL - 1000000LL)) {
      ans -= (((long long)((((maxi - mina) + 1000000LL * 998244353LL) /
                                998244353LL -
                            1000000LL) +
                           1000000007) *
               (long long)(pwr10[upto - digits] % 1000000007)) %
              1000000007);
      if (ans < 0) ans += 1000000007;
      if (ans >= 1000000007) ans -= 1000000007;
      return;
    }
  }
  long long cursum = presum;
  for (long long nxt = x * 10LL; nxt < (x + 1LL) * 10LL; nxt++) {
    if (digits || nxt) {
      dfs(nxt, digits + 1, upto, cursum + 1);
      cursum += count_pref(nxt, digits + 1);
    }
  }
}
int main() {
  pwr10[0] = 1LL;
  for (int i = 1; i <= 15; i++) {
    pwr10[i] = 10LL * pwr10[i - 1];
  }
  scanf("%lld", &n);
  char tmp[20];
  sprintf(tmp, "%lld", n);
  digcnt = strlen(tmp);
  long long tmp2 = n;
  for (int i = 0; i < digcnt; i++) {
    pref[digcnt - i] = tmp2;
    tmp2 /= 10LL;
  }
  for (int i = 1; i <= digcnt; i++) {
    dfs(0, 0, i, -1);
  }
  ans = (((long long)(ans) * (long long)(998244353)) % 1000000007);
  printf("%d", ans);
  return 0;
}

```