#include using namespace std; typedef long long ll; typedef vector vi; typedef vector vl; typedef pair pii; typedef pair pll; typedef int _loop_int; #define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i) #define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i) #define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i) #define DEBUG(x) cout<<#x<<": "<>n; if(n >= MOD){ puts("0"); return 0; } if(false){ ll x = 1; FOR(i,1,MOD){ x = x * i % MOD; if(i%(MOD/256)==0){ printf("M[%d] = %lld;\n",i,x); } } }else{ map M; M[0] = 1; M[3906250] = 714469525; M[7812500] = 411278297; M[11718750] = 518244246; M[15625000] = 26078120; M[19531250] = 24466848; M[23437500] = 589240816; M[27343750] = 842272651; M[31250000] = 86516931; M[35156250] = 819748105; M[39062500] = 658463604; M[42968750] = 48006566; M[46875000] = 752391549; M[50781250] = 510863510; M[54687500] = 686384505; M[58593750] = 513692786; M[62500000] = 498440078; M[66406250] = 150354137; M[70312500] = 269174995; M[74218750] = 555861545; M[78125000] = 623685432; M[82031250] = 348958758; M[85937500] = 96141114; M[89843750] = 498679724; M[93750000] = 646617630; M[97656250] = 701779706; M[101562500] = 28291357; M[105468750] = 856945555; M[109375000] = 238082618; M[113281250] = 827665801; M[117187500] = 786430071; M[121093750] = 232018338; M[125000000] = 935080803; M[128906250] = 836252615; M[132812500] = 586228462; M[136718750] = 805287637; M[140625000] = 21945719; M[144531250] = 614220209; M[148437500] = 837801456; M[152343750] = 490027773; M[156250000] = 409109146; M[160156250] = 651216427; M[164062500] = 303124227; M[167968750] = 951221398; M[171875000] = 364701337; M[175781250] = 795538962; M[179687500] = 148350569; M[183593750] = 136724157; M[187500000] = 670821828; M[191406250] = 897990080; M[195312500] = 265505287; M[199218750] = 296668617; M[203125000] = 830131719; M[207031250] = 51439824; M[210937500] = 314385204; M[214843750] = 916351987; M[218750000] = 574749701; M[222656250] = 892699578; M[226562500] = 227183216; M[230468750] = 762745094; M[234375000] = 420234887; M[238281250] = 921779498; M[242187500] = 818166921; M[246093750] = 364513389; M[250000000] = 112390913; M[253906250] = 975334107; M[257812500] = 595648930; M[261718750] = 578268546; M[265625000] = 458508472; M[269531250] = 748449353; M[273437500] = 187805536; M[277343750] = 229089764; M[281250000] = 643455042; M[285156250] = 141290483; M[289062500] = 832095631; M[292968750] = 150755137; M[296875000] = 28936598; M[300781250] = 782206916; M[304687500] = 264667016; M[308593750] = 502122216; M[312500000] = 464643614; M[316406250] = 644173348; M[320312500] = 693083025; M[324218750] = 407897111; M[328125000] = 708326952; M[332031250] = 520689513; M[335937500] = 209978716; M[339843750] = 51238131; M[343750000] = 298641073; M[347656250] = 718646507; M[351562500] = 421728413; M[355468750] = 793551739; M[359375000] = 65645502; M[363281250] = 840794725; M[367187500] = 622424851; M[371093750] = 897030045; M[375000000] = 529726489; M[378906250] = 824961638; M[382812500] = 963908580; M[386718750] = 148560148; M[390625000] = 105776888; M[394531250] = 135442356; M[398437500] = 63401518; M[402343750] = 228259732; M[406250000] = 872682299; M[410156250] = 38741196; M[414062500] = 155811519; M[417968750] = 347546650; M[421875000] = 933295133; M[425781250] = 436450952; M[429687500] = 803256912; M[433593750] = 463511049; M[437500000] = 835720092; M[441406250] = 620338862; M[445312500] = 509312849; M[449218750] = 139766062; M[453125000] = 426286887; M[457031250] = 40872698; M[460937500] = 214310502; M[464843750] = 131967328; M[468750000] = 70371679; M[472656250] = 89439658; M[476562500] = 825326374; M[480468750] = 92753025; M[484375000] = 591062021; M[488281250] = 439887896; M[492187500] = 419061828; M[496093750] = 392568716; M[500000000] = 733333339; M[503906250] = 766632667; M[507812500] = 733878273; M[511718750] = 273687215; M[515625000] = 406828148; M[519531250] = 495141350; M[523437500] = 319527924; M[527343750] = 443395497; M[531250000] = 379850306; M[535156250] = 547227992; M[539062500] = 268500523; M[542968750] = 138016354; M[546875000] = 556596747; M[550781250] = 902620074; M[554687500] = 585393176; M[558593750] = 592401312; M[562500000] = 404533909; M[566406250] = 691479197; M[570312500] = 734297155; M[574218750] = 38654771; M[578125000] = 958501915; M[582031250] = 706116312; M[585937500] = 408885251; M[589843750] = 540983562; M[593750000] = 969021396; M[597656250] = 212851067; M[601562500] = 607605949; M[605468750] = 906543777; M[609375000] = 472325230; M[613281250] = 357247016; M[617187500] = 685303163; M[621093750] = 812801438; M[625000000] = 44135644; M[628906250] = 79659424; M[632812500] = 723971607; M[636718750] = 509131674; M[640625000] = 315385078; M[644531250] = 224877938; M[648437500] = 974901805; M[652343750] = 601198190; M[656250000] = 254834284; M[660156250] = 497082802; M[664062500] = 221704894; M[667968750] = 198421659; M[671875000] = 624015727; M[675781250] = 284596661; M[679687500] = 341245120; M[683593750] = 98451570; M[687500000] = 430345388; M[691406250] = 310121083; M[695312500] = 167380627; M[699218750] = 561947482; M[703125000] = 642821983; M[707031250] = 958216230; M[710937500] = 670006283; M[714843750] = 692662800; M[718750000] = 584987581; M[722656250] = 514902053; M[726562500] = 776683072; M[730468750] = 348401723; M[734375000] = 254009038; M[738281250] = 873361523; M[742187500] = 5052678; M[746093750] = 710599610; M[750000000] = 217598709; M[753906250] = 419344276; M[757812500] = 687914578; M[761718750] = 272383531; M[765625000] = 840892704; M[769531250] = 379279013; M[773437500] = 9687821; M[777343750] = 733935156; M[781250000] = 680778659; M[785156250] = 219395009; M[789062500] = 230368570; M[792968750] = 224253999; M[796875000] = 406075920; M[800781250] = 820372682; M[804687500] = 216155688; M[808593750] = 510283130; M[812500000] = 807827182; M[816406250] = 678976140; M[820312500] = 427874355; M[824218750] = 658469834; M[828125000] = 974657241; M[832031250] = 287150287; M[835937500] = 955461108; M[839843750] = 768960774; M[843750000] = 757452839; M[847656250] = 455030985; M[851562500] = 926551075; M[855468750] = 30413763; M[859375000] = 692179125; M[863281250] = 558246076; M[867187500] = 166326785; M[871093750] = 657332680; M[875000000] = 393556719; M[878906250] = 835525623; M[882812500] = 170012974; M[886718750] = 180181136; M[890625000] = 223796635; M[894531250] = 72032685; M[898437500] = 932982797; M[902343750] = 38863204; M[906250000] = 861932447; M[910156250] = 690607104; M[914062500] = 85853649; M[917968750] = 994010090; M[921875000] = 33723946; M[925781250] = 73062179; M[929687500] = 626632507; M[933593750] = 567110585; M[937500000] = 131731042; M[941406250] = 143630897; M[945312500] = 420165676; M[949218750] = 502721802; M[953125000] = 982197935; M[957031250] = 695722157; M[960937500] = 641538576; M[964843750] = 237181745; M[968750000] = 912934355; M[972656250] = 473889915; M[976562500] = 385222994; M[980468750] = 894124456; M[984375000] = 273780895; M[988281250] = 472901645; M[992187500] = 598653456; M[996093750] = 274108493; M[1000000000] = 698611116; map::iterator it = M.upper_bound(n); it--; int i = it->first; ll v = it->second; while(i < n){ i++; v = v * i % MOD; } printf("%lld\n",v); } return 0; }