#313744 (Nim) No.502 階乗を計算するだけ

提出ソース
結果

問題	No.502 階乗を計算するだけ
ユーザー	むらため
提出日時	2019-01-30 06:16:05
言語	Nim (2.0.2)
結果	WA (最新) AC (最初)
実行時間	-
コード長	40,119 bytes
コンパイル時間	1,888 ms
コンパイル使用メモリ	67,064 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-09-14 03:16:11
合計ジャッジ時間	3,389 ms
ジャッジサーバーID （参考情報）	judge13 / judge15
このコードへのチャレンジ（β）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	1 ms 4,380 KB
testcase_07	AC	1 ms 4,380 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	1 ms 4,380 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	1 ms 4,380 KB
testcase_13	AC	1 ms 4,380 KB
testcase_14	AC	2 ms 4,380 KB
testcase_15	AC	1 ms 4,380 KB
testcase_16	AC	2 ms 4,380 KB
testcase_17	AC	1 ms 4,376 KB
testcase_18	AC	1 ms 4,376 KB
testcase_19	AC	2 ms 4,376 KB
testcase_20	AC	1 ms 4,380 KB
testcase_21	AC	1 ms 4,376 KB
testcase_22	AC	3 ms 4,380 KB
testcase_23	AC	1 ms 4,380 KB
testcase_24	AC	2 ms 4,380 KB
testcase_25	AC	2 ms 4,380 KB
testcase_26	AC	2 ms 4,380 KB
testcase_27	AC	2 ms 4,376 KB
testcase_28	AC	2 ms 4,376 KB
testcase_29	AC	2 ms 4,380 KB
testcase_30	AC	2 ms 4,380 KB
testcase_31	AC	2 ms 4,376 KB
testcase_32	AC	2 ms 4,376 KB
testcase_33	AC	2 ms 4,376 KB
testcase_34	AC	3 ms 4,376 KB
testcase_35	AC	2 ms 4,376 KB
testcase_36	AC	2 ms 4,380 KB
testcase_37	AC	2 ms 4,380 KB
testcase_38	AC	3 ms 4,376 KB
testcase_39	AC	2 ms 4,380 KB
testcase_40	AC	2 ms 4,380 KB
testcase_41	AC	1 ms 4,376 KB
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
const MOD = 1_0000_0000_7
proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}
proc scan(): int =
  while true:
    let k = getchar_unlocked()
    if k < '0': return
    result = 10 * result + k.ord - '0'.ord
# 先に計算すれば間に合う
if false:
  var ans = 1
  for i in 1..MOD:
    ans = (ans * i) mod MOD
    if i mod 250000 == 0 : stdout.write ans,","

