結果
| 問題 |
No.502 階乗を計算するだけ
|
| ユーザー |
 14番
|
| 提出日時 | 2017-06-04 17:44:08 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 31,299 bytes |
| コンパイル時間 | 1,098 ms |
| コンパイル使用メモリ | 121,996 KB |
| 実行使用メモリ | 31,956 KB |
| 最終ジャッジ日時 | 2024-09-22 05:42:48 |
| 合計ジャッジ時間 | 5,108 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 TLE * 1 -- * 19 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
public class Program
{
public void Proc()
{
decimal mod = 1000000000 + 7;
long num = long.Parse(Reader.ReadLine());
if(num >= mod) {
Console.WriteLine(0);
return;
}
Dictionary<long, long> dic = new Dictionary<long, long>();
KeyValuePair<long, long> fromKeyPair = dic.LastOrDefault(a => a.Key < num);
long fromKey = 1;
decimal ans = 1;
if (fromKeyPair.Value > 0) {
fromKey = fromKeyPair.Key;
ans = fromKeyPair.Value;
}
for (long i = fromKey + 1; i <= num; i++) {
ans = ans * i;
ans = ans % mod;
if(ans == 0) {
break;
}
}
Console.WriteLine(ans.ToString());
}
private Dictionary<long, long> GetDic() {
Dictionary<long, long> dic = new Dictionary<long, long>();
dic[1000000] = 641102369;
dic[2000000] = 578095319;
dic[3000000] = 5832229;
dic[4000000] = 259081142;
dic[5000000] = 974067448;
dic[6000000] = 316220877;
dic[7000000] = 690120224;
dic[8000000] = 251368199;
dic[9000000] = 980250487;
dic[10000000] = 682498929;
dic[11000000] = 134623568;
dic[12000000] = 95936601;
dic[13000000] = 933097914;
dic[14000000] = 167332441;
dic[15000000] = 598816162;
dic[16000000] = 336060741;
dic[17000000] = 248744620;
dic[18000000] = 626497524;
dic[19000000] = 288843364;
dic[20000000] = 491101308;
dic[21000000] = 245341950;
dic[22000000] = 565768255;
dic[23000000] = 246899319;
dic[24000000] = 968999;
dic[25000000] = 586350670;
dic[26000000] = 638587686;
dic[27000000] = 881746146;
dic[28000000] = 19426633;
dic[29000000] = 850500036;
dic[30000000] = 76479948;
dic[31000000] = 268124147;
dic[32000000] = 842267748;
dic[33000000] = 886294336;
dic[34000000] = 485348706;
dic[35000000] = 463847391;
dic[36000000] = 544075857;
dic[37000000] = 898187927;
dic[38000000] = 798967520;
dic[39000000] = 82926604;
dic[40000000] = 723816384;
dic[41000000] = 156530778;
dic[42000000] = 721996174;
dic[43000000] = 299085602;
dic[44000000] = 323604647;
dic[45000000] = 172827403;
dic[46000000] = 398699886;
dic[47000000] = 530389102;
dic[48000000] = 294587621;
dic[49000000] = 813805606;
dic[50000000] = 67347853;
dic[51000000] = 497478507;
dic[52000000] = 196447201;
dic[53000000] = 722054885;
dic[54000000] = 228338256;
dic[55000000] = 407719831;
dic[56000000] = 762479457;
dic[57000000] = 746536789;
dic[58000000] = 811667359;
dic[59000000] = 778773518;
dic[60000000] = 27368307;
dic[61000000] = 438371670;
dic[62000000] = 59469516;
dic[63000000] = 5974669;
dic[64000000] = 766196482;
dic[65000000] = 606322308;
dic[66000000] = 86609485;
dic[67000000] = 889750731;
dic[68000000] = 340941507;
dic[69000000] = 371263376;
dic[70000000] = 625544428;
dic[71000000] = 788878910;
dic[72000000] = 808412394;
dic[73000000] = 996952918;
dic[74000000] = 585237443;
dic[75000000] = 1669644;
dic[76000000] = 361786913;
dic[77000000] = 480748381;
dic[78000000] = 595143852;
dic[79000000] = 837229828;
dic[80000000] = 199888908;
dic[81000000] = 526807168;
dic[82000000] = 579691190;
dic[83000000] = 145404005;
dic[84000000] = 459188207;
dic[85000000] = 534491822;
dic[86000000] = 439729802;
dic[87000000] = 840398449;
dic[88000000] = 899297830;
dic[89000000] = 235861787;
dic[90000000] = 888050723;
dic[91000000] = 656116726;
dic[92000000] = 736550105;
dic[93000000] = 440902696;
dic[94000000] = 85990869;
dic[95000000] = 884343068;
dic[96000000] = 56305184;
dic[97000000] = 973478770;
dic[98000000] = 168891766;
dic[99000000] = 804805577;
dic[100000000] = 927880474;
dic[101000000] = 876297919;
dic[102000000] = 934814019;
dic[103000000] = 676405347;
dic[104000000] = 567277637;
dic[105000000] = 112249297;
dic[106000000] = 44930135;
dic[107000000] = 39417871;
dic[108000000] = 47401357;
dic[109000000] = 108819476;
dic[110000000] = 281863274;
dic[111000000] = 60168088;
dic[112000000] = 692636218;
dic[113000000] = 432775082;
dic[114000000] = 14235602;
dic[115000000] = 770511792;
dic[116000000] = 400295761;
dic[117000000] = 697066277;
dic[118000000] = 421835306;
dic[119000000] = 220108638;
dic[120000000] = 661224977;
dic[121000000] = 261799937;
dic[122000000] = 168203998;
dic[123000000] = 802214249;
dic[124000000] = 544064410;
dic[125000000] = 935080803;
dic[126000000] = 583967898;
dic[127000000] = 211768084;
dic[128000000] = 751231582;
dic[129000000] = 972424306;
dic[130000000] = 623534362;
dic[131000000] = 335160196;
dic[132000000] = 243276029;
dic[133000000] = 554749550;
dic[134000000] = 60050552;
dic[135000000] = 797848181;
dic[136000000] = 395891998;
dic[137000000] = 172428290;
dic[138000000] = 159554990;
dic[139000000] = 887420150;
dic[140000000] = 970055531;
dic[141000000] = 250388809;
dic[142000000] = 487998999;
dic[143000000] = 856259313;
dic[144000000] = 82104855;
dic[145000000] = 232253360;
dic[146000000] = 513365505;
dic[147000000] = 244109365;
dic[148000000] = 1559745;
dic[149000000] = 695345956;
dic[150000000] = 261384175;
dic[151000000] = 849009131;
dic[152000000] = 323214113;
dic[153000000] = 747664143;
dic[154000000] = 444090941;
dic[155000000] = 659224434;
dic[156000000] = 80729842;
dic[157000000] = 570033864;
dic[158000000] = 664989237;
dic[159000000] = 827348878;
dic[160000000] = 195888993;
dic[161000000] = 576798521;
dic[162000000] = 457882808;
dic[163000000] = 731551699;
dic[164000000] = 212938473;
dic[165000000] = 509096183;
dic[166000000] = 827544702;
dic[167000000] = 678320208;
dic[168000000] = 677711203;
dic[169000000] = 289752035;
dic[170000000] = 66404266;
dic[171000000] = 555972231;
dic[172000000] = 195290384;
dic[173000000] = 97136305;
dic[174000000] = 349551356;
dic[175000000] = 785113347;
dic[176000000] = 83489485;
dic[177000000] = 66247239;
dic[178000000] = 52167191;
dic[179000000] = 307390891;
dic[180000000] = 547665832;
dic[181000000] = 143066173;
dic[182000000] = 350016754;
dic[183000000] = 917404120;
dic[184000000] = 296269301;
dic[185000000] = 996122673;
dic[186000000] = 23015220;
dic[187000000] = 602139210;
dic[188000000] = 748566338;
dic[189000000] = 187348575;
dic[190000000] = 109838563;
dic[191000000] = 574053420;
dic[192000000] = 105574531;
dic[193000000] = 304173654;
dic[194000000] = 542432219;
dic[195000000] = 34538816;
dic[196000000] = 325636655;
dic[197000000] = 437843114;
dic[198000000] = 630621321;
dic[199000000] = 26853683;
dic[200000000] = 933245637;
dic[201000000] = 616368450;
dic[202000000] = 238971581;
dic[203000000] = 511371690;
dic[204000000] = 557301633;
dic[205000000] = 911398531;
dic[206000000] = 848952161;
dic[207000000] = 958992544;
dic[208000000] = 925152039;
dic[209000000] = 914456118;
dic[210000000] = 724691727;
dic[211000000] = 636817583;
dic[212000000] = 238087006;
dic[213000000] = 946237212;
dic[214000000] = 910291942;
dic[215000000] = 114985663;
dic[216000000] = 492237273;
dic[217000000] = 450387329;
dic[218000000] = 834860913;
dic[219000000] = 763017204;
dic[220000000] = 368925948;
dic[221000000] = 475812562;
dic[222000000] = 740594930;
dic[223000000] = 45060610;
dic[224000000] = 806047532;
dic[225000000] = 464456846;
dic[226000000] = 172115341;
dic[227000000] = 75307702;
dic[228000000] = 116261993;
dic[229000000] = 562519302;
dic[230000000] = 268838846;
dic[231000000] = 173784895;
dic[232000000] = 243624360;
dic[233000000] = 61570384;
dic[234000000] = 481661251;
dic[235000000] = 938269070;
dic[236000000] = 95182730;
dic[237000000] = 91068149;
dic[238000000] = 115435332;
dic[239000000] = 495022305;
dic[240000000] = 136026497;
dic[241000000] = 506496856;
dic[242000000] = 710729672;
dic[243000000] = 113570024;
dic[244000000] = 366384665;
dic[245000000] = 564758715;
dic[246000000] = 270239666;
dic[247000000] = 277118392;
dic[248000000] = 79874094;
dic[249000000] = 702807165;
dic[250000000] = 112390913;
dic[251000000] = 730341625;
dic[252000000] = 103056890;
dic[253000000] = 677948390;
dic[254000000] = 339464594;
dic[255000000] = 167240465;
dic[256000000] = 108312174;
dic[257000000] = 839079953;
dic[258000000] = 479334442;
dic[259000000] = 271788964;
dic[260000000] = 135498044;
dic[261000000] = 277717575;
dic[262000000] = 591048681;
dic[263000000] = 811637561;
dic[264000000] = 353339603;
dic[265000000] = 889410460;
dic[266000000] = 839849206;
dic[267000000] = 192345193;
dic[268000000] = 736265527;
dic[269000000] = 316439118;
dic[270000000] = 217544623;
dic[271000000] = 788132977;
dic[272000000] = 618898635;
dic[273000000] = 183011467;
dic[274000000] = 380858207;
dic[275000000] = 996097969;
dic[276000000] = 898554793;
dic[277000000] = 335353644;
dic[278000000] = 54062950;
dic[279000000] = 611251733;
dic[280000000] = 419363534;
dic[281000000] = 965429853;
dic[282000000] = 160398980;
dic[283000000] = 151319402;
dic[284000000] = 990918946;
dic[285000000] = 607730875;
dic[286000000] = 450718279;
dic[287000000] = 173539388;
dic[288000000] = 648991369;
dic[289000000] = 970937898;
dic[290000000] = 500780548;
dic[291000000] = 780122909;
dic[292000000] = 39052406;
dic[293000000] = 276894233;
dic[294000000] = 460373282;
dic[295000000] = 651081062;
dic[296000000] = 461415770;
dic[297000000] = 358700839;
dic[298000000] = 643638805;
dic[299000000] = 560006119;
dic[300000000] = 668123525;
dic[301000000] = 686692315;
dic[302000000] = 673464765;
dic[303000000] = 957633609;
dic[304000000] = 199866123;
dic[305000000] = 563432246;
dic[306000000] = 841799766;
dic[307000000] = 385330357;
dic[308000000] = 504962686;
dic[309000000] = 954061253;
dic[310000000] = 128487469;
dic[311000000] = 685707545;
dic[312000000] = 299172297;
dic[313000000] = 717975101;
dic[314000000] = 577786541;
dic[315000000] = 318951960;
dic[316000000] = 773206631;
dic[317000000] = 306832604;
dic[318000000] = 204355779;
dic[319000000] = 573592106;
dic[320000000] = 30977140;
dic[321000000] = 450398100;
dic[322000000] = 363172638;
dic[323000000] = 258379324;
dic[324000000] = 472935553;
dic[325000000] = 93940075;
dic[326000000] = 587220627;
dic[327000000] = 776264326;
dic[328000000] = 793270300;
dic[329000000] = 291733496;
dic[330000000] = 522049725;
dic[331000000] = 579995261;
dic[332000000] = 335416359;
dic[333000000] = 142946099;
dic[334000000] = 472012302;
dic[335000000] = 559947225;
dic[336000000] = 332139472;
dic[337000000] = 499377092;
dic[338000000] = 464599136;
dic[339000000] = 164752359;
dic[340000000] = 309058615;
dic[341000000] = 86117128;
dic[342000000] = 580204973;
dic[343000000] = 563781682;
dic[344000000] = 954840109;
dic[345000000] = 624577416;
dic[346000000] = 895609896;
dic[347000000] = 888287558;
dic[348000000] = 836813268;
dic[349000000] = 926036911;
dic[350000000] = 386027524;
dic[351000000] = 184419613;
dic[352000000] = 724205533;
dic[353000000] = 403351886;
dic[354000000] = 715247054;
dic[355000000] = 716986954;
dic[356000000] = 830567832;
dic[357000000] = 383388563;
dic[358000000] = 68409439;
dic[359000000] = 6734065;
dic[360000000] = 189239124;
dic[361000000] = 68322490;
dic[362000000] = 943653305;
dic[363000000] = 405755338;
dic[364000000] = 811056092;
dic[365000000] = 179518046;
dic[366000000] = 825132993;
dic[367000000] = 343807435;
dic[368000000] = 985084650;
dic[369000000] = 868553027;
dic[370000000] = 148528617;
dic[371000000] = 160684257;
dic[372000000] = 882148737;
dic[373000000] = 591915968;
dic[374000000] = 701445829;
dic[375000000] = 529726489;
dic[376000000] = 302177126;
dic[377000000] = 974886682;
dic[378000000] = 241107368;
dic[379000000] = 798830099;
dic[380000000] = 940567523;
dic[381000000] = 11633075;
dic[382000000] = 325334066;
dic[383000000] = 346091869;
dic[384000000] = 115312728;
dic[385000000] = 473718967;
dic[386000000] = 218129285;
dic[387000000] = 878471898;
dic[388000000] = 180002392;
dic[389000000] = 699739374;
dic[390000000] = 917084264;
dic[391000000] = 856859395;
dic[392000000] = 435327356;
dic[393000000] = 808651347;
dic[394000000] = 421623838;
dic[395000000] = 105419548;
dic[396000000] = 59883031;
dic[397000000] = 322487421;
dic[398000000] = 79716267;
dic[399000000] = 715317963;
dic[400000000] = 429277690;
dic[401000000] = 398078032;
dic[402000000] = 316486674;
dic[403000000] = 384843585;
dic[404000000] = 940338439;
dic[405000000] = 937409008;
dic[406000000] = 940524812;
dic[407000000] = 947549662;
dic[408000000] = 833550543;
dic[409000000] = 593524514;
dic[410000000] = 996164327;
dic[411000000] = 987314628;
dic[412000000] = 697611981;
dic[413000000] = 636177449;
dic[414000000] = 274192146;
dic[415000000] = 418537348;
dic[416000000] = 925347821;
dic[417000000] = 952831975;
dic[418000000] = 893732627;
dic[419000000] = 1277567;
dic[420000000] = 358655417;
dic[421000000] = 141866945;
dic[422000000] = 581830879;
dic[423000000] = 987597705;
dic[424000000] = 347046911;
dic[425000000] = 775305697;
dic[426000000] = 125354499;
dic[427000000] = 951540811;
dic[428000000] = 247662371;
dic[429000000] = 343043237;
dic[430000000] = 568392357;
dic[431000000] = 997474832;
dic[432000000] = 209244402;
dic[433000000] = 380480118;
dic[434000000] = 149586983;
dic[435000000] = 392838702;
dic[436000000] = 309134554;
dic[437000000] = 990779998;
dic[438000000] = 263053337;
dic[439000000] = 325362513;
dic[440000000] = 780072518;
dic[441000000] = 551028176;
dic[442000000] = 990826116;
dic[443000000] = 989944961;
dic[444000000] = 155569943;
dic[445000000] = 596737944;
dic[446000000] = 711553356;
dic[447000000] = 268844715;
dic[448000000] = 451373308;
dic[449000000] = 379404150;
dic[450000000] = 462639908;
dic[451000000] = 961812918;
dic[452000000] = 654611901;
dic[453000000] = 382776490;
dic[454000000] = 41815820;
dic[455000000] = 843321396;
dic[456000000] = 675258797;
dic[457000000] = 845583555;
dic[458000000] = 934281721;
dic[459000000] = 741114145;
dic[460000000] = 275105629;
dic[461000000] = 666247477;
dic[462000000] = 325912072;
dic[463000000] = 526131620;
dic[464000000] = 252551589;
dic[465000000] = 432030917;
dic[466000000] = 554917439;
dic[467000000] = 818036959;
dic[468000000] = 754363835;
dic[469000000] = 795190182;
dic[470000000] = 909210595;
dic[471000000] = 278704903;
dic[472000000] = 719566487;
dic[473000000] = 628514947;
dic[474000000] = 424989675;
dic[475000000] = 321685608;
dic[476000000] = 50590510;
dic[477000000] = 832069712;
dic[478000000] = 198768464;
dic[479000000] = 702004730;
dic[480000000] = 99199382;
dic[481000000] = 707469729;
dic[482000000] = 747407118;
dic[483000000] = 302020341;
dic[484000000] = 497196934;
dic[485000000] = 5003231;
dic[486000000] = 726997875;
dic[487000000] = 382617671;
dic[488000000] = 296229203;
dic[489000000] = 183888367;
dic[490000000] = 703397904;
dic[491000000] = 552133875;
dic[492000000] = 732868367;
dic[493000000] = 350095207;
dic[494000000] = 26031303;
dic[495000000] = 863250534;
dic[496000000] = 216665960;
dic[497000000] = 561745549;
dic[498000000] = 352946234;
dic[499000000] = 784139777;
dic[500000000] = 733333339;
dic[501000000] = 503105966;
dic[502000000] = 459878625;
dic[503000000] = 803187381;
dic[504000000] = 16634739;
dic[505000000] = 180898306;
dic[506000000] = 68718097;
dic[507000000] = 985594252;
dic[508000000] = 404206040;
dic[509000000] = 749724532;
dic[510000000] = 97830135;
dic[511000000] = 611751357;
dic[512000000] = 31131935;
dic[513000000] = 662741752;
dic[514000000] = 864326453;
dic[515000000] = 864869025;
dic[516000000] = 167831173;
dic[517000000] = 559214642;
dic[518000000] = 718498895;
dic[519000000] = 91352335;
dic[520000000] = 608823837;
dic[521000000] = 473379392;
dic[522000000] = 385388084;
dic[523000000] = 152267158;
dic[524000000] = 681756977;
dic[525000000] = 46819124;
dic[526000000] = 313132653;
dic[527000000] = 56547945;
dic[528000000] = 442795120;
dic[529000000] = 796616594;
dic[530000000] = 256141983;
dic[531000000] = 152028387;
dic[532000000] = 636578562;
dic[533000000] = 385377759;
dic[534000000] = 553033642;
dic[535000000] = 491415383;
dic[536000000] = 919273670;
dic[537000000] = 996049638;
dic[538000000] = 326686486;
dic[539000000] = 160150665;
dic[540000000] = 141827977;
dic[541000000] = 540818053;
dic[542000000] = 693305776;
dic[543000000] = 593938674;
dic[544000000] = 186576440;
dic[545000000] = 688809790;
dic[546000000] = 565456578;
dic[547000000] = 749296077;
dic[548000000] = 519397500;
dic[549000000] = 551096742;
dic[550000000] = 696628828;
dic[551000000] = 775025061;
dic[552000000] = 370732451;
dic[553000000] = 164246193;
dic[554000000] = 915265013;
dic[555000000] = 457469634;
dic[556000000] = 923043932;
dic[557000000] = 912368644;
dic[558000000] = 777901604;
dic[559000000] = 464118005;
dic[560000000] = 637939935;
dic[561000000] = 956856710;
dic[562000000] = 490676632;
dic[563000000] = 453019482;
dic[564000000] = 462528877;
dic[565000000] = 502297454;
dic[566000000] = 798895521;
dic[567000000] = 100498586;
dic[568000000] = 699767918;
dic[569000000] = 849974789;
dic[570000000] = 811575797;
dic[571000000] = 438952959;
dic[572000000] = 606870929;
dic[573000000] = 907720182;
dic[574000000] = 179111720;
dic[575000000] = 48053248;
dic[576000000] = 508038818;
dic[577000000] = 811944661;
dic[578000000] = 752550134;
dic[579000000] = 401382061;
dic[580000000] = 848924691;
dic[581000000] = 764368449;
dic[582000000] = 34629406;
dic[583000000] = 529840945;
dic[584000000] = 435904287;
dic[585000000] = 26011548;
dic[586000000] = 208184231;
dic[587000000] = 446477394;
dic[588000000] = 206330671;
dic[589000000] = 366033520;
dic[590000000] = 131772368;
dic[591000000] = 185646898;
dic[592000000] = 648711554;
dic[593000000] = 472759660;
dic[594000000] = 523696723;
dic[595000000] = 271198437;
dic[596000000] = 25058942;
dic[597000000] = 859369491;
dic[598000000] = 817928963;
dic[599000000] = 330711333;
dic[600000000] = 724464507;
dic[601000000] = 437605233;
dic[602000000] = 701453022;
dic[603000000] = 626663115;
dic[604000000] = 281230685;
dic[605000000] = 510650790;
dic[606000000] = 596949867;
dic[607000000] = 295726547;
dic[608000000] = 303076380;
dic[609000000] = 465070856;
dic[610000000] = 272814771;
dic[611000000] = 538771609;
dic[612000000] = 48824684;
dic[613000000] = 951279549;
dic[614000000] = 939889684;
dic[615000000] = 564188856;
dic[616000000] = 48527183;
dic[617000000] = 201307702;
dic[618000000] = 484458461;
dic[619000000] = 861754542;
dic[620000000] = 326159309;
dic[621000000] = 181594759;
dic[622000000] = 668422905;
dic[623000000] = 286273596;
dic[624000000] = 965656187;
dic[625000000] = 44135644;
dic[626000000] = 359960756;
dic[627000000] = 936229527;
dic[628000000] = 407934361;
dic[629000000] = 267193060;
dic[630000000] = 456152084;
dic[631000000] = 459116722;
dic[632000000] = 124804049;
dic[633000000] = 262322489;
dic[634000000] = 920251227;
dic[635000000] = 816929577;
dic[636000000] = 483924582;
dic[637000000] = 151834896;
dic[638000000] = 167087470;
dic[639000000] = 490222511;
dic[640000000] = 903466878;
dic[641000000] = 361583925;
dic[642000000] = 368114731;
dic[643000000] = 339383292;
dic[644000000] = 388728584;
dic[645000000] = 218107212;
dic[646000000] = 249153339;
dic[647000000] = 909458706;
dic[648000000] = 322908524;
dic[649000000] = 202649964;
dic[650000000] = 92255682;
dic[651000000] = 573074791;
dic[652000000] = 15570863;
dic[653000000] = 94331513;
dic[654000000] = 744158074;
dic[655000000] = 196345098;
dic[656000000] = 334326205;
dic[657000000] = 9416035;
dic[658000000] = 98349682;
dic[659000000] = 882121662;
dic[660000000] = 769795511;
dic[661000000] = 231988936;
dic[662000000] = 888146074;
dic[663000000] = 137603545;
dic[664000000] = 582627184;
dic[665000000] = 407518072;
dic[666000000] = 919419361;
dic[667000000] = 909433461;
dic[668000000] = 986708498;
dic[669000000] = 310317874;
dic[670000000] = 373745190;
dic[671000000] = 263645931;
dic[672000000] = 256853930;
dic[673000000] = 876379959;
dic[674000000] = 702823274;
dic[675000000] = 147050765;
dic[676000000] = 308186532;
dic[677000000] = 175504139;
dic[678000000] = 180350107;
dic[679000000] = 797736554;
dic[680000000] = 606241871;
dic[681000000] = 384547635;
dic[682000000] = 273712630;
dic[683000000] = 586444655;
dic[684000000] = 682189174;
dic[685000000] = 666493603;
dic[686000000] = 946867127;
dic[687000000] = 819114541;
dic[688000000] = 502371023;
dic[689000000] = 261970285;
dic[690000000] = 825871994;
dic[691000000] = 126925175;
dic[692000000] = 701506133;
dic[693000000] = 314738056;
dic[694000000] = 341779962;
dic[695000000] = 561011609;
dic[696000000] = 815463367;
dic[697000000] = 46765164;
dic[698000000] = 49187570;
dic[699000000] = 188054995;
dic[700000000] = 957939114;
dic[701000000] = 64814326;
dic[702000000] = 933376898;
dic[703000000] = 329837066;
dic[704000000] = 338121343;
dic[705000000] = 765215899;
dic[706000000] = 869630152;
dic[707000000] = 978119194;
dic[708000000] = 632627667;
dic[709000000] = 975266085;
dic[710000000] = 435887178;
dic[711000000] = 282092463;
dic[712000000] = 129621197;
dic[713000000] = 758245605;
dic[714000000] = 827722926;
dic[715000000] = 201339230;
dic[716000000] = 918513230;
dic[717000000] = 322096036;
dic[718000000] = 547838438;
dic[719000000] = 985546115;
dic[720000000] = 852304035;
dic[721000000] = 593090119;
dic[722000000] = 689189630;
dic[723000000] = 555842733;
dic[724000000] = 567033437;
dic[725000000] = 469928208;
dic[726000000] = 212842957;
dic[727000000] = 117842065;
dic[728000000] = 404149413;
dic[729000000] = 155133422;
dic[730000000] = 663307737;
dic[731000000] = 208761293;
dic[732000000] = 206282795;
dic[733000000] = 717946122;
dic[734000000] = 488906585;
dic[735000000] = 414236650;
dic[736000000] = 280700600;
dic[737000000] = 962670136;
dic[738000000] = 534279149;
dic[739000000] = 214569244;
dic[740000000] = 375297772;
dic[741000000] = 811053196;
dic[742000000] = 922377372;
dic[743000000] = 289594327;
dic[744000000] = 219932130;
dic[745000000] = 211487466;
dic[746000000] = 701050258;
dic[747000000] = 398782410;
dic[748000000] = 863002719;
dic[749000000] = 27236531;
dic[750000000] = 217598709;
dic[751000000] = 375472836;
dic[752000000] = 810551911;
dic[753000000] = 178598958;
dic[754000000] = 247844667;
dic[755000000] = 676526196;
dic[756000000] = 812283640;
dic[757000000] = 863066876;
dic[758000000] = 857241854;
dic[759000000] = 113917835;
dic[760000000] = 624148346;
dic[761000000] = 726089763;
dic[762000000] = 564827277;
dic[763000000] = 826300950;
dic[764000000] = 478982047;
dic[765000000] = 439411911;
dic[766000000] = 454039189;
dic[767000000] = 633292726;
dic[768000000] = 48562889;
dic[769000000] = 802100365;
dic[770000000] = 671734977;
dic[771000000] = 945204804;
dic[772000000] = 508831870;
dic[773000000] = 398781902;
dic[774000000] = 897162044;
dic[775000000] = 644050694;
dic[776000000] = 892168027;
dic[777000000] = 828883117;
dic[778000000] = 277714559;
dic[779000000] = 713448377;
dic[780000000] = 624500515;
dic[781000000] = 590098114;
dic[782000000] = 808691930;
dic[783000000] = 514359662;
dic[784000000] = 895205045;
dic[785000000] = 715264908;
dic[786000000] = 628829100;
dic[787000000] = 484492064;
dic[788000000] = 919717789;
dic[789000000] = 513196123;
dic[790000000] = 748510389;
dic[791000000] = 403652653;
dic[792000000] = 574455974;
dic[793000000] = 77123823;
dic[794000000] = 172096141;
dic[795000000] = 819801784;
dic[796000000] = 581418893;
dic[797000000] = 15655126;
dic[798000000] = 15391652;
dic[799000000] = 875641535;
dic[800000000] = 203191898;
dic[801000000] = 264582598;
dic[802000000] = 880691101;
dic[803000000] = 907800444;
dic[804000000] = 986598821;
dic[805000000] = 340030191;
dic[806000000] = 264688936;
dic[807000000] = 369832433;
dic[808000000] = 785804644;
dic[809000000] = 842065079;
dic[810000000] = 423951674;
dic[811000000] = 663560047;
dic[812000000] = 696623384;
dic[813000000] = 496709826;
dic[814000000] = 161960209;
dic[815000000] = 331910086;
dic[816000000] = 541120825;
dic[817000000] = 951524114;
dic[818000000] = 841656666;
dic[819000000] = 162683802;
dic[820000000] = 629786193;
dic[821000000] = 190395535;
dic[822000000] = 269571439;
dic[823000000] = 832671304;
dic[824000000] = 76770272;
dic[825000000] = 341080135;
dic[826000000] = 421943723;
dic[827000000] = 494210290;
dic[828000000] = 751040886;
dic[829000000] = 317076664;
dic[830000000] = 672850561;
dic[831000000] = 72482816;
dic[832000000] = 493689107;
dic[833000000] = 135625240;
dic[834000000] = 100228913;
dic[835000000] = 684748812;
dic[836000000] = 639655136;
dic[837000000] = 906233141;
dic[838000000] = 929893103;
dic[839000000] = 277813439;
dic[840000000] = 814362881;
dic[841000000] = 562608724;
dic[842000000] = 406024012;
dic[843000000] = 885537778;
dic[844000000] = 10065330;
dic[845000000] = 60625018;
dic[846000000] = 983737173;
dic[847000000] = 60517502;
dic[848000000] = 551060742;
dic[849000000] = 804930491;
dic[850000000] = 823845496;
dic[851000000] = 727416538;
dic[852000000] = 946421040;
dic[853000000] = 678171399;
dic[854000000] = 842203531;
dic[855000000] = 175638827;
dic[856000000] = 894247956;
dic[857000000] = 538609927;
dic[858000000] = 885362182;
dic[859000000] = 946464959;
dic[860000000] = 116667533;
dic[861000000] = 749816133;
dic[862000000] = 241427979;
dic[863000000] = 871117927;
dic[864000000] = 281804989;
dic[865000000] = 163928347;
dic[866000000] = 563796647;
dic[867000000] = 640266394;
dic[868000000] = 774625892;
dic[869000000] = 59342705;
dic[870000000] = 256473217;
dic[871000000] = 674115061;
dic[872000000] = 918860977;
dic[873000000] = 322633051;
dic[874000000] = 753513874;
dic[875000000] = 393556719;
dic[876000000] = 304644842;
dic[877000000] = 767372800;
dic[878000000] = 161362528;
dic[879000000] = 754787150;
dic[880000000] = 627655552;
dic[881000000] = 677395736;
dic[882000000] = 799289297;
dic[883000000] = 846650652;
dic[884000000] = 816701166;
dic[885000000] = 687265514;
dic[886000000] = 787113234;
dic[887000000] = 358757251;
dic[888000000] = 701220427;
dic[889000000] = 607715125;
dic[890000000] = 245795606;
dic[891000000] = 600624983;
dic[892000000] = 10475577;
dic[893000000] = 728620948;
dic[894000000] = 759404319;
dic[895000000] = 36292292;
dic[896000000] = 491466901;
dic[897000000] = 22556579;
dic[898000000] = 114495791;
dic[899000000] = 647630109;
dic[900000000] = 586445753;
dic[901000000] = 482254337;
dic[902000000] = 718623833;
dic[903000000] = 763514207;
dic[904000000] = 66547751;
dic[905000000] = 953634340;
dic[906000000] = 351472920;
dic[907000000] = 308474522;
dic[908000000] = 494166907;
dic[909000000] = 634359666;
dic[910000000] = 172114298;
dic[911000000] = 865440961;
dic[912000000] = 364380585;
dic[913000000] = 921648059;
dic[914000000] = 965683742;
dic[915000000] = 260466949;
dic[916000000] = 117483873;
dic[917000000] = 962540888;
dic[918000000] = 237120480;
dic[919000000] = 620531822;
dic[920000000] = 193781724;
dic[921000000] = 213092254;
dic[922000000] = 107141741;
dic[923000000] = 602742426;
dic[924000000] = 793307102;
dic[925000000] = 756154604;
dic[926000000] = 236455213;
dic[927000000] = 362928234;
dic[928000000] = 14162538;
dic[929000000] = 753042874;
dic[930000000] = 778983779;
dic[931000000] = 25977209;
dic[932000000] = 49389215;
dic[933000000] = 698308420;
dic[934000000] = 859637374;
dic[935000000] = 49031023;
dic[936000000] = 713258160;
dic[937000000] = 737331920;
dic[938000000] = 923333660;
dic[939000000] = 804861409;
dic[940000000] = 83868974;
dic[941000000] = 682873215;
dic[942000000] = 217298111;
dic[943000000] = 883278906;
dic[944000000] = 176966527;
dic[945000000] = 954913;
dic[946000000] = 105359006;
dic[947000000] = 390019735;
dic[948000000] = 10430738;
dic[949000000] = 706334445;
dic[950000000] = 315103615;
dic[951000000] = 567473423;
dic[952000000] = 708233401;
dic[953000000] = 48160594;
dic[954000000] = 946149627;
dic[955000000] = 346966053;
dic[956000000] = 281329488;
dic[957000000] = 462880311;
dic[958000000] = 31503476;
dic[959000000] = 185438078;
dic[960000000] = 965785236;
dic[961000000] = 992656683;
dic[962000000] = 916291845;
dic[963000000] = 881482632;
dic[964000000] = 899946391;
dic[965000000] = 321900901;
dic[966000000] = 512634493;
dic[967000000] = 303338827;
dic[968000000] = 121000338;
dic[969000000] = 967284733;
dic[970000000] = 492741665;
dic[971000000] = 152233223;
dic[972000000] = 165393390;
dic[973000000] = 680128316;
dic[974000000] = 917041303;
dic[975000000] = 532702135;
dic[976000000] = 741626808;
dic[977000000] = 496442755;
dic[978000000] = 536841269;
dic[979000000] = 131384366;
dic[980000000] = 377329025;
dic[981000000] = 301196854;
dic[982000000] = 859917803;
dic[983000000] = 676511002;
dic[984000000] = 373451745;
dic[985000000] = 847645126;
dic[986000000] = 823495900;
dic[987000000] = 576368335;
dic[988000000] = 73146164;
dic[989000000] = 954958912;
dic[990000000] = 847549272;
dic[991000000] = 241289571;
dic[992000000] = 646654592;
dic[993000000] = 216046746;
dic[994000000] = 205951465;
dic[995000000] = 3258987;
dic[996000000] = 780882948;
dic[997000000] = 822439091;
dic[998000000] = 598245292;
dic[999000000] = 869544707;
dic[1000000000] = 698611116;
return dic;
}
public class Reader
{
private static StringReader sr;
public static bool IsDebug = false;
public static string ReadLine()
{
if (IsDebug)
{
if (sr == null)
{
sr = new StringReader(InputText.Trim());
}
return sr.ReadLine();
}
else
{
return Console.ReadLine();
}
}
private static string InputText = @"
636079592
";
}
public static void Main(string[] args)
{
#if DEBUG
Reader.IsDebug = true;
#endif
Program prg = new Program();
prg.Proc();
}
}