#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair <ll, ll> pll;

const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const ll Inf = 1LL << 62;

int mp[2020];

int main() {
	int s;
	mp[1] = 0;
	mp[2] = 0;
	mp[3] = 1;
	mp[4] = 1;
	mp[5] = 1;
	mp[6] = 2;
	mp[7] = 3;
	mp[8] = 4;
	mp[9] = 6;
	mp[10] = 9;
	mp[11] = 13;
	mp[12] = 19;
	mp[13] = 28;
	mp[14] = 41;
	mp[15] = 60;
	mp[16] = 88;
	mp[17] = 129;
	mp[18] = 189;
	mp[19] = 277;
	mp[20] = 406;
	mp[21] = 595;
	mp[22] = 872;
	mp[23] = 1278;
	mp[24] = 1873;
	mp[25] = 2745;
	mp[26] = 4023;
	mp[27] = 5896;
	mp[28] = 8641;
	mp[29] = 12664;
	mp[30] = 18560;
	mp[31] = 27201;
	mp[32] = 39865;
	mp[33] = 58425;
	mp[34] = 85626;
	mp[35] = 125491;
	mp[36] = 183916;
	mp[37] = 269542;
	mp[38] = 395033;
	mp[39] = 578949;
	mp[40] = 848491;
	mp[41] = 1243524;
	mp[42] = 1822473;
	mp[43] = 2670964;
	mp[44] = 3914488;
	mp[45] = 5736961;
	mp[46] = 8407925;
	mp[47] = 12322413;
	mp[48] = 18059374;
	mp[49] = 26467299;
	mp[50] = 38789712;
	mp[51] = 56849086;
	mp[52] = 83316385;
	mp[53] = 122106097;
	mp[54] = 178955183;
	mp[55] = 262271568;
	mp[56] = 384377665;
	mp[57] = 563332848;
	mp[58] = 825604416;
	mp[59] = 209982074;
	mp[60] = 773314922;
	mp[61] = 598919331;
	mp[62] = 808901405;
	mp[63] = 582216320;
	mp[64] = 181135644;
	mp[65] = 990037049;
	mp[66] = 572253362;
	mp[67] = 753389006;
	mp[68] = 743426048;
	mp[69] = 315679403;
	mp[70] = 69068402;
	mp[71] = 812494450;
	mp[72] = 128173846;
	mp[73] = 197242248;
	mp[74] = 9736691;
	mp[75] = 137910537;
	mp[76] = 335152785;
	mp[77] = 344889476;
	mp[78] = 482800013;
	mp[79] = 817952798;
	mp[80] = 162842267;
	mp[81] = 645642280;
	mp[82] = 463595071;
	mp[83] = 626437338;
	mp[84] = 272079611;
	mp[85] = 735674682;
	mp[86] = 362112013;
	mp[87] = 634191624;
	mp[88] = 369866299;
	mp[89] = 731978312;
	mp[90] = 366169929;
	mp[91] = 736036228;
	mp[92] = 468014533;
	mp[93] = 834184462;
	mp[94] = 570220683;
	mp[95] = 38235209;
	mp[96] = 872419671;
	mp[97] = 442640347;
	mp[98] = 480875556;
	mp[99] = 353295220;
	mp[100] = 795935567;
	mp[101] = 276811116;
	mp[102] = 630106336;
	mp[103] = 426041896;
	mp[104] = 702853012;
	mp[105] = 332959341;
	mp[106] = 759001237;
	mp[107] = 461854242;
	mp[108] = 794813583;
	mp[109] = 553814813;
	mp[110] = 15669048;
	mp[111] = 810482631;
	mp[112] = 364297437;
	mp[113] = 379966485;
	mp[114] = 190449109;
	mp[115] = 554746546;
	mp[116] = 934713031;
	mp[117] = 125162133;
	mp[118] = 679908679;
	mp[119] = 614621703;
	mp[120] = 739783836;
	mp[121] = 419692508;
	mp[122] = 34314204;
	mp[123] = 774098040;
	mp[124] = 193790541;
	mp[125] = 228104745;
	mp[126] = 2202778;
	mp[127] = 195993319;
	mp[128] = 424098064;
	mp[129] = 426300842;
	mp[130] = 622294161;
	mp[131] = 46392218;
	mp[132] = 472693060;
	mp[133] = 94987214;
	mp[134] = 141379432;
	mp[135] = 614072492;
	mp[136] = 709059706;
	mp[137] = 850439138;
	mp[138] = 464511623;
	mp[139] = 173571322;
	mp[140] = 24010453;
	mp[141] = 488522076;
	mp[142] = 662093398;
	mp[143] = 686103851;
	mp[144] = 174625920;
	mp[145] = 836719318;
	mp[146] = 522823162;
	mp[147] = 697449082;
	mp[148] = 534168393;
	mp[149] = 56991548;
	mp[150] = 754440630;
	mp[151] = 288609016;
	mp[152] = 345600564;
	mp[153] = 100041187;
	mp[154] = 388650203;
	mp[155] = 734250767;
	mp[156] = 834291954;
	mp[157] = 222942150;
	mp[158] = 957192917;
	mp[159] = 791484864;
	mp[160] = 14427007;
	mp[161] = 971619924;
	mp[162] = 763104781;
	mp[163] = 777531788;
	mp[164] = 749151705;
	mp[165] = 512256479;
	mp[166] = 289788260;
	mp[167] = 38939958;
	mp[168] = 551196437;
	mp[169] = 840984697;
	mp[170] = 879924655;
	mp[171] = 431121085;
	mp[172] = 272105775;
	mp[173] = 152030423;
	mp[174] = 583151508;
	mp[175] = 855257283;
	mp[176] = 7287699;
	mp[177] = 590439207;
	mp[178] = 445696483;
	mp[179] = 452984182;
	mp[180] = 43423382;
	mp[181] = 489119865;
	mp[182] = 942104047;
	mp[183] = 985527429;
	mp[184] = 474647287;
	mp[185] = 416751327;
	mp[186] = 402278749;
	mp[187] = 876926036;
	mp[188] = 293677356;
	mp[189] = 695956105;
	mp[190] = 572882134;
	mp[191] = 866559490;
	mp[192] = 562515588;
	mp[193] = 135397715;
	mp[194] = 1957198;
	mp[195] = 564472786;
	mp[196] = 699870501;
	mp[197] = 701827699;
	mp[198] = 266300478;
	mp[199] = 966170979;
	mp[200] = 667998671;
	mp[201] = 934299149;
	mp[202] = 900470121;
	mp[203] = 568468785;
	mp[204] = 502767927;
	mp[205] = 403238041;
	mp[206] = 971706826;
	mp[207] = 474474746;
	mp[208] = 877712787;
	mp[209] = 849419606;
	mp[210] = 323894345;
	mp[211] = 201607125;
	mp[212] = 51026724;
	mp[213] = 374921069;
	mp[214] = 576528194;
	mp[215] = 627554918;
	mp[216] = 2475980;
	mp[217] = 579004174;
	mp[218] = 206559085;
	mp[219] = 209035065;
	mp[220] = 788039239;
	mp[221] = 994598324;
	mp[222] = 203633382;
	mp[223] = 991672621;
	mp[224] = 986270938;
	mp[225] = 189904313;
	mp[226] = 181576927;
	mp[227] = 167847858;
	mp[228] = 357752171;
	mp[229] = 539329098;
	mp[230] = 707176956;
	mp[231] = 64929120;
	mp[232] = 604258218;
	mp[233] = 311435167;
	mp[234] = 376364287;
	mp[235] = 980622505;
	mp[236] = 292057665;
	mp[237] = 668421952;
	mp[238] = 649044450;
	mp[239] = 941102115;
	mp[240] = 609524060;
	mp[241] = 258568503;
	mp[242] = 199670611;
	mp[243] = 809194671;
	mp[244] = 67763167;
	mp[245] = 267433778;
	mp[246] = 76628442;
	mp[247] = 144391609;
	mp[248] = 411825387;
	mp[249] = 488453829;
	mp[250] = 632845438;
	mp[251] = 44670818;
	mp[252] = 533124647;
	mp[253] = 165970078;
	mp[254] = 210640896;
	mp[255] = 743765543;
	mp[256] = 909735621;
	mp[257] = 120376510;
	mp[258] = 864142053;
	mp[259] = 773877667;
	mp[260] = 894254177;
	mp[261] = 758396223;
	mp[262] = 532273883;
	mp[263] = 426528053;
	mp[264] = 184924269;
	mp[265] = 717198152;
	mp[266] = 143726198;
	mp[267] = 328650467;
	mp[268] = 45848612;
	mp[269] = 189574810;
	mp[270] = 518225277;
	mp[271] = 564073889;
	mp[272] = 753648699;
	mp[273] = 271873969;
	mp[274] = 835947858;
	mp[275] = 589596550;
	mp[276] = 861470519;
	mp[277] = 697418370;
	mp[278] = 287014913;
	mp[279] = 148485425;
	mp[280] = 845903795;
	mp[281] = 132918701;
	mp[282] = 281404126;
	mp[283] = 127307914;
	mp[284] = 260226615;
	mp[285] = 541630741;
	mp[286] = 668938655;
	mp[287] = 929165270;
	mp[288] = 470796004;
	mp[289] = 139734652;
	mp[290] = 68899915;
	mp[291] = 539695919;
	mp[292] = 679430571;
	mp[293] = 748330486;
	mp[294] = 288026398;
	mp[295] = 967456969;
	mp[296] = 715787448;
	mp[297] = 3813839;
	mp[298] = 971270808;
	mp[299] = 687058249;
	mp[300] = 690872088;
	mp[301] = 662142889;
	mp[302] = 349201131;
	mp[303] = 40073212;
	mp[304] = 702216101;
	mp[305] = 51417225;
	mp[306] = 91490437;
	mp[307] = 793706538;
	mp[308] = 845123763;
	mp[309] = 936614200;
	mp[310] = 730320731;
	mp[311] = 575444487;
	mp[312] = 512058680;
	mp[313] = 242379404;
	mp[314] = 817823891;
	mp[315] = 329882564;
	mp[316] = 572261968;
	mp[317] = 390085852;
	mp[318] = 719968416;
	mp[319] = 292230377;
	mp[320] = 682316229;
	mp[321] = 402284638;
	mp[322] = 694515015;
	mp[323] = 376831237;
	mp[324] = 779115875;
	mp[325] = 473630883;
	mp[326] = 850462120;
	mp[327] = 629577988;
	mp[328] = 103208864;
	mp[329] = 953670984;
	mp[330] = 583248965;
	mp[331] = 686457829;
	mp[332] = 640128806;
	mp[333] = 223377764;
	mp[334] = 909835593;
	mp[335] = 549964392;
	mp[336] = 773342156;
	mp[337] = 683177742;
	mp[338] = 233142127;
	mp[339] = 6484276;
	mp[340] = 689662018;
	mp[341] = 922804145;
	mp[342] = 929288421;
	mp[343] = 618950432;
	mp[344] = 541754570;
	mp[345] = 471042984;
	mp[346] = 89993409;
	mp[347] = 631747979;
	mp[348] = 102790956;
	mp[349] = 192784365;
	mp[350] = 824532344;
	mp[351] = 927323300;
	mp[352] = 120107658;
	mp[353] = 944640002;
	mp[354] = 871963295;
	mp[355] = 992070953;
	mp[356] = 936710948;
	mp[357] = 808674236;
	mp[358] = 800745182;
	mp[359] = 737456123;
	mp[360] = 546130352;
	mp[361] = 346875527;
	mp[362] = 84331643;
	mp[363] = 630461995;
	mp[364] = 977337522;
	mp[365] = 61669158;
	mp[366] = 692131153;
	mp[367] = 669468668;
	mp[368] = 731137826;
	mp[369] = 423268972;
	mp[370] = 92737633;
	mp[371] = 823875459;
	mp[372] = 247144424;
	mp[373] = 339882057;
	mp[374] = 163757509;
	mp[375] = 410901933;
	mp[376] = 750783990;
	mp[377] = 914541499;
	mp[378] = 325443425;
	mp[379] = 76227408;
	mp[380] = 990768907;
	mp[381] = 316212325;
	mp[382] = 392439733;
	mp[383] = 383208633;
	mp[384] = 699420958;
	mp[385] = 91860684;
	mp[386] = 475069317;
	mp[387] = 174490268;
	mp[388] = 266350952;
	mp[389] = 741420269;
	mp[390] = 915910537;
	mp[391] = 182261482;
	mp[392] = 923681751;
	mp[393] = 839592281;
	mp[394] = 21853756;
	mp[395] = 945535507;
	mp[396] = 785127781;
	mp[397] = 806981537;
	mp[398] = 752517037;
	mp[399] = 537644811;
	mp[400] = 344626341;
	mp[401] = 97143371;
	mp[402] = 634788182;
	mp[403] = 979414523;
	mp[404] = 76557887;
	mp[405] = 711346069;
	mp[406] = 690760585;
	mp[407] = 767318472;
	mp[408] = 478664534;
	mp[409] = 169425112;
	mp[410] = 936743584;
	mp[411] = 415408111;
	mp[412] = 584833223;
	mp[413] = 521576800;
	mp[414] = 936984911;
	mp[415] = 521818127;
	mp[416] = 43394920;
	mp[417] = 980379831;
	mp[418] = 502197951;
	mp[419] = 545592871;
	mp[420] = 525972695;
	mp[421] = 28170639;
	mp[422] = 573763510;
	mp[423] = 99736198;
	mp[424] = 127906837;
	mp[425] = 701670347;
	mp[426] = 801406545;
	mp[427] = 929313382;
	mp[428] = 630983722;
	mp[429] = 432390260;
	mp[430] = 361703635;
	mp[431] = 992687357;
	mp[432] = 425077610;
	mp[433] = 786781245;
	mp[434] = 779468595;
	mp[435] = 204546198;
	mp[436] = 991327443;
	mp[437] = 770796031;
	mp[438] = 975342229;
	mp[439] = 966669665;
	mp[440] = 737465689;
	mp[441] = 712807911;
	mp[442] = 679477569;
	mp[443] = 416943251;
	mp[444] = 129751155;
	mp[445] = 809228724;
	mp[446] = 226171968;
	mp[447] = 355923123;
	mp[448] = 165151840;
	mp[449] = 391323808;
	mp[450] = 747246931;
	mp[451] = 912398771;
	mp[452] = 303722572;
	mp[453] = 50969496;
	mp[454] = 963368267;
	mp[455] = 267090832;
	mp[456] = 318060328;
	mp[457] = 281428588;
	mp[458] = 548519420;
	mp[459] = 866579748;
	mp[460] = 148008329;
	mp[461] = 696527749;
	mp[462] = 563107490;
	mp[463] = 711115819;
	mp[464] = 407643561;
	mp[465] = 970751051;
	mp[466] = 681866863;
	mp[467] = 89510417;
	mp[468] = 60261461;
	mp[469] = 742128324;
	mp[470] = 831638741;
	mp[471] = 891900202;
	mp[472] = 634028519;
	mp[473] = 465667253;
	mp[474] = 357567448;
	mp[475] = 991595967;
	mp[476] = 457263213;
	mp[477] = 814830661;
	mp[478] = 806426621;
	mp[479] = 263689827;
	mp[480] = 78520481;
	mp[481] = 884947102;
	mp[482] = 148636922;
	mp[483] = 227157403;
	mp[484] = 112104498;
	mp[485] = 260741420;
	mp[486] = 487898823;
	mp[487] = 600003321;
	mp[488] = 860744741;
	mp[489] = 348643557;
	mp[490] = 948646878;
	mp[491] = 809391612;
	mp[492] = 158035162;
	mp[493] = 106682033;
	mp[494] = 916073645;
	mp[495] = 74108800;
	mp[496] = 180790833;
	mp[497] = 96864471;
	mp[498] = 170973271;
	mp[499] = 351764104;
	mp[500] = 448628575;
	mp[501] = 619601846;
	mp[502] = 971365950;
	mp[503] = 419994518;
	mp[504] = 39596357;
	mp[505] = 10962300;
	mp[506] = 430956818;
	mp[507] = 470553175;
	mp[508] = 481515475;
	mp[509] = 912472293;
	mp[510] = 383025461;
	mp[511] = 864540936;
	mp[512] = 777013222;
	mp[513] = 160038676;
	mp[514] = 24579605;
	mp[515] = 801592827;
	mp[516] = 961631503;
	mp[517] = 986211108;
	mp[518] = 787803928;
	mp[519] = 749435424;
	mp[520] = 735646525;
	mp[521] = 523450446;
	mp[522] = 272885863;
	mp[523] = 8532381;
	mp[524] = 531982827;
	mp[525] = 804868690;
	mp[526] = 813401071;
	mp[527] = 345383891;
	mp[528] = 150252574;
	mp[529] = 963653645;
	mp[530] = 309037529;
	mp[531] = 459290103;
	mp[532] = 422943741;
	mp[533] = 731981270;
	mp[534] = 191271366;
	mp[535] = 614215107;
	mp[536] = 346196370;
	mp[537] = 537467736;
	mp[538] = 151682836;
	mp[539] = 497879206;
	mp[540] = 35346935;
	mp[541] = 187029771;
	mp[542] = 684908977;
	mp[543] = 720255912;
	mp[544] = 907285683;
	mp[545] = 592194653;
	mp[546] = 312450558;
	mp[547] = 219736234;
	mp[548] = 811930887;
	mp[549] = 124381438;
	mp[550] = 344117672;
	mp[551] = 156048552;
	mp[552] = 280429990;
	mp[553] = 624547662;
	mp[554] = 780596214;
	mp[555] = 61026197;
	mp[556] = 685573859;
	mp[557] = 466170066;
	mp[558] = 527196263;
	mp[559] = 212770115;
	mp[560] = 678940181;
	mp[561] = 206136437;
	mp[562] = 418906552;
	mp[563] = 97846726;
	mp[564] = 303983163;
	mp[565] = 722889715;
	mp[566] = 820736441;
	mp[567] = 124719597;
	mp[568] = 847609312;
	mp[569] = 668345746;
	mp[570] = 793065343;
	mp[571] = 640674648;
	mp[572] = 309020387;
	mp[573] = 102085723;
	mp[574] = 742760371;
	mp[575] = 51780751;
	mp[576] = 153866474;
	mp[577] = 896626845;
	mp[578] = 948407596;
	mp[579] = 102274063;
	mp[580] = 998900908;
	mp[581] = 947308497;
	mp[582] = 49582553;
	mp[583] = 48483454;
	mp[584] = 995791951;
	mp[585] = 45374497;
	mp[586] = 93857951;
	mp[587] = 89649895;
	mp[588] = 135024392;
	mp[589] = 228882343;
	mp[590] = 318532238;
	mp[591] = 453556630;
	mp[592] = 682438973;
	mp[593] = 971204;
	mp[594] = 454527834;
	mp[595] = 136966800;
	mp[596] = 137938004;
	mp[597] = 592465838;
	mp[598] = 729432638;
	mp[599] = 867370642;
	mp[600] = 459836473;
	mp[601] = 189269104;
	mp[602] = 56639739;
	mp[603] = 516476212;
	mp[604] = 705745316;
	mp[605] = 762385055;
	mp[606] = 278861260;
	mp[607] = 984606576;
	mp[608] = 746991624;
	mp[609] = 25852877;
	mp[610] = 10459446;
	mp[611] = 757451070;
	mp[612] = 783303947;
	mp[613] = 793763393;
	mp[614] = 551214456;
	mp[615] = 334518396;
	mp[616] = 128281782;
	mp[617] = 679496238;
	mp[618] = 14014627;
	mp[619] = 142296409;
	mp[620] = 821792647;
	mp[621] = 835807274;
	mp[622] = 978103683;
	mp[623] = 799896323;
	mp[624] = 635703590;
	mp[625] = 613807266;
	mp[626] = 413703582;
	mp[627] = 49407165;
	mp[628] = 663214431;
	mp[629] = 76918006;
	mp[630] = 126325171;
	mp[631] = 789539602;
	mp[632] = 866457608;
	mp[633] = 992782779;
	mp[634] = 782322374;
	mp[635] = 648779975;
	mp[636] = 641562747;
	mp[637] = 423885114;
	mp[638] = 72665082;
	mp[639] = 714227829;
	mp[640] = 138112936;
	mp[641] = 210778018;
	mp[642] = 925005847;
	mp[643] = 63118776;
	mp[644] = 273896794;
	mp[645] = 198902634;
	mp[646] = 262021410;
	mp[647] = 535918204;
	mp[648] = 734820838;
	mp[649] = 996842248;
	mp[650] = 532760445;
	mp[651] = 267581276;
	mp[652] = 264423517;
	mp[653] = 797183962;
	mp[654] = 64765231;
	mp[655] = 329188748;
	mp[656] = 126372703;
	mp[657] = 191137934;
	mp[658] = 520326682;
	mp[659] = 646699385;
	mp[660] = 837837319;
	mp[661] = 358163994;
	mp[662] = 4863372;
	mp[663] = 842700691;
	mp[664] = 200864678;
	mp[665] = 205728050;
	mp[666] = 48428734;
	mp[667] = 249293412;
	mp[668] = 455021462;
	mp[669] = 503450196;
	mp[670] = 752743608;
	mp[671] = 207765063;
	mp[672] = 711215259;
	mp[673] = 463958860;
	mp[674] = 671723923;
	mp[675] = 382939175;
	mp[676] = 846898035;
	mp[677] = 518621951;
	mp[678] = 901561126;
	mp[679] = 748459154;
	mp[680] = 267081098;
	mp[681] = 168642217;
	mp[682] = 917101371;
	mp[683] = 184182462;
	mp[684] = 352824679;
	mp[685] = 269926043;
	mp[686] = 454108505;
	mp[687] = 806933184;
	mp[688] = 76859220;
	mp[689] = 530967725;
	mp[690] = 337900902;
	mp[691] = 414760122;
	mp[692] = 945727847;
	mp[693] = 283628742;
	mp[694] = 698388864;
	mp[695] = 644116704;
	mp[696] = 927745446;
	mp[697] = 626134303;
	mp[698] = 270251000;
	mp[699] = 197996439;
	mp[700] = 824130742;
	mp[701] = 94381735;
	mp[702] = 292378174;
	mp[703] = 116508909;
	mp[704] = 210890644;
	mp[705] = 503268818;
	mp[706] = 619777727;
	mp[707] = 830668371;
	mp[708] = 333937182;
	mp[709] = 953714909;
	mp[710] = 784383273;
	mp[711] = 118320448;
	mp[712] = 72035350;
	mp[713] = 856418623;
	mp[714] = 974739071;
	mp[715] = 46774414;
	mp[716] = 903193037;
	mp[717] = 877932101;
	mp[718] = 924706515;
	mp[719] = 827899545;
	mp[720] = 705831639;
	mp[721] = 630538147;
	mp[722] = 458437685;
	mp[723] = 164269317;
	mp[724] = 794807464;
	mp[725] = 253245142;
	mp[726] = 417514459;
	mp[727] = 212321916;
	mp[728] = 465567058;
	mp[729] = 883081517;
	mp[730] = 95403426;
	mp[731] = 560970484;
	mp[732] = 444051994;
	mp[733] = 539455420;
	mp[734] = 100425897;
	mp[735] = 544477891;
	mp[736] = 83933304;
	mp[737] = 184359201;
	mp[738] = 728837092;
	mp[739] = 812770396;
	mp[740] = 997129597;
	mp[741] = 725966682;
	mp[742] = 538737071;
	mp[743] = 535866661;
	mp[744] = 261833336;
	mp[745] = 800570407;
	mp[746] = 336437061;
	mp[747] = 598270397;
	mp[748] = 398840797;
	mp[749] = 735277858;
	mp[750] = 333548248;
	mp[751] = 732389045;
	mp[752] = 467666896;
	mp[753] = 801215144;
	mp[754] = 533604182;
	mp[755] = 1271071;
	mp[756] = 802486215;
	mp[757] = 336090390;
	mp[758] = 337361461;
	mp[759] = 139847669;
	mp[760] = 475938059;
	mp[761] = 813299520;
	mp[762] = 953147189;
	mp[763] = 429085241;
	mp[764] = 242384754;
	mp[765] = 195531936;
	mp[766] = 624617177;
	mp[767] = 867001931;
	mp[768] = 62533860;
	mp[769] = 687151037;
	mp[770] = 554152961;
	mp[771] = 616686821;
	mp[772] = 303837851;
	mp[773] = 857990812;
	mp[774] = 474677626;
	mp[775] = 778515477;
	mp[776] = 636506282;
	mp[777] = 111183901;
	mp[778] = 889699378;
	mp[779] = 526205653;
	mp[780] = 637389554;
	mp[781] = 527088925;
	mp[782] = 53294571;
	mp[783] = 690684125;
	mp[784] = 217773043;
	mp[785] = 271067614;
	mp[786] = 961751739;
	mp[787] = 179524775;
	mp[788] = 450592389;
	mp[789] = 412344121;
	mp[790] = 591868896;
	mp[791] = 42461278;
	mp[792] = 454805399;
	mp[793] = 46674288;
	mp[794] = 89135566;
	mp[795] = 543940965;
	mp[796] = 590615253;
	mp[797] = 679750819;
	mp[798] = 223691777;
	mp[799] = 814307030;
	mp[800] = 494057842;
	mp[801] = 717749619;
	mp[802] = 532056642;
	mp[803] = 26114477;
	mp[804] = 743864096;
	mp[805] = 275920731;
	mp[806] = 302035208;
	mp[807] = 45899297;
	mp[808] = 321820028;
	mp[809] = 623855236;
	mp[810] = 669754533;
	mp[811] = 991574561;
	mp[812] = 615429790;
	mp[813] = 285184316;
	mp[814] = 276758870;
	mp[815] = 892188660;
	mp[816] = 177372969;
	mp[817] = 454131839;
	mp[818] = 346320492;
	mp[819] = 523693461;
	mp[820] = 977825300;
	mp[821] = 324145785;
	mp[822] = 847839246;
	mp[823] = 825664539;
	mp[824] = 149810317;
	mp[825] = 997649563;
	mp[826] = 823314095;
	mp[827] = 973124412;
	mp[828] = 970773968;
	mp[829] = 794088056;
	mp[830] = 767212461;
	mp[831] = 737986422;
	mp[832] = 532074471;
	mp[833] = 299286925;
	mp[834] = 37273340;
	mp[835] = 569347811;
	mp[836] = 868634736;
	mp[837] = 905908076;
	mp[838] = 475255880;
	mp[839] = 343890609;
	mp[840] = 249798678;
	mp[841] = 725054558;
	mp[842] = 68945160;
	mp[843] = 318743838;
	mp[844] = 43798389;
	mp[845] = 112743549;
	mp[846] = 431487387;
	mp[847] = 475285776;
	mp[848] = 588029325;
	mp[849] = 19516705;
	mp[850] = 494802481;
	mp[851] = 82831799;
	mp[852] = 102348504;
	mp[853] = 597150985;
	mp[854] = 679982784;
	mp[855] = 782331288;
	mp[856] = 379482266;
	mp[857] = 59465043;
	mp[858] = 841796331;
	mp[859] = 221278590;
	mp[860] = 280743633;
	mp[861] = 122539957;
	mp[862] = 343818547;
	mp[863] = 624562180;
	mp[864] = 747102137;
	mp[865] = 90920677;
	mp[866] = 715482857;
	mp[867] = 462584987;
	mp[868] = 553505664;
	mp[869] = 268988514;
	mp[870] = 731573501;
	mp[871] = 285079158;
	mp[872] = 554067672;
	mp[873] = 285641166;
	mp[874] = 570720324;
	mp[875] = 124787989;
	mp[876] = 410429155;
	mp[877] = 981149479;
	mp[878] = 105937461;
	mp[879] = 516366616;
	mp[880] = 497516088;
	mp[881] = 603453549;
	mp[882] = 119820158;
	mp[883] = 617336246;
	mp[884] = 220789788;
	mp[885] = 340609946;
	mp[886] = 957946192;
	mp[887] = 178735973;
	mp[888] = 519345919;
	mp[889] = 477292104;
	mp[890] = 656028077;
	mp[891] = 175373989;
	mp[892] = 652666093;
	mp[893] = 308694163;
	mp[894] = 484068152;
	mp[895] = 136734238;
	mp[896] = 445428401;
	mp[897] = 929496553;
	mp[898] = 66230784;
	mp[899] = 511659185;
	mp[900] = 441155731;
	mp[901] = 507386515;
	mp[902] = 19045693;
	mp[903] = 460201424;
	mp[904] = 967587939;
	mp[905] = 986633632;
	mp[906] = 446835049;
	mp[907] = 414422981;
	mp[908] = 401056606;
	mp[909] = 847891655;
	mp[910] = 262314629;
	mp[911] = 663371235;
	mp[912] = 511262883;
	mp[913] = 773577512;
	mp[914] = 436948740;
	mp[915] = 948211623;
	mp[916] = 721789128;
	mp[917] = 158737861;
	mp[918] = 106949477;
	mp[919] = 828738605;
	mp[920] = 987476466;
	mp[921] = 94425936;
	mp[922] = 923164541;
	mp[923] = 910641000;
	mp[924] = 5066929;
	mp[925] = 928231470;
	mp[926] = 838872463;
	mp[927] = 843939392;
	mp[928] = 772170855;
	mp[929] = 611043311;
	mp[930] = 454982696;
	mp[931] = 227153544;
	mp[932] = 838196855;
	mp[933] = 293179544;
	mp[934] = 520333088;
	mp[935] = 358529936;
	mp[936] = 651709480;
	mp[937] = 172042561;
	mp[938] = 530572497;
	mp[939] = 182281970;
	mp[940] = 354324531;
	mp[941] = 884897028;
	mp[942] = 67178991;
	mp[943] = 421503522;
	mp[944] = 306400543;
	mp[945] = 373579534;
	mp[946] = 795083056;
	mp[947] = 101483592;
	mp[948] = 475063126;
	mp[949] = 270146175;
	mp[950] = 371629767;
	mp[951] = 846692893;
	mp[952] = 116839061;
	mp[953] = 488468828;
	mp[954] = 335161714;
	mp[955] = 452000775;
	mp[956] = 940469603;
	mp[957] = 275631310;
	mp[958] = 727632085;
	mp[959] = 668101681;
	mp[960] = 943732991;
	mp[961] = 671365069;
	mp[962] = 339466743;
	mp[963] = 283199727;
	mp[964] = 954564796;
	mp[965] = 294031532;
	mp[966] = 577231259;
	mp[967] = 531796048;
	mp[968] = 825827580;
	mp[969] = 403058832;
	mp[970] = 934854880;
	mp[971] = 760682453;
	mp[972] = 163741278;
	mp[973] = 98596151;
	mp[974] = 859278604;
	mp[975] = 23019875;
	mp[976] = 121616026;
	mp[977] = 980894630;
	mp[978] = 3914498;
	mp[979] = 125530524;
	mp[980] = 106425147;
	mp[981] = 110339645;
	mp[982] = 235870169;
	mp[983] = 342295316;
	mp[984] = 452634961;
	mp[985] = 688505130;
	mp[986] = 30800439;
	mp[987] = 483435400;
	mp[988] = 171940523;
	mp[989] = 202740962;
	mp[990] = 686176362;
	mp[991] = 858116885;
	mp[992] = 60857840;
	mp[993] = 747034202;
	mp[994] = 605151080;
	mp[995] = 666008920;
	mp[996] = 413043115;
	mp[997] = 18194188;
	mp[998] = 684203108;
	mp[999] = 97246216;
	mp[1000] = 115440404;
	mp[1001] = 799643512;
	mp[1002] = 896889728;
	mp[1003] = 12330125;
	mp[1004] = 811973637;
	mp[1005] = 708863358;
	mp[1006] = 721193483;
	mp[1007] = 533167113;
	mp[1008] = 242030464;
	mp[1009] = 963223947;
	mp[1010] = 496391053;
	mp[1011] = 738421517;
	mp[1012] = 701645457;
	mp[1013] = 198036503;
	mp[1014] = 936458020;
	mp[1015] = 638103470;
	mp[1016] = 836139973;
	mp[1017] = 772597986;
	mp[1018] = 410701449;
	mp[1019] = 246841415;
	mp[1020] = 19439394;
	mp[1021] = 430140843;
	mp[1022] = 676982258;
	mp[1023] = 696421652;
	mp[1024] = 126562488;
	mp[1025] = 803544746;
	mp[1026] = 499966391;
	mp[1027] = 626528879;
	mp[1028] = 430073618;
	mp[1029] = 930040009;
	mp[1030] = 556568881;
	mp[1031] = 986642499;
	mp[1032] = 916682501;
	mp[1033] = 473251375;
	mp[1034] = 459893867;
	mp[1035] = 376576361;
	mp[1036] = 849827736;
	mp[1037] = 309721596;
	mp[1038] = 686297957;
	mp[1039] = 536125686;
	mp[1040] = 845847282;
	mp[1041] = 532145232;
	mp[1042] = 68270911;
	mp[1043] = 914118193;
	mp[1044] = 446263418;
	mp[1045] = 514534329;
	mp[1046] = 428652515;
	mp[1047] = 874915933;
	mp[1048] = 389450255;
	mp[1049] = 818102770;
	mp[1050] = 693018696;
	mp[1051] = 82468944;
	mp[1052] = 900571714;
	mp[1053] = 593590403;
	mp[1054] = 676059347;
	mp[1055] = 576631054;
	mp[1056] = 170221450;
	mp[1057] = 846280797;
	mp[1058] = 422911844;
	mp[1059] = 593133294;
	mp[1060] = 439414084;
	mp[1061] = 862325928;
	mp[1062] = 455459215;
	mp[1063] = 894873299;
	mp[1064] = 757199220;
	mp[1065] = 212658428;
	mp[1066] = 107531720;
	mp[1067] = 864730940;
	mp[1068] = 77389361;
	mp[1069] = 184921081;
	mp[1070] = 49652014;
	mp[1071] = 127041375;
	mp[1072] = 311962456;
	mp[1073] = 361614470;
	mp[1074] = 488655845;
	mp[1075] = 800618301;
	mp[1076] = 162232764;
	mp[1077] = 650888609;
	mp[1078] = 451506903;
	mp[1079] = 613739667;
	mp[1080] = 264628269;
	mp[1081] = 716135172;
	mp[1082] = 329874832;
	mp[1083] = 594503101;
	mp[1084] = 310638266;
	mp[1085] = 640513098;
	mp[1086] = 235016192;
	mp[1087] = 545654458;
	mp[1088] = 186167549;
	mp[1089] = 421183741;
	mp[1090] = 966838199;
	mp[1091] = 153005741;
	mp[1092] = 574189482;
	mp[1093] = 541027674;
	mp[1094] = 694033415;
	mp[1095] = 268222890;
	mp[1096] = 809250564;
	mp[1097] = 503283972;
	mp[1098] = 771506862;
	mp[1099] = 580757419;
	mp[1100] = 84041384;
	mp[1101] = 855548246;
	mp[1102] = 436305658;
	mp[1103] = 520347042;
	mp[1104] = 375895281;
	mp[1105] = 812200939;
	mp[1106] = 332547974;
	mp[1107] = 708443255;
	mp[1108] = 520644187;
	mp[1109] = 853192161;
	mp[1110] = 561635409;
	mp[1111] = 82279589;
	mp[1112] = 935471750;
	mp[1113] = 497107152;
	mp[1114] = 579386741;
	mp[1115] = 514858484;
	mp[1116] = 11965629;
	mp[1117] = 591352370;
	mp[1118] = 106210847;
	mp[1119] = 118176476;
	mp[1120] = 709528846;
	mp[1121] = 815739693;
	mp[1122] = 933916169;
	mp[1123] = 643445008;
	mp[1124] = 459184694;
	mp[1125] = 393100856;
	mp[1126] = 36545857;
	mp[1127] = 495730551;
	mp[1128] = 888831407;
	mp[1129] = 925377264;
	mp[1130] = 421107808;
	mp[1131] = 309939208;
	mp[1132] = 235316465;
	mp[1133] = 656424273;
	mp[1134] = 966363481;
	mp[1135] = 201679939;
	mp[1136] = 858104212;
	mp[1137] = 824467686;
	mp[1138] = 26147618;
	mp[1139] = 884251830;
	mp[1140] = 708719509;
	mp[1141] = 734867127;
	mp[1142] = 619118950;
	mp[1143] = 327838452;
	mp[1144] = 62705572;
	mp[1145] = 681824522;
	mp[1146] = 9662967;
	mp[1147] = 72368539;
	mp[1148] = 754193061;
	mp[1149] = 763856028;
	mp[1150] = 836224567;
	mp[1151] = 590417621;
	mp[1152] = 354273642;
	mp[1153] = 190498202;
	mp[1154] = 780915823;
	mp[1155] = 135189458;
	mp[1156] = 325687660;
	mp[1157] = 106603476;
	mp[1158] = 241792934;
	mp[1159] = 567480594;
	mp[1160] = 674084070;
	mp[1161] = 915877004;
	mp[1162] = 483357591;
	mp[1163] = 157441654;
	mp[1164] = 73318651;
	mp[1165] = 556676242;
	mp[1166] = 714117896;
	mp[1167] = 787436547;
	mp[1168] = 344112782;
	mp[1169] = 58230671;
	mp[1170] = 845667218;
	mp[1171] = 189779993;
	mp[1172] = 248010664;
	mp[1173] = 93677875;
	mp[1174] = 283457868;
	mp[1175] = 531468532;
	mp[1176] = 625146407;
	mp[1177] = 908604275;
	mp[1178] = 440072800;
	mp[1179] = 65219200;
	mp[1180] = 973823475;
	mp[1181] = 413896268;
	mp[1182] = 479115468;
	mp[1183] = 452938936;
	mp[1184] = 866835204;
	mp[1185] = 345950665;
	mp[1186] = 798889601;
	mp[1187] = 665724798;
	mp[1188] = 11675456;
	mp[1189] = 810565057;
	mp[1190] = 476289848;
	mp[1191] = 487965304;
	mp[1192] = 298530354;
	mp[1193] = 774820202;
	mp[1194] = 262785499;
	mp[1195] = 561315853;
	mp[1196] = 336136048;
	mp[1197] = 598921547;
	mp[1198] = 160237393;
	mp[1199] = 496373441;
	mp[1200] = 95294981;
	mp[1201] = 255532374;
	mp[1202] = 751905815;
	mp[1203] = 847200796;
	mp[1204] = 102733163;
	mp[1205] = 854638978;
	mp[1206] = 701839767;
	mp[1207] = 804572930;
	mp[1208] = 659211901;
	mp[1209] = 361051661;
	mp[1210] = 165624584;
	mp[1211] = 824836485;
	mp[1212] = 185888139;
	mp[1213] = 351512723;
	mp[1214] = 176349201;
	mp[1215] = 362237340;
	mp[1216] = 713750063;
	mp[1217] = 890099264;
	mp[1218] = 252336597;
	mp[1219] = 966086660;
	mp[1220] = 856185917;
	mp[1221] = 108522507;
	mp[1222] = 74609160;
	mp[1223] = 930795077;
	mp[1224] = 39317577;
	mp[1225] = 113926737;
	mp[1226] = 44721807;
	mp[1227] = 84039384;
	mp[1228] = 197966121;
	mp[1229] = 242687928;
	mp[1230] = 326727312;
	mp[1231] = 524693433;
	mp[1232] = 767381361;
	mp[1233] = 94108666;
	mp[1234] = 618802099;
	mp[1235] = 386183453;
	mp[1236] = 480292119;
	mp[1237] = 99094211;
	mp[1238] = 485277664;
	mp[1239] = 965569783;
	mp[1240] = 64663987;
	mp[1241] = 549941651;
	mp[1242] = 515511427;
	mp[1243] = 580175414;
	mp[1244] = 130117058;
	mp[1245] = 645628485;
	mp[1246] = 225803892;
	mp[1247] = 355920950;
	mp[1248] = 1549428;
	mp[1249] = 227353320;
	mp[1250] = 583274270;
	mp[1251] = 584823698;
	mp[1252] = 812177018;
	mp[1253] = 395451281;
	mp[1254] = 980274979;
	mp[1255] = 792451990;
	mp[1256] = 187903264;
	mp[1257] = 168178236;
	mp[1258] = 960630226;
	mp[1259] = 148533483;
	mp[1260] = 316711719;
	mp[1261] = 277341938;
	mp[1262] = 425875421;
	mp[1263] = 742587140;
	mp[1264] = 19929071;
	mp[1265] = 445804492;
	mp[1266] = 188391625;
	mp[1267] = 208320696;
	mp[1268] = 654125188;
	mp[1269] = 842516813;
	mp[1270] = 50837502;
	mp[1271] = 704962690;
	mp[1272] = 547479496;
	mp[1273] = 598316998;
	mp[1274] = 303279681;
	mp[1275] = 850759177;
	mp[1276] = 449076168;
	mp[1277] = 752355849;
	mp[1278] = 603115019;
	mp[1279] = 52191180;
	mp[1280] = 804547029;
	mp[1281] = 407662041;
	mp[1282] = 459853221;
	mp[1283] = 264400243;
	mp[1284] = 672062284;
	mp[1285] = 131915498;
	mp[1286] = 396315741;
	mp[1287] = 68378018;
	mp[1288] = 200293516;
	mp[1289] = 596609257;
	mp[1290] = 664987275;
	mp[1291] = 865280791;
	mp[1292] = 461890041;
	mp[1293] = 126877309;
	mp[1294] = 992158100;
	mp[1295] = 454048134;
	mp[1296] = 580925443;
	mp[1297] = 573083536;
	mp[1298] = 27131663;
	mp[1299] = 608057106;
	mp[1300] = 181140635;
	mp[1301] = 208272298;
	mp[1302] = 816329404;
	mp[1303] = 997470039;
	mp[1304] = 205742330;
	mp[1305] = 22071727;
	mp[1306] = 19541759;
	mp[1307] = 225284089;
	mp[1308] = 247355816;
	mp[1309] = 266897575;
	mp[1310] = 492181664;
	mp[1311] = 739537480;
	mp[1312] = 6435048;
	mp[1313] = 498616712;
	mp[1314] = 238154185;
	mp[1315] = 244589233;
	mp[1316] = 743205945;
	mp[1317] = 981360130;
	mp[1318] = 225949356;
	mp[1319] = 969155301;
	mp[1320] = 950515424;
	mp[1321] = 176464773;
	mp[1322] = 145620067;
	mp[1323] = 96135484;
	mp[1324] = 272600257;
	mp[1325] = 418220324;
	mp[1326] = 514355808;
	mp[1327] = 786956065;
	mp[1328] = 205176382;
	mp[1329] = 719532190;
	mp[1330] = 506488248;
	mp[1331] = 711664630;
	mp[1332] = 431196813;
	mp[1333] = 937685061;
	mp[1334] = 649349684;
	mp[1335] = 80546490;
	mp[1336] = 18231544;
	mp[1337] = 667581228;
	mp[1338] = 748127718;
	mp[1339] = 766359262;
	mp[1340] = 433940483;
	mp[1341] = 182068194;
	mp[1342] = 948427456;
	mp[1343] = 382367932;
	mp[1344] = 564436126;
	mp[1345] = 512863575;
	mp[1346] = 895231507;
	mp[1347] = 459667626;
	mp[1348] = 972531201;
	mp[1349] = 867762701;
	mp[1350] = 327430320;
	mp[1351] = 299961514;
	mp[1352] = 167724208;
	mp[1353] = 495154528;
	mp[1354] = 795116042;
	mp[1355] = 962840250;
	mp[1356] = 457994771;
	mp[1357] = 253110806;
	mp[1358] = 215951049;
	mp[1359] = 673945820;
	mp[1360] = 927056626;
	mp[1361] = 143007668;
	mp[1362] = 816953488;
	mp[1363] = 744010107;
	mp[1364] = 887017775;
	mp[1365] = 703971256;
	mp[1366] = 447981356;
	mp[1367] = 334999124;
	mp[1368] = 38970373;
	mp[1369] = 486951729;
	mp[1370] = 821950853;
	mp[1371] = 860921226;
	mp[1372] = 347872948;
	mp[1373] = 169823794;
	mp[1374] = 30745013;
	mp[1375] = 378617961;
	mp[1376] = 548441755;
	mp[1377] = 579186768;
	mp[1378] = 957804729;
	mp[1379] = 506246477;
	mp[1380] = 85433238;
	mp[1381] = 43237960;
	mp[1382] = 549484437;
	mp[1383] = 634917675;
	mp[1384] = 678155635;
	mp[1385] = 227640065;
	mp[1386] = 862557740;
	mp[1387] = 540713368;
	mp[1388] = 768353433;
	mp[1389] = 630911166;
	mp[1390] = 171624527;
	mp[1391] = 939977960;
	mp[1392] = 570889119;
	mp[1393] = 742513646;
	mp[1394] = 682491599;
	mp[1395] = 253380711;
	mp[1396] = 995894357;
	mp[1397] = 678385949;
	mp[1398] = 931766660;
	mp[1399] = 927661010;
	mp[1400] = 606046952;
	mp[1401] = 537813605;
	mp[1402] = 465474608;
	mp[1403] = 71521553;
	mp[1404] = 609335158;
	mp[1405] = 74809759;
	mp[1406] = 146331312;
	mp[1407] = 755666470;
	mp[1408] = 830476229;
	mp[1409] = 976807541;
	mp[1410] = 732474004;
	mp[1411] = 562950226;
	mp[1412] = 539757760;
	mp[1413] = 272231757;
	mp[1414] = 835181983;
	mp[1415] = 374939736;
	mp[1416] = 647171493;
	mp[1417] = 482353469;
	mp[1418] = 857293205;
	mp[1419] = 504464691;
	mp[1420] = 986818160;
	mp[1421] = 844111358;
	mp[1422] = 348576042;
	mp[1423] = 335394195;
	mp[1424] = 179505546;
	mp[1425] = 528081588;
	mp[1426] = 863475783;
	mp[1427] = 42981322;
	mp[1428] = 571062910;
	mp[1429] = 434538686;
	mp[1430] = 477520008;
	mp[1431] = 48582911;
	mp[1432] = 483121597;
	mp[1433] = 960641605;
	mp[1434] = 9224509;
	mp[1435] = 492346106;
	mp[1436] = 452987704;
	mp[1437] = 462212213;
	mp[1438] = 954558319;
	mp[1439] = 407546016;
	mp[1440] = 869758229;
	mp[1441] = 824316541;
	mp[1442] = 231862550;
	mp[1443] = 101620772;
	mp[1444] = 925937313;
	mp[1445] = 157799856;
	mp[1446] = 259420628;
	mp[1447] = 185357934;
	mp[1448] = 343157790;
	mp[1449] = 602578418;
	mp[1450] = 787936352;
	mp[1451] = 131094135;
	mp[1452] = 733672553;
	mp[1453] = 521608898;
	mp[1454] = 652703033;
	mp[1455] = 386375579;
	mp[1456] = 907984477;
	mp[1457] = 560687503;
	mp[1458] = 947063082;
	mp[1459] = 855047552;
	mp[1460] = 415735048;
	mp[1461] = 362798123;
	mp[1462] = 217845668;
	mp[1463] = 633580716;
	mp[1464] = 996378839;
	mp[1465] = 214224500;
	mp[1466] = 847805216;
	mp[1467] = 844184048;
	mp[1468] = 58408541;
	mp[1469] = 906213757;
	mp[1470] = 750397798;
	mp[1471] = 808806339;
	mp[1472] = 715020089;
	mp[1473] = 465417880;
	mp[1474] = 274224212;
	mp[1475] = 989244301;
	mp[1476] = 454662174;
	mp[1477] = 728886386;
	mp[1478] = 718130680;
	mp[1479] = 172792847;
	mp[1480] = 901679233;
	mp[1481] = 619809906;
	mp[1482] = 792602753;
	mp[1483] = 694281979;
	mp[1484] = 314091878;
	mp[1485] = 106694624;
	mp[1486] = 800976603;
	mp[1487] = 115068474;
	mp[1488] = 221763098;
	mp[1489] = 22739694;
	mp[1490] = 137808168;
	mp[1491] = 359571266;
	mp[1492] = 382310960;
	mp[1493] = 520119128;
	mp[1494] = 879690394;
	mp[1495] = 262001347;
	mp[1496] = 782120475;
	mp[1497] = 661810862;
	mp[1498] = 923812209;
	mp[1499] = 705932677;
	mp[1500] = 367743532;
	mp[1501] = 291555734;
	mp[1502] = 997488411;
	mp[1503] = 365231936;
	mp[1504] = 656787670;
	mp[1505] = 654276074;
	mp[1506] = 19508003;
	mp[1507] = 676295673;
	mp[1508] = 330571740;
	mp[1509] = 350079743;
	mp[1510] = 26375409;
	mp[1511] = 356947149;
	mp[1512] = 707026892;
	mp[1513] = 733402301;
	mp[1514] = 90349443;
	mp[1515] = 797376335;
	mp[1516] = 530778629;
	mp[1517] = 621128072;
	mp[1518] = 418504400;
	mp[1519] = 949283029;
	mp[1520] = 570411094;
	mp[1521] = 988915494;
	mp[1522] = 938198516;
	mp[1523] = 508609603;
	mp[1524] = 497525090;
	mp[1525] = 435723599;
	mp[1526] = 944333202;
	mp[1527] = 441858285;
	mp[1528] = 877581884;
	mp[1529] = 821915079;
	mp[1530] = 263773357;
	mp[1531] = 141355234;
	mp[1532] = 963270313;
	mp[1533] = 227043663;
	mp[1534] = 368398897;
	mp[1535] = 331669203;
	mp[1536] = 558712866;
	mp[1537] = 927111763;
	mp[1538] = 258780959;
	mp[1539] = 817493825;
	mp[1540] = 744605581;
	mp[1541] = 3386533;
	mp[1542] = 820880358;
	mp[1543] = 565485932;
	mp[1544] = 568872465;
	mp[1545] = 389752816;
	mp[1546] = 955238748;
	mp[1547] = 524111206;
	mp[1548] = 913864022;
	mp[1549] = 869102763;
	mp[1550] = 393213962;
	mp[1551] = 307077977;
	mp[1552] = 176180733;
	mp[1553] = 569394695;
	mp[1554] = 876472672;
	mp[1555] = 52653398;
	mp[1556] = 622048093;
	mp[1557] = 498520758;
	mp[1558] = 551174156;
	mp[1559] = 173222242;
	mp[1560] = 671743000;
	mp[1561] = 222917149;
	mp[1562] = 396139391;
	mp[1563] = 67882384;
	mp[1564] = 290799533;
	mp[1565] = 686938924;
	mp[1566] = 754821308;
	mp[1567] = 45620834;
	mp[1568] = 732559758;
	mp[1569] = 487381059;
	mp[1570] = 533001893;
	mp[1571] = 265561644;
	mp[1572] = 752942703;
	mp[1573] = 285944589;
	mp[1574] = 551506233;
	mp[1575] = 304448929;
	mp[1576] = 590393518;
	mp[1577] = 141899744;
	mp[1578] = 446348673;
	mp[1579] = 36742184;
	mp[1580] = 178641928;
	mp[1581] = 624990601;
	mp[1582] = 661732785;
	mp[1583] = 840374713;
	mp[1584] = 465365307;
	mp[1585] = 127098085;
	mp[1586] = 967472798;
	mp[1587] = 432838098;
	mp[1588] = 559936183;
	mp[1589] = 527408974;
	mp[1590] = 960247072;
	mp[1591] = 520183248;
	mp[1592] = 47592215;
	mp[1593] = 7839280;
	mp[1594] = 528022528;
	mp[1595] = 575614743;
	mp[1596] = 583454023;
	mp[1597] = 111476544;
	mp[1598] = 687091287;
	mp[1599] = 270545303;
	mp[1600] = 382021847;
	mp[1601] = 69113127;
	mp[1602] = 339658430;
	mp[1603] = 721680277;
	mp[1604] = 790793404;
	mp[1605] = 130451827;
	mp[1606] = 852132104;
	mp[1607] = 642925501;
	mp[1608] = 773377328;
	mp[1609] = 625509425;
	mp[1610] = 268434919;
	mp[1611] = 41812240;
	mp[1612] = 667321665;
	mp[1613] = 935756584;
	mp[1614] = 977568824;
	mp[1615] = 644890482;
	mp[1616] = 580647059;
	mp[1617] = 558215876;
	mp[1618] = 203106351;
	mp[1619] = 783753410;
	mp[1620] = 341969279;
	mp[1621] = 545075630;
	mp[1622] = 328829033;
	mp[1623] = 670798312;
	mp[1624] = 215873935;
	mp[1625] = 544702968;
	mp[1626] = 215501273;
	mp[1627] = 431375208;
	mp[1628] = 976078176;
	mp[1629] = 191579442;
	mp[1630] = 622954650;
	mp[1631] = 599032819;
	mp[1632] = 790612261;
	mp[1633] = 413566904;
	mp[1634] = 12599716;
	mp[1635] = 803211977;
	mp[1636] = 216778874;
	mp[1637] = 229378590;
	mp[1638] = 32590560;
	mp[1639] = 249369434;
	mp[1640] = 478748024;
	mp[1641] = 511338584;
	mp[1642] = 760708018;
	mp[1643] = 239456035;
	mp[1644] = 750794619;
	mp[1645] = 511502630;
	mp[1646] = 750958665;
	mp[1647] = 501753277;
	mp[1648] = 13255900;
	mp[1649] = 764214565;
	mp[1650] = 265967835;
	mp[1651] = 279223735;
	mp[1652] = 43438293;
	mp[1653] = 309406128;
	mp[1654] = 588629863;
	mp[1655] = 632068156;
	mp[1656] = 941474284;
	mp[1657] = 530104140;
	mp[1658] = 162172289;
	mp[1659] = 103646566;
	mp[1660] = 633750706;
	mp[1661] = 795922995;
	mp[1662] = 899569561;
	mp[1663] = 533320260;
	mp[1664] = 329243248;
	mp[1665] = 228812802;
	mp[1666] = 762133062;
	mp[1667] = 91376303;
	mp[1668] = 320189105;
	mp[1669] = 82322160;
	mp[1670] = 173698463;
	mp[1671] = 493887568;
	mp[1672] = 576209728;
	mp[1673] = 749908191;
	mp[1674] = 243795752;
	mp[1675] = 820005480;
	mp[1676] = 569913664;
	mp[1677] = 813709416;
	mp[1678] = 633714889;
	mp[1679] = 203628546;
	mp[1680] = 17337955;
	mp[1681] = 651052844;
	mp[1682] = 854681390;
	mp[1683] = 872019345;
	mp[1684] = 523072182;
	mp[1685] = 377753565;
	mp[1686] = 249772903;
	mp[1687] = 772845085;
	mp[1688] = 150598643;
	mp[1689] = 400371546;
	mp[1690] = 173216624;
	mp[1691] = 323815267;
	mp[1692] = 724186813;
	mp[1693] = 897403437;
	mp[1694] = 221218697;
	mp[1695] = 945405510;
	mp[1696] = 842808940;
	mp[1697] = 64027630;
	mp[1698] = 9433133;
	mp[1699] = 852242073;
	mp[1700] = 916269703;
	mp[1701] = 925702836;
	mp[1702] = 777944902;
	mp[1703] = 694214598;
	mp[1704] = 619917427;
	mp[1705] = 397862322;
	mp[1706] = 92076913;
	mp[1707] = 711994340;
	mp[1708] = 109856655;
	mp[1709] = 201933568;
	mp[1710] = 913927908;
	mp[1711] = 23784556;
	mp[1712] = 225718124;
	mp[1713] = 139646025;
	mp[1714] = 163430581;
	mp[1715] = 389148705;
	mp[1716] = 528794730;
	mp[1717] = 692225311;
	mp[1718] = 81374009;
	mp[1719] = 610168739;
	mp[1720] = 302394043;
	mp[1721] = 383768052;
	mp[1722] = 993936791;
	mp[1723] = 296330827;
	mp[1724] = 680098879;
	mp[1725] = 674035663;
	mp[1726] = 970366490;
	mp[1727] = 650465362;
	mp[1728] = 324501018;
	mp[1729] = 294867501;
	mp[1730] = 945332863;
	mp[1731] = 269833874;
	mp[1732] = 564701375;
	mp[1733] = 510034231;
	mp[1734] = 779868105;
	mp[1735] = 344569473;
	mp[1736] = 854603704;
	mp[1737] = 634471802;
	mp[1738] = 979041275;
	mp[1739] = 833644972;
	mp[1740] = 468116767;
	mp[1741] = 447158035;
	mp[1742] = 280803000;
	mp[1743] = 748919767;
	mp[1744] = 196077795;
	mp[1745] = 476880795;
	mp[1746] = 225800555;
	mp[1747] = 421878350;
	mp[1748] = 898759145;
	mp[1749] = 124559693;
	mp[1750] = 546438043;
	mp[1751] = 445197181;
	mp[1752] = 569756874;
	mp[1753] = 116194910;
	mp[1754] = 561392091;
	mp[1755] = 131148958;
	mp[1756] = 247343868;
	mp[1757] = 808735959;
	mp[1758] = 939884917;
	mp[1759] = 187228778;
	mp[1760] = 995964737;
	mp[1761] = 935849647;
	mp[1762] = 123078418;
	mp[1763] = 119043148;
	mp[1764] = 54892788;
	mp[1765] = 177971206;
	mp[1766] = 297014354;
	mp[1767] = 351907142;
	mp[1768] = 529878348;
	mp[1769] = 826892702;
	mp[1770] = 178799837;
	mp[1771] = 708678185;
	mp[1772] = 535570880;
	mp[1773] = 714370717;
	mp[1774] = 423048895;
	mp[1775] = 958619775;
	mp[1776] = 672990485;
	mp[1777] = 96039373;
	mp[1778] = 54659141;
	mp[1779] = 727649626;
	mp[1780] = 823688999;
	mp[1781] = 878348140;
	mp[1782] = 605997759;
	mp[1783] = 429686751;
	mp[1784] = 308034884;
	mp[1785] = 914032643;
	mp[1786] = 343719387;
	mp[1787] = 651754271;
	mp[1788] = 565786907;
	mp[1789] = 909506294;
	mp[1790] = 561260558;
	mp[1791] = 127047458;
	mp[1792] = 36553745;
	mp[1793] = 597814303;
	mp[1794] = 724861761;
	mp[1795] = 761415506;
	mp[1796] = 359229802;
	mp[1797] = 84091556;
	mp[1798] = 845507062;
	mp[1799] = 204736857;
	mp[1800] = 288828413;
	mp[1801] = 134335468;
	mp[1802] = 339072325;
	mp[1803] = 627900738;
	mp[1804] = 762236206;
	mp[1805] = 101308524;
	mp[1806] = 729209262;
	mp[1807] = 491445461;
	mp[1808] = 592753985;
	mp[1809] = 321963240;
	mp[1810] = 813408701;
	mp[1811] = 406162679;
	mp[1812] = 728125919;
	mp[1813] = 541534613;
	mp[1814] = 947697292;
	mp[1815] = 675823204;
	mp[1816] = 217357810;
	mp[1817] = 165055095;
	mp[1818] = 840878299;
	mp[1819] = 58236102;
	mp[1820] = 223291197;
	mp[1821] = 64169489;
	mp[1822] = 122405591;
	mp[1823] = 345696788;
	mp[1824] = 409866277;
	mp[1825] = 532271868;
	mp[1826] = 877968656;
	mp[1827] = 287834926;
	mp[1828] = 820106794;
	mp[1829] = 698075443;
	mp[1830] = 985910369;
	mp[1831] = 806017156;
	mp[1832] = 504092592;
	mp[1833] = 490002954;
	mp[1834] = 296020103;
	mp[1835] = 800112695;
	mp[1836] = 290115642;
	mp[1837] = 586135745;
	mp[1838] = 386248433;
	mp[1839] = 676364075;
	mp[1840] = 262499813;
	mp[1841] = 648748246;
	mp[1842] = 325112314;
	mp[1843] = 587612127;
	mp[1844] = 236360366;
	mp[1845] = 561472680;
	mp[1846] = 149084800;
	mp[1847] = 385445166;
	mp[1848] = 946917846;
	mp[1849] = 96002639;
	mp[1850] = 481447805;
	mp[1851] = 428365644;
	mp[1852] = 524368283;
	mp[1853] = 5816081;
	mp[1854] = 434181725;
	mp[1855] = 958550008;
	mp[1856] = 964366089;
	mp[1857] = 398547807;
	mp[1858] = 357097808;
	mp[1859] = 321463890;
	mp[1860] = 720011697;
	mp[1861] = 77109498;
	mp[1862] = 398573388;
	mp[1863] = 118585078;
	mp[1864] = 195694576;
	mp[1865] = 594267964;
	mp[1866] = 712853042;
	mp[1867] = 908547618;
	mp[1868] = 502815575;
	mp[1869] = 215668610;
	mp[1870] = 124216221;
	mp[1871] = 627031796;
	mp[1872] = 842700406;
	mp[1873] = 966916627;
	mp[1874] = 593948416;
	mp[1875] = 436648815;
	mp[1876] = 403565435;
	mp[1877] = 997513851;
	mp[1878] = 434162659;
	mp[1879] = 837728094;
	mp[1880] = 835241938;
	mp[1881] = 269404590;
	mp[1882] = 107132677;
	mp[1883] = 942374615;
	mp[1884] = 211779198;
	mp[1885] = 318911875;
	mp[1886] = 261286483;
	mp[1887] = 473065681;
	mp[1888] = 791977556;
	mp[1889] = 53264032;
	mp[1890] = 526329713;
	mp[1891] = 318307262;
	mp[1892] = 371571294;
	mp[1893] = 897901007;
	mp[1894] = 216208262;
	mp[1895] = 587779556;
	mp[1896] = 485680556;
	mp[1897] = 701888818;
	mp[1898] = 289668367;
	mp[1899] = 775348923;
	mp[1900] = 477237734;
	mp[1901] = 766906101;
	mp[1902] = 542255017;
	mp[1903] = 19492744;
	mp[1904] = 786398845;
	mp[1905] = 328653855;
	mp[1906] = 348146599;
	mp[1907] = 134545437;
	mp[1908] = 463199292;
	mp[1909] = 811345891;
	mp[1910] = 945891328;
	mp[1911] = 409090613;
	mp[1912] = 220436497;
	mp[1913] = 166327818;
	mp[1914] = 575418431;
	mp[1915] = 795854928;
	mp[1916] = 962182746;
	mp[1917] = 537601170;
	mp[1918] = 333456091;
	mp[1919] = 295638830;
	mp[1920] = 833240000;
	mp[1921] = 166696084;
	mp[1922] = 462334914;
	mp[1923] = 295574907;
	mp[1924] = 462270991;
	mp[1925] = 924605905;
	mp[1926] = 220180805;
	mp[1927] = 682451796;
	mp[1928] = 607057694;
	mp[1929] = 827238499;
	mp[1930] = 509690288;
	mp[1931] = 116747975;
	mp[1932] = 943986474;
	mp[1933] = 453676755;
	mp[1934] = 570424730;
	mp[1935] = 514411197;
	mp[1936] = 968087952;
	mp[1937] = 538512675;
	mp[1938] = 52923865;
	mp[1939] = 21011810;
	mp[1940] = 559524485;
	mp[1941] = 612448350;
	mp[1942] = 633460160;
	mp[1943] = 192984638;
	mp[1944] = 805432988;
	mp[1945] = 438893141;
	mp[1946] = 631877779;
	mp[1947] = 437310760;
	mp[1948] = 876203901;
	mp[1949] = 508081673;
	mp[1950] = 945392433;
	mp[1951] = 821596327;
	mp[1952] = 329677993;
	mp[1953] = 275070419;
	mp[1954] = 96666739;
	mp[1955] = 426344732;
	mp[1956] = 701415151;
	mp[1957] = 798081890;
	mp[1958] = 224426615;
	mp[1959] = 925841766;
	mp[1960] = 723923649;
	mp[1961] = 948350264;
	mp[1962] = 874192023;
	mp[1963] = 598115665;
	mp[1964] = 546465922;
	mp[1965] = 420657938;
	mp[1966] = 18773596;
	mp[1967] = 565239518;
	mp[1968] = 985897456;
	mp[1969] = 4671045;
	mp[1970] = 569910563;
	mp[1971] = 555808012;
	mp[1972] = 560479057;
	mp[1973] = 130389613;
	mp[1974] = 686197625;
	mp[1975] = 246676675;
	mp[1976] = 377066288;
	mp[1977] = 63263906;
	mp[1978] = 309940581;
	mp[1979] = 687006869;
	mp[1980] = 750270775;
	mp[1981] = 60211349;
	mp[1982] = 747218218;
	mp[1983] = 497488986;
	mp[1984] = 557700335;
	mp[1985] = 304918546;
	mp[1986] = 802407532;
	mp[1987] = 360107860;
	mp[1988] = 665026406;
	mp[1989] = 467433931;
	mp[1990] = 827541791;
	mp[1991] = 492568190;
	mp[1992] = 960002121;
	mp[1993] = 787543905;
	mp[1994] = 280112088;
	mp[1995] = 240114202;
	mp[1996] = 27658100;
	mp[1997] = 307770188;
	mp[1998] = 547884390;
	mp[1999] = 575542490;
	mp[2000] = 883312678;

	cin >> s;
	cout << mp[s] << endl;
	return 0;
}

Measured memory_bytes: 3624