#821909 (C90) No.2141 Enumeratest

提出ソース

結果

問題	No.2141 Enumeratest
ユーザー	tails
提出日時	2022-12-02 23:02:12
言語	C90 (gcc 11.4.0)
結果	AC
実行時間	1 ms / 2,000 ms
コード長	60,723 bytes
コンパイル時間	977 ms
コンパイル使用メモリ	27,520 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-10-10 01:30:53
合計ジャッジ時間	1,909 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	0 ms 5,248 KB
testcase_04	AC	0 ms 5,248 KB
testcase_05	AC	0 ms 5,248 KB
testcase_06	AC	0 ms 5,248 KB
testcase_07	AC	1 ms 5,248 KB
testcase_08	AC	0 ms 5,248 KB
testcase_09	AC	1 ms 5,248 KB
testcase_10	AC	0 ms 5,248 KB
testcase_11	AC	1 ms 5,248 KB
testcase_12	AC	1 ms 5,248 KB
testcase_13	AC	1 ms 5,248 KB
testcase_14	AC	0 ms 5,248 KB
testcase_15	AC	1 ms 5,248 KB
testcase_16	AC	0 ms 5,248 KB
testcase_17	AC	0 ms 5,248 KB
testcase_18	AC	1 ms 5,248 KB
testcase_19	AC	0 ms 5,248 KB
testcase_20	AC	1 ms 5,248 KB
testcase_21	AC	0 ms 5,248 KB
testcase_22	AC	0 ms 5,248 KB
testcase_23	AC	1 ms 5,248 KB
testcase_24	AC	1 ms 5,248 KB
testcase_25	AC	0 ms 5,248 KB
testcase_26	AC	1 ms 5,248 KB
testcase_27	AC	1 ms 5,248 KB
testcase_28	AC	1 ms 5,248 KB
testcase_29	AC	0 ms 5,248 KB
testcase_30	AC	1 ms 5,248 KB
testcase_31	AC	1 ms 5,248 KB
testcase_32	AC	1 ms 5,248 KB
testcase_33	AC	1 ms 5,248 KB
testcase_34	AC	1 ms 5,248 KB
testcase_35	AC	1 ms 5,248 KB
testcase_36	AC	0 ms 5,248 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.c:11:7: warning: type defaults to ‘int’ in declaration of ‘tbl’ [-Wimplicit-int]
   11 | const tbl[]={1,998183600,738130753,329123348,664569192,404685826,636609227,867546745,63750749,424306193,412914257,864891325,325103287,168381519,406785193,582054051,785955203,152777872,381292153,600175941,726619450,656441378,317595073,883289975,194494561,284904384,34734868,420873231,296603224,331300395,803944518,689524625,526215428,433549714,811703700,141662225,570411301,253378389,971974931,832913914,676020518,420698188,697722899,197313116,149595226,616791413,453092391,704615552,457336628,163407552,565386092,441842280,281453020,373711892,741344969,952280583,296995053,304975811,749850910,819775236,455453640,577202107,385758279,798892272,252219955,100710769,585207765,432242971,643534673,641956402,527019786,716317644,302508614,603909217,185866325,552758548,188398043,655001584,26011477,966644560,767996071,860470582,861310332,703764560,624333062,199166762,702584752,667931441,460310675,247918565,681244341,248684467,600201741,928617014,189812063,768802442,443267457,681313716,657100611,981176765,915944106,734536118,971662331,983867489,124357400,96036405,872551226,680280659,160490153,775940878,716032788,215661137,740084590,635691211,274940348,315381707,258066996,728560905,464933791,820492060,87896728,779968592,744321583,249815302,580535184,839791509,615825587,188342103,197756513,354737984,673925095,849373447,8642490,69350321,49980647,215573095,458705539,149439844,400540463,693878161,337853080,334094208,20745397,364722935,935436571,717519452,409489976,588214711,399670390,169223342,305891557,325973151,894204841,322918478,265119994,46925024,406799272,730851103,14158234,623840175,859830510,816148100,924887623,249085458,76987333,686515322,776729451,975092562,115923013,958271728,933041686,160513131,855340974,609810174,988100842,581078991,9065496,609424259,843693933,103506550,972561196,868183926,668606179,529474423,793999543,87127386,933689860,501393022,619796067,560999880,753579386

ソースコード

raw source code

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#define rd() ({long _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define wt(v) ({unsigned _z=v;do*--wp=_z%10+48;while(_z/=10);})
#define MD 998244353
#define FAC_D 166

typedef unsigned long ulong;

const tbl[]={1,998183600,738130753,329123348,664569192,404685826,636609227,867546745,63750749,424306193,412914257,864891325,325103287,168381519,406785193,582054051,785955203,152777872,381292153,600175941,726619450,656441378,317595073,883289975,194494561,284904384,34734868,420873231,296603224,331300395,803944518,689524625,526215428,433549714,811703700,141662225,570411301,253378389,971974931,832913914,676020518,420698188,697722899,197313116,149595226,616791413,453092391,704615552,457336628,163407552,565386092,441842280,281453020,373711892,741344969,952280583,296995053,304975811,749850910,819775236,455453640,577202107,385758279,798892272,252219955,100710769,585207765,432242971,643534673,641956402,527019786,716317644,302508614,603909217,185866325,552758548,188398043,655001584,26011477,966644560,767996071,860470582,861310332,703764560,624333062,199166762,702584752,667931441,460310675,247918565,681244341,248684467,600201741,928617014,189812063,768802442,443267457,681313716,657100611,981176765,915944106,734536118,971662331,983867489,124357400,96036405,872551226,680280659,160490153,775940878,716032788,215661137,740084590,635691211,274940348,315381707,258066996,728560905,464933791,820492060,87896728,779968592,744321583,249815302,580535184,839791509,615825587,188342103,197756513,354737984,673925095,849373447,8642490,69350321,49980647,215573095,458705539,149439844,400540463,693878161,337853080,334094208,20745397,364722935,935436571,717519452,409489976,588214711,399670390,169223342,305891557,325973151,894204841,322918478,265119994,46925024,406799272,730851103,14158234,623840175,859830510,816148100,924887623,249085458,76987333,686515322,776729451,975092562,115923013,958271728,933041686,160513131,855340974,609810174,988100842,581078991,9065496,609424259,843693933,103506550,972561196,868183926,668606179,529474423,793999543,87127386,933689860,501393022,619796067,560999880,753579386,371292523,697493119,504954175,247587476,461152617,215859929,230361643,413267547,284756171,872262626,518707686,216227468,278572907,126259528,94620594,650453126,682035449,485944850,93689169,568293359,434743600,638426297,420337610,853741763,233092317,286360311,943836744,436266176,792995492,619665756,349959696,347086150,116816852,753535692,589594379,83802085,662361407,818684014,302500336,886767614,811109895,649446609,291397639,938206071,833799517,466420763,773902760,786358241,846221461,865054865,615404034,534687702,43682966,845503881,436905135,665835809,424472775,889915857,477219872,65505425,280220184,293814878,551789472,160246760,214653113,395546350,171353785,992948531,421315557,571929447,946364017,876915207,406653540,283424569,962108570,751264714,815923958,502859673,672279561,218022698,821035483,845112279,165407167,364828071,438492725,521308620,189605012,402875801,956275019,623502040,713554724,140891150,25679172,625606005,845102504,819721226,463684201,862300086,446724251,471092693,835149584,598942192,932668051,489892679,589878052,836801162,407203905,530222172,314358460,341629239,724267660,307791044,634863948,955939248,672437617,731789841,467343305,368377659,829341136,100886704,645519032,347234575,776450700,138404831,213128418,377382111,368766704,677993545,727552649,892873128,487579535,726115903,190091995,958213632,362049020,189910270,543911977,618327408,368331279,963316503,10569467,139134448,820539708,763343663,658472346,318954083,757256345,216484450,692710634,392739738,615630854,542765384,398036577,251958132,994062870,275263045,119583324,596551117,397829537,416329632,61319126,362786843,500414383,527871683,379841295,508799684,975088468,396727088,616690321,562022731,473674348,380717285,346573004,442062078,264706931,926621721,365667348,193803778,940331141,640190823,979302044,162431361,849229274,647790378,439304886,82356944,658545742,814782804,15968160,409540367,711828282,903259344,38698675,587776631,231269159,191452342,387893788,368628771,858172496,633314771,758070088,450079265,238400342,473654205,973940008,426670415,879933236,643740392,51664906,640467778,82152407,793058255,552632694,77282518,58345113,745547477,393755818,464533431,603050847,226117167,744940832,429348566,6990490,85987728,790206635,172833072,592554226,255838947,531945362,976795246,923833068,966861464,777962051,806421589,641728048,478656656,914931297,466137771,936887473,74276459,19602089,13166080,188623192,179668527,727260125,495170225,238973586,457125238,208581,39175262,19287302,339655211,928930155,38926268,437312903,759744010,534601076,106056475,413590446,391639507,888850414,934639241,476866735,388817935,554178008,334660299,443040644,703991583,379661063,834367525,965307561,517349131,933205472,464322154,888134496,532996354,958417888,878940288,568342981,100878494,741147356,446986733,516259243,936002956,34831475,976342490,353775318,276406757,303557571,133100202,733851105,564418584,58728687,521050034,955265831,491955340,914679421,268228754,801889735,609264563,451985779,486846951,887447885,902820648,420386662,976786526,821500424,198435396,392189890,357777890,103681521,316141466,741363372,834718028,726000491,521994983,441465175,879908242,440701185,530002450,45267342,113328955,537460046,191737950,573473236,976565168,315967310,555344855,204863194,904103995,500957184,475377942,424805073,395165816,587687918,523188887,183194468,401705940,612905278,126588447,350105151,674973952,893607132,601881242,607682358,888556049,178927111,8200229,497136198,70320929,617315725,748334389,747472597,807155300,691658386,867414268,759395968,956722214,491947301,755313957,448361421,854299188,234635108,901125114,831988448,929310537,360907960,385945257,463533712,646947412,703896827,775590905,839890500,379366311,616830753,480803737,147748398,887721879,796870030,380183457,995330822,219999253,245318083,936781657,640982534,130342298,797626286,880345036,73427596,285036797,618054983,952275656,988724365,494443084,447390107,514906121,862323972,969755092,754447673,50601419,751341166,942998720,846967127,923994704,396236402,971171212,83227720,977842579,681997824,318901400,589823698,384832422,825337843,432394641,647833574,570183906,140844599,749208142,678562214,358358344,791605221,958295271,918220189,369913682,829939389,644574931,796078297,993130039,338769793,531490251,126741833,907780594,376300443,946830158,436853959,207767229,185886021,827060307,507413320,137811299,34431831,69953688,685061656,877121384,541142776,747354078,814877286,790818239,906720577,413933258,177588314,865439928,560692971,667164992,230333688,497424292,47447632,860847795,824965405,19584191,449128572,868784982,147372346,816551489,765417527,836632382,460119204,773276421,407325919,827484784,79607379,313223398,17583190,582103751,928057394,632263949,282831260,560973001,859438521,796200580,702401392,219108753,681929021,545399129,74985603,433676922,736055793,821216384,455509878,208393329,354311714,440309504,931318865,321237926,671274328,163828112,517890995,530496339,729300696,906472554,857942229,205288679,388864146,524310100,783377989,516182426,130554309,983565429,122136201,617203649,447151563,118186475,763701030,553877235,365053800,648656091,263249624,713204670,123891626,887337321,623588037,48371527,759094812,482049976,948910818,615566865,969798650,944564033,874621889,356580497,366451371,555904611,226717447,714588859,552423672,354667041,443281154,459072850,975084155,392266595,878735607,594464463,791936191,953129233,597902234,608378897,915945175,31872332,895717351,326234120,460292569,384286427,207388247,742031887,388383992,59112116,501988048,87495469,491441768,239554076,561673235,755839368,567640296,639753175,94934029,181567708,302978346,16548167,887863184,963738209,345510877,453064659,225346103,724043782,575819201,545644591,969182477,525113773,182059704,708781487,423603333,921009977,778756726,593149900,877827985,142040297,613746495,67100290,428484389,152501876,333823310,932684174,273507688,490047985,790882897,288066663,285967836,603140176,80058539,727243955,671451991,332576509,266637784,982220950,329652984,426245351,971985329,647383643,786594806,573682848,760162458,799185152,319845225,372743832,520399425,66821945,695718702,790708508,664855268,706460381,595544074,165723487,897241474,162314743,331518206,513271759,280547125,471401945,763476086,946979334,585181048,114691204,144550555,769761761,981365157,794199837,900083705,480666622,574772923,957392870,406558223,320208571,16039003,730083310,994644318,636121545,66599718,741510356,177292308,890819913,193782809,807703833,40600638,309231516,81082624,270548575,260104266,860225997,27446107,729129056,593025478,62603908,966830500,798574453,88377615,517669141,470871503,683687630,96258490,136782622,956784997,471106837,580099526,44449756,98532953,745427620,656470659,92381005,380322939,537826345,111054802,161129129,954559070,860278010,964421160,956207634,971460443,581092314,643619493,285528990,187745784,282514583,52904190,184257601,826365003,790750246,929548667,839828866,191225546,499188464,213384209,422062915,340239367,794852488,183152035,78941441,153251856,448274742,808254943,640372827,588532329,361697470,808692178,750832999,264437537,341743284,228209071,309607850,487343044,560566770,825187061,771754991,545578757,965844149,903969521,414396196,332951439,314791033,969669808,778883719,363641611,113769575,539649703,498330912,526598419,104015990,821422320,890457799,489571546,156024273,154396862,445149312,657636028,362331459,529817058,227719238,971094589,27208659,448046785,803542035,621106063,210491385,925555673,426175006,271358940,755648052,202122959,571270525,307299964,461958636,493511117,348666928,767295880,781835746,67778740,93841769,748059790,280637457,330567809,777534208,299580064,710315172,648157957,214141251,504710796,602546201,341851325,540117883,112552997,768181674,362143117,26058902,995461123,513549416,719585461,400199904,122182946,673117903,302646915,746268270,549139239,233912834,982134552,548658467,409577414,746601267,810916801,132382159,28078201,683178457,381519106,807432198,807686771,300324664,320245814,324139664,901688502,895854233,833724707,736907116,867257200,498542971,26122821,569565684,510590404,157273542,759213474,796192544,632173622,270746327,809598122,50416063,245978620,510800819,435403100,67254310,409981871,687253934,767924472,561528520,606929401,977639303,298867171,754588014,744980719,35948751,864041905,823435887,84126809,734761283,285807245,540363294,216412219,268701954,238205763,861996223,324194799,503743782,112279621,312652294,247154183,349130728,329871238,626635674,162920658,926223741,653005607,975459768,882837589,759532894,412069764,4995791,549715628,695590118,710796547,259237535,632507261,146599073,797702500,807961108,625876964,506749777,854871908,815738245,725043430,904489392,211619122,778219528,894353983,549893912,39625613,763458512,673047300,568952468,729895952,857188818,281670962,844321488,33325731,847588438,300321376,355992017,342727628,96277374,610020409,786306074,360165161,678091909,187504992,943559649,765090850,399251154,10474843,455510796,593452245,847679669,970526957,346898852,154320026,806908844,338261629,286613017,665436535,930295944,198456641,743885081,391994060,111686891,88908546,905516023,117587456,416339127,381370220,230773833,892941430,270489077,532852517,501096501,67316478,976121342,831490830,119244444,629725062,53614740,70615722,362248671,354683289,764139368,42094878,179670775,216021200,378651735,653401763,826482550,980437575,483243168,945602810,751043862,718886128,342442137,155673172,883308971,139633587,118054408,452354327,557050248,334702757,605760508,612853029,34930767,843528466,399406497,42175584,377780125,140150008,585914551,754433289,844185930,849046659,697853432,296118618,284923149,647599874,968238506,731018845,271180238,128797536,290548384,995275554,445257293,730232421,974888908,233869729,825661423,581093987,794763494,523447315,350258820,550939874,16040586,107786219,691048770,176920598,423112784,893072329,192041732,180495369,225517576,269438452,634036872,606264697,160403074,497088962,810591866,638668261,820097447,596290906,768586350,220756883,450598077,360926919,863182423,443414183,438926566,620557331,181471577,980309565,722547788,239140968,133165349,473508627,159503167,479110909,134336189,431169293,967872085,721577480,602360094,414740678,741150558,54753569,300927002,659265559,498650275,949396195,186154795,831224672,866082075,158926473,760716381,707444656,297497690,915268270,87789403,958155833,368475453,51033033,410063373,5871975,634526136,874540933,783641991,825818159,997527203,170148059,222827534,129104532,111748513,629157819,822613896,862941557,621264876,600964092,28128416,61701821,251558130,508510087,444483234,305078996,697554825,327106973,102107389,409444804,203735800,667866292,4057090,483463916,799860045,220804389,95856009,401818406,468929254,759993360,287131975,11257026,552326029,701798416,68812693,243954867,652462879,784421913,23182437,549732359,8557363,942729029,488715085,593128203,321925406,920610857,703029696,368060283,404875261,186440713,276783558,907711100,166996859,997803224,824610132,561566170,915986934,2766833,21857009,115536431,700739927,498473181,576921990,692367641,27704971,720692643,120805044,238354155,802070681,543849750,810703287,831769872,161179000,327931726,270841830,964867977,942564446,683359183,269391022,334133940,559648308,342395810,44860821,82334683,150143439,1977062,700352355,223666513,484434655,719740084,156723890,588458334,874339877,592696823,373850127,940433956,589566011,103319507,610615404,382074927,17816488,50609901,21234851,89840072,455879228,137266507,357864472,911712751,823033137,816129656,85567975,308221687,821766945,827004760,599666974,350350731,121200685,237956252,27439499,173171803,482375628,708050349,716104560,420922091,171521228,720666051,144747657,127205962,665877762,335405381,712424646,481791431,669989185,617305476,521783048,175481871,22806527,460051770,274586180,412607925,541949462,583924214,163015402,611721924,719092256,605104260,223319984,642859743,254148975,831870013,396777580,573684243,571685913,851612303,28249948,930885215,648729682,490445457,867630398,199804744,786184390,589057208,705988489,913277652,992165243,831929017,193179733,610668730,264467127,608920485,613055020,458076793,682092592,956662873,775775985,104099418,476362190,905752805,65121161,688825875,802065245,190119173,490885567,757503217,665109347,546895111,298039260,44437366,961469049,413726803,986642433,897429740,822862357,858185357,219681113,601332523,575409371,574284844,792536285,892710893,420882231,196720199,386140938,752639039,762018575,479378300,433931156,643205421,663929459,369711350,337059144,176968827,725123389,339813386,22530600,879619651,59941342,990201954,309355431,191332670,796800739,738520879,297474662,729560304,916725419,700714175,201854119,13254428,394125188,527394980,484502815,643429232,798371563,780070396,214811791,593784078,247036873,17993166,691339416,660430120,128555950,792213208,562424708,36944855,821658971,140295197,337690005,401707904,85455920,406527099,634746599,381259771,381443825,973481955,760152602,796783570,25967732,835930748,305922128,43645230,154310156,555350257,391432098,774070751,698937498,412908918,280608491,918682089,15413858,848622881,534902589,218450130,628444617,343907585,355856891,65286810,200135397,301735700,361374578,221104366,928962829,979960264,664136722,139890039,472369514,666717807,662922325,204274162,641013478,79709480,420099785,50423810,552058576,292077647,742240459,168475750,605341563,614344659,733655817,893558042,389211233,474489423,192382220,938603503,344736591,78513112,188432495,840177661,537464521,200255465,975471911,902287484,494354253,771634849,507253066,887287494,859131187,176112950,307843846,925835578,779280990,536237652,337301236,465068851,140632356,488894133,958298678,991147164,307789952,507724685,168761024,913889842,723686248,781465211,345948216,283745623,686472994,226341703,251644711,718871491,29920727,3725833,686553064,225673297,900970710,613726410,802824265,1115581,301495303,301181222,405183833,737087769,835382115,945490987,420369081,396316431,47140072,797236070,244243151,122791098,619137288,966440012,439381856,77417742,13463301,308838395,736537324,660164420,104829030,207670699,575086632,811967982,884839614,406474144,592703061,347034990,716610121,743832217,376279279,770717360,964847778,375942100,771400250,616350758,179557684,787117913,538511851,951808623,684750347,798492509,924193995,793893302,733462638,25326776,424581998,635212758,945660321,798216566,534254285,874748021,547999846,906352911,736848306,701409053,382177886,791902017,330777547,660268706,64246296,57048759,507566686,898220060,885151474,833885620,573012457,997464418,390046674,393313169,902785798,650212465,534675304,333783591,298273057,689637945,49832578,183083856,398124851,480761468,419316235,811370772,518222322,791460244,270251482,106223731,248624513,521226097,307098658,279285484,12035496,380788802,935885384,17923417,243879838,168003836,520377790,285383573,519770143,34817698,730908933,969584736,464476359,389158330,632085715,879328912,190946561,124471038,899126996,823103624,518149581,875822555,220504926,2999255,129472706,760940314,656471044,780297114,790771837,348211203,376379542,145772283,379796132,433028774,731943580,371159358,392742018,574998977,582919257,957483555,360800969,332474118,63562452,62330354,475652375,241104158,808227955,358903048,878848043,154301941,966889544,442901601,30691715,43846166,187981821,393311700,268438482,423190927,833128270,174660768,949366379,890349368,786138671,613320359,190056526,270866042,986940798,762899184,564976246,623084131,375338478,114571672,225058827,98245374,790297326,104444242,748349719,353812603,364423277,244771139,86572147,395268069,685601643,520642547,472096346,903249728,538765897,547982603,633990535,149984058,664620462,154921795,366625789,621126468,669972601,113890194,526054678,591418,704504317,754653753,110916321,922330442,920713987,804806056,524153318,968440404,924128740,267833703,240986539,255902610,357415986,597070518,69685338,528620881,418746985,287927446,341923741,66580918,56038923,618066245,203787141,40586475,76520254,983014044,610632166,511942486,828197628,371934835,326819223,512522189,498561741,543121129,899566048,778878345,786458413,788761811,934531580,14599110,476305409,302694447,719591684,369277080,967374881,448881425,370942336,669515929,222663649,660530211,197459963,80504222,748403368,115556,213688986,151472475,539834447,341204457,153270287,852178048,22096336,898466157,37964142,820291127,454434629,392422738,60843094,773923376,62048002,391619128,358583149,785831575,46330289,146981719,510172535,197588757,742871156,680058038,162483680,727650197,358319301,407473209,898485851,608277478,188218693,361291561,366887299,433743194,343371884,744387861,788888524,774458692,528779869,151566233,886095511,546707687,867348581,555269997,66826093,326556133,823333590,16906768,611495251,728951246,90750359,212195569,250317542,559467915,41604150,898816374,835661197,232092547,299888058,108086594,422264534,815538525,605807211,501645352,899682450,722417963,115438978,663745220,191319743,11072508,686290852,354570539,57526211,625607192,678269159,19092975,345164249,783165009,410847335,849851997,557957032,153880795,809368175,51551862,397720557,965009526,208901934,872881337,336680819,113861766,572442310,696019524,243042885,708113092,436495646,286034624,550343456,478905296,324697655,302641830,49301692,126680424,888006069,452638403,370786842,619644440,938384174,704961251,511129292,353173754,323450092,542642589,266362305,990377769,369919903,288030090,989714416,343860907,862431600,96991139,358841541,508744340,175778599,741110723,585871397,184074825,826036189,666111324,754497298,4566621,993614624,886444746,860280617,882155755,508838839,743751884,867360014,746929304,594709036,161600331,633526498,898095287,621834849,535201570,449996930,426655243,145255829,910843752,175227126,770066830,321838923,540475559,699945170,810752958,541804723,418116823,90074210,632601425,915951703,93854854,718468063,553033117,257691914,40944658,163564801,977741689,410467403,823679642,955696441,411549901,121071084,442077105,675903557,791665527,141709791,442998998,865404436,977876441,83834556,397135637,729785968,813817790,117680595,216159496,484875134,356571915,699063995,68015574,80711350,995319987,948008379,57907015,829797698,608535127,920910966,598770832,360893740,812658921,653893481,580383240,301607578,358874571,266656126,765740802,924195036,417894925,322765946,579476231,179713322,60710937,240003294,254806081,491140594,410305606,404661208,727647550,798546172,222882511,619768482,491182985,973760202,571923074,524840845,644180001,729675114,529247742,255603651,24034990,125463418,662316620,45524691,549279762,127619003,827811019,867339886,575617118,693478348,581442854,800848781,438139956,742052115,868258854,899859763,15102002,403414632,336224246,19454315,728529985,852068087,699471969,355466179,20798747,442898112,430493452,484227795,254849732,684587383,36177602,51462242,682522302,763846780,536965499,511725889,748373310,973435315,10439634,129486137,400144407,515887172,414382978,101510966,422998033,49781684,979572318,373925452,460067794,442667924,435850564,577498213,810034903,86996161,610151643,769709258,122081009,300936523,266119216,228855792,772611949,841873159,54959830,993371520,647862270,299073157,909527795,448557463,704940924,578562898,249799904,965040006,247657509,475741258,671623260,518052698,954585874,785707991,337011325,589523934,702199974,393626617,613388098,803849071,590355641,714417591,821730663,443616225,823692071,922106734,753587976,860171431,601309445,539520744,186378296,842493055,957024336,249800687,119764511,842009054,764177610,920174676,206108086,875667281,932374459,687025129,938861607,69114985,144373835,935898033,528464130,470015852,178103790,751885497,549743474,453968443,512073617,431406349,744799407,512718764,722660321,329355598,236784316,120560335,67897704,869347595,88232437,130132874,11055106,525665993,813628908,794959808,308793178,969846442,639095600,721821875,301857570,270288578,564174296,689717047,922279697,350178303,878592520,921076968,713792943,175364171,510008204,74991774,746021255,228196379,588633138,826264099,926467986,179015072,47795244,30859970,898082806,290381021,597473593,725047060,166094800,749051591,119172741,295310814,960691005,96722953,220532407,738102670,345460551,952009219,633160721,849014521,313848138,808059492,5320140,562383297,395109410,366737034,915095589,955857462,394902357,781186514,131667762,662421722,946581904,399690344,818775403,796311566,484048393,758346454,112235126,870685881,580478214,632281867,425761671,307536447,609912866,828832093,740936567,292177666,102215651,624599427,930223875,4252359,822908157,81839705,802159134,287011063,929955456,285394246,102441620,346762442,336208499,223201780,468855755,330430337,651846290,873080580,114382306,942518225,822595465,667615060,828983454,423014584,21493687,221738793,879929913,632194216,207274350,268654051,234672029,345697916,873840512,876327232,207988193,62931981,180576657,453970585,210289548,627900870,405921192,989056160,199496490,433130866,116901359,728058672,124465186,753900878,730652264,88304109,345704963,297829720,904804786,419016795,682912647,406171906,405918528,93197388,779985488,77281075,884087975,684564505,168068352,331379985,716621072,300389222,458923739,956947152,214220518,208412682,330215085,617287356,752569055,149051990,390387274,567543770,620641950,833459604,299047141,733941662,105315079,512759545,824431865,286322800,139990544,39646717,806075042,830591568,206333719,135566396,989047710,952476130,775578281,823964768,785001791,125939895,315110690,715392849,785702,468054927,782642611,849536714,405911442,896265159,176024976,744861451,932538237,599489160,856908618,917864345,972414800,375882393,346697193,799055119,803033117,734291272,915413593,740408577,22377234,575520887,229680724,896543082,100998754,977811245,513572160,719775247,387643285,495537383,578371286,198901820,362912211,841680276,355810856,921597841,873904679,938724278,27606216,991051733,833412845,351827305,227311068,195874515,328953991,858921076,42873504,803185367,914484162,562276567,405264807,841314386,656607824,453709771,400901896,394735501,79538288,258325822,33792791,368833487,512240191,225369840,246550457,7235167,559596994,625373923,425104692,868864951,363341549,324842353,650160088,45061002,578697251,84115809,477209436,531576394,789339143,56381863,793343672,843404993,161191209,405933808,690389192,314688146,405193119,672575429,68331542,972262313,355555994,617236149,540971299,161041105,915572137,644713805,613096667,321155239,954513396,728498500,896439236,993164408,741100454,201650923,25513520,469824267,388878580,272557183,892287671,874909248,427993607,101888583,392882646,712814968,540793602,155067051,451681476,626612618,690550473,100819776,53745512,99069874,825113328,637892286,861360698,194643807,208656392,134817804,505673448,316278882,561406202,90156836,646530720,23440840,630461081,454217150,388737075,227766782,548362155,423262606,543193983,253121350,309820495,158297458,145604862,41459699,901726050,462939497,926962436,356531752,416391654,655987717,299972082,721836717,474124646,422469771,954389334,661737509,553586982,929963602,435019965,831392146,632416331,513201951,985868949,68501210,584039223,747728272,566331231,628173249,605124230,425565467,629399728,31836247,31309788,648150131,408691752,788858815,819918951,626972215,761152807,844271597,867722466,635583733,599291232,879970071,490051574,654668259,844603832,137686342,586291300,876641347,885016523,616873364,835084505,186534984,511611723,524729251,408796016,454860373,655294294,669253523,722445977,745479287,440423484,511555506,996432863,660081919,59583021,813946319,855705583,959255561,822105469,154615352,440787483,918355208,224353221,763051723,799193251,736188520,490870416,830142780,538784045,777132036,1136437,313550037,631388470,326266119,330958556,325519379,330450575,19271763,839632816,737340982,218922121,341858600,980070179,225297287,466506583,242282898,813786296,57808834,897385377,271215688,913988928,818174370,163400023,711080482,28410358,380839733,824615602,187757044,572822307,913227790,423074616,678374665,918389781,839677711,641073302,214478411,235769499,284638271,936349868,750835333,680908868,144693483,37394453,308872708,9508654,411833289,61531496,447757447,725114569,380104970,879313188,53366734,428589360,92786421,981645285,178535238,313829588,760394241,269655278,413989806,766119748,906948888,878826736,567715724,360699697,842505077,107779219,179811805,789888267,220289545,721579757,19758101,874331053,61299189,140085570,432790588,843843338,855827583,136937417,57924927,236654993,81052796,124037171,669266193,502220236,953576951,785011298,185575712,115857113,397268360,715693360,643625062,46151936,93786952,273631334,641891080,461444719,459847683,328796352,319907811,620406927,78738530,54431474,252572335,126675951,704271581,365007062,792715699,85347850,850806623,96457626,100731526,146190515,146719703,905044267,236164924,48998459,737428126,38782039,178995467,603989319,372641990,640910380,451468709,573118245,553311455,745877026,696206144,111290772,622685700,723611949,513680019,774924327,291761711,919913020,191418703,74194746,777855613,637312,146471305,401483993,141005749,578768867,394909802,207762082,378314055,12828572,569275692,841003698,397530157,814902116,501725144,64838941,670274478,671584544,207137368,475491759,181102568,62846371,136599598,616586627,662417751,602682987,658988781,520978997,621663425,735722710,618454997,684753657,637650165,788303705,735329337,775207483,711237248,854893314,811756975,964502163,289568434,18744951,134367265,108264149,922993111,920470471,283735186,922444384,372127393,94202758,306713956,326348748,633399951,133752127,303936357,567847513,722424336,530981476,971301014,40308965,557412184,549735839,886962880,15716846,945703935,434082900,546611948,389819565,195079071,899780606,252249995,588123049,981750251,466185018,293816425,222108455,343549660,451281267,544611378,194381308,435861399,758009601,745525006,324067956,378312125,506252166,817524164,603325670,495850969,195939842,257703757,18064700,411282560,287532578,334771331,644084699,736368638,862049887,319077025,888138152,607067585,978805015,941471777,521038541,211266182,898085358,602432177,72351664,988735356,300833234,576095651,307394554,859716522,881864735,317399388,166139024,27577740,366659253,21845327,759130032,993940832,406259268,175238032,753175622,870371235,939806105,246046513,404442621,742479482,793061151,485823382,487215374,570167532,823172838,77001499,716332950,691590935,939291497,455831486,122305653,948196297,928739167,530196548,460377108,278648391,101224649,830458875,611801718,803453650,908549349,179571351,212151417,283065240,241991700,785950898,100364864,763928422,966293114,701828859,993299532,981535583,890529295,285033118,79608392,445742845,850222539,56757883,487289161,819216847,183545065,303824720,818516595,813463607,270971716,861228995,992030247,822698156,855354151,150252103,677359435,485203490,878411771,974499863,702914802,615721805,558481814,87042062,421159131,36282321,470283981,252010066,674167632,803095882,925650268,40198184,301947573,940373354,561105013,835954794,718496601,706486452,197950648,563282308,868769787,190414985,384142441,593447864,15682408,59209374,889849586,953887927,385776836,823298105,415785657,902120826,74714960,223837009,546797885,270132513,436484173,586388131,947711333,821871711,42438550,601705101,63965326,831840764,525641712,73220618,108605429,27577010,264314346,88636856,750591735,287312439,121507667,16175665,76777903,593188816,331665627,274812536,568257227,204594913,451875648,704118343,511706810,495360041,866429434,180679454,954840999,606087605,972299154,651746525,868833841,610615877,377841825,365657567,550954810,587486923,19399350,559677427,767170512,118291730,667960751,209703130,493107798,269084754,303907578,651448052,180818737,291519759,235226137,208911738,859854939,951659505,17584419,752645844,523470622,468066741,611379646,887344126,121476721,231486827,186678696,350142524,358641148,722694525,679995275,935266529,731608644,412854977,412970007,472820385,679146133,675732921,490088859,587449052,641420776,756535794,846029695,344719082,625397018,889625093,785574637,585395096,289736011,988300357,837920021,139778021,614093539,108971495,283747141,307988544,728100140,627867518,529585649,782457043,539090071,7185565,390782971,227349532,370288320,823908420,854892689,120691770,388023748,111023451,447822466,711968544,835695111,249835445,757144965,606383172,427621268,487494947,24731741,711229468,855188224,818701258,917677459,609007789,256114804,568195815,229586188,855400275,464867616,511111387,411903842,356679916,49439008,449891299,651871200,915723065,454135718,312826770,961368390,281131306,437162056,832511885,298033773,55750770,785134664,750136826,46927716,6977943,368866621,977039283,173294218,701429555,35416758,772177975,521612266,731528476,862833647,427749674,570117904,564900809,529228825,376303877,687812463,6526276,53078581,477633874,902000978,435765494,48620654,502389900,615637789,232586293,651166971,298648235,141013367,76230900,499086065,765809481,547805388,831921068,919110155,686521494,501450099,623578918,144895276,730760916,798556236,510743557,245796744,43142414,716782768,278259931,112205991,97035337,40456722,850288049,478649510,958329500,734729826,301776563,247756337,15214390,652780498,818678017,674113596,497916860,24821121,489311570,320313776,219771130,262299442,837832618,99518705,67193778,78473863,965997448,574998778,697392475,547241520,229265099,305623834,52044187,890766629,116272838,168074491,94047914,512779060,683436309,157205871,136474689,482283975,262105458,915541686,88586642,154533510,164799604,467048179,938487832,244026025,677658849,452644369,664719993,781350458,975023633,822922610,889079753,440321346,41619403,924268767,553506683,739063519,675052257,820002406,664075600,67203024,70902811,196415416,551689795,651857842,851262962,773614355,303200823,108814595,819650151,846874014,836686536,207663484,596491984,320056998,17715150,180169023,379872035,570729787,284896217,929103126,992534797,827873589,369728026,454474521,191052130,521307412,423060483,474027963,978897250,738457796,638601322,881103448,395462262,628191026,601587674,242133622,303445630,83407644,974446464,487133758,346261074,706851107,767982449,818738958,748781795,644596860,320516125,238509291,870238578,957325684,500386841,603613604,556235103,198130006,383887158,701232532,495871296,719777492,441867367,374743786,658630901,521388721,316544531,346481985,172851132,540098041,533564643,437788534,500378255,905278080,707309350,576824693,664380,61968625,885920336,262802222,585145927,204636321,308357005,125750072,129658421,577879836,470419701,609992771,765806570,42525460,895655499,148227663,682182278,499273288,603114982,390744221,741650746,960589982,848437828,589605910,39657416,876697782,145937243,856973387,356527023,59786575,284788497,104710819,295118315,656892049,947459013,96050312,982183927,39874090,101592821,911172254,325370844,275938503,286294604,874362871,984209701,500031309,686401520,795821572,554852427,588354338,864482022,544983510,750932955,190797914,437315751,167934325,276886120,840370804,851934176,827843949,289677046,990764517,545421927,134942713,855087166,706613778,590680452,503601470,464803183,631658625,458996639,525856244,61267081,476177073,930439770,19673044,120478796,470365910,156325561,565691085,585040223,179249896,650207578,494466923,703397173,642456422,555664533,439788636,633578032,111714802,975182190,163040931,425276943,486429852,552251256,981720287,554651515,529666862,342258056,9269304,477565593,335405057,170479829,191786740,645559024,9313018,717259077,576292784,690155830,270386233,884455337,879862441,549913426,804752787,129497125,891110289,645059755,106526039,454634684,162860555,2392146,604447797,319287167,409342792,495492561,389643152,24777831,539022473,24076389,159895415,607323717,944250001,11401159,335458645,825709415,245807850,875893760,395886959,729241639,379050264,552357514,521421640,213716054,572251241,602918015,951074407,694021092,710349119,185289440,719686208,780580107,80215000,676349749,329743014,710861570,461097185,680645800,375912414,632995166,978074375,300523548,316168141,432826525,280886318,63113098,894382471,572918961,922752615,705980693,678883491,186336855,744972345,161250497,279087087,974389977,159307286,293198640,222446498,715454905,368036881,899938098,616572287,956793705,295480786,316046354,872193527,622612668,460001868,629371084,209831831,937683822,925902695,358496468,182443047,981531649,400941990,538024918,320417510,509336373,190018977,544269307,804521380,923203925,670184396,684835391,616401836,920597854,78683600,575623826,122446152,383809358,468027303,218645381,543823516,717148416,994798273,953191500,841377920,244149956,236058082,238573154,241829792,275667202,134050387,887657706,786582563,538443224,947074760,686496648,418914119,19598677,41365414,754995867,370374960,599190425,987832636,603326701,462586268,636972072,661263599,502138997,902428574,741110421,589536739,941068195,408832269,427106289,877286713,67603161,883590336,680115697,360933971,437881642,521038232,506138302,365470903,691889541,723894223,337185964,265724692,83129448,846547818,402877958,193000798,182696136,792286175,987096975,501632744,769409775,868488868,54988135,596578992,93249071,751542271,468839498,759873096,329505746,555179372,675545769,77438459,163400414,468010861,923078087,431487473,467674493,88118077,738384405,68887986,490965153,282324900,324773967,708199689,246508143,133316728,123470830,413421879,124999135,12378238,611046789,163841889,755460602,848836815,755765187,233826857,623172621,547183011,134630918,879428913,428507725,978648683,709554405,837129171,228887613,110958865,302430041,742257984,913981325,568844507,636552862,155493892,156893053,70714550,258597915,787108869,864104816,187506046,907541135,20769763,702470897,660786194,427219337,237697818,426055634,940605357,38270057,942551746,110486514,653800691,791799370,348671131,404542702,321458803,186082672,194811254,338314256,312117790,106257465,874156635,755350216,779180289,295058341,485747509,555408316,392134116,310818734,301182451,462298680,154815924,251330220,759514240,795501817,187440648,244108530,749290179,821034165,393870482,940194375,106843265,797846174,405791466,968448023,225282962,723529265,410288167,664434258,497627081,460238414,202358634,243553851,8357328,839143443,987418304,958672880,232939868,503266047,195999121,551166917,484131127,190736824,38271733,381289152,151384917,292314657,89039823,535289427,717600520,286857834,181045627,64295712,69491218,934032574,167446027,830866591,14227029,127090600,929030275,702766189,853300181,599902228,473502422,603327708,523686776,384811741,884965877,684707535,334998182,187529465,854046397,44068326,713069771,229704085,582367306,102631889,719300899,114560917,707106877,601325594,953589838,343122904,153292273,74064977,321886370,827223890,568269409,669871199,90901411,835030438,829492044,862288345,387996757,488089083,483106455,323664046,640904743,976587908,192359622,547985717,929376342,744766473,782809939,992925162,840128527,204294559,695062147,475997433,444183362,459409296,250941564,852328185,19108792,586465288,321121137,437521594,897087116,909710787,613747963,724523723,443704036,739055607,166321567,530347493,230928856,674911521,964675555,264076284,859023675,619583834,369275604,342950547,108920675,508780501,47261436,472215677,20560769,729926578,477998928,770971517,802391614,352649861,588993043,633251402,700224719,880497929,321523471,636056669,884405338,713481380,647796346,925895851,389907649,959861871,277300891,823490043,93112445,617207663,528215265,404086347,714129787,819164237,279796428,230682432,804398733,466085474,117348376,125859781,218265629,72983565,177340824,732184424,723605981,929394527,627965243,403885310,617174496,800863291,986354273,60564642,75193892,91080095,844361161,792131556,463786251,956429466,602607123,497058374,830468709,708792685,638425958,332109173,478120298,612481480,431773329,892627408,901053726,526334999,414579537,660778492,753688336,652625537,164036094,789852790,944925923,698028170,297915290,250474776,788271078,360920127,140442129,597828808,753291164,10711376,15072304,924111675,45351874,487579046,738632198,698960832,268310628,228374152,20041959,8034580,523463543,715448561,264039416,304736805,31525612,300580200,311909305,804467575,159311311,192315416,105670393,167773475,411410772,56433914,913363374,423989345,603536564,971168248,734662782,260611426,524094013,313244160,896245485,974950925,725218500,214602618,585437496,8975086,719016867,484351843,823461419,323517241,845786241,530492351,794626549,296462569,528566573,571806372,822127645,601802254,77408520,833268750,493456706,605559373,400947155,578958857,394306033,353736674,781045991,449314435,984111071,740722499,382239037,621052418,167005891,333237616,908699072,706545237,832470122,398624636,553372978,56288954,501700718,96223829,880685875,235624020,471994012,193170498,521492253,565203775,172202421,918088669,243280722,566342530,788233352,976476808,939724912,946794656,653995266,114154464,697848856,935703158,359327760,33332401,612646923,692234144,21916801,16485308,538882794,293817823,180775063,208084000,178567260,581396883,246691205,435019778,848625850,932253473,904251746,244962522,264992111,84390064,759224876,7141814,413282223,327152053,283415879,21590215,440444551,950082357,663366340,946893667,542979813,875425970,951451290,6853250,135075861,241451226,933050872,735529323,246423556,585993235,589719151,481806051,308305161,609496064,762308547,32118983,169903172,616469970,750432739,356559457,792113194,817527737,443724592,901178244,413554962,349867190,508995346,689415131,427431597,186772314,745492354,933496367,232444176,918038215,69241116,358669354,373471704,137507373,226289886,73345901,565623014,783757460,927813858,830972345,534419446,286045335,567603700,574358537,559449587,201566734,674596205,913414272,943299551,178922751,564676306,435189858,465796684,839312684,41127298,359927695,573289668,52302216,462395668,935752729,766940469,814363160,818620574,126354891,460130825,786908079,10690562,599987244,798654854,764266719,528773828,869672832,181487515,145743383,882704353,695903142,217437922,601677129,94566275,526033445,586651570,504775152,399804039,445560490,717186025,818377301,165500262,739016732,300996450,573311717,686607053,518414622,183600540,551880691,957212836,294227194,16591644,301693504,786546627,84121753,272344670,310944226,679265593,566557830,605876464,781976868,163544766,244878295,162011405,412428949,869545992,966691505,702872567,456786431,614037758,407625594,380671051,440061808,75810429,36004459,589653359,606309912,551026537,596388872,217934376,509579347,810368083,961206276,319587647,349099010,783556260,250736651,492617655,132666360,981715726,541865448,438822598,112995644,467168280,261096355,761466058,336752798,143680120,70498816,505010161,941078988,716567100,753517341,395296688,743033630,455108528,479455730,843991522,210640442,547290774,440687921,281643276,736800419,851725858,876218109,152984183,455280784,518892782,257518055,171208897,895861620,577142287,673051423,159381663,291712398,78812808,307565945,347672694,785413629,235401668,605824311,244661324,973558366,692365706,57892979,315364506,345086708,929110869,363683488,449177340,444027758,317602413,356449173,656154050,977960935,89896022,389084181,885007452,247411353,925642216,409563313,381466593,417596979,64569816,762990305,729569730,276084925,708117767,320013347,664575495,646523879,256685169,244713994,12306071,984092006,311054759,449925400,689816976,138590886,74218432,364692274,502996954,32209577,169931887,979355188,201752605,63284029,538535766,427535717,968100699,224195684,847773816,260176122,7478471,25747970,981745148,955336454,472117275,666690269,643544432,802435969,464261803,403717197,610708535,985958931,51660652,621640123,4155269,60442746,116501435,317335229,885630908,802985642,575296636,113764329,934802603,650975762,641220960,123944949,46307148,721906158,674226198,794443289,862446041,164565728,247323602,629952103,666637123,910779440,636863516,547086411,826669711,53665924,59520387,823646310,57350713,915997271,230009211,110415023,805478959,650436070,149278003,492169015,14875860,165578787,699929644,36668961,405415392,660649285,903253677,387862572,194578175,314139550,637102769,53327314,872830829,843074288,590416120,590051917,93118645,363417728,35261335,966773726,561782087,818498763,929445093,274382978,238331385,228640207,492974069,582172005,758943384,885326319,5049009,483738438,471451202,915903662,397019272,683624808,951531756,465363138,358528474,262202159,141068754,660862074,715304569,437183277,209300088,636670668,655851551,328103986,399465576,426078511,663601991,131985615,329835305,734705566,659201789,441295801,725891002,314075162,463873019,34320558,427839860,764075700,36970219,281387142,102784235,275131836,25026666,208853165,452076497,528541700,155244529,549663315,39000021,739858146,284627257,816230478,264404207,948977820,526360141,182281064,110495054,277070751,216424307,746949641,479290293,779046879,786541171,777662719,507005549,711112750,666797348,705927245,385830859,924968596,487281989,898030476,812254365,700614170,699258525,409054455,757634635,188184038,408652849,538465242,580644939,866853520,182610957,898589296,612457662,407742434,259923157,204655991,103168491,217459571,504777849,224963145,583865929,197543902,295816528,763870716,502311457,390568971,437177808,421657697,319513512,168036216,258179320,382022971,401777898,86156732,919269675,44014836,295532299,543176089,984998624,221295252,651698390,284069650,282896846,875046702,155841780,980660579,730201207,407420825,11989408,301402371,288668815,878503747,758399270,776434136,598489506,563719527,934581367,481805056,449705754,907983624,406103000,750416413,698238021,245524396,772423267,993916914,116265922,117811602,537851841,422715802,871422872,326699247,945339272,805828526,741484073,14837296,27610508,347039352,491158719,353473209,310997579,282868040,295013493,564655996,280570066,778533868,327286477,908881912,242560951,261348763,36453675,47836690,804184380,402535311,440225916,933859331,509725581,950850060,521527831,173156070,526910129,782520718,987555840,984594888,852743715,902254740,275760293,968431194,568400516,835055494,218480910,285480437,615183149,797503709,339650136,229378060,457089943,799613031,220260729,463550922,99616394,315273563,495911296,734585942,678720054,404295056,82119350,550249093,516315428,106981440,749390395,319675908,4194477,41355177,579738714,180006356,628954926,363020125,756437078,992037882,399417358,181084582,652203098,316973612,733248104,626643430,234994262,657283959,672463684,347870409,303863224,70582889,661299957,643494536,348053360,566907728,224385070,584402563,960900275,204722010,568978530,384335292,963839096,126707684,561112186,536709277,600473344,87915405,539110903,582512627,837737212,781816483,794011173,672921005,678482180,843274022,33753608,890301452,986668493,507935439,607974434,970511986,472166618,485209093,833199508,190644541,766807920,630261275,107252285,256564769,83696082,259686402,34429062,74222744,93285157,70876403,185024931,23522038,782467313,355389776,142376596,675119253,264121246,915565014,574057971,607687513,425305646,548172624,82169394,876833057,731062515,928929595,416973813,77121749,21797658,374905994,391397190,689665909,157019253,788440040,570972959,17049799,263263456,952735859,247796712,11173768,509183884,314797386,835596505,870028010,570078010,80932943,291189805,130816590,943294663,866532006,623791248,375278262,556074657,845137727,666812957,205080494,486718301,881320595,134779503,119509771,936735057,344456785,262128623,204979183,940543387,504171836,292114587,313986797,761589594,53228465,237194775,341465558,364428933,758731968,336218554,982835496,858924108,55742638,414636942,229981524,313122951,259557695,321024042,215703011,445108784,197338537,948072826,175479417,176374393,675125188,659154877,470195033,836444081,370137150,268629056,913240,346252604,133374670,226105910,601272627,404590672,164361643,775066243,838422018,157015234,487977095,636374562,940652139,265891112,601846447,846925894,831946432,81803389,708331078,358183708,512469208,740981361,303457048,514194043,107426162,780654592,324575556,861084405,929387047,392254055,743385277,757392855,472347802,981894656,479044825,899127187,472572293,701898019,737706536,974638121,44730034,541169242,950605943,522637108,136165293,672556909,509230058,79705017,742053276,373069765,214891068,317613313,403254309,80444450,204154009,384650759,894378928,550589560,948798870,71151678,770298531,287945850,275591381,247093288,913139028,652641977,433804601,253327958,919694378,129154259,883287271,391079928,817006773,420290869,939776883,107890041,187095756,721928328,476961382,367380388,206109136,911171842,397920144,332801228,552764858,780679867,679860133,325380153,88816235,445405943,70957440,579131446,293831812,475617604,949627016,550485254,242180193,917215806,893768080,112976498,401193440,920160380,679436842,830424924,492897770,908082708,854155515,953043166,265947460,478425267,596784565,879493985,126301944,925960129,934115284,105357761,908934405,912326506,671746716,796431195,832773956,413476115,773004323,5174130,771260813,255255048,743361493,739825080,829590859,828163011,756116745,556555159,801187164,384728440,725939470,912390483,724017184,661155987,903526633,674487049,435392437,690203778,75657673,720533838,167425354,217281374,277119174,981202568,757610015,667448778,387336798,417087753,625195313,6968339,304272466,682891885,336759380,921583202,460515757,439108293,772115081,30394101,876082815,176718844,75458309,93093964,378566931,657725911,117219088,893902889,36938651,982392466,554097152,564218610,222562096,271838172,805927753,339603010,91055916,872893944,741218372,574007736,281891661,887441994,30842932,108515985,895306739,749712960,117778733,753192487,25416069,172125632,104485195,649009551,794226188,20542441,352749684,306640959,189286450,67344928,607900116,798899599,248426596,683366843,899731222,317208327,619372868,633322416,294959367,78563238,188289786,648247292,12942017,796429743,223523210,457498226,949232126,647306656,225693823,133864191,119139539,286689876,309884834,158144783,206046739,226132952,648035465,267931867,853809955,599239138,714106637,312445854,420014504,191474872,142047465,783772242,518774525,270743665,153817775,763726972,513677562,4882362,63411962,844204250,80195957,309407478,712307748,243574092,629247549,834890459,370163970,297109566,494763475,776188904,757497698,948181888,664343318,531705871,720138879,775738902,700110081,431070708,941616096,600478470,454735082,57313606,91422342,383548654,282891844,160760098,397535029,630411302,220232345,330494097,215376690,433971745,657969338,416897762,264889361,979706165,69649272,123610230,475277442,286789165,583785201,283405402,926901102,964422416,221249643,694936965,330528326,235905347,267302127,975722992,697033389,401785114,7896707,256065816,762340289,185421889,935347538,235124120,735262430,574381228,862684506,399788217,814633013,912081467,4705872,342325245,635939770,771544481,976606713,563402601,882655106,230818506,344169046,733152500,778356444,269997848,394958268,74043397,130061220,679593951,714507966,740812972,210989226,137239104,341479512,690745081,94050366,789660760,788357497,4646829,463392057,90346162,703588192,913038753,891922956,517240951,570678922,644523875,563966469,445049646,88608911,627550955,307647340,697265451,5533235,933608005,314903862,512516800,180472620,199974685,617657713,861865037,249472994,947009670,489698539,560432952,71664866,557185770,197703097,549990360,633408065,992322706,321353792,800048885,611208395,547514737,838730930,442933676,506793358,648702822,585952031,19952890,938789959,973201072,648188889,570976238,915690529,393227241,315475751,375815746,650632851,115464899,857301655,300386198,821624103,399860623,523427465,153002453,476184636,674761194,666550569,276941514,993149209,828341322,547876568,389496274,125456045,710311711,898364094,910755762,913925928,627229907,785585534,560661842,898523678,181865015,170786464,500215448,325932770,103876074,394316158,160358956,694031137,261860336,158417729,229752885,946639475,169056835,981243364,635269267,716233539,863193912,228002052,793641676,815795075,902068952,750620816,964899747,275642026,243642668,507166862,967902265,119503803,3088282,304605424,617547919,298377531,835018215,351706609,168896511,110392591,618094524,358075611,917334816,775081463,142564717,522757215,581274397,224693334,941852857,777111638,688597875,698863099,91361985,658663932,927618765,272609467,401334422,106445182,746085741,467233298,312672734,413957917,808425096,129229273,84244113,225772569,947600275,305751118,872051300,238423801,176001457,991171982,466429433,292180265,904391594,556197483,103593598,816845298,865794294,522204412,837930199,945315581,906629775,291995675,430509860,383196182,327412263,762316909,354516245,524740249,438532258,935956209,806758190,506537973,241095515,31708283,174946527,838159847,774310593,242426330,530863077,81351543,745637448,218076803,599492690,813808887,493078813,405495724,971158354,271998868,545658266,797741757,326481298,409333127,373830947,670102294,933618330,679928064,961142198,893855078,59296854,378493832,42342673,284955047,648658133,688121020,144855567,802406382,818272462,37349677,633799538,977305693,456337155,278234178,69242299,317206513,808590111,417897409,329784887,60129585,43704655,501441880,444067057,686895488,574533254,631206310,592391858,990167788,607732128,762112750,128940596,760854746,462053554,13371140,641950150,620687509,743257723,676099482,197278637,400907663,970216240,762587889,65283759,65309653,988473472,77464841,515751250,123623541,251660088,869722289,216363029,405844293,860636722,106509358,334686038,848604387,694930585,531504890,490550001,105736489,775847131,502481339,322558444,700860284,942228694,531548531,985846632,128417968,136545876,260794138,23023174,910414256,397289980,564796645,541243055,288875249,558736801,523773446,494913199,185040018,482734929,628651791,491926734,21714948,503291133,306392722,545701430,300547938,111842327,613499031,760186051,818741553,930501729,475440557,887686269,836401068,468138706,191958293,399755092,795699817,932329695,430331119,236565637,785399278,238564219,938565189,601071589,508131030,547568018,208755289,566041978,860478779,302460504,655072675,624433847,472406693,773676990,464334781,954635819,110065957,84282741,621208308,236799553,829175033,721258906,623938387,802711372,965167803,541149749,673813814,386840231,110997022,224049237,432711406,539103441,816203469,701251415,147710161,880196779,677948141,372566566,934435333,77104790,887174044,214359815,451409595,181255654,670089609,816485025,963236315,75609480,104763880,131741615,135817828,938550552,773564884,903505456,509665972,494157846,718564508,721560714,703174786,634497566,25607986,587440835,200025382,771834100,906027378,215402164,186229595,262608472,533591527,750526828,333978858,405259125,344598760,570859343,765581118,577168438,836454175,50086999,662677789,796708064,698171888,6254619,476953162,86635054,866495868,352446760,811787877,774720120,180729673,112044752,6378117,266302134,561207907,974038087,312167237,782676545,982739736,42992883,368518365,8179509,912966157,420514269,57247053,5304902,520592612,409588269,699028591,818376074,681312846,593613681,481265948,480771722,338506729,876691806,768493420,608540044,166092788,693091526,428005933,761816427,963551431,441336520,261168491,827076393,306568432,893698919,762298700,267881553,963383614,349929531,225313212,136834490,678524163,158730086,224101534,763225951,829596021,133889067,373284245,638729791,658094830,188536826,932046679,421937984,557472152,257961198,743287969,458668618,563445618,889715089,255982851,218091372,939942990,897411961,279892051,159773132,289956419,438519357,257542235,296888758,202622905,91608404,539578574,982930300,439236379,226351389,107858573,269024667,377214988,855491086,250675890,863318123,383634693,847388799,622952293,873626776,310712053,177142248,220739748,207452296,346861645,1473764,56296772,163932301,245681718,64517728,268113712,750421190,847517850,564959410,412185620,118752506,478741059,259181248,717828124,223648584,438585598,241770391,438522036,190020772,85751571,639521924,10006794,533849348,544625082,129578877,224680859,508096003,798284495,798442978,408074654,155919524,931604459,144907816,739550235,577230330,762408652,722774600,331928602,168855134,402470050,123859725,342030199,407131248,737018595,775264749,856384652,116634911,957505217,252341081,368280847,153637122,69326698,526328154,116061003,559753346,891622317,493984632,563086097,116884594,783815704,68498216,210207897,921796880,502927123,386056826,525433615,300612244,632967913,20119873,128763805,93189845,209881257,804073616,877567422,551626330,352091924,298952698,33898929,66480762,750334863,464109863,649155479,193976333,862126725,111313972,261501575,616667649,962077967,817494499,948891379,824489586,212840756,908568896,130806033,446123128,912803199,211146366,356253816,744266848,506805126,463714634,754898057,217177283,329787081,715528892,340899574,842410094,494254580,466346720,473945402,11416330,834571868,574204092,703455222,108832008,227985055,32107356,362957626,54638471,166425263,632729475,84647817,259616357,337008463,285168991,166866624,662511115,144909593,828270315,120295373,465708829,335487422,264591087,475559074,303949995,992686929,657070856,969647816,433405289,810998261,995200037,399229662,775675036,426379945,647418224,208495532,3016597,157191130,632867046,906556466,950807302,304415814,64752737,709932015,513636024,801892184,465309277,640029415,283344020,332907462,886565669,977271168,547433317,515421588,883240644,648887428,759586187,180723868,58258491,927007945,789622997,730156017,820717006,991490212,687415174,127243522,663349897,516453040,160181108,158259880,325649839,624762677,639427249,759717111,830075849,739327642,666052134,494796875,636607739,891393174,699930927,552889677,352058900,992284832,589111329,363974438,588649762,545000564,864091535,9366333,828668835,419555952,603912145,359748023,821312260,386778341,189197687,687289856,505229815,463545217,437734630,812610609,95424723,383928847,164783945,228349612,151648153,616902722,354567498,649282186,600904924,320452227,761798270,879197022,596265754,247740108,882602714,948071947,205492399,54817455,833537070,421673461,227015582,40102839,341422776,717712008,534568505,153668643,997866510,937208888,704777712,402268517,95617041,613261496,198442228,703818448,643467161,612013745,884150645,515450995,522924018,885391497,851869105,642055330,527481572,197777832,31833688,877652750,601147392,421707420,635816411,897870052,484802184,160168476,519339598,325998896,444611174,84039143,102747114,160425961,947213847,84866622,893720177,607826618,758415473,728867927,519301876,729309054,690455583,632856713,546904255,160619010,946151361,297600460,410819338,689037365,584790391,321152009,528900770,420040767,134774070,968677241,447736269,64851087,123485513,177698760,868616844,761793845,100470050,370940600,198337292,976809296,583341278,614941020,383833775,916312288,986926181,16480729,263368542,839490643,526799162,538756493,565389163,146534294,775061173,19987057,75464525,831624242,796350986,427742775,840657290,951211046,703841623,976114569,629220156,659642687,360019671,522414074,666482689,915895825,136263622,555470195,6596101,939242520,21120819,136312829,581920699,36865301,191207140,449223447,446168582,444346051,75852844,179002448,753646908,216017256,636161987,766279111,971997284,127554312,695905238,95056041,360480044,754332730,898714493,170284446,167134346,310511527,786205776,710302826,794495970,221810676,105809912,231472420,892301403,522359377,191918558,960492512,930142985,435039804,523510339,294704423,172072107,896360615,6775731,752282738,538000647,442342243,195935456,410774697,89599641,413280422,722362061,636003353,160350898,121416855,470172535,962914108,995846016,8237421,203169478,216871306,246970678,736822242,897922373,326384003,145544088,255075506,937667363,316664844,520621454,188989631,20538953,812999429,560647040,180077129,631686870,799075147,256483693,499796100,943673727,623372151,858734113,799591379,216796860,974943494,423296057,944013193,866743378,866130422,207826590,312842368,611378282,281762920,481624907,436004368,805404795,438178915,963106653,282467028,845077390,548925872,651244776,450697317,190526330,78361773,94577098,422744811,116963336,518625099,678519983,900815800,20944049,813585416,440783087,28884032,911747749,85459700,870642,375105731,820482383,239556997,741389055,799977991,488403280,310218621,3216438,287555517,97138878,111968050,458236198,899786117,767391239,465974872,347131729,697247337,60705978,152363489,302235159,294962969,426096770,211170245,263908900,357923369,563717743,559649802,319693131,884142403,668636694,31821322,977674907,183365992,852534170,44815639,408177415,141782948,287382935,343586172,526539334,100039022,990683804,917690536,12194784,173083033,901416994,684476890,757813817,10472085,712981456,458092168,932232216,803383616,585422110,320839669,248968650,405904453,224551908,436541449,859883616,76167103,427898172,109137270,716590869,125197451,790649618,885382365,466559646,234908382,309425498,845661311,514109587,401657707,602226611,488692949,898662849,502921498,962167732,661807145,917920681,655273650,795792527,44468393,19422898,813968522,38280075,413559255,440090842,962139584,667808859,861096778,429302778,447760332,864376605,506803689,920968253,949188370,407064998,723884891,815764385,760023008,729414985,894537404,262960259,560272462,330750856,776955550,348536230,721331039,817131992,631227643,536114328,931394713,201894156,49270462,746907070,499638968,53892358,249645435,822101349,626690636,871811243,421298803,558503210,721065966,344588301,911621289,209112314,344507438,695450233,768790249,177987668,911276104,209267510,587766610,114020928,355157741,34096770,300605714,591855436,757309153,843622616,486482305,943211431,513203658,42810295,763862690,655082978,361516534,974834579,146708147,888615104,101526104,901623587,260679343,127150396,63638021,361269616,270935124,203626476,117065559,399473555,297445779,};


ulong inverse(int a){
	int b=MD;
	int u=1;
	int v=0;
	int s,t;
	while(b){
		t=a/b;
		s=b; b=a-t*b; a=s;
		s=v; v=u-t*v; u=s;
	}
	if(u<0){
		u+=MD;
	}
	return u;
}

ulong fac(ulong n){
	ulong z;
	if(n%FAC_D<=FAC_D/2){
		z=tbl[n/FAC_D];
		for(ulong i=n/FAC_D*FAC_D;i<n;){
			z=z*++i%MD;
		}
	}else{
		z=1;
		for(ulong i=(n/FAC_D+1)*FAC_D;i>n;){
			z=z*i--%MD;
		}
		z=inverse(z)*tbl[n/FAC_D+1]%MD;
		
	}
	return z;
}

ulong ifac(ulong n){
	return inverse(fac(n));
}

ulong modpow(ulong a,ulong b){
	ulong r=1;
	while(b){
		if(b&1){
			r=r*a%MD;
		}
		b>>=1;
		a=a*a%MD;
	}
	return r;
}

int main(){
	char*mmap();
	char*rp=mmap(0l,1l<<25,1,2,0,0ll);
	ulong n=rd();
	ulong m=rd();
	ulong z=fac(m);
	z=z*modpow(ifac(m/n),n-m%n)%MD;
	z=z*modpow(ifac(m/n+1),m%n)%MD;
	char wbuf[64],*wp=wbuf+sizeof wbuf;
	wt(z);
	write(1,wp,wbuf+sizeof wbuf-wp);
	_exit(0);
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード