#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef unsigned long long ull; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int p=998244353; int n,k; ull f[2][20005]; ull s[10005]; int res[10005],fac[10005],ifac[10005]; inline int qp(int a,int b){ int res=1; for(;b;b>>=1,a=a*1llu*a%p)if(b&1)res=res*1llu*a%p; return res; } inline int add(int a,int b){if((a+=b)>=p)a-=p;return a;} const int A[]={132437264,289095462,20658737,369002275,385664949,439067552,446280781,368473738,234610518,530927743,166043612,341340381,761944433,490751094,489027060,618220427,639059295,120391109,409267251,97886088,830656248,87202326,694749038,288279690,290964055,124736054,351264669,95379971,825896849,401014325,283919244,716338918,286688351,929703098,652142788,643760704,237167712,296551647,131470656,267998588,351989758,685134491,212404249,198110560,204397731,580100525,658141702,119580236,799847299,651300033,803702342,198384685,949391219,553088750,354337991,384917444,660150793,884386509,564548366,269881689,328694726,445905995,978801330,398169408,596240806,650084853,827309146,820728660,523778463,409154933,524912727,743165354,307777842,149187502,721378038,132297308,541578804,956684399,957835761,890744589,273700259,250780945,315289976,181351794,777198161,362474787,543349235,452714253,753454857,161000412,222032065,542565584,900188908,237108775,333291010,246848898,468922152,460375636,454054684,725755697,289883772,610775238,598896301,191954068,583247463,680385478,721880519,699463925,157506371,389644930,678265809,253965602,408183608,383217570,198922524,450054118,548373555,322265477,904215469,487515393,646304774,871262784,134462350,525201394,781507605,524628643,509878490,180289189,826274901,25931554,207634735,449304353,39619577,469305398,739371931,172893824,134322480,955589929,16021154,120752494,659758432,150602148,246924176,685622484,355939066,222028306,679572851,779268120,890350328,244692073,193725893,739960927,798954099,567076065,502745017,446550715,313381713,196783085,192541884,393649593,197935116,494434124,269019419,196723838,811059882,289606289,721710356,875771911,993929090,936681589,763279767,841275777,823256929,70099859,378758590,485855475,958503967,919001479,416797552,829628195,505528881,446964181,383900352,589948174,963273972,363682894,850422965,593645203,627236174,114016200,784995050,369997857,393668700,806770369,561886905,479512534,655219260,400718884,939546771,807718608,480158967,76623646,781157118,188758768,538474420,109304909,342550151,613692854,257424704,958644514,604407682,2703085,796553098,96842773,532343353,214957734,914091327,177080692,909068964,317676345,589820578,866834966,239357379,653162335,644724085,727078658,215895464,159955544,506882239,312029484,996642938,629201006,309112081,329304130,458637045,457869947,602933039,352082117,530572026,326413573,501386160,38801265,892983553,421285924,345686435,167506625,73516263,658389356,885937864,39810329,386339016,312875580,362057541,172691466,145552612,433733264,18706341,572885358,175639079,178823431,858798758,538670896,788183097,19775650,281351334,50000996,713788316,193905662,546276681,866155974,701225828,629467191,128546095,159434264,194671120,860436840,526559680,806643275,678445369,513089086,399065004,512889350,19405169,138746330,39907218,781636112,893726064,50361977,687571055,624335571,179132119,347786744,631153377,801347088,645957772,26302210,46128919,967324890,387864487,823317582,696610164,618768629,597161211,214650384,480407376,827610187,757084517,532060584,58255920,648427072,393486585,256186259,46015360,500224044,109988194,46800034,218613970,374985735,616633619,712899889,938006545,502673661,623680218,44470327,664795107,527900205,40559115,413120319,12254766,935304660,667542286,219796030,68543099,172030776,795825447,850363480,944330303,663872386,883880046,483637684,457130790,281084477,702581978,919893261,327981579,467093694,705055584,255351276,206524827,621697471,647895905,713949699,986572744,231171681,970177784,669313659,310726187,994671518,245367698,87929952,172348857,713341407,91341612,909244233,897909802,508346509,917586828,832233630,535690261,540288127,544048375,138138577,15819213,923339882,689074645,829497885,720435952,735141012,767537119,926753599,638579845,73000563,883948203,479368804,773785670,567840177,472676290,507663944,879017320,803722488,78768150,896888684,262381581,221610815,152586056,464200127,26309255,599101513,761489365,321357293,484279525,189663924,281973688,873643301,248515135,603407414,31515273,604623605,542453101,955086149,917618159,169960211,71831916,823305654,781211750,754083896,187059475,503418243,358806084,3887831,69970364,489671571,496438625,924449619,980635366,519656388,964507688,505741188,388362051,794642614,774187948,21241062,828343519,166198008,494102938,475075655,173031917,888165150,771998788,326059613,959552930,227650288,68129637,435247569,391117680,6347835,594301060,503409404,79845072,797295908,998123782,149211799,619878167,700724720,728360869,368877938,585334331,302563607,850120728,928939709,478697180,892540895,603759429,778385959,699113933,230826968,361946451,565780727,258661178,672143547,923302806,663752536,233625590,30715291,136085722,791984951,224035236,766402440,778074736,801926195,879072248,944261044,349058678,346789631,832182989,538579675,944894556,308232804,837468171,71935536,231865400,13999560,254959518,509757016,732558226,220906457,81315272,833621788,609373869,57083877,831781983,114718883,90015241,955341870,364983719,51355655,628023766,492586249,466966900,152518666,836089440,418712339,77488167,90313091,214261668,343401385,272445761,606249382,60853437,22847488,384761874,471814868,747570119,73345168,662618729,100735938,995500616,417221180,346264612,643991115,878407667,255689906,883701552,918590769,796501447,501733539,403838158,371894014,28923041,408041718,223963615,169369587,407226935,996200453,228467241,966455035,459402705,485270538,824694764,869061276,869981102,838498102,32309847,342028955,235390223,119939469,431508919,609798198,205311491,662474096,508880033,716482089,223727298,795018349,861142299,394194499,180409649,264846482,114394192,519713849,406407978,724068706,11346959,411036489,759389048,90809127,792586115,83704753,400499636,243602949,240039329,516782014,399956747,531254599,127330373,935817621,51393200,499181544,608092790,440389468,274726821,129258294,461797442,562207522,212878508,931122831,296291024,249831902,104143127,934972952,478422583,237873615,184909752,628670311,641897713,746928162,303368253,137128584,786365665,475228617,749249632,393102822,94097158,412185518,327438704,13423540,172027060,57255358,964148663,690534191,102669622,988110419,289757978,529061561,675333907,181978948,235062758,649202310,811384552,179100605,47748575,449686375,338618170,237920045,313630379,548474375,860118242,980785058,119207259,359226119,23281288,71765717,687051107,987985414,260119770,128070149,903420430,835214446,120761369,771811179,853895166,277603351,869719377,525187590,620837668,991402116,599433508,399230065,173814506,244027595,333191343,860029025,206010415,17172169,662646605,40436825,964190646,992471026,777480829,334479733,161917886,277308821,311801164,980665623,436609080,881345346,427094389,159666209,244028843,41252396,460647120,390180781,741767473,612126750,201063762,27085812,955640053,947687679,737872205,252791085,625561835,703632922,912977624,766619639,975255353,516468064,551679225,754902755,956669292,744923011,713208137,26737328,754369973,671134378,632384232,454938203,834980569,394191942,624267523,275427151,931133279,983882009,408618440,777196506,637884467,307554247,144030518,665904799,930814793,7302478,449508043,717477190,827630169,156237690,687086946,465121485,7107648,400162820,887383704,719060170,878025130,277602338,442260466,3276625,331630084,297979015,611390816,381185548,49019833,727467171,705796318,316757164,244997074,559030843,93321759,716943682,741652776,279514580,157072331,899957313,707099058,400325056,888070752,436077344,420306627,200532307,64334123,473943016,517424661,46747311,539999474,724176087,341166923,799026041,503626422,987986046,394627080,732882852,19980697,898949690,798434862,474568090,867170228,651640110,930013451,64198156,901051129,913991366,313180055,555767666,292906039,951108483,783939112,853179193,268413022,539688685,143373537,425855616,233836445,360416670,32939465,118997068,15080521,307306428,254878905,972731333,541337225,971484063,578753972,120191548,756726824,49155023,118497621,466070025,340023260,942624173,195914323,100905469,600726320,941290098,287859711,799579375,622621919,341653377,462216359,464315895,997804937,318774969,371692384,566114463,316956607,763099110,888811200,628278700,18873738,402350301,713345262,259663011,956834260,27782341,615269365,694644177,902983509,932082011,701802285,474529127,338088477,756736186,930516997,526738491,249460900,478902499,491105783,867185253,222228358,10530849,182742325,535146529,602202698,786999901,50817177,837071808,282561782,445227657,539762788,869239509,983775994,296349477,130220633,436192613,126696782,515160898,889524354,280004169,772871983,57113452,821531486,420703276,292304520,375458225,864262804,404831527,581382401,643429473,585146426,590227242,849305350,476545002,431610773,367089092,774977486,181320913,279791719,703921059,18750824,980831455,479517967,205810063,941823642,816928974,343351782,552108283,642959441,963465210,280897168,213792879,801895685,619566361,722879105,796105618,640968004,860607791,72501739,18766012,886390277,431297890,318302968,226711976,935511153,86305127,766289786,682048466,76346729,302001255,801648702,302108484,970953147,144372235,984115751,85389074,81312858,221592499,823898625,985551204,341503453,350122755,271748049,679695519,903469136,978274813,830298278,377113764,669789908,26757329,266447237,659235980,69948887,578431560,12580077,390882286,535042837,307169204,490880070,59111426,494918693,26276149,651668120,383432290,584934050,663573952,426728709,455303828,507249090,207353536,907107058,312630598,259858606,84119745,686331314,851130127,143886308,231355452,370239573,621020642,582057998,354788544,268373520,366889790,221109091,851792473,620749738,673963660,363308878,912492843,770300929,77976760,274613485,804605568,587189584,694044891,976305559,240409006,151423346,287910269,463979339,48188479,742026056,70422875,943516462,270746389,411896470,909809805,123618504,599484335,15849122,529242454,112159324,720395861,445571708,966557590,726042734,338610690,682053008,935595138,138737159,205215259,359493899,302645466,477152825,614682258,364306548,300167335,529073915,288099018,868463000,985077176,636809359,304070649,530755314,677372688,525033527,352426598,205812134,374085310,207000564,462675585,89063329,922149192,22860486,189043101,775885521,359939752,44079811,56537698,83401731,134344169,377692090,980215971,980005042,895612575,628069504,738759561,8828460,917451396,263510566,733121732,249468471,974904369,712697417,262044155,933974880,983047869,690388286,504230776,482213607,939227999,334682789,787615255,550663942,47015733,680942474,349075530,167968306,890998467,810809651,960853521,164546197,149346952,31777674,252758151,785988729,621268,105803591,657662785,334175682,848410271,286104562,641364245,163651297,660433365,662737932,632214596,176889527,971465526,774868926,64098251,709347238,374250615,155979207,722452203,289863918,659729132,823861613,2714878,750748113,217187072,558978848,119169235,163174210,187143904,71859063,520787726,700475051,902611527,948002777,266737643,11758323,781273343,549752231,646355872,751374760,202624175,603905087,366742781,678774189,227339576,893294395,325598632,879692855,101325679,155644504,269718408,597040399,893799,647460179,124562204,650703906,395511930,92959634,374278085,457454270,180982001,833042289,404017146,135486610,607786224,717681579,704829252,128558792,716238700,509564048,521203512,599388137,284751835,516118419,358595509,487320630,712048974,419486325,829905913,717458805,862925350,856602203,378272247,72102267,382070945,498656379,628140377,827167792,251847290,360127236,103959615,414088491,848181746,42371898,232178526,623856554,555452707,995513759,249253804,695914255,331703791,458108988,899653401,796107339,434371341,299436682,157401485,277803226,744501789,918435412,363917149,270019854,10459036,895091171,226930230,568681472,439909786,629251999,336639259,789909503,77328181,968608432,601165249,769809304,837538443,726326566,174856030,882146919,534919705,142751316,802784655,356623457,610901891,461848931,569640973,901199171,521756521,810602549,748089489,599576356,479628940,520812613,377945237,296120209,261575219,221683653,296789365,905848507,396413669,254284507,310009700,609365619,3008993,664608460,189236715,716380132,975496348,285571429,582907314,491714802,521173289,415435345,22107346,266915196,885027375,282362908,493374240,54766014,922246290,293254945,694259185,651685973,711786827,725772481,663281851,81611611,648391523,670668770,866245633,352746419,189205251,880092204,64244875,584499997,964833015,292032904,757702449,478845795,270312099,745648404,349871156,52501931,983608866,744136863,443903404,2742286,553397752,107686612,235498917,52238759,278097975,148206750,119838687,897955340,585318697,543773029,744178291,695452946,382020448,305289480,61183632,963618113,501036273,834836504,601656062,802898921,566626977,781233087,784771572,728601534,453478532,778002897,971412679,90964313,876149474,893224741,233605234,911340775,345618054,351241117,931876999,333237972,395221556,557431919,175309753,366106648,651640391,43054201,753598110,971398176,281984120,225593734,199246385,25607687,987276731,133995761,407626334,937414330,453084556,773846781,313287838,46212374,400310574,294785333,798387748,927558676,928643055,953655123,653909182,450232477,362860856,248589214,878988166,857464205,12203849,540596791,470901058,427694990,101404086,804340244,990315128,296179027,245463556,782056719,384823058,767837914,450756103,248879388,466275657,780307783,178631180,483745672,812155251,626926581,995668526,344246298,537860499,174694884,226429345,23563592,813826044,191696815,350954726,961052387,222122901,380924189,990742761,171865786,830321475,467731458,704927392,976679727,44106224,660804819,559645338,153543134,376733713,21951840,647033699,327464493,128311405,962348465,874501222,366859275,193185357,403773007,283138049,498765746,28981168,306371466,391096145,652568849,160383576,388805756,907564773,842150095,46167699,385133634,589473668,291789134,921253049,401095091,910130381,553307286,500384727,806196994,582209400,802410232,3097882,258792125,77448495,421579624,33295222,570420780,611000424,267161056,27004840,363559855,423084481,250537170,59833430,2586290,615411905,806527377,166021979,418864375,257349702,960877115,344667573,861051650,138927554,865318294,493935644,238391783,431365073,851910962,191027238,245481403,930783402,510591671,170137740,64958248,488132854,145340020,583758263,9134673,751184913,700917703,858083024,5783604,630672331,369832904,30450886,921725158,205782651,812911926,463458894,151389072,121332373,513490255,599702294,46998867,412045348,21663696,703389590,916857140,924080449,817244442,514574164,812434595,577710821,642409267,980874202,395018120,736436381,577715240,115487402,979149442,28597699,733097753,169179062,32419276,742737400,354067600,104120608,590593880,383617157,717535861,559316862,938802514,252167140,588541763,451077443,392251813,771967655,133272545,973233831,321292194,102340425,847216382,777524838,482152570,372715367,368712464,797501184,458959209,431367857,522246985,197112437,319111767,148248577,224557277,912149136,893979422,946495764,347985568,317007450,826539724,25726605,677229778,896692826,363818449,928795065,539882607,458437920,544351879,570934018,942608876,310889277,410005017,670736013,442339624,41409324,799491745,206336516,106504091,858781440,529379903,568932948,302188230,382444302,360747874,535120374,315359946,623935512,94548990,444754785,814580739,453422481,524634739,646913258,212290477,697767786,235634912,372267386,384094118,374394645,915660349,717775647,794853700,860423604,804331258,263538882,326001494,605848716,124234818,235930412,540753001,381783621,853237921,197103141,666954707,548675369,669734248,618099188,640298105,109154919,784621594,123791295,671400742,50292323,190265331,212519619,379620155,576993099,582434753,945621318,542924959,193854245,524115047,525666721,417964931,387188007,974314494,357590604,375465010,910039118,651166685,846666562,749610846,796582153,129434034,571983648,969211855,656718951,81907944,707135647,709885224,974171144,928672024,982555320,870376962,320153173,624066461,801763313,880985224,690736250,66824654,311545333,919042419,509785708,75014056,177453664,806750652,789101872,260423103,768721977,806626686,729000279,164779504,127636854,755354767,573742168,414379870,583984492,19452257,310902840,740247450,922491541,565558355,926796095,616800085,574151978,458681641,542772833,866247095,275440617,955699936,332590664,812080707,923220963,716862445,718283055,486785051,68478891,161991753,881444359,667324677,518810590,642979768,292136136,120518511,400063408,633976439,884007229,584493613,321589100,795841739,452062049,298062397,270894180,463406669,966848670,31705176,961733675,914348586,516840413,526810373,776835071,792194727,883911701,510199303,865520026,18950110,905524490,537232122,65584629,821839132,552808520,808168912,132005222,838801653,153377229,929892071,22245819,671388871,395142037,861761533,909668144,397702006,575796355,50116637,681808057,510699683,450954905,182033839,724346771,761931960,45308087,467031148,726781218,574619940,176119386,233149541,444516656,826275489,686840754,261484610,869797008,835399215,240433272,333793971,57107445,910293085,60746352,615394651,210233406,566961612,358086832,123438780,716363984,459419519,929740976,53175285,365523507,969850352,691290788,655625979,455068033,108115438,615457133,541685113,145314812,616691501,485181103,767794888,230903091,719239776,141200159,588625030,103466850,818009478,404214229,558570138,940660944,725346559,868919901,351229689,578483531,474788975,910503638,191607658,594338347,242976556,798176984,446298256,716008007,375191615,883424500,504629481,368538408,103504597,537202342,898521966,750286682,274512700,222800789,834670276,981310752,928434700,439213869,710778932,452337290,624110916,778687647,22268842,622599129,476105112,796640285,780483186,881367816,820638945,753264568,546020548,879668467,809354086,859619637,877790980,544739583,795261394,974422451,142435889,823070251,376144184,57661017,473018250,520078669,333764574,605433175,886571083,360656434,275527902,954203164,768171911,821585384,456536806,686873813,99138689,23967127,825824666,632292815,591555697,61392700,668775516,89352569,176963163,849659734,394011293,249017278,14734579,447919376,269950850,695807255,503647429,856365677,660049982,349086999,245751366,324441106,504993212,352740769,360211423,624152274,683801657,451836708,913571530,340474534,464542122,179072295,231559425,985220554,752053136,604091543,791053332,348051258,558505392,264970485,768950815,996569342,215899271,885857310,538793752,78824325,395221253,562308754,490648367,190531066,359749647,36700642,742750765,154965725,879316476,545755752,849602303,996157321,299161676,51164615,902403967,782606504,10064402,570221135,764969146,923167180,46732176,991377631,354873191,250730583,342963822,617382269,234651141,607366892,108864971,338870931,34865788,617277577,228798134,287051860,223504848,55929345,645749666,628804052,737032092,267683882,176335331,514077253,964054399,268953539,476274909,599535242,620509138,167053959,767909465,65770615,928112082,202565795,819172700,106909037,830732155,848608349,111665768,635042163,845442226,920110583,543618205,516884284,931327469,257479672,385612352,656993391,394373021,291444560,476339773,918501416,907602492,309747047,380011434,497255329,429614779,135430671,913598763,619203336,805226277,913052422,569541205,674467818,449268974,37959752,215548128,544374018,819002371,796168846,74428739,406461696,127124008,905301500,129995313,37563824,115324434,770346874,955854166,442097927,103615939,921451295,695927399,624762524,510940487,45067822,461463394,965361568,66158018,877228919,238902284,563163544,125196379,888537749,551209256,791457307,611012238,525211386,987308582,488285605,552481456,321522873,112162415,198427374,244822099,57108724,210460035,803967321,305372673,126374709,7616806,603502632,370224304,159136741,8589642,400598694,77801259,972823441,358661037,489533904,974886032,983048051,125707693,121114301,430645080,681323139,560690032,99476668,507673283,254437214,331180542,714581883,802488145,785351561,306605980,664737436,735584263,478610921,516620418,609535474,803851778,866659612,489212773,775356030,295767137,667615916,439362196,696366747,113687153,237404537,216089912,637303013,194409736,941286812,747460017,786195715,870410162,17437459,790090415,642367002,753859346,227215278,935707535,819033903,712607226,396465846,135240933,703560140,706978707,291023772,507020713,110101194,511872832,805498457,682935265,884858501,298723057,597103209,580550720,452084467,866632521,107441544,603141282,506654781,854172718,644403018,556664339,238484496,248503649,458370886,554516813,892138731,99870960,542940315,104364985,274373385,787391276,110184588,639388975,466909482,618402309,328181097,220540548,808854137,227639211,406769657,505129999,97046718,976646738,964608544,702605705,34372367,871397437,624044023,441190080,664600728,462503890,500155471,990523605,369830249,585893036,62127686,400354239,703669954,172583002,642026729,781645981,691230454,594184840,646585679,205938105,383185149,824429279,188995584,92267855,663141201,439066436,920839124,665976215,925202740,735675606,465349833,538571096,268907907,95899252,89455046,157312336,542177037,754279812,738394652,553046644,153479028,892752823,870946272,391786747,39613946,630681259,1143145,788870698,249451498,960252710,15381240,237620517,682462094,238852359,581854313,945721686,651655117,384958048,327423743,118655182,892775325,124004605,180528896,759051239,960336821,912318499,529764752,29262049,538394057,919915591,438046553,527382522,652087017,921325360,317346622,607227004,436173246,357090076,430252659,89048383,385067553,815891601,321713179,674594208,124818641,772084199,632354358,532418377,657592751,90180487,814860682,303239258,254819068,622735037,898454546,91575050,923274627,714816076,28481484,384039852,787097093,688760489,479844604,13260977,560130526,40487542,89366826,159388960,344297349,928709969,700244610,418989177,85886364,578020021,911230351,956531094,115618202,682237264,745995520,216653535,188004116,955259735,474856970,993075379,743423480,178607419,643280608,678337354,123981122,192213610,660824082,625827084,650332261,967199049,80289257,713485469,196777422,507961507,233427870,866321441,223278455,158150243,99049758,779424944,537644114,313611916,194015182,380195169,471345889,379437614,546388767,412026479,933290309,458446429,113730182,773004380,356893353,532570014,552573507,274270072,636191987,80084728,529120217,715136540,562626311,973602010,92517435,544939303,837200652,571049794,575432230,96854248,483320219,767517199,903267520,32869272,477437862,927052896,28659281,284447208,180336675,913907311,261954722,778338544,669963806,859510065,293455301,679685123,769896651,771088828,100692968,227256216,569923158,155122097,862487263,250427170,678279807,165764102,725833311,628875040,423074356,701698476,497255658,789074519,892436244,567555411,240314421,889817459,212144113,272858591,246967801,145068876,751624506,1814479,563873818,37657837,472024122,815898575,466852355,925749562,714639905,498386853,340077374,432825979,198644292,364436880,465195190,127268420,534320210,310674895,733322868,234418848,206997655,458638349,64546986,130052054,433690770,386531598,254403640,994577443,333635465,51594409,14534749,86493413,229560962,191896546,764914251,714638243,350543506,754875708,644928510,83279224,835008793,452682709,789144973,346287725,676576089,143788230,965245377,448480077,177129796,3457041,991785463,359746289,236021199,457712926,793312179,619808997,892481393,955571653,71528014,779092125,974735082,137589569,783735596,284746752,930941776,704005731,94855605,969749811,292151632,147225105,963538101,428683053,721527245,620340841,912864442,231865121,182592345,518826905,924400170,368514285,285459156,125535478,604901973,32786146,572627444,281697182,921055689,647604071,386404299,136234548,558159199,958814932,671894316,942801997,5803102,220309609,837374551,919975929,792985775,345549975,501734134,764796944,445966720,466968598,565070361,520919163,792934496,746684800,603795904,734436195,149909589,785653741,696340811,396134715,426568584,914089684,9201691,850020210,804931196,374795597,160824018,296653987,727139324,613810218,77314241,295492039,474646229,417949377,166964909,134631077,826308953,117188027,327481579,513322268,265783738,263091800,399896398,673810534,162584763,560991081,149226612,525386489,394226773,279659770,413725848,470416301,553993833,677425315,737249279,125812366,368269967,975212318,13291660,79613531,109125868,733028667,720158265,833265743,882275558,496889547,293664926,731418555,607715024,623520239,383067656,811416942,314008776,521007871,438368969,666648286,907444153,250616838,737887052,85563152,910496509,527147338,194941230,530880182,865185792,743601995,757594049,466645912,351621688,991914188,249015877,350200033,62495693,342700573,774899404,253913815,629927434,852336758,397934620,798431448,332868157,719324877,871439491,876025798,229505759,787206087,190039436,93244663,923701206,800603162,191124843,73660270,576687625,862107555,904968442,803204632,832946292,281387129,452712060,201991343,741557103,921867280,699575507,452208331,239424086,994246435,61556237,711760852,260749160,882171926,600835775,161938925,801131698,784745605,562035395,597166117,332704527,198323940,770881535,617296729,660157534,942339753,654578453,164783944,957915422,355210236,846763586,525364606,440316207,779386885,303827421,931431046,136630787,267510294,109001523,825846541,32525412,208510467,544448795,566691215,816329471,858217324,62339405,337316346,609980338,914119087,247081634,513375712,899030646,106140008,956199561,354693456,727338391,546236660,46923775,13627294,259893688,236437757,755881924,571723050,740249861,340607359,765105866,226867552,756748092,353111241,932983299,352264353,570003781,773449481,138979598,183685233,477912776,531747373,735429470,974506250,331315759,171335393,374510162,854285875,523464257,644606990,564071291,741081195,612575778,673296819,196739189,811980107,556073768,130866970,931505230,993998977,456569706,716285688,322090876,302789222,527592117,507994974,302637436,712639651,197217632,585264562,377457586,740266219,165575028,309988496,620824189,97887413,791664555,703128545,482968969,987722554,682030359,524148358,953875134,743217593,919705182,311873683,941489014,950118151,498814248,992484460,8389114,387349329,408939747,476895222,935683208,567407175,72365778,566780688,498206921,307613512,219343333,754067208,582647504,752961653,939935300,475210907,791376671,158068021,213730620,852670857,43528791,789692324,79833671,304573683,292295503,111036864,401648820,479413019,819796862,639346353,201771815,702615941,438193125,561978194,251285299,939875747,259874763,636377286,251026429,223366998,886327646,48147275,231367102,454707907,683644260,596582473,387358820,55689956,549979547,733643785,876342931,184238720,32392641,727886797,219299008,27030746,460378695,974227319,6743682,979688038,564606524,918693294,171576528,268507838,462879161,453538131,969095469,856962883,510450261,334290781,597252799,544590917,899845132,613363018,664126928,891780577,745683951,568943625,176168137,155377220,920937788,459354130,244509572,158839669,493689600,263019160,476280699,682277724,884915224,948342388,73070829,477246596,204848253,324593108,644603384,146464620,107467017,873741985,651278451,75256521,910204729,669453197,78772748,18215824,693539377,586927696,647896210,666831758,590325702,329542512,677637395,367998410,484959735,566979412,396195173,816531639,860384589,940874314,638115237,671674779,67788010,439833479,789115843,150729151,803509159,767264765,960670024,174905354,703991663,826743281,413217476,479270839,298553826,731607288,863515216,865004177,640417255,360435207,718569154,780479059,235839748,657631621,319089234,846815114,857200487,582068325,784402808,934685083,348998376,337942925,917959133,762588143,737778957,430044658,559575480,129935888,834845997,490533082,399666006,939460277,302251093,289134490,647255535,269298801,888293266,762792842,132817838,967212988,517993176,89016268,749247742,306471820,167202261,981121069,49357428,343795313,402212622,210152922,218555735,486241722,40120224,629589822,69120595,799206335,957484759,616137708,909743642,445464149,611360936,936273614,759604179,121737122,140480369,922571295,157974613,133238197,630673358,216116292,307979112,244337916,617991899,317932308,633214844,202288684,659475320,261467234,11137552,41523913,122923855,643389327,318321758,697823257,825228710,164557700,941982876,40762745,948194172,978725909,911419278,506754724,434050920,209212446,318061424,336584650,851968160,598445639,929866579,841451115,275372058,227007126,362783805,516529186,63520921,302109296,831656324,641090027,662964270,680005152,290846645,741483683,334833800,376074324,824150870,684516381,70216278,11031335,113707129,802906756,412288380,377233367,160416668,854201061,686650340,354281406,952731920,872692405,110564378,560827248,46731584,125399002,982809085,18565075,364118387,255024498,235625192,472333606,252134854,227811957,699532394,580871150,849009925,787234143,637087989,728205097,183525217,472220437,447492117,438765172,577472445,688186949,749328400,380006958,60008643,38479010,228618868,22998551,958818893,467206604,781092815,252724986,540661772,318697525,105474661,344965153,97695073,854973729,948652329,528963259,752875418,712430430,610473541,225688503,443589048,713683526,172827485,497298757,355949140,686235177,779455553,228910121,229752024,498790487,717624554,293770730,609325709,205437781,594663938,395330492,70306142,931496431,589534824,420964912,739467023,204685510,82543852,106437211,591992076,447021708,9706801,565189413,715948599,481560835,478065708,294624528,93914385,713927303,99353474,945039819,929164872,184039253,242296703,4401513,83656139,558418150,489865779,926674293,15601800,469581097,967900371,237547154,827246297,527449041,126540503,618434287,38418473,516977774,379446000,781691890,288846314,512290902,403451650,40133610,169152980,493011210,525464049,956895825,590315857,934767643,242033602,865495786,493800529,409716018,750590941,876797248,486372675,587399464,846978442,324395297,948990059,57853219,753100857,441989301,837491219,318193050,898346522,720789151,374968399,673994400,898116775,626124406,55903772,272649207,833237932,533017235,503340085,645120200,974804016,430019571,148568617,3489346,851775418,589193127,975212950,118948497,610970090,155418746,708997456,881396442,106614692,697591374,223036945,584655131,798212681,951610481,941745987,294158228,951688745,951900988,728519852,313459252,523868215,592435967,776332025,901045385,438701251,523743824,524953366,847038872,847691100,978377507,652839182,826561197,825021294,304513507,230514942,246187319,895617705,632859733,75050669,771021211,601116693,870710157,85466141,91709959,268217667,132760192,732547485,595729539,556841643,113095962,490726166,912891603,382332232,535073375,249798379,223941603,792079757,800635985,114513025,823680253,99905444,946822605,694547470,604166000,350182255,143804891,711806536,182281752,710884826,940876023,760283401,579352725,706687040,691432772,417826509,930441831,365871402,738650876,199629643,769809253,759384623,810853311,524584976,776214599,874822591,816405240,910010308,448651535,846327050,926436638,781577626,675309998,185894805,115491935,199595521,119849872,756141980,119793559,340714951,100865084,307524337,937343285,204714625,77811379,887837824,532793310,24882922,475507500,206940824,780370374,52608349,186187148,620124832,856079514,242650759,670546087,995415219,33169616,861390917,152706761,681255034,783094633,801090224,529311828,13686976,567397359,927368501,916840733,608241191,934609585,795382248,654590168,286218451,934563894,914701632,875369937,390967066,46581669,637844810,37392174,263815845,649731004,40828666,911664192,190366918,389549556,568906096,356459637,453835778,653207013,633878989,771230583,605639460,585788647,856523266,812655309,555466990,844009358,308090940,481730675,111616720,515157460,209264795,230921518,749710354,716986468,113868512,611113,283617029,415977015,527102480,672055263,53633887,367349711,203841224,341928196,648679464,72041121,246159162,46301819,616349240,985996699,870750771,451009990,338678832,682993524,9839960,324393273,886018213,776626225,754363446,109252062,943359479,11981585,359103824,205347322,703032079,846118676,399030325,313981153,726682291,131724347,267463860,312358684,641100517,386792610,26076546,754660161,275045582,610543494,518069938,2231629,418046617,950174173,912462866,798454906,597042930,733137058,350410436,379182801,342882909,798467499,128260860,443281028,761926130,592693119,247212254,752682904,503418095,881584288,557885776,504588383,893725080,548951185,399730630,291740030,547439563,420445306,323759412,361781470,492542097,511470015,842004793,256410741,453468230,532850007,799140637,468118961,670070162,594341824,2808430,617018958,433231669,444274634,482336495,821136305,426194049,306776145,171843232,748943699,239673315,360583748,623433206,102662939,736062438,197828092,173489256,635379127,78157283,526181526,782239572,583211877,583238270,945923178,901544269,320155297,465067229,530929388,693968430,495086011,374702117,604729917,565657590,343048907,586183495,805385127,174399548,784459837,525626571,436684285,72956332,396571978,709039435,166286394,108864846,742328782,366734241,712718906,866366422,337582252,283769299,534295505,109047994,936506035,666000492,157266434,841992557,309011741,303173122,193140146,707429604,470731298,550369842,585154114,623416591,923962882,840652414,570962906,209603703,522166241,617514265,276471587,77066999,628199509,49469350,97315232,870414776,191037890,490824706,48083654,912429348,667617038,229633855,930014917,144926621,548011686,434069838,461252567,738026070,226131381,559438581,760597397,943902288,783723150,365616971,266457353,851167343,13765646,113477720,712420192,530281668,557855399,429919355,184559618,559384209,474744054,377889134,698681538,967728637,455202246,534995978,388521253,355539931,830285274,611395420,573537141,972955614,656333967,329141010,269685203,590616451,184994209,171691962,868151670,490733095,477170028,4811280,13189665,286434535,946739275,751770849,890109098,761705021,945016959,874461685,606874999,13777149,166154129,752102242,560866298,329869929,227004610,457359435,817183288,95949724,616899068,763891217,804622170,120677673,915749474,257055473,374284035,275985308,950102282,699133832,907054752,699856405,104352741,612841549,934001056,928025922,466812084,63377346,812103362,208089437,844054650,725319880,698368151,257802131,30795364,105128243,560361557,924067527,358741106,77144959,177332813,81384233,95239516,817522451,53323843,652359420,446116775,614000666,254768390,308130629,526269414,671092953,737122021,247984539,787029713,318098502,872512697,842239594,564269348,349209510,428589089,618071431,862527593,126658051,979396934,100362088,118664869,680774278,495686975,663795402,326248103,776923162,436071176,738932270,138854242,565570818,558761053,810787609,107117154,920789615,778333367,777663317,527392758,712144847,978518529,553836392,214075695,964021874,835795057,899936989,447378242,374542102,658617760,844133463,202858674,802380397,685579138,961086796,645804714,226815933,430041736,571533392,354848120,923777163,607158165,447357133,683892672,796684764,954886856,780596404,47466805,748661329,156758937,576215222,181561816,122599280,878622711,86977634,226034227,486396091,223775612,798324867,363242360,689846159,133767950,289411829,3466466,691175053,29226373,130707816,565074346,728837860,124242306,109472616,745571221,943473231,600691954,440785157,965981189,96039477,79551984,669025505,432256721,640602847,318609033,381760207,531457466,593238847,765563345,555750959,680538853,402523111,440801472,320203586,224812235,495616231,812593749,975962199,290301626,315083923,952904635,96478908,264666642,864129645,893786745,958544060,780310850,993330911,991381457,501133759,708777805,253585806,361315244,391930570,862575456,444384754,141665617,203157208,590385005,693355112,844267795,790349185,280007781,374320562,883709789,344027453,185551458,517196010,25142251,346445096,19144962,307540716,459810171,91745389,921314261,613614534,971420046,62533814,9846560,336900182,966765095,657156736,27428986,191610077,757612312,473420349,607593205,614436655,1178621,454086233,50280832,477729796,54330516,597187041,580688370,976619769,60662813,139284615,135931737,28632622,936729653,461295124,663821543,476903215,702725703,188889427,592798053,369098908,338283759,966541475,467873726,500931910,948488161,571441484,50788387,638731453,795002706,296083337,549040898,270291189,683801003,26444337,702642539,310903129,573998101,330488921,842526927,526052232,497073409,900467152,554271392,522672602,919730511,487028781,563958776,799402392,356861980,978131801,259234434,112720251,418365332,931280812,823768948,53220643,735712272,315703125,308963175,803380169,810455624,46338807,720056806,623828135,24978231,169216475,642514958,257899890,638378756,45336339,423961256,665456617,57301556,330444165,995749962,159381624,562230636,787794994,885578918,854975006,130726831,150077274,655335305,711896568,697707566,234551899,905392739,485439965,106305739,499217044,39719110,276979911,475837167,516429280,470060651,937911383,926886761,444023859,397280875,886577401,759338403,900244493,553963289,770890106,19670466,938290280,998140945,649268863,268743274,101057279,584547934,293382140,881669918,562742770,104630485,519941267,363971183,331672667,290276075,311285643,557622803,730629321,985717835,413668858,643420027,40552668,337419870,668345418,319302030,850098260,335865549,623266581,351136292,648174682,52774410,768580163,475617331,145416751,890684114,734925977,663224125,243558743,299584912,571969917,993621799,389760697,289195922,826652227,568076869,565483243,722846576,673334968,573681854,501772039,402447418,603592646,562252226,474658440,878484851,936194119,170889067,943705687,795290166,903450793,485831095,167841747,933749904,403551499,746860954,737140799,87241734,807159020,162562970,60881315,870091741,705382788,399370285,463514735,499533990,831007443,921751584,908598805,208584762,687955745,872735418,910348311,99670028,734849719,908783784,775280199,631417816,390144361,773844991,917102021,906905454,187277593,599991388,68978340,307317625,415647189,131747095,727643496,857135457,127232396,269981617,212263396,440507607,456849904,162165338,650215143,590039157,644633464,659292428,844526655,55609505,401314767,20394635,22059082,903911330,375366371,834322150,286356472,523502966,368144743,197929169,961955483,659069802,638634555,450665849,34943507,489488989,433857465,727658202,437092936,506133477,855656205,793960346,202926006,226506949,984962378,456105000,469774337,938136303,191425495,76129219,406979674,323401134,577459262,393077563,503335472,750871483,175158694,3174520,221248722,82830060,786397107,672024895,641880266,343539513,59746534,633493665,444054535,828903657,544589220,407221528,623821360,906135320,287937116,255989155,934378153,322584090,747813141,806951963,191867210,249473944,957221862,285078057,510033873,751038909,621468796,704429826,434711866,1184937,114637292,534380429,975343398,930460297,596669541,275056928,416006541,752022723,991680169,216378983,703281867,506495369,340521008,847189797,14497498,593014024,611551868,101117812,881747813,525620707,119555916,653357502,144476234,22121153,765468867,729952522,662689348,417928233,260885918,340756968,902055294,513859688,865665956,78125119,617727661,120747517,745391358,399265201,957858480,210420181,496129522,955852175,624390984,746388364,604843799,230476369,245204668,586144364,171811458,700744006,458245645,51691094,296977508,596443927,267916811,56177540,387881275,766154601,918263630,213083340,863482064,214704913,927248374,43658732,215689541,304266930,610452485,830157729,521916244,474408856,578364776,225777083,289171338,208985839,702945893,332232049,493612385,776880990,434530989,48894927,666439134,951057155,90958327,820019714,932656001,649699488,849686386,62477309,853883322,627850696,287955057,59357727,899030204,441320337,750445241,891026704,185571351,464827112,141490391,159487839,321350558,515241657,590816270,787151893,935311552,755407216,357527834,425805628,9420775,362387606,691926248,804007455,854729687,120854140,496755918,11896461,532770057,533303371,81081782,716829081,658265095,721781158,634299416,698100820,812581101,107422350,884199972,54381874,208354608,236253745,441072234,871894093,796454621,308595882,458596711,937264189,483852379,568301584,129711405,666760340,498900801,459474516,468913204,603932185,282476343,133766715,352329233,905326404,930137979,928439794,159884184,455941159,775350852,416072773,764074102,512026280,710138653,759580141,41552961,802602029,143409258,13887196,111637027,314056313,174328639,284296943,268642744,466482707,306636917,954400056,309954211,497386596,466559583,196532812,982533964,142853806,22336333,741538510,294813290,478101138,187569693,128775239,131018658,514958994,873240905,994433078,711988969,695509463,574937879,301818856,911862722,384788147,627580522,420671910,142091163,671666140,250784702,717642950,883920826,330179113,341172796,377182421,198913729,384852938,285730786,658974485,517264170,411499157,995345342,741294371,828324396,426268793,133705112,334531170,600109957,944436380,387013196,450764188,320568688,497562123,209006171,900575190,24405132,670522815,920071991,122092692,252889076,256827713,445260748,7260264,702207399,654663115,867954664,102167754,612196459,598647161,496100744,857459882,182048930,461677734,554228962,269705313,555779843,986119578,627098761,275531539,830629808,731959272,569761475,141743042,741074539,76902010,920747552,139156521,899906065,38483703,192942236,493001433,345032779,743907068,50721514,64665050,905514364,8135756,250290791,171164595,713002990,9997299,295077250,673863117,381408890,393049831,713296852,32411854,286379332,507544800,677593449,827245598,761449569,616359691,61088791,683084923,705062371,317223369,7949540,937478624,591205815,505007492,231995014,502091050,438995151,622457230,108597841,283912548,814916202,55179218,228256271,536751578,459724475,677906699,75906394,666584605,7944870,159846613,185176143,792454653,291238768,734518007,152017883,500807497,359077033,356591638,129535847,456054474,732488025,713887061,354674403,928824041,978676456,95472367,645378862,124591198,149306434,892836266,238096473,215188950,735060909,196607161,654416659,851188062,261493167,841229236,331994552,275948579,23148235,794367267,882434626,83742422,156496697,908119245,18664506,598573721,45858306,764043775,958379200,278098724,363519289,9009278,392064045,320539081,444049826,466410431,146943321,484090884,81784954,134319199,881537588,976801553,750438910,968492173,888194021,345521050,938415349,435493526,758066080,607759928,974707014,868256377,611310279,204912007,852003851,85803324,376151872,99088940,630852434,11761221,270566736,911963249,372563389,102326928,474281994,50082965,992349783,955872359,537807285,256834223,44811366,433256416,924500501,27789218,642760677,237473043,884997659,347457902,327470526,118051703,168540775,484189079,166729681,539236278,924945757,201556513,96214004,419931581,885603569,412432808,6312176,360152883,68292409,777968112,903453367,58182243,846027961,202680694,886212191,88794338,794650039,993087812,235457130,136162813,20496573,593643571,883037685,100629587,900937565,618999336,255711843,675485315,751079686,758146405,340489183,199561920,234653452,518457988,310658658,525131646,797551431,389176751,940827288,87999509,176264846,16544542,371260833,123575407,265926967,610581823,103677496,845982841,731171992,317242419,484814865,583564629,55803929,79369828,226083749,321192234,398076809,120581011,454582779,210719949,207749219,900670490,258543521,829288027,490323877,172458255,880200148,535906043,794637842,15798371,173375626,211683255,989007345,995032682,499978856,472112497,571987347,991630963,120951882,685383180,647884822,763769279,641576294,62702704,313095738,699606624,479904210,454138586,114215426,646462422,193374712,882545214,157873093,483597634,909891785,630126278,293161637,788869669,644958575,483030508,242921661,613959185,701740187,163116948,366292633,20231041,457929209,853872822,508268165,549601516,49526213,473569534,254268700,143184528,110220574,620991307,508421275,79258733,896997860,984808668,977705725,71219260,630080934,709780045,214059031,993993341,222690155,396844461,201409850,454315723,750028294,410533823,990737707,447362622,237344184,589503820,502023733,465731485,749959994,518494919,617447933,694017129,941290353,984864465,500884699,234672253,943897310,948864766,195481363,463739342,333958490,741227185,880061503,934605104,821429548,203645199,250687871,609305346,100874342,497325616,343643765,606192876,168669005,336434808,555250622,544716490,68498910,193518603,835534144,85873174,616308958,414740519,206994759,260504664,418492510,677202315,549242471,388904963,991150400,930528637,79881243,544296829,153665049,64222730,305349891,748427977,185969229,813490584,308765414,176530995,464716341,198891991,55907060,182424853,250132422,376081875,621720771,55929147,321512349,8002259,338264096,39396102,572951954,467540773,400505213,186103133,269200301,719538541,274328967,820860045,876598949,362991771,174244135,378741111,947406,226889517,410066913,214088433,12987008,17608131,431193540,351577583,520257741,293741093,50207439,415245002,249196094,920432235,907459803,832402118,420616746,980570166,661679150,334585029,910245653,154840712,110989979,129062512,304761498,770986607,870860479,640160261,747019081,808597698,363107019,404225370,270705244,402436027,356547970,146552171,238931355,732897932,587523797,286814817,592173688,782378498,175869964,516971741,702144431,680768182,24945719,194141920,831571245,792519065,314927962,666369762,44011986,679231735,772270646,205417852,915433322,13506231,145311443,368417444,352208319,18708317,594808016,110753066,721090306,169866179,806194763,384901755,125427015,974751100,614000868,742244117,932876129,59726806,470744008,648331418,129073991,658506493,815421900,981988799,41727759,35933505,426621381,572679501,740709096,501712805,560252612,928510931,851019281,668995963,496803608,99284480,635118528,789793114,471797496,216921190,745735767,9312717,435873593,95502355,224148767,728509931,115299842,745964974,418242056,382189243,580025278,469285861,368421939,88525876,193892017,160347258,335605310,206809512,909539456,522149191,153326338,869275908,684871357,472378583,996926142,787037589,902467005,218329454,694990410,770057423,27177362,862635904,8142402,349496020,617667810,375251824,6864417,276368790,35859708,838381843,15210025,205729567,327914490,897878465,941555730,115778256,419674604,944467276,322761769,892152791,457027996,586440695,321404986,726693075,85787610,970677754,379112726,978923678,574356587,111610586,800399111,716593784,420466512,407063819,988261930,410708381,602825071,290962208,162046786,73862397,658420564,762734547,356402596,487806,404651254,632991496,764109431,792584033,757555331,791885115,428337988,781326794,472441617,501735257,727507757,720447137,37671288,678147154,766381182,795266693,225810195,194581313,228330686,35644276,143191680,22591571,823263815,495782582,441515719,964649065,382298725,537471013,757422819,101255195,113773538,506677961,255164214,111357038,766144288,550088005,225815565,641154684,942445039,575769257,163524166,673803706,56661270,633770485,535464396,535464519,253051907,148709699,319627868,147318711,97966888,346689453,688008871,525726849,747682908,330877562,179955681,650941563,74797121,410596144,172737106,283930710,466169141,463728146,91780437,284585244,536266290,494337483,710585212,856906552,570254771,828560963,936609107,936277619,234125690,53057760,119438130,103483788,42548540,68404671,963846556,933173607,146308813,209970478,394524124,976335408,905687708,418740058,597376737,743896431,987142326,465131653,611867572,805940209,246784284,747171040,192019202,838426697,151952221,799527588,771674484,810326409,117574048,29072514,715857582,532153908,22801531,974598462,619975786,400711468,440940491,821672941,806635527,648830871,245777418,181497902,327809379,290129931,252962079,592197108,616448958,611334680,664173182,71011008,163569313,181740681,121732485,994495953,490219092,747859250,688322135,92519442,60040658,962314171,567498786,351322027,448981581,569579748,360254344,560946429,786876341,539235106,28811797,325860881,380906250,110395764,467446398,275501782,291454655,524399012,912095506,557153300,631615796,831602500,265485427,956663428,587104506,899207916,453474832,68099663,174883507,121683669,410171301,223618648,417460291,876069058,503884010,209593827,439380562,529329486,140187311,293179108,901230497,371013600,519226231,520914445,232467799,829783050,420766440,38346936,973861503,358018917,765005002,66142384,783324555,122818507,946370642,700379952,141707194,529804280,659433277,674969076,725778469,973475376,12326638,469794333,207246264,198253241,29948618,399683040,190023541,498441314,376830937,729440539,792628625,67621669,923540562,104003651,722075329,406678923,804682571,433302722,954283250,30821158,978802689,792329031,615289631,857791930,443051411,302819735,271703689,645769799,533390548,727617567,432489695,105539076,420803005,853255095,175465608,877129594,148958197,232561982,384636617,637162064,928067823,756635324,697556123,415737368,621227689,617240115,148699078,503186130,146438315,726237483,563009696,307890315,564349942,764604375,242364744,845958900,770213028,897378336,963285189,161287056,847315528,670745748,723354515,834018299,665474524,32268366,813378792,196609170,328113062,615364083,87750616,94330258,378052379,182735570,689181873,280625069,600756304,441990066,531549553,509357179,946037462,284192977,707771706,55790362,476972238,641345813,457242680,891007654,773722851,295786076,892435066,104731893,867785277,260656023,637076107,160542903,589942617,906195780,208536368,605927892,638611490,128909536,560782021,177583599,353495677,365777718}; void slv(){ n=read(),k=read(); fac[0]=ifac[0]=1;up(i,1,n)fac[i]=fac[i-1]*1llu*i%p,ifac[i]=qp(fac[i],p-2); f[0][0]=1; up(i,1,min(4999,n)){ int op=i&1;up(j,0,2*i)f[op][j]=0; int s=0; up(j,0,2*(i-1)){ f[op][j+1]+=f[!op][j]*1llu*((s+=j)<<1); f[op][j]+=f[!op][j]*1llu*(s-j); f[op][j+2]+=f[!op][j]*1llu*(s+j+1); } ull sm=0; up(j,0,2*i)f[op][j]%=p,sm+=f[op][j];res[i]=sm%p; res[i]=qp(res[i],k); } up(i,5000,n)res[i]=qp(A[i-5000],k); s[0]=1; up(i,1,n){ int op=i&1; down(j,i,1)s[j]=(s[j-1]+s[j]*1llu*j)%p;s[0]=0;__int128_t nw=0; up(j,1,i-1)nw+=res[j]*1llu*s[j];nw%=p; res[i]=(res[i]+p-(int)nw)%p; } up(i,1,n)res[i]=res[i]*1llu*ifac[i]%p; up(i,1,n)printf("%d\n",res[i]); } int main(){ slv(); return 0; }