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 dic = GetDic(); KeyValuePair 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 GetDic() { Dictionary dic = new Dictionary(); 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(); } }