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
49772
 4772
 1000
 272
 5000000
 1
 999999999971
 11000000017
 999999999989
 999999
 999999999980
 999999999978
 999999999997
 110000000017
 1117
 10000001
 999999999974
 4999772
 100000001
 127
 9
 10
 4999999772
 28
 13
 99999
 499772
 5000
 11000017
 5000000000
 499999999772
 49999772
 101
 2
 999999999995
 500000000
 1000000
 999999999
 999999999981
 1000001
 999999999979
 999999999986
 19
 110000017
 999999999999
 15
 10000000
 9999999999
 99999999999
 999999999985
 999999999998
 500000000000
 99
 18
 16
 50000000000
 25
 6
 10000000000
 999
 14
 100000
 7
 999999999988
 999999999972
 26
 110017
 1000000000
 999999999983
 999999999977
 50000000
 23
 1001
 100000000
 1100017
 50
 20
 11
 100000000000
 100000000001
 999999999992
 999999999984
 22
 27
 999999999994
 100001
 1000000001
 11017
 500
 999999999990
 99999999
 1100000017
 499999772
 10000
 999999999973
 100
 999999999991
 999999999975
 9999999
 999999999976
 999999999996
 999999999993
 49999999772
 999999999982
 500000
 29
 30
 5
 17
 24
 4
 50000
 9999
 999999999987
 10001
 8
 10000000001

995052901
 356605313
 451513186
 694516211
 853844097
 0
 333709237
 373998013
 302107465
 171557960
 317908351
 321419659
 302107465
 585402415
 773520641
 634819509
 328442275
 254133202
 935616365
 949086041
 0
 998244353
 268322335
 966642581
 992977391
 831376599
 379528732
 956316208
 59762503
 467123902
 414128261
 984377030
 891149459
 0
 302107465
 930417499
 187358846
 439402098
 316152697
 203159732
 319664005
 307374427
 982443467
 955778446
 302107465
 989466083
 619018623
 721104268
 431235549
 309130081
 302107465
 224827737
 859547687
 984199121
 987710429
 335161312
 971909543
 0
 736905154
 435712300
 991221737
 847177485
 0
 303863119
 331953583
 970153889
 654448714
 453447330
 312641389
 323175313
 584087918
 975420851
 467314072
 919815479
 874550050
 928018193
 980687813
 996488699
 440013819
 478638207
 302107465
 310885735
 977176505
 968398235
 302107465
 862978371
 467492562
 35423188
 294227099
 302107465
 904014593
 262194816
 330706604
 213159344
 330197929
 875348573
 302107465
 326686621
 603217737
 324930967
 302107465
 302107465
 900792008
 314397043
 979239627
 964886927
 963131273
 0
 985954775
 973665197
 0
 594763789
 197358458
 305618773
 228960230
 0
 754461694

#include <bits/stdc++.h>
using namespace std;
const long long p = 998244353;
const long long mod = 1e9 + 7;
long long read() {
  long long s = 0;
  char c = getchar(), lc = '+';
  while (c < '0' || '9' < c) lc = c, c = getchar();
  while ('0' <= c && c <= '9') s = s * 10 + c - '0', c = getchar();
  return lc == '-' ? -s : s;
}
void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + '0');
  else
    write(x / 10), putchar(x % 10 + '0');
}
void print(long long x, char c = '\n') {
  write(x);
  putchar(c);
}
long long pw[8], sum[7], cnt = 0, ans = 0, n;
vector<long long> v[7];
void dfs0(long long deep, long long val) {
  v[deep].push_back((cnt++ - val + p) % p);
  if (deep < 6)
    for (long long i = 0; i <= 9; i++) dfs0(deep + 1, val * 10 + i);
}
void dfs1(long long deep, long long val) {
  static long long idx = 0;
  if (val > n) return;
  if (val * pw[6] > n / 10 && (val + 1) * pw[6] - 1 <= n) {
    for (long long i = 0; i <= 6; i++) {
      long long now = (idx - val % p * pw[i] % p + p) % p, siz = v[i].size();
      long long tot =
          v[i].end() - lower_bound(v[i].begin(), v[i].end(), p - now);
      ans = (ans + sum[i] + now * siz - p * tot) % mod;
    }
    idx += cnt;
    return;
  }
  ans = (ans + (idx++ - val % p + p) % p) % mod;
  for (long long i = !deep; i <= 9; i++) dfs1(deep + 1, val * 10 + i);
}
void Multi_test_no_horses() {
  n = read();
  dfs0(0, 0);
  for (long long i = pw[0] = 1; i <= 7; i++) pw[i] = pw[i - 1] * 10;
  for (long long i = 0; i <= 6; i++) {
    sort(v[i].begin(), v[i].end());
    for (long long j : v[i]) sum[i] += j;
  }
  dfs1(0, 0);
  print(ans);
}
signed main(signed Hello, char *CodeForces[]) {
  (void)Hello, (void)CodeForces;
  long long T = 1;
  while (T--) Multi_test_no_horses();
  return 0;
}
