259_D. Little Elephant and Elections_10263
There have recently been elections in the zoo. Overall there were 7 main political parties: one of them is the Little Elephant Political Party, 6 other parties have less catchy names.

Political parties find their number in the ballot highly important. Overall there are m possible numbers: 1, 2, ..., m. Each of these 7 parties is going to be assigned in some way to exactly one number, at that, two distinct parties cannot receive the same number.

The Little Elephant Political Party members believe in the lucky digits 4 and 7. They want to evaluate their chances in the elections. For that, they need to find out, how many correct assignments are there, such that the number of lucky digits in the Little Elephant Political Party ballot number is strictly larger than the total number of lucky digits in the ballot numbers of 6 other parties. 

Help the Little Elephant Political Party, calculate this number. As the answer can be rather large, print the remainder from dividing it by 1000000007 (109 + 7).

Input

A single line contains a single positive integer m (7 ≤ m ≤ 109) — the number of possible numbers in the ballot.

Output

In a single line print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

Examples

Input

7


Output

0


Input

8


Output

1440
#include <bits/stdc++.h>
int m, n = 0, num[(20)];
long long f[(20)][(20)], cnt[(20)], ans = 0;
void CountBit(int m);
long long dfs(int bit, int value, bool limit);
void solve(int p, int s, int q, long long tot);
int main() {
  scanf("%d", &m);
  CountBit(m);
  memset(f, 0xff, sizeof(f));
  for (int i = 0; i <= n; i++) cnt[i] = dfs(n, i, true);
  cnt[0]--;
  for (int i = 1; i <= n; i++) solve(0, 1, i, cnt[i]);
  printf(
      "%I64d"
      "\n",
      ans);
  return 0;
}
void solve(int p, int s, int q, long long tot) {
  if (p >= q) return;
  if (s == 7) {
    if (q > p) ans += tot, ans %= (1000000007LL);
    return;
  }
  for (int i = 0; i < q; i++) {
    if (cnt[i]) {
      cnt[i]--;
      solve(p + i, s + 1, q, tot * (cnt[i] + 1) % (1000000007LL));
      cnt[i]++;
    }
  }
}
long long dfs(int bit, int value, bool limit) {
  long long ret = 0, &save = f[bit][value];
  if (!bit) {
    if (!value) return save = 1;
    return 0;
  }
  if (!limit && (~save)) return save;
  int border = limit ? num[bit] : 9;
  for (int i = 0; i <= border; i++)
    ret += dfs(bit - 1, value - (i == 4 || i == 7), limit && i == border);
  if (!limit) save = ret;
  return ret;
}
void CountBit(int m) {
  while (m) num[++n] = m % 10, m /= 10;
}

8
 7
 44
 30
 987549745
 674810014
 545794012
 15478459
 1000
 1000000
 794512405
 42
 10000
 25
 245
 301542785
 9
 10000000
 10
 40
 74
 68745844
 1000000000
 458754
 11
 100000000
 54785
 128
 100000
 47
 76
 38
 794363157
 445440595
 7740009
 20
 10010
 37
 396
 310999586
 3
 10001000
 14
 46
 107
 3155051
 327403
 32
 100000001
 21918
 104
 101000
 53
 22
 131
 103030222
 813491179
 4617957
 34
 10110
 17
 785
 100369446
 10001010
 33
 70
 793339
 397951
 59
 1951
 144
 101010
 77
 16
 12
 227
 158781220
 740897485
 7270579
 52
 11110
 31
 720
 4
 2
 1

1440
 0
 359621144
 581454720
 206294274
 550536983
 829479797
 638813679
 193577116
 638519268
 90508418
 831345485
 726889821
 139536000
 528398086
 763583849
 10080
 994715261
 40320
 771100852
 257814864
 739902866
 14594961
 667496909
 120960
 133127802
 118850209
 879893164
 459307763
 907362803
 346536310
 420143979
 200269697
 649450926
 508805876
 23063040
 573979997
 736115186
 578701143
 596714021
 0
 593687751
 997920
 664537617
 322796220
 69083282
 428250161
 994593600
 871990922
 563619476
 420182328
 818307750
 515674684
 53464320
 271502795
 405590973
 581468834
 156723979
 491890393
 308416248
 4942080
 601102153
 478382308
 91883995
 278763193
 200522672
 581784804
 570165282
 905392213
 305583950
 900585527
 762579139
 792926698
 3706560
 302400
 798970472
 51467497
 326692497
 85781298
 840973919
 810788396
 765072000
 637686688
 0
 0
 0