const cache = [1,50180518,154425679,419049924,641102369,364780107,448516387,313981369,578095319,86051964,119948046,6473915,5832229,280841874,929795683,915960706,259081142,680500135,59433257,777579921,974067448,443699470,261465122,603788888,316220877,971390710,663134272,881294189,690120224,31722990,304661605,707692373,251368199,963306784,704262886,579475748,980250487,734818225,386267146,100884205,682498929,133000963,681184885,254932760,134623568,357323104,427907847,975779652,95936601,919157566,140928835,315458993,933097914,776765946,391177708,545976183,167332441,513852415,739650465,753653734,598816162,731423907,292015879,593871940,336060741,207290943,810640932,955078514,248744620,641859244,892704918,315949401,626497524,107592271,118508240,734189521,288843364,696506364,406755567,475021638,491101308,660970291,668723114,154792097,245341950,399096325,560364972,33884628,565768255,300395832,913230882,560677262,246899319,707244298,756627904,657076885,968999,69887676,7998896,192791675,586350670,769890636,328019447,800219212,638587686,931841936,497857012,655344665,881746146,840019426,526658674,612357186,19426633,553937377,560607302,807333916,850500036,880872897,916364742,810805566,76479948,322985309,732041432,174482879,268124147,86516931,30473806,914380037,842267748,398602165,878381584,680656982,886294336,909101450,73995168,580824852,485348706,122117390,771153434,264030845,463847391,968395514,72518508,576302511,544075857,901200113,264638935,152184821,898187927,796504086,468116664,790455369,798967520,965695346,359622660,448291975,82926604,611143741,59761470,903969875,723816384,685474055,320608814,662323964,156530778,584805623,278224088,543834126,721996174,738626268,222176885,243683233,299085602,286707267,814440466,541988189,323604647,533682664,359932651,601233044,172827403,152460596,213590923,33229645,398699886,91389423,983975503,303301488,530389102,73104194,619965361,374924406,294587621,222036968,221896631,480109897,813805606,120043214,676243000,473715194,67347853,391673277,557470122,974946838,497478507,689208753,494243939,581484231,196447201,50157541,726686688,817437629,722054885,293079212,435396042,404508102,228338256,222897920,574429123,926809891,407719831,758320845,583676448,82985148,762479457,415304400,342545697,427418645,746536789,828621886,3669475,949026022,811667359,145285614,249780014,631030761,778773518,442531044,306921081,242462872,27368307,77771567,467386519,4370529,438371670,995836327,44635470,827994736,59469516,28160617,498440078,25984366,5974669,824164565,9221150,855559028,766196482,958335419,679975009,667185460,606322308,9559926,147307265,89921971,86609485,739691207,435993596,608829799,889750731,353853362,607649469,481928480,340941507,977029829,886844916,534028979,371263376,983879272,198057134,300726763,625544428,476241984,527225600,339579929,788878910,401616424,743572663,986102459,808412394,818701791,603835511,513189131,996952918,868842432,409420559,163232029,585237443,711783886,307534126,581374971,1669644,79259751,210601394,908609880,361786913,893046012,470618701,839717177,480748381,749016143,550969600,197931559,595143852,997893857,901560583,985470745,837229828,394853292,727223125,80778437,199888908,897424081,180269718,288483853,526807168,204998281,899715096,147218753,579691190,249046858,775147177,337926751,145404005,681418236,401312408,424113478,459188207,732957544,552930818,232777869,534491822,416625292,669251006,48075339,439729802,718791818,504703143,192610639,840398449,453095025,624903360,229348550,899297830,656687365,556957390,518355602,235861787,849506324,850796519,171990028,888050723,761457408,834568419,471765488,656116726,668120697,196710441,812015902,736550105,330330359,857549983,190137617,440902696,316132690,63145422,646617630,85990869,660571898,807209645,523043590,884343068,406752816,132114154,39076031,56305184,162501223,973762120,522647499,973478770,593853757,270603374,435947909,168891766,561523336,217608725,67114373,804805577,449084887,641317239,125126440,927880474,251289824,157803266,765558904,876297919,180495840,189324843,640767445,934814019,239309967,374934947,791217839,676405347,705889788,30657162,591992125,567277637,324526871,686637388,156725044,112249297,982528783,631678522,545644885,44930135,456099497,954976637,73036821,39417871,325644102,977168136,720288971,47401357,288148411,809639670,285927540,108819476,519477996,250361638,878780790,281863274,402597124,410799320,511989267,60168088,681009252,142840220,937233252,692636218,292413264,261319829,485726626,432775082,541754926,200805416,311504863,14235602,63335394,616435469,84287295,770511792,96895351,174624465,633454181,400295761,167446553,580310773,744878746,697066277,178528305,102309489,314411152,421835306,676782859,228266417,783864754,220108638,166858810,334251014,261544848,661224977,851013614,812005526,665917774,261799937,495178170,356438399,981467959,168203998,393977287,835330203,882285670,802214249,167565851,316146626,825930120,544064410,533800842,877125482,450607735,935080803,168503996,576478595,62912270,583967898,34071782,885117574,713158620,211768084,315395810,672118586,939316799,751231582,479341187,192990501,837281502,972424306,244644804,125666214,522618190,623534362,633456379,362493992,106410541,335160196,422499436,924982465,657769953,243276029,846044660,85322142,334528202,554749550,632297821,437447268,194789090,60050552,135925402,733942454,866577339,797848181,28171985,643938537,21282665,395891998,231013739,435508211,494663390,172428290,410243078,422713438,411403698,159554990,335001889,812391270,604125905,887420150,668082332,449205554,377054744,970055531,969968376,222343461,415570957,250388809,217712473,689850274,760739075,487998999,884457327,748359168,329883103,856259313,572557213,29781141,601327885,82104855,861553992,543656809,677599921,232253360,758934169,132581614,976001516,513365505,321373540,443711760,719653575,244109365,90546446,956163585,405020688,1559745,915310808,193109503,812886618,695345956,568939003,36042990,235609235,261384175,768691593,953585846,386455793,849009131,659065850,600281990,825918223,323214113,80831393,762863177,858635499,747664143,210306859,388430024,25622409,444090941,87926617,396611787,546936010,659224434,324526942,991836842,83467123,80729842,409109146,231753353,641290181,570033864,905913526,24300293,747854366,664989237,57375259,653829979,473372076,827348878,439147086,7704403,815156180,195888993,907760783,30813167,961838486,576798521,348380456,947304403,20999669,457882808,867003058,137550654,815829567,731551699,546621827,995246811,782564184,212938473,898497340,593989303,331620540,509096183,79318301,478919708,139609452,827544702,852527478,602197504,864783272,678320208,975254490,496537397,197346690,677711203,252191884,386677716,241051648,289752035,863428057,456967785,708251942,66404266,932229123,208554578,45119221,555972231,157658774,680796549,949023861,195290384,966054139,364911332,546764650,97136305,604368046,294375015,272880393,349551356,845424929,290196031,428059156,785113347,96985836,297880214,23235359,83489485,754222558,644670437,527942477,66247239,110851843,135500451,445331645,52167191,633799488,498572695,973699797,307390891,364846814,499606972,76286067,547665832,795548462,932668364,590807733,143066173,632128211,499761057,186300854,350016754,288480859,113905458,709755487,917404120,606670553,493905303,102838342,296269301,353144768,86726457,811888735,996122673,798173587,809339058,193180428,23015220,55861328,835803486,44899292,602139210,37610337,670821828,611816110,748566338,411293772,631823487,565520310,187348575,940303862,382748764,237554637,109838563,15091364,94904185,780977954,574053420,392208799,973865472,274399323,105574531,163760155,752194712,127281208,304173654,363104769,83284607,258610236,542432219,808205344,536973025,450988908,34538816,503777150,283727326,256983152,325636655,81442440,243291133,67947043,437843114,645366082,312536013,558022461,630621321,389538807,682680116,722670891,26853683,278654022,611209607,558817540,933245637,629940486,894820080,809376987,616368450,871418457,198631047,829549992,238971581,352487536,595959409,672398528,511371690,267098585,683585700,647902320,557301633,589386102,253427558,525116697,911398531,20284688,246476028,596636467,848952161,140580859,272634280,650776749,958992544,843194652,325284740,731179455,925152039,118437170,495860053,451556823,914456118,788508590,841108662,450677610,724691727,292911692,445713321,50697395,636817583,734002852,814845293,36295352,238087006,954446221,170238260,30646237,946237212,230801891,457433989,271686306,910291942,763604371,599284582,5335057,114985663,532934543,17739814,19912403,492237273,629150786,194710256,342244474,450387329,391570698,471822076,948232111,834860913,785993517,831422618,574749701,763017204,133314423,100582220,226847592,368925948,541510595,128260642,942789776,475812562,882136272,917840849,641494632,740594930,972553616,51595198,252144386,45060610,568320974,994271859,90970078,806047532,844782619,476604857,257358749,464456846,976794640,835245756,168194948,172115341,804157813,545338291,599598784,75307702,202730650,344053349,945626457,116261993,700228825,945918607,869726861,562519302,306551674,281653965,856213472,268838846,459136580,635794655,27784049,173784895,195823038,258300540,900411980,243624360,582688934,722807834,617913920,61570384,534263309,691306302,667796618,481661251,926951316,752609613,431760716,938269070,179206505,381369130,381881589,95182730,966530892,885113729,173657240,91068149,588337788,758827428,271865096,115435332,610160522,617737077,114135134,495022305,492342417,641462345,306192390,136026497,267464078,537165746,279269277,506496856,174970822,997042337,90514504,710729672,579006599,185163716,682921198,113570024,146968038,90871114,168401529,366384665,439086433,783454081,674470294,564758715,46898789,75276833,472326685,270239666,395559459,203381481,419744205,277118392,7188448,639320111,759485230,79874094,468710311,366910724,103414281,702807165,281297120,582981397,381725460,112390913,156492285,245293699,729422905,730341625,773141422,338718815,97158395,103056890,875857662,1840485,343213463,677948390,297735574,391004385,737700456,339464594,96544119,145153314,860570333,167240465,74390429,455408691,244668811,108312174,396616574,155105232,771683822,839079953,385456615,605298160,927359747,479334442,702962709,540479427,267762479,271788964,212339018,587614008,63666996,135498044,781772889,861409420,835801021,277717575,400629971,938160268,979782104,591048681,455215137,115579849,737471837,811637561,817145156,629027151,248249832,353339603,639625455,463734842,510402229,889410460,312462646,481429323,965800223,839849206,152903258,296744952,72253743,192345193,970717824,181445064,467121659,736265527,368455044,30430299,396328969,316439118,575162392,844263530,57185601,217544623,464215765,366151601,57828926,788132977,693531911,82871673,276473015,618898635,574689359,693326853,754346899,183011467,349250965,60732294,504593092,380858207,18113296,421458551,660639183,996097969,181740107,207173800,751843095,898554793,303227882,970529845,606286881,335353644,485523580,761545908,763321144,54062950,600987925,385459037,185004499,611251733,345339647,825396690,247939378,419363534,628748445,560597174,752518020,965429853,643455042,105595573,424892642,160398980,783180043,207103817,650632666,151319402,92385023,964295934,434988033,990918946,26564924,850425472,10981017,607730875,173261653,799102651,332158901,450718279,75983084,522004028,907007969,173539388,815008397,39280804,549292472,648991369,445107198,226831444,906280520,970937898,912066462,341918865,861275443,500780548,270273864,177947455,951474053,780122909,999689912,211496717,46150432,39052406,528785595,368878414,319272200,276894233,131599333,276398021,252626758,460373282,887411171,920539895,250031809,651081062,273580685,211855474,382695448,461415770,92037551,853050198,608097530,358700839,658062542,628370214,701180054,643638805,597477354,202808666,950035054,560006119,595629812,186304556,777723800,668123525,549006222,583546391,101505544,686692315,686455742,102543936,348192750,673464765,554637634,397417003,360068751,957633609,928189430,290432801,802114087,199866123,84031138,265595990,42373810,563432246,269064424,785424741,829787075,841799766,373395898,650453047,974382613,385330357,288926821,503167666,630690705,504962686,418193550,352181130,65598198,954061253,255352545,209208323,268154825,128487469,88740503,839054128,697952502,685707545,64735192,922908862,673294371,299172297,700634351,464643614,121294519,717975101,615385448,424067031,859578405,577786541,261968121,61051402,168036384,318951960,784024352,359014876,368791906,773206631,849864532,831641758,642519652,306832604,511251965,59719938,26351537,204355779,517507962,767173825,484120991,573592106,689705001,383865684,560006077,30977140,856866029,760404254,681084363,450398100,327925913,177740910,611192355,363172638,545114584,354990705,485051702,258379324,334158390,74773587,956671090,472935553,622288553,861711207,123889992,93940075,75819676,645018357,862359850,587220627,49131878,82698356,736010283,776264326,304956416,977544813,487108846,793270300,511918488,788636352,957041224,291733496,10717142,55908790,359357227,522049725,23157292,662927596,980166568,579995261,914360545,766145844,337932245,335416359,703381557,851663162,937689383,142946099,777472742,244577950,736666250,472012302,188817398,989345508,64125479,559947225,118585278,118167528,176012367,332139472,194856362,840577550,827185666,499377092,806053828,915199651,519827597,464599136,546457796,585779428,28005289,164752359,64866657,61316420,392711312,309058615,102560024,615081450,836944364,86117128,882577502,241930728,400766332,580204973,55295957,790715390,405956327,563781682,128445971,461178318,298641073,954840109,777013595,435208217,656755310,624577416,634861021,226031891,82745517,895609896,409062999,462654883,333627931,888287558,262144765,660966455,22096102,836813268,792900494,269404558,50835004,926036911,924996982,670433353,243869444,386027524,597639870,204891068,902590285,184419613,505790549,520697215,474430451,724205533,976309799,894659709,758670815,403351886,330493114,726465115,167487184,715247054,922182249,737530798,422453091,716986954,348078468,943314229,21995092,830567832,186987976,534311010,726178560,383388563,813935745,398145141,126925831,68409439,709975950,266372070,973405188,6734065,988931221,251832060,888173888,189239124,781940697,344955776,880553380,68322490,423691274,623974296,978280935,943653305,851264493,697868489,897594464,405755338,8179625,665567790,927743985,811056092,369338822,833885272,496199986,179518046,939687659,844330145,527489278,825132993,799664596,656058147,809505297,343807435,2827835,868431947,340515688,985084650,139614173,575345122,127487658,868553027,58318116,942820142,247860407,148528617,946870992,633107927,35954298,160684257,120166368,961130399,565310565,882148737,228859128,848419420,688083912,591915968,210216822,615889822,780334053,701445829,465596398,545393547,104653021,529726489,144345463,480474681,936910823,302177126,989016154,270945720,512233057,974886682,909477026,488043087,154954575,241107368,783480311,740529892,778849197,798830099,644967278,819011249,424891680,940567523,160664454,876883097,329853148,11633075,541298538,293918195,299929674,325334066,591794484,337883503,84159401,346091869,921012832,51918298,566893129,115312728,454612480,119960294,684622122,473718967,292819094,743143063,406278443,218129285,781034202,926604003,506761150,878471898,773033829,524012393,795791806,180002392,751537106,715754,88166180,699739374,882641788,389016352,842593397,917084264,415911041,465386262,791787792,856859395,291654785,301620109,850176909,435327356,622828826,514251437,501105113,808651347,451059310,801370191,469440779,421623838,531057483,382922882,513049899,105419548,287343485,127456989,612899951,59883031,971839530,114166180,762268297,322487421,678396642,900904073,900364431,79716267,353442556,786066682,126560226,715317963,686146929,683150470,45365306,429277690,708166323,64740307,3484986,398078032,293926937,711401317,995439502,316486674,544257806,52757021,124863480,384843585,884700803,849418710,705409965,940338439,415576459,509520746,347282247,937409008,992696257,102624539,600200925,940524812,872682299,787687576,731881871,947549662,364196979,668564391,229334261,833550543,545504068,822407919,856956061,593524514,877327319,192210898,980344495,996164327,964207235,961867068,434012492,987314628,286430541,967411361,780595857,697611981,969047646,394996809,34672910,636177449,323744863,72168208,374786137,274192146,287472693,338788555,113323151,418537348,742559831,463708507,69008941,925347821,719644259,458367886,27763917,952831975,646388990,15393104,909214594,893732627,735213121,987575845,898028459,1277567,223248648,230566735,665333924,358655417,223197712,123947564,930759285,141866945,842098649,844163282,374795557,581830879,537439701,446827670,935741093,987597705,852235665,698430079,407816563,347046911,151905639,651947420,240892916,775305697,492008437,317604388,845163950,125354499,308887195,110831147,967725028,951540811,832662735,952124856,845162620,247662371,785880192,57339735,576679412,343043237,872180421,770497428,379863199,568392357,476950237,330540451,260929681,997474832,185692768,684274016,716946797,209244402,315395096,711263223,49390359,380480118,243118678,152615685,759199434,149586983,900793615,338740524,995747272,392838702,910032594,86684635,955972829,309134554,845568911,210200531,155663520,990779998,285326836,835720092,345577925,263053337,408703678,530748609,497144475,325362513,510483254,228060468,878195412,780072518,17172937,542860209,948969391,551028176,904864746,635027430,141792616,990826116,176937330,982142330,863774214,989944961,749274500,935582860,568293758,155569943,15681808,991755346,831058399,596737944,194068667,25397869,895257338,711553356,641663134,512486787,786465403,268844715,820872480,112916884,522558396,451373308,376000899,944100328,741445356,379404150,209267503,440154068,571164311,462639908,316069410,669000996,401973416,961812918,531236497,346462698,502666603,654611901,136802920,301178006,150416637,382776490,55375312,211395011,422051547,41815820,871852494,183468905,222665263,843321396,62920475,401648188,173838973,675258797,890536564,133581040,903661822,845583555,341196632,836420358,646836329,934281721,640140324,86418476,831112129,741114145,220487467,94141511,316386753,275105629,979797482,390946091,559432452,666247477,966503421,458436231,396240783,325912072,534810677,928715741,214235012,526131620,788809194,530236183,865388360,252551589,689309663,503759878,536133947,432030917,677830799,620192986,309402088,554917439,750984570,762826007,145805953,818036959,81443984,601095260,41179328,754363835,458536137,821331296,70371679,795190182,773892397,739181445,407722696,909210595,577028140,599067303,418444423,278704903,62993661,903915339,259072478,719566487,556335261,571901643,670199338,628514947,270981826,651386309,90279196,424989675,681992385,942214416,185681382,321685608,130556133,250239248,240820183,50590510,971807975,287162360,771773244,832069712,296532211,172844240,604055008,198768464,894636965,329937332,991921977,702004730,720914685,805897219,516388424,99199382,158987836,195756808,778775932,707469729,885756033,310916425,670767006,747407118,351493841,795864732,913233036,302020341,119640479,385010048,36845914,497196934,349980699,515746342,597954988,5003231,982508563,905975384,153520256,726997875,865823506,226911103,107356392,382617671,521947854,907257761,793284363,296229203,154085699,176691201,318596296,183888367,56749561,430569820,602757844,703397904,324673458,662960264,132121543,552133875,523366740,594030230,639546130,732868367,209466039,138744932,8988146,350095207,749620993,303170656,531576301,26031303,515158909,963071930,492695794,863250534,780437548,212666452,575216934,216665960,638556474,757888960,177684386,561745549,562296933,894162271,812475180,352946234,580035475,269943732,184110313,784139777,763098123,389730744,329325894,733333339,880022333,504457401,218497700,503105966,616431012,814692089,103728644,459878625,737550606,100166031,109030261,803187381,850296900,84186594,679420228,16634739,503893633,625504439,933782733,180898306,757778713,815851993,74501572,68718097,201382580,521750002,762252768,985594252,839800502,804272708,512439938,404206040,103475955,625602963,285113911,749724532,529301141,904212599,178132320,97830135,766268183,927950630,592652662,611751357,137238973,336128288,845919569,31131935,865644603,493898122,299277870,662741752,515476884,174140647,164492104,864326453,751136030,214750670,43701181,864869025,8887214,682983341,435060431,167831173,25604695,361169784,848139022,559214642,816554584,316571311,446465693,718498895,918502589,129884877,18640795,91352335,311782156,262054502,963775207,608823837,837833331,30341256,517258417,473379392,366327994,86738528,255729768,385388084,392405824,85051770,54276784,152267158,161185571,883676662,378084701,681756977,33883485,914781910,682883599,46819124,502392006,499828799,46917827,313132653,245193338,300653641,12075963,56547945,603678770,652279266,545875253,442795120,982609115,841355804,131639745,796616594,647409797,186372829,306980454,256141983,485445052,284655550,169597670,152028387,379850306,2518954,31181614,636578562,505653433,665181047,831021896,385377759,404687511,115557610,458459110,553033642,587498064,707031841,979834383,491415383,758063496,267732098,908178229,919273670,256434523,771891931,552471386,996049638,663866346,204194403,694757059,326686486,173643971,524269810,2248257,160150665,444690706,18364502,384810005,141827977,810647416,541689171,900740408,540818053,810402559,444923677,949493953,693305776,503058099,895259210,375967121,593938674,161454270,261432589,649856271,186576440,992074918,525216705,530065902,688809790,929706952,957610877,111794298,565456578,236073918,981362547,58735152,749296077,390533216,246808791,259513659,519397500,729013272,633032196,30284937,551096742,149403717,997104085,362551229,696628828,535204787,473521307,927742823,775025061,626473195,274750982,545251906,370732451,434042870,684205655,464031225,164246193,882721043,919530230,32662554,915265013,680768945,925117963,394623417,457469634,888387042,591773508,702969354,923043932,609091666,579491909,143798661,912368644,46998687,657283032,595858865,777901604,481276117,580108890,22361807,464118005,203547549,619229549,483558744,637939935,599005133,875658633,193870331,956856710,298802,390856783,726314250,490676632,299422881,404533909,435121890,453019482,603917664,191649870,150553457,462528877,698933272,13751809,486715188,502297454,776548167,629218582,133071834,798895521,924905215,623841561,573562278,100498586,621266591,77511478,618032574,699767918,877833437,416820652,161898173,849974789,902379873,741447563,798504599,811575797,479758433,747107591,499010965,438952959,201569596,248233087,931771067,606870929,196769088,32074225,891063982,907720182,619098899,999821136,428300314,179111720,143331121,778287926,278397454,48053248,31526202,966053837,787560730,508038818,626235187,433786890,94861131,811944661,830945967,631265590,87780527,752550134,721855051,739608890,572025679,401382061,623774744,623047959,697726795,848924691,957422361,730897743,247450929,764368449,745025896,605025034,608462543,34629406,416058816,894517500,139436117,529840945,278458947,112657644,298190159,435904287,372256709,997813035,601486951,26011548,291022920,56222592,97351796,208184231,772929863,198012676,767534240,446477394,859801172,672903454,975341439,206330671,94465568,181069006,614184554,366033520,740391117,504590032,494367785,131772368,267618556,213456517,302086918,185646898,928205658,713536809,715330554,648711554,850059166,187129040,469712035,472759660,502848626,446982306,969021396,523696723,656468842,306339620,286635747,271198437,423288002,284132069,954000323,25058942,495453104,971058102,537377458,859369491,443690710,255041381,196713118,817928963,508204070,136849970,45695706,330711333,666341116,742765041,843088355,724464507,809267734,730186918,11080649,437605233,463987622,864978329,838929133,701453022,731076258,133269512,421036348,626663115,582977276,11085731,83851975,281230685,390122869,141658162,421426349,510650790,355948203,527887355,873058725,596949867,345997577,731147272,264084667,295726547,503240185,613729514,601174554,303076380,851791356,514155754,121194194,465070856,800063145,415213535,965919023,272814771,184686454,684096122,632193883,538771609,730991627,579671055,420200867,48824684,665227492,972590066,931112114,951279549,725694913,217176278,345817436,939889684,574205882,957342287,384889445,564188856,592279840,469432979,694843199,48527183,21902144,119648328,44795822,201307702,802254172,264639326,903528535,484458461,669489248,337340034,441033713,861754542,413891559,974596348,841027029,326159309,390199216,774336224,497146072,181594759,924931589,287297719,248257271,668422905,38845386,860780776,512802592,286273596,516618289,467363131,913603004,965656187,126529811,570457971,138675908,44135644,636627889,938561592,851896887,359960756,176151938,255726848,894598068,936229527,410308322,586418403,220030439,407934361,317333782,577750062,146416748,267193060,662652196,110628267,935649923,456152084,60946382,748372491,293662192,459116722,659735093,496690748,950266352,124804049,126560238,778806615,438286538,262322489,907002100,471005141,129372756,920251227,970961239,881907746,895793744,816929577,476444551,71346633,887255104,483924582,100185513,885773623,143605973,151834896,361590882,697422579,807615657,167087470,267901776,348461966,711693305,490222511,680740402,271101205,401755350,903466878,715272319,695845167,295084907,361583925,258259781,139849160,325806930,368114731,443530581,611223434,833080932,339383292,872311829,240693388,46955186,388728584,32574568,787495569,391193596,218107212,599308635,647286378,307984829,249153339,932961293,301439625,586792543,909458706,91708783,825527586,50301975,322908524,78590841,713473839,843123325,202649964,664498313,316700583,316918770,92255682,127372587,619301661,329387504,573074791,824317170,265672103,561692362,15570863,251174519,330425149,586180318,94331513,649900422,80303342,696956978,744158074,791892722,714604162,722445437,196345098,534352784,956948468,857979370,334326205,254834284,656410044,127044863,9416035,458110400,98875930,119649397,98349682,16884564,249359071,176785272,882121662,92640308,609122097,999848032,769795511,193161253,27204169,237046881,231988936,511571733,341541162,842346391,888146074,354841505,563593105,849312843,137603545,930679925,597887794,412615826,582627184,57117083,173167319,362484731,407518072,14215092,525248491,635619282,919419361,264611701,34084880,852918398,909433461,393375325,459822212,345031724,986708498,340913095,578423178,271252437,310317874,87583783,688545487,866590795,373745190,776987068,426767514,278552186,263645931,538628231,33023513,922701788,256853930,140789737,216838327,640988873,876379959,95507008,681776798,876322324,702823274,123882694,152276951,59374455,147050765,233410503,552142680,35704301,308186532,301215741,892943080,434299900,175504139,940023660,531982651,690607561,180350107,345442939,853751105,822184689,797736554,604822277,911931389,232362648,606241871,718337842,734505544,245141211,384547635,263075911,205897697,323047155,273712630,89453695,295898944,583133449,586444655,558697741,298511537,290216431,682189174,96990023,391491433,343716916,666493603,464758241,769644373,201607244,946867127,756277394,779729071,972999959,819114541,674569332,430345388,896027796,502371023,314857121,565093850,557328233,261970285,482510647,73676677,360538408,825871994,50282375,439985219,848800658,126925175,182750707,537175030,694924737,701506133,270786053,922419422,363612940,314738056,979368575,331629774,609036071,341779962,880783035,993829303,536334772,561011609,402903958,310187903,183115127,815463367,875798648,419922946,683932582,46765164,433478033,153796383,132454834,49187570,922226681,978824517,383337126,188054995,718482843,229507993,700976123,957939114,682286838,976365496,805214934,64814326,373842324,34962064,155766116,933376898,187332912,639423687,637495943,329837066,182348131,938220928,405582552,338121343,926098094,723473543,146566000,765215899,131922689,374248877,438738934,869630152,470257565,825793239,320300717,978119194,184896757,712565751,758462453,632627667,295578365,996588391,145731547,975266085,364036671,10259433,272998870,435887178,323977958,310651169,121069149,282092463,531278823,235000767,577576413,129621197,25546644,131119231,514619865,758245605,694061362,122477672,677013842,827722926,886870220,104141028,532227478,201339230,727451710,632232583,195965817,918513230,473514925,9760876,116358524,322096036,694366495,661083628,685332237,547838438,677677736,278005187,584987581,985546115,693648786,462757650,118194477,852304035,218286248,747700707,456194172,593090119,296710496,31738433,342936417,689189630,469446997,302579083,444073731,555842733,886385642,407991608,379151892,567033437,317981504,883930382,954089026,469928208,20212688,933753541,975683488,212842957,481292014,952917862,414912172,117842065,28097196,636059822,178897316,404149413,822758467,5021656,61518602,155133422,742486361,396892116,115857733,663307737,575453013,252202515,853930475,208761293,499864031,556478432,625653444,206282795,27880608,438269075,346492037,717946122,869524540,308402114,369103748,488906585,980182828,58731649,869661127,414236650,804613839,138477462,873260580,280700600,81734900,829290435,459219589,962670136,178172249,691030367,72329014,534279149,537833730,534216193,794712949,214569244,36268977,306753329,394287348,375297772,463532789,506050984,263462485,811053196,792786455,768114732,421060593,922377372,205115006,685756954,595274897,289594327,518383122,77516399,73888244,219932130,751394698,423659297,383271365,211487466,377514463,88929658,746386624,701050258,309611110,207594892,330355869,398782410,640856244,311095371,24744781,863002719,670288657,558395120,255040696,27236531,931168051,653991930,353239467,217598709,781020811,6140104,972113519,375472836,849594910,227970396,31410247,810551911,757615675,759994826,516032510,178598958,377031550,212759058,9686973,247844667,999846916,738789531,86543232,676526196,879111625,935116236,119739860,812283640,848427753,270258531,565862182,863066876,705496924,523449284,801513025,857241854,418500955,244920548,387092719,113917835,21877268,285558056,97284372,624148346,682784756,217519213,561654530,726089763,352824826,288577505,891889167,564827277,832629099,182270197,483658324,826300950,646326336,154134669,534700971,478982047,183049692,992035084,503430216,439411911,219303738,781040881,156134325,454039189,142729429,173642567,668241128,633292726,858489537,181058575,104993372,48562889,527138624,316466042,124587966,802100365,876320124,528654390,858364998,671734977,858133285,588427118,49376708,945204804,726732838,617419803,974144226,508831870,677809471,923976569,156518337,398781902,99323099,345695843,816670686,897162044,471843395,488776232,369094329,644050694,330811245,522005226,973416962,892168027,191125092,663939743,193605173,828883117,830802454,636309857,402982516,277714559,159824027,22220478,49663121,713448377,210889515,862322982,571277611,624500515,407103715,670822030,365482665,590098114,680778659,282104097,753616208,808691930,423902795,671075979,300932787,514359662,206759980,161646605,434335908,895205045,549714378,18763728,153438911,715264908,899235151,171766217,192342724,628829100,334114105,727088567,359891374,484492064,908311531,847440256,548560882,919717789,208899363,118695128,679467158,513196123,45414561,1927054,42959761,748510389,348918148,604018013,843674138,403652653,273385515,900440408,632605096,574455974,821021955,135656153,880890811,77123823,526993194,195346599,56502013,172096141,676901075,796894379,81604980,819801784,373985666,102159868,259431090,581418893,78286032,26773666,206868336,15655126,476723349,961808256,851072785,15391652,408633673,340290036,35315014,875641535,719520121,25732221,241832128,203191898,473267301,762975242,420952629,264582598,371324086,186922308,355774622,880691101,557084915,828454217,24253373,907800444,689821082,342392035,736853549,986598821,535525460,200084575,149804464,340030191,768081306,556841547,186211491,264688936,428518660,275811253,679462627,369832433,929312595,444094748,947276770,785804644,808828689,277341268,374979150,842065079,760675071,898092098,914050434,423951674,628367003,207638534,561666414,663560047,847729387,230631176,918279883,696623384,677643926,807827182,838631314,496709826,824643649,879400608,268508478,161960209,118455504,865140964,638916884,331910086,595056675,603116309,914846095,541120825,194421372,574610474,924349532,951524114,552366416,962158915,717746026,841656666,644421061,662109025,66170345,162683802,287729735,60582516,452150624,629786193,372818418,883014120,135244193,190395535,460530089,472550413,758814521,269571439,548497019,468747428,742578942,832671304,196050185,125435851,6781185,76770272,232148410,470689842,741672203,341080135,620476493,207220566,951129936,421943723,936839332,324979737,51494655,494210290,713382609,604177687,795746563,751040886,498345007,95589267,846819151,317076664,452510575,717683969,205274111,672850561,783750968,988189352,450234257,72482816,971472181,161579561,491714430,493689107,360330010,388537544,582518116,135625240,854083379,555187833,347560883,100228913,66186191,728822117,985137704,684748812,734776265,576796201,401326141,639655136,796209722,266200149,503714909,906233141,878024868,85157309,105377683,929893103,195199702,133047646,120745161,277813439,371372528,9837620,432877198,814362881,368379357,380021947,581522681,562608724,989285272,213027699,50796761,406024012,909228903,315587760,994881682,885537778,911172977,925665844,757452839,10065330,370208025,107125810,3580132,60625018,344012987,376366561,807646193,983737173,493893741,253250904,575576511,60517502,409506874,466459786,65622391,551060742,77506095,139998669,857431457,804930491,157228580,592347496,711156492,823845496,419227352,765555389,984977683,727416538,46584186,590444719,2501513,946421040,856874250,717927112,387898276,678171399,956616948,86811998,489873285,842203531,988327543,371706626,890758947,175638827,925067613,408502422,11678054,894247956,368924610,831246288,350900559,538609927,385235011,782723657,164882083,885362182,925942919,831257253,553912269,946464959,199414022,453770195,782119525,116667533,629989348,982647665,842242752,749816133,490671428,712106516,78737356,241427979,482765383,710965692,975094049,871117927,221820501,378998132,134829676,281804989,536113355,603830959,739829205,163928347,136513878,644386154,878420651,563796647,542148001,274795785,472528188,640266394,516352236,107234102,998521225,774625892,599384668,791185412,558910407,59342705,617013273,97826191,293805419,256473217,514374724,590213099,867596433,674115061,848719823,703665287,830317963,918860977,373481767,8947163,890867014,322633051,191299885,192270447,697655701,753513874,694996968,294830834,459908543,393556719,970585862,25181126,760054479,304644842,873279068,234845827,204376198,767372800,771150004,553063981,315969637,161362528,710636564,749473336,247325286,754787150,824758462,58596576,839990536,627655552,912441135,159512462,448500279,677395736,931122474,846532820,913221154,799289297,355619107,354655649,60539447,846650652,51274689,978805070,203405153,816701166,998236923,315419580,613463418,687265514,875185877,833548006,646487702,787113234,554878994,97846412,527523396,358757251,221457585,226478218,840254556,701220427,488072551,567481117,449946621,607715125,716622769,90197399,877666937,245795606,515785806,962901304,839471675,600624983,71973421,242901954,724924078,10475577,344060712,650859047,446205244,728620948,966778414,435811032,970873983,759404319,144525537,573183959,729080802,36292292,729120659,183555163,73699158,491466901,67697554,447239215,828875694,22556579,971344891,873791394,697681175,114495791,481946740,197736875,876537140,647630109,234472331,485056460,898731557,586445753,548287183,190508668,602630219,482254337,646752647,322924180,428138881,718623833,15068830,116698549,312363755,763514207,684084869,810987160,277786757,66547751,626294224,300695571,958655399,953634340,880602425,324833924,688128659,351472920,861932447,384343273,415039162,308474522,373631176,20450004,569050859,494166907,415503144,85288039,547092626,634359666,539009721,397059212,840027487,172114298,201311372,198532616,747683336,865440961,655271342,3739182,146797889,364380585,303429350,990631624,39924750,921648059,141635885,903288230,72955529,965683742,871905742,374214450,116291970,260466949,154402093,112429098,728655283,117483873,241732798,281744795,209020476,962540888,345412932,642772349,91231061,237120480,741050360,504371008,861763291,620531822,300590108,563045796,932725389,193781724,947174007,695511574,538073920,213092254,353479328,782794242,828991388,107141741,609843843,662565976,12912536,602742426,937988698,857268414,72744602,793307102,950442238,919116765,152628797,756154604,504041378,443183564,396891083,236455213,302278108,626871594,103848028,362928234,140309569,938420738,213659695,14162538,575687769,801639277,444280792,753042874,616861022,723950758,50516153,778983779,837944632,672909594,547174121,25977209,722798197,323582350,885292639,49389215,776263424,254189314,611939143,698308420,483538711,181353334,59867597,859637374,303580516,801413581,463605137,49031023,384590208,709178470,570179364,713258160,257013268,410465453,889588353,737331920,175295865,131731042,593621397,923333660,470174298,601117743,22452361,804861409,490376355,327520749,38855237,83868974,148882603,260831555,618730947,682873215,553990723,937240859,596073754,217298111,395336950,659873007,18025576,883278906,788047493,366761197,663477084,176966527,144817333,110744650,724190111,954913,997271782,246965865,615769726,105359006,482858165,338471174,41442781,390019735,371027602,549660657,966410761,10430738,199841489,58007504,384029152,706334445,21905318,864696066,304787447,315103615,243608321,465054749,427738793,567473423,987541329,85292764,773918648,708233401,310071740,426786760,10015863,48160594,152922550,142441517,742843324,946149627,777188493,394265229,100206080,346966053,153650145,71050762,21945704,281329488,708954705,246955022,141203116,462880311,86073587,253486451,947585477,31503476,89564621,411673788,637772581,185438078,120790929,521591989,182578852,965785236,998492024,16651371,815104059,992656683,429962264,545638190,279864100,916291845,201601450,65591903,348671498,881482632,38459482,957757479,132384442,899946391,983226396,84428155,459565762,321900901,895310341,674721611,82386031,512634493,244851135,970053019,267715957,303338827,628232723,860842034,580915649,121000338,87276158,87654126,912934355,967284733,561438135,580938783,16702713,492741665,60154389,671517513,983550467,152233223,799829882,335102896,56859637,165393390,209582914,160150497,847526451,680128316,854476671,685723887,556328448,917041303,758337414,782192657,117871095,532702135,175289715,56081734,44529952,741626808,551426320,642939667,647693437,496442755,594597941,867195255,552272388,536841269,910558979,412622873,113175090,131384366,983776383,994065976,260276116,377329025,120671803,974508445,503334842,301196854,748347356,574480664,827155024,859917803,438877561,20211256,46268671,676511002,733823944,437157360,188284405,373451745,115749503,83118246,702144005,847645126,435308472,268761837,935072263,823495900,896878185,459628134,116910205,576368335,509039064,494290402,282151037,73146164,953270692,98016105,763638412,954958912,130224147,486828649,579036716,847549272,536884008,201882845,930801429,241289571,34140074,420567331,522704662,646654592,716556217,788599446,964261108,216046746,657890333,682599498,78982470,205951465,36722836,383521365,907252430,3258987,172424584,433576760,787672534,780882948,504605118,510148825,230771225,822439091,681956393,128900492,328152609,598245292,478087198,606924610,524378352,869544707,963814773,933768689,657395111,698611116,]
let n = scan()
if n >= MOD : quit "0" ,0
else:
  var ans = cache[n div 250000]
  for i in (1+((n div 250000)*250000))..n:
    ans = ans * i
    if ans > MOD : ans = ans mod MOD
  echo ans
yukicoder

結果

テストケース

ソースコード
