Problem: 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long n, m, fl, numb[1000], tans, ans;
long long s, q, ar[100][100], arr[100];
void calc(long n) {
  long s = 0;
  while (n) {
    q = n % 10;
    if (q == 4) ++s;
    if (q == 7) ++s;
    n /= 10;
  }
  arr[s]++;
}
int main() {
  ios_base::sync_with_stdio(0);
  ar[1][0] = 3145728;
  ar[1][1] = 5505024;
  ar[1][2] = 4128768;
  ar[1][3] = 1720320;
  ar[1][4] = 430080;
  ar[1][5] = 64512;
  ar[1][6] = 5376;
  ar[1][7] = 192;
  ar[1][8] = 0;
  ar[1][9] = 0;
  ar[1][10] = 0;
  ar[2][0] = 6291456;
  ar[2][1] = 11010048;
  ar[2][2] = 8257536;
  ar[2][3] = 3440640;
  ar[2][4] = 860160;
  ar[2][5] = 129024;
  ar[2][6] = 10752;
  ar[2][7] = 384;
  ar[2][8] = 0;
  ar[2][9] = 0;
  ar[2][10] = 0;
  ar[3][0] = 8388607;
  ar[3][1] = 15728641;
  ar[3][2] = 12845056;
  ar[3][3] = 5963776;
  ar[3][4] = 1720320;
  ar[3][5] = 315392;
  ar[3][6] = 35840;
  ar[3][7] = 2304;
  ar[3][8] = 64;
  ar[3][9] = 0;
  ar[3][10] = 0;
  ar[4][0] = 10485760;
  ar[4][1] = 20447232;
  ar[4][2] = 17432576;
  ar[4][3] = 8486912;
  ar[4][4] = 2580480;
  ar[4][5] = 501760;
  ar[4][6] = 60928;
  ar[4][7] = 4224;
  ar[4][8] = 128;
  ar[4][9] = 0;
  ar[4][10] = 0;
  ar[5][0] = 12582911;
  ar[5][1] = 25165825;
  ar[5][2] = 22020096;
  ar[5][3] = 11010048;
  ar[5][4] = 3440640;
  ar[5][5] = 688128;
  ar[5][6] = 86016;
  ar[5][7] = 6144;
  ar[5][8] = 192;
  ar[5][9] = 0;
  ar[5][10] = 0;
  ar[6][0] = 14680064;
  ar[6][1] = 29884416;
  ar[6][2] = 26607616;
  ar[6][3] = 13533184;
  ar[6][4] = 4300800;
  ar[6][5] = 874496;
  ar[6][6] = 111104;
  ar[6][7] = 8064;
  ar[6][8] = 256;
  ar[6][9] = 0;
  ar[6][10] = 0;
  ar[7][0] = 17825792;
  ar[7][1] = 35389440;
  ar[7][2] = 30736384;
  ar[7][3] = 15253504;
  ar[7][4] = 4730880;
  ar[7][5] = 939008;
  ar[7][6] = 116480;
  ar[7][7] = 8256;
  ar[7][8] = 256;
  ar[7][9] = 0;
  ar[7][10] = 0;
  ar[8][0] = 20971520;
  ar[8][1] = 40894464;
  ar[8][2] = 34865152;
  ar[8][3] = 16973824;
  ar[8][4] = 5160960;
  ar[8][5] = 1003520;
  ar[8][6] = 121856;
  ar[8][7] = 8448;
  ar[8][8] = 256;
  ar[8][9] = 0;
  ar[8][10] = 0;
  ar[9][0] = 24117248;
  ar[9][1] = 46399488;
  ar[9][2] = 38993920;
  ar[9][3] = 18694144;
  ar[9][4] = 5591040;
  ar[9][5] = 1068032;
  ar[9][6] = 127232;
  ar[9][7] = 8640;
  ar[9][8] = 256;
  ar[9][9] = 0;
  ar[9][10] = 0;
  ar[10][0] = 25165824;
  ar[10][1] = 50331648;
  ar[10][2] = 44040192;
  ar[10][3] = 22020096;
  ar[10][4] = 6881280;
  ar[10][5] = 1376256;
  ar[10][6] = 172032;
  ar[10][7] = 12288;
  ar[10][8] = 384;
  ar[10][9] = 0;
  ar[10][10] = 0;
  ar[11][0] = 28311552;
  ar[11][1] = 55836672;
  ar[11][2] = 48168960;
  ar[11][3] = 23740416;
  ar[11][4] = 7311360;
  ar[11][5] = 1440768;
  ar[11][6] = 177408;
  ar[11][7] = 12480;
  ar[11][8] = 384;
  ar[11][9] = 0;
  ar[11][10] = 0;
  ar[12][0] = 29360128;
  ar[12][1] = 59768832;
  ar[12][2] = 53215232;
  ar[12][3] = 27066368;
  ar[12][4] = 8601600;
  ar[12][5] = 1748992;
  ar[12][6] = 222208;
  ar[12][7] = 16128;
  ar[12][8] = 512;
  ar[12][9] = 0;
  ar[12][10] = 0;
  ar[13][0] = 32505856;
  ar[13][1] = 65273856;
  ar[13][2] = 57344000;
  ar[13][3] = 28786688;
  ar[13][4] = 9031680;
  ar[13][5] = 1813504;
  ar[13][6] = 227584;
  ar[13][7] = 16320;
  ar[13][8] = 512;
  ar[13][9] = 0;
  ar[13][10] = 0;
  ar[14][0] = 35651584;
  ar[14][1] = 70778880;
  ar[14][2] = 61472768;
  ar[14][3] = 30507008;
  ar[14][4] = 9461760;
  ar[14][5] = 1878016;
  ar[14][6] = 232960;
  ar[14][7] = 16512;
  ar[14][8] = 512;
  ar[14][9] = 0;
  ar[14][10] = 0;
  ar[15][0] = 38797312;
  ar[15][1] = 76283904;
  ar[15][2] = 65601536;
  ar[15][3] = 32227328;
  ar[15][4] = 9891840;
  ar[15][5] = 1942528;
  ar[15][6] = 238336;
  ar[15][7] = 16704;
  ar[15][8] = 512;
  ar[15][9] = 0;
  ar[15][10] = 0;
  ar[16][0] = 41943039;
  ar[16][1] = 81788929;
  ar[16][2] = 69730304;
  ar[16][3] = 33947648;
  ar[16][4] = 10321920;
  ar[16][5] = 2007040;
  ar[16][6] = 243712;
  ar[16][7] = 16896;
  ar[16][8] = 512;
  ar[16][9] = 0;
  ar[16][10] = 0;
  ar[17][0] = 42991616;
  ar[17][1] = 85721088;
  ar[17][2] = 74776576;
  ar[17][3] = 37273600;
  ar[17][4] = 11612160;
  ar[17][5] = 2315264;
  ar[17][6] = 288512;
  ar[17][7] = 20544;
  ar[17][8] = 640;
  ar[17][9] = 0;
  ar[17][10] = 0;
  ar[18][0] = 46137343;
  ar[18][1] = 91226113;
  ar[18][2] = 78905344;
  ar[18][3] = 38993920;
  ar[18][4] = 12042240;
  ar[18][5] = 2379776;
  ar[18][6] = 293888;
  ar[18][7] = 20736;
  ar[18][8] = 640;
  ar[18][9] = 0;
  ar[18][10] = 0;
  ar[19][0] = 47185920;
  ar[19][1] = 95158272;
  ar[19][2] = 83951616;
  ar[19][3] = 42319872;
  ar[19][4] = 13332480;
  ar[19][5] = 2688000;
  ar[19][6] = 338688;
  ar[19][7] = 24384;
  ar[19][8] = 768;
  ar[19][9] = 0;
  ar[19][10] = 0;
  ar[20][0] = 50331648;
  ar[20][1] = 100663296;
  ar[20][2] = 88080384;
  ar[20][3] = 44040192;
  ar[20][4] = 13762560;
  ar[20][5] = 2752512;
  ar[20][6] = 344064;
  ar[20][7] = 24576;
  ar[20][8] = 768;
  ar[20][9] = 0;
  ar[20][10] = 0;
  ar[21][0] = 53477376;
  ar[21][1] = 106168320;
  ar[21][2] = 92209152;
  ar[21][3] = 45760512;
  ar[21][4] = 14192640;
  ar[21][5] = 2817024;
  ar[21][6] = 349440;
  ar[21][7] = 24768;
  ar[21][8] = 768;
  ar[21][9] = 0;
  ar[21][10] = 0;
  ar[22][0] = 56623104;
  ar[22][1] = 111673344;
  ar[22][2] = 96337920;
  ar[22][3] = 47480832;
  ar[22][4] = 14622720;
  ar[22][5] = 2881536;
  ar[22][6] = 354816;
  ar[22][7] = 24960;
  ar[22][8] = 768;
  ar[22][9] = 0;
  ar[22][10] = 0;
  ar[23][0] = 58720255;
  ar[23][1] = 116391937;
  ar[23][2] = 100925440;
  ar[23][3] = 50003968;
  ar[23][4] = 15482880;
  ar[23][5] = 3067904;
  ar[23][6] = 379904;
  ar[23][7] = 26880;
  ar[23][8] = 832;
  ar[23][9] = 0;
  ar[23][10] = 0;
  ar[24][0] = 60817408;
  ar[24][1] = 121110528;
  ar[24][2] = 105512960;
  ar[24][3] = 52527104;
  ar[24][4] = 16343040;
  ar[24][5] = 3254272;
  ar[24][6] = 404992;
  ar[24][7] = 28800;
  ar[24][8] = 896;
  ar[24][9] = 0;
  ar[24][10] = 0;
  ar[25][0] = 62914559;
  ar[25][1] = 125829121;
  ar[25][2] = 110100480;
  ar[25][3] = 55050240;
  ar[25][4] = 17203200;
  ar[25][5] = 3440640;
  ar[25][6] = 430080;
  ar[25][7] = 30720;
  ar[25][8] = 960;
  ar[25][9] = 0;
  ar[25][10] = 0;
  ar[26][0] = 65011712;
  ar[26][1] = 130547712;
  ar[26][2] = 114688000;
  ar[26][3] = 57573376;
  ar[26][4] = 18063360;
  ar[26][5] = 3627008;
  ar[26][6] = 455168;
  ar[26][7] = 32640;
  ar[26][8] = 1024;
  ar[26][9] = 0;
  ar[26][10] = 0;
  ar[27][0] = 67108863;
  ar[27][1] = 135266305;
  ar[27][2] = 119275520;
  ar[27][3] = 60096512;
  ar[27][4] = 18923520;
  ar[27][5] = 3813376;
  ar[27][6] = 480256;
  ar[27][7] = 34560;
  ar[27][8] = 1088;
  ar[27][9] = 0;
  ar[27][10] = 0;
  ar[28][0] = 67108863;
  ar[28][1] = 138412033;
  ar[28][2] = 124780544;
  ar[28][3] = 64225280;
  ar[28][4] = 20643840;
  ar[28][5] = 4243456;
  ar[28][6] = 544768;
  ar[28][7] = 39936;
  ar[28][8] = 1280;
  ar[28][9] = 0;
  ar[28][10] = 0;
  ar[29][0] = 67108863;
  ar[29][1] = 141557761;
  ar[29][2] = 130285568;
  ar[29][3] = 68354048;
  ar[29][4] = 22364160;
  ar[29][5] = 4673536;
  ar[29][6] = 609280;
  ar[29][7] = 45312;
  ar[29][8] = 1472;
  ar[29][9] = 0;
  ar[29][10] = 0;
  ar[30][0] = 67108863;
  ar[30][1] = 142606337;
  ar[30][2] = 134217728;
  ar[30][3] = 73400320;
  ar[30][4] = 25690112;
  ar[30][5] = 5963776;
  ar[30][6] = 917504;
  ar[30][7] = 90112;
  ar[30][8] = 5120;
  ar[30][9] = 128;
  ar[30][10] = 0;
  ar[31][0] = 67108863;
  ar[31][1] = 145752065;
  ar[31][2] = 139722752;
  ar[31][3] = 77529088;
  ar[31][4] = 27410432;
  ar[31][5] = 6393856;
  ar[31][6] = 982016;
  ar[31][7] = 95488;
  ar[31][8] = 5312;
  ar[31][9] = 128;
  ar[31][10] = 0;
  ar[32][0] = 67108863;
  ar[32][1] = 146800641;
  ar[32][2] = 143654912;
  ar[32][3] = 82575360;
  ar[32][4] = 30736384;
  ar[32][5] = 7684096;
  ar[32][6] = 1290240;
  ar[32][7] = 140288;
  ar[32][8] = 8960;
  ar[32][9] = 256;
  ar[32][10] = 0;
  ar[33][0] = 67108863;
  ar[33][1] = 149946369;
  ar[33][2] = 149159936;
  ar[33][3] = 86704128;
  ar[33][4] = 32456704;
  ar[33][5] = 8114176;
  ar[33][6] = 1354752;
  ar[33][7] = 145664;
  ar[33][8] = 9152;
  ar[33][9] = 256;
  ar[33][10] = 0;
  ar[34][0] = 69206016;
  ar[34][1] = 154664960;
  ar[34][2] = 153747456;
  ar[34][3] = 89227264;
  ar[34][4] = 33316864;
  ar[34][5] = 8300544;
  ar[34][6] = 1379840;
  ar[34][7] = 147584;
  ar[34][8] = 9216;
  ar[34][9] = 256;
  ar[34][10] = 0;
  ar[35][0] = 72351744;
  ar[35][1] = 160169984;
  ar[35][2] = 157876224;
  ar[35][3] = 90947584;
  ar[35][4] = 33746944;
  ar[35][5] = 8365056;
  ar[35][6] = 1385216;
  ar[35][7] = 147776;
  ar[35][8] = 9216;
  ar[35][9] = 256;
  ar[35][10] = 0;
  ar[36][0] = 75497471;
  ar[36][1] = 165675009;
  ar[36][2] = 162004992;
  ar[36][3] = 92667904;
  ar[36][4] = 34177024;
  ar[36][5] = 8429568;
  ar[36][6] = 1390592;
  ar[36][7] = 147968;
  ar[36][8] = 9216;
  ar[36][9] = 256;
  ar[36][10] = 0;
  ar[37][0] = 76546048;
  ar[37][1] = 169607168;
  ar[37][2] = 167051264;
  ar[37][3] = 95993856;
  ar[37][4] = 35467264;
  ar[37][5] = 8737792;
  ar[37][6] = 1435392;
  ar[37][7] = 151616;
  ar[37][8] = 9344;
  ar[37][9] = 256;
  ar[37][10] = 0;
  ar[38][0] = 79691775;
  ar[38][1] = 175112193;
  ar[38][2] = 171180032;
  ar[38][3] = 97714176;
  ar[38][4] = 35897344;
  ar[38][5] = 8802304;
  ar[38][6] = 1440768;
  ar[38][7] = 151808;
  ar[38][8] = 9344;
  ar[38][9] = 256;
  ar[38][10] = 0;
  ar[39][0] = 80740352;
  ar[39][1] = 179044352;
  ar[39][2] = 176226304;
  ar[39][3] = 101040128;
  ar[39][4] = 37187584;
  ar[39][5] = 9110528;
  ar[39][6] = 1485568;
  ar[39][7] = 155456;
  ar[39][8] = 9472;
  ar[39][9] = 256;
  ar[39][10] = 0;
  ar[40][0] = 83886080;
  ar[40][1] = 184549376;
  ar[40][2] = 180355072;
  ar[40][3] = 102760448;
  ar[40][4] = 37617664;
  ar[40][5] = 9175040;
  ar[40][6] = 1490944;
  ar[40][7] = 155648;
  ar[40][8] = 9472;
  ar[40][9] = 256;
  ar[40][10] = 0;
  ar[41][0] = 87031808;
  ar[41][1] = 190054400;
  ar[41][2] = 184483840;
  ar[41][3] = 104480768;
  ar[41][4] = 38047744;
  ar[41][5] = 9239552;
  ar[41][6] = 1496320;
  ar[41][7] = 155840;
  ar[41][8] = 9472;
  ar[41][9] = 256;
  ar[41][10] = 0;
  ar[42][0] = 90177536;
  ar[42][1] = 195559424;
  ar[42][2] = 188612608;
  ar[42][3] = 106201088;
  ar[42][4] = 38477824;
  ar[42][5] = 9304064;
  ar[42][6] = 1501696;
  ar[42][7] = 156032;
  ar[42][8] = 9472;
  ar[42][9] = 256;
  ar[42][10] = 0;
  ar[43][0] = 92274687;
  ar[43][1] = 200278017;
  ar[43][2] = 193200128;
  ar[43][3] = 108724224;
  ar[43][4] = 39337984;
  ar[43][5] = 9490432;
  ar[43][6] = 1526784;
  ar[43][7] = 157952;
  ar[43][8] = 9536;
  ar[43][9] = 256;
  ar[43][10] = 0;
  ar[44][0] = 94371840;
  ar[44][1] = 204996608;
  ar[44][2] = 197787648;
  ar[44][3] = 111247360;
  ar[44][4] = 40198144;
  ar[44][5] = 9676800;
  ar[44][6] = 1551872;
  ar[44][7] = 159872;
  ar[44][8] = 9600;
  ar[44][9] = 256;
  ar[44][10] = 0;
  ar[45][0] = 96468991;
  ar[45][1] = 209715201;
  ar[45][2] = 202375168;
  ar[45][3] = 113770496;
  ar[45][4] = 41058304;
  ar[45][5] = 9863168;
  ar[45][6] = 1576960;
  ar[45][7] = 161792;
  ar[45][8] = 9664;
  ar[45][9] = 256;
  ar[45][10] = 0;
  ar[46][0] = 98566144;
  ar[46][1] = 214433792;
  ar[46][2] = 206962688;
  ar[46][3] = 116293632;
  ar[46][4] = 41918464;
  ar[46][5] = 10049536;
  ar[46][6] = 1602048;
  ar[46][7] = 163712;
  ar[46][8] = 9728;
  ar[46][9] = 256;
  ar[46][10] = 0;
  ar[47][0] = 100663295;
  ar[47][1] = 219152385;
  ar[47][2] = 211550208;
  ar[47][3] = 118816768;
  ar[47][4] = 42778624;
  ar[47][5] = 10235904;
  ar[47][6] = 1627136;
  ar[47][7] = 165632;
  ar[47][8] = 9792;
  ar[47][9] = 256;
  ar[47][10] = 0;
  ar[48][0] = 100663295;
  ar[48][1] = 222298113;
  ar[48][2] = 217055232;
  ar[48][3] = 122945536;
  ar[48][4] = 44498944;
  ar[48][5] = 10665984;
  ar[48][6] = 1691648;
  ar[48][7] = 171008;
  ar[48][8] = 9984;
  ar[48][9] = 256;
  ar[48][10] = 0;
  ar[49][0] = 100663295;
  ar[49][1] = 225443841;
  ar[49][2] = 222560256;
  ar[49][3] = 127074304;
  ar[49][4] = 46219264;
  ar[49][5] = 11096064;
  ar[49][6] = 1756160;
  ar[49][7] = 176384;
  ar[49][8] = 10176;
  ar[49][9] = 256;
  ar[49][10] = 0;
  ar[50][0] = 100663295;
  ar[50][1] = 226492417;
  ar[50][2] = 226492416;
  ar[50][3] = 132120576;
  ar[50][4] = 49545216;
  ar[50][5] = 12386304;
  ar[50][6] = 2064384;
  ar[50][7] = 221184;
  ar[50][8] = 13824;
  ar[50][9] = 384;
  ar[50][10] = 0;
  ar[51][0] = 100663295;
  ar[51][1] = 229638145;
  ar[51][2] = 231997440;
  ar[51][3] = 136249344;
  ar[51][4] = 51265536;
  ar[51][5] = 12816384;
  ar[51][6] = 2128896;
  ar[51][7] = 226560;
  ar[51][8] = 14016;
  ar[51][9] = 384;
  ar[51][10] = 0;
  ar[52][0] = 100663295;
  ar[52][1] = 230686721;
  ar[52][2] = 235929600;
  ar[52][3] = 141295616;
  ar[52][4] = 54591488;
  ar[52][5] = 14106624;
  ar[52][6] = 2437120;
  ar[52][7] = 271360;
  ar[52][8] = 17664;
  ar[52][9] = 512;
  ar[52][10] = 0;
  ar[53][0] = 100663295;
  ar[53][1] = 233832449;
  ar[53][2] = 241434624;
  ar[53][3] = 145424384;
  ar[53][4] = 56311808;
  ar[53][5] = 14536704;
  ar[53][6] = 2501632;
  ar[53][7] = 276736;
  ar[53][8] = 17856;
  ar[53][9] = 512;
  ar[53][10] = 0;
  ar[54][0] = 102760448;
  ar[54][1] = 238551040;
  ar[54][2] = 246022144;
  ar[54][3] = 147947520;
  ar[54][4] = 57171968;
  ar[54][5] = 14723072;
  ar[54][6] = 2526720;
  ar[54][7] = 278656;
  ar[54][8] = 17920;
  ar[54][9] = 512;
  ar[54][10] = 0;
  ar[55][0] = 105906176;
  ar[55][1] = 244056064;
  ar[55][2] = 250150912;
  ar[55][3] = 149667840;
  ar[55][4] = 57602048;
  ar[55][5] = 14787584;
  ar[55][6] = 2532096;
  ar[55][7] = 278848;
  ar[55][8] = 17920;
  ar[55][9] = 512;
  ar[55][10] = 0;
  ar[56][0] = 109051903;
  ar[56][1] = 249561089;
  ar[56][2] = 254279680;
  ar[56][3] = 151388160;
  ar[56][4] = 58032128;
  ar[56][5] = 14852096;
  ar[56][6] = 2537472;
  ar[56][7] = 279040;
  ar[56][8] = 17920;
  ar[56][9] = 512;
  ar[56][10] = 0;
  ar[57][0] = 110100480;
  ar[57][1] = 253493248;
  ar[57][2] = 259325952;
  ar[57][3] = 154714112;
  ar[57][4] = 59322368;
  ar[57][5] = 15160320;
  ar[57][6] = 2582272;
  ar[57][7] = 282688;
  ar[57][8] = 18048;
  ar[57][9] = 512;
  ar[57][10] = 0;
  ar[58][0] = 113246207;
  ar[58][1] = 258998273;
  ar[58][2] = 263454720;
  ar[58][3] = 156434432;
  ar[58][4] = 59752448;
  ar[58][5] = 15224832;
  ar[58][6] = 2587648;
  ar[58][7] = 282880;
  ar[58][8] = 18048;
  ar[58][9] = 512;
  ar[58][10] = 0;
  ar[59][0] = 114294784;
  ar[59][1] = 262930432;
  ar[59][2] = 268500992;
  ar[59][3] = 159760384;
  ar[59][4] = 61042688;
  ar[59][5] = 15533056;
  ar[59][6] = 2632448;
  ar[59][7] = 286528;
  ar[59][8] = 18176;
  ar[59][9] = 512;
  ar[59][10] = 0;
  ar[60][0] = 117440512;
  ar[60][1] = 268435456;
  ar[60][2] = 272629760;
  ar[60][3] = 161480704;
  ar[60][4] = 61472768;
  ar[60][5] = 15597568;
  ar[60][6] = 2637824;
  ar[60][7] = 286720;
  ar[60][8] = 18176;
  ar[60][9] = 512;
  ar[60][10] = 0;
  ar[61][0] = 120586240;
  ar[61][1] = 273940480;
  ar[61][2] = 276758528;
  ar[61][3] = 163201024;
  ar[61][4] = 61902848;
  ar[61][5] = 15662080;
  ar[61][6] = 2643200;
  ar[61][7] = 286912;
  ar[61][8] = 18176;
  ar[61][9] = 512;
  ar[61][10] = 0;
  ar[62][0] = 123731968;
  ar[62][1] = 279445504;
  ar[62][2] = 280887296;
  ar[62][3] = 164921344;
  ar[62][4] = 62332928;
  ar[62][5] = 15726592;
  ar[62][6] = 2648576;
  ar[62][7] = 287104;
  ar[62][8] = 18176;
  ar[62][9] = 512;
  ar[62][10] = 0;
  ar[63][0] = 125829119;
  ar[63][1] = 284164097;
  ar[63][2] = 285474816;
  ar[63][3] = 167444480;
  ar[63][4] = 63193088;
  ar[63][5] = 15912960;
  ar[63][6] = 2673664;
  ar[63][7] = 289024;
  ar[63][8] = 18240;
  ar[63][9] = 512;
  ar[63][10] = 0;
  ar[64][0] = 127926272;
  ar[64][1] = 288882688;
  ar[64][2] = 290062336;
  ar[64][3] = 169967616;
  ar[64][4] = 64053248;
  ar[64][5] = 16099328;
  ar[64][6] = 2698752;
  ar[64][7] = 290944;
  ar[64][8] = 18304;
  ar[64][9] = 512;
  ar[64][10] = 0;
  ar[65][0] = 130023423;
  ar[65][1] = 293601281;
  ar[65][2] = 294649856;
  ar[65][3] = 172490752;
  ar[65][4] = 64913408;
  ar[65][5] = 16285696;
  ar[65][6] = 2723840;
  ar[65][7] = 292864;
  ar[65][8] = 18368;
  ar[65][9] = 512;
  ar[65][10] = 0;
  ar[66][0] = 132120576;
  ar[66][1] = 298319872;
  ar[66][2] = 299237376;
  ar[66][3] = 175013888;
  ar[66][4] = 65773568;
  ar[66][5] = 16472064;
  ar[66][6] = 2748928;
  ar[66][7] = 294784;
  ar[66][8] = 18432;
  ar[66][9] = 512;
  ar[66][10] = 0;
  cin >> n;
  m = n / 15000000;
  for (int i = 0; i < 10; i++) arr[i] = ar[m][i];
  for (int i = m * 15000000 + 1; i <= n; i++) calc(i);
  for (int mask = 0; mask <= 999999; ++mask) {
    fl = 0;
    for (int j = 0; j <= 9; j++) numb[j] = arr[j];
    long p = mask;
    s = 0;
    tans = 1;
    for (int i = 1; i <= 6; i++) {
      q = p % 10;
      s += q;
      p /= 10;
      tans = tans * numb[q] % 1000000007;
      numb[q]--;
      if (numb[q] < 0) fl = 1;
    }
    long long qq = 0;
    for (int pp = s + 1; pp <= 9; pp++) {
      qq += numb[pp];
    }
    tans *= qq;
    tans %= 1000000007;
    if (fl == 0) ans = ans + tans;
    ans %= 1000000007;
  }
  cout << ans << endl;
  cin.get();
  cin.get();
  return 0;
}