#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=1010,N=1000,MAXM=9000010,Mod=998244353; int n,m,k,ans,f[MAXN][2],g[MAXN][2]; void add(int &x,int y){x+=y;if(x>=Mod)x-=Mod;} int res[MAXN][MAXN]; bool vis[MAXN]; int res1[MAXN]={0,1,3,9,26,73,201,546,1469,3925,10434,27633,72977,192322,506037,1329885,3491810,9161929,24026745,62983842,165055853,432445861,134561665,970532063,782642970,383346798,375786032,760788514,941889589,135500411,597073725,925911867,721044082,314473497,373371351,109386087,558766678,778384777,199329313,658463894,459050774,81153944,505830796,882689214,36694033,7529024,547920964,763801012,996860713,733538409,213757784,922474542,590167628,914009326,287333612,211915446,876260598,477829033,672129283,770120027,101353220,453161889,101843900,534525776,869556652,809790628,29352481,210318725,469218808,932567927,800701076,410456213,308998093,273199126,23921405,821698035,494461180,761239877,990122842,610857431,640640074,907444037,276210176,303200181,399173394,425886055,939861232,519961857,865530183,571151674,831703862,893273605,784988692,333680302,954760935,15042533,48712842,51299643,943837740,464539471,809654226,687681607,696396101,287517708,932912106,51751364,292873612,971444018,914118828,352721944,302399019,871179143,948057764,245077210,324317400,803917705,243032439,229350472,55116344,154437647,845074771,259809955,683623437,294863983,203308825,319743118,765281781,996580376,265415649,872800940,506278497,945594615,933136770,57322892,637068065,657376209,938539080,366953714,572724840,175537656,597254887,906471817,702650188,358946701,685614529,324257408,534611798,776241839,787441425,570982201,891793414,40485807,93061304,967248346,272806804,768884324,874537625,534355818,84273069,426438575,614504322,255997723,826068570,572634374,587420385,580798447,935562641,788820493,553249578,113874074,270753016,664901365,658739508,179138370,609051083,114032782,658060481,715442038,197096740,288243455,494179818,847388385,355925756,829247133,354799084,674094413,548884037,731846168,166987054,802757580,315593446,285615690,824439488,757585796,584572650,266886007,754081783,76619107,629516833,126436570,371780645,236392195,828858306,238374396,853869993,265468393,818222571,945841031,530828297,664432469,499801975,906127892,364401867,471695453,621675627,535313698,266474360,825015874,335653187,429080949,447619831,904083239,248750570,801631604,82093096,287767157,470958615,504609168,800114202,411979711,463050536,33378754,744232499,420634877,953281812,315696860,738003135,391968220,419945934,831958400,7618196,45495813,839824140,901153342,714478062,940453902,504985407,365438904,173204475,316165214,101028200,634882158,104810759,274912501,912407155,850781080,413369023,930924924,467870560,642593790,801480525,444987215,894493039,964027034,446902680,270043299,149951803,751505635,253219093,298437038,224418456,537715553,716278296,266219521,387313698,507344082,357963566,11281005,561836933,451411703,343250700,678289798,893273143,404838529,122593299,563887431,774472414,170336651,551128631,117498367,64997779,604757588,807311515,931494370,215806421,166171957,184959225,193205268,3655679,34004322,530842393,427004363,483622414,490766315,920727756,139030697,222813588,984064220,643954319,769926643,311837069,452340541,620452155,559551126,357515980,109870681,164088150,766377943,906525321,494401657,653819983,623094605,525780811,573126139,431354228,194694142,98487745,990532540,659659357,554521907,136059116,114449651,728878257,120628901,721117773,225965660,316239103,443427088,455393039,803698138,719349240,878134018,962621686,104868784,533481919,863838420,794556235,989364779,114362737,226594467,314674028,215934345,328386816,759741721,933625230,6707735,8867272,866388322,290308764,395781875,681280318,218301640,108842783,378663071,569774801,415918074,844981611,456542433,194410095,464461019,876274943,520723419,393347591,74223908,655621947,550504502,308105403,994728101,923178629,265495950,847662961,233223001,754687943,841471571,389232609,559970993,759925491,658295722,90186512,357446547,476029889,58396640,669400130,895550889,906991168,603144230,454373458,862084369,339607393,565170710,176281831,599162030,895690047,636879687,109380872,874859704,889414378,538304412,211829528,68089865,932495806,616531619,684344595,970993254,299372990,61578774,154269448,939041802,743747363,448716156,911921549,909600673,60229187,749006087,151405707,625666065,571769491,778485120,143126940,402755254,572369224,328813222,439480756,42205321,787020816,525650933,198252654,882237077,81741261,619018192,294398875,297082612,662657319,824261708,76872531,931067102,774529444,503655627,955194937,802955478,332212791,945498542,14936717,110085491,340378814,961169067,646875913,181686783,299129364,519346812,866202078,295597081,446241895,896189711,950205099,368425661,976049446,208700389,937473263,187340719,781257650,476872331,284972602,647516346,200029472,32211201,55882393,453992502,944963808,660391959,589931202,216839913,271953775,23507535,644029782,604770656,559148582,848652235,540518060,875054878,292463734,410948056,759359545,506844448,37090243,152747875,519552217,604462093,689185049,253795028,648337042,847001406,204237792,381830614,177002632,617163152,613969858,101956843,441054572,723025969,731661527,477479349,708306700,664256758,316339941,345004505,839156454,416941911,893600799,232990467,734852329,835796915,499243559,111832754,732541393,883631746,512278840,835787823,363762021,985830436,61416267,123258443,161550512,67775993,452787620,116118467,541364040,803077465,458075979,746298779,134628266,358179247,344607225,483282281,720519324,908835103,467104809,409450031,595186698,45748538,874313278,250478255,214917170,71620268,352882013,694658176,148112972,576699066,241287819,460504636,768662226,104109963,53900917,79814943,229988222,699038343,48415341,800006513,67980099,826151704,263689088,662565475,124574108,505267803,982962503,628841757,268739929,904221058,902876242,718802368,80564615,171692042,733868288,632137670,363483124,856677212,8546473,762424247,474428583,46999191,435333074,800039493,48619976,504711342,788562805,507074583,21344670,130815585,520570048,731586132,275571494,292627701,997310311,494567577,69898522,878628899,900012583,485946372,881634636,810085036,847364178,329494910,330828435,44161808,560488521,160233760,959050181,801614215,609920387,354647145,105265799,261884107,283609879,793636597,510193340,557463338,803236504,136081481,165655965,483938113,534017419,612076587,290137228,230673575,346560453,698361696,528988106,446018270,922142353,550071381,182130033,900923910,336874669,733387806,115931108,112667648,220351743,544947395,409365717,669389012,573035478,994674446,304413202,696637609,346911464,461653520,274918217,833328079,170786857,561695931,284894755,828909031,278940673,155107070,480768701,877731008,335243920,486617358,843597013,483907046,482323914,711464274,150623711,730493877,28054544,319284768,864541080,147332406,314665771,274595467,463226103,25049435,426588447,887559690,503533838,152661313,11933432,996349998,212316827,100467131,10573509,772475635,994564815,584886001,502160629,405730768,681545792,573690489,905582143,876924523,191172945,621534762,528579182,670987172,897951110,850003710,304579477,363506694,387240198,813086,16886138,853219484,156543214,833418076,784749438,399395792,167057752,607261445,669205839,427558937,664365408,669081806,548213401,384469532,421261818,511449168,377352178,147384703,116600958,306016225,10399472,139574407,238863828,238097235,795832546,793721035,870460529,387920492,428553886,170002691,622465943,782929944,895637854,242611548,502430062,608656476,11495042,794717414,119212963,47254766,991217917,870754737,504490857,406095666,240551805,367315430,964905847,737936129,664703635,87776966,256564702,1303312,382606284,420548934,425351659,946372678,599010939,215882326,775569119,569958132,847304538,799709651,205577106,119260108,756680100,365000897,759741413,760572280,212917656,254798205,306467640,174586077,235497668,568321081,544049530,211239772,380983018,516091393,336055383,826091906,813765929,954785775,729751184,589276059,745937910,66015152,280039920,433480650,339154114,219730213,589777920,92597631,766980553,373297776,675797683,303376383,527626745,867850057,254371483,245137918,182544970,703746743,734706055,110637367,810715348,755549869,320505349,929841417,922036321,738791090,97628390,155410021,572989202,974088290,172092725,179045764,640511972,296936256,353922063,972080467,980331700,801428063,87223702,779762881,898127205,204987615,290550814,815850822,458884936,159303613,214269510,873992131,193948252,271557128,749887785,239946827,486611308,256715615,353681279,944619706,764272101,911118180,96681252,625344967,279215019,206755889,329964246,760960045,910317928,883042170,563149797,451578357,81927546,371377531,190062841,511015286,969147252,650510587,485285802,809393758,952744997,68540283,283495717,846697892,389611301,581140107,873572859,80861795,442800941,400384799,62285351,390823750,322402185,997304083,516619561,239751006,575270622,234846484,621573137,617992835,206889537,946377173,526667364,415453095,283348273,560148781,649967831,893738587,40971327,239843953,703408944,921835350,165002048,770202443,546691167,666775889,49201809,664937568,320849543,42821416,296279768,825103661,140714055,511625949,228605623,837807641,617317683,673879233,723787666,136419065,956317541,283007817,983120546,854205681,949933276,736467705,737705661,433120922,471089099,799010363,565425613,172722428,500142281,426016929,971022240,876788553,435309649,975805913,590706069,986485664,752608957,35545981,875415946,642254012,149183459,995704162,227522856,455518182,679850536,665671118,478682555,91660374,435354927,496028421,614222717,469624492,38864636,131885876,328381559,796435935,949036161,825136731,73546751,482826372,554845006,539778281,778873460,227364992,757244714,757682487,938918127,905302654,467695708,873929275,909893021,365595949,201320207,267215434,658027619,824026118,48368125,780934802,222927606,736052431,686905458,724504191,286287611,728452693,92525511,927255691,454283499,956900445,464296055,524721570,289092002,697489836,516759600,276041858,156116115,880051122,864793462}; int res2[MAXN]={0,0,1,2,4,9,20,43,91,191,398,824,1697,3480,7111,14487,29439,59694,120820,244153,492716,993171,1999923,4023679,8089182,16251760,32632321,65490672,131377999,263452079,528125695,60150685,124063210,254727989,521040924,64167658,164012265,390633211,891136998,976839063,295546365,186623423,417005060,666108447,548186027,738214560,377998973,129752985,745533054,992690737,874603040,512051667,160441924,716425713,852197800,282129426,692410701,486248942,619668000,562156188,222454529,962031998,188254852,477132394,413709193,904608421,608286491,193455356,617040199,518282294,348209973,265638307,640514200,243686243,867402006,646709736,694592302,661409707,376246867,984785073,656461768,502575953,929856457,208116868,370966922,231212107,829384567,861656057,249648223,712530800,531592416,584081278,318414633,519456496,176567468,890801794,607176999,460221497,126027086,239416974,493842959,235925230,937171581,577022044,337053102,802766471,384278991,375131886,315081445,928459087,498778093,542530559,833201789,259570466,497041469,108369089,55309890,651377590,661740886,337511439,883098669,530816253,391557271,886420948,415904505,339285646,155524008,397028127,996540396,790777328,58688050,472919200,979243389,146887050,985690167,208995420,379171335,140271582,315568638,282195454,211655055,101805700,562640964,813865260,324363210,708926738,533716048,930322671,534275532,663516500,707979904,254762723,397638514,115402800,816480050,377563237,971761482,224886881,531691490,167756468,736683513,258519361,783523715,721302599,266271584,290350117,426902915,610314982,645252536,229443745,665140122,231980701,993025769,355755035,814774919,2462994,8412713,755906216,361156090,680138490,170933673,847675492,859403834,348250621,295386797,323154601,139872967,131622365,205814834,936701563,836364537,14394458,270718874,648349338,608501635,973871909,260101021,692828180,180687013,84143809,991422669,704887604,748227531,277963787,497268026,435916201,591249679,123049862,843896663,667520918,631983644,477675898,63799153,424214924,548679984,307935332,631632227,786217999,811401242,593540990,410791646,535473715,245757116,347441553,945818485,714145740,674789668,272757968,962616841,88021989,997164437,899660625,944630012,99177550,371190553,26954542,653115441,398172554,660328590,559400123,820733028,672327806,939677979,742227371,642525657,333344098,464562968,634653611,929024937,271588048,410795463,804764848,121796347,147304500,574695530,318118965,593807722,217624947,701160072,865212083,418551722,14621148,157286440,81271020,741900586,9131209,249239498,19728606,371042448,118494132,175959816,186794383,479020305,274756136,908875242,330459378,636666512,76749553,290270714,29927165,620003784,52959288,614035711,996770367,834017562,88406970,940512808,833795275,224535905,372136082,986225012,91992450,97158588,146586268,400568164,976832180,153440822,631111756,891870067,915068300,787376489,985795498,967764313,472316982,429568585,288391373,483633593,836649298,934466176,428736247,581783522,315308432,764325566,372149470,444061361,579613575,684189126,426573772,134311814,295962977,423635902,762760974,553885336,78962579,983923460,682281946,931604961,114122277,868684986,341402138,492562296,644560192,400510083,172366337,633715270,587194907,892770829,195033211,803410292,747664727,767898482,355190394,213931469,886384251,9165171,527374813,301985800,818773558,334226270,88978123,537130216,70517590,189634168,841138771,555432229,440391091,130306843,299779768,757893672,44569842,22269685,542106657,675000385,965381979,71817886,394126902,767074639,380598099,722252841,502502276,2878624,901054147,658091555,125459864,907031227,178258900,229297712,499581595,570796419,116653037,649268120,730544656,880693003,586302665,831332079,576560335,143591640,11200145,392103580,790067845,946170635,988253765,808158260,547984783,221812210,591780881,287455950,755119518,918427839,575164207,397208640,956302359,729558826,174509721,122978904,893683124,27760781,653766539,918376403,697077718,102206912,367523895,215297015,930766944,550007503,451771606,420511358,209920376,988913232,269308851,912629421,857894961,693265887,682859304,13533822,996823919,588695292,38521843,174015025,275888923,169899865,743400587,607251036,666411664,521549154,87334583,522814188,888163618,157488973,577644259,147261590,389942160,244926815,312981418,902594897,3879917,942857572,842630793,855662681,33820935,492124982,684633004,664533255,643701076,321787077,689465391,752718544,239750653,616720617,150865347,726650586,528203095,693447316,14506147,715073533,816966096,345609234,412059114,940941508,108121619,265715222,524470383,210031616,795165683,177752298,309312271,317432705,662583699,637359135,568435971,439833896,502310089,240660519,630210083,946555859,352534400,83156222,149200299,343755921,173422055,254441421,883522574,98148808,384439927,193967489,375804656,492158991,900879650,883958282,754546892,316717126,340738296,275091666,834221484,353719536,382302189,714847843,340596067,224101254,573363832,765041573,184458760,181004869,950122731,920515360,103789225,297427261,533819184,116721739,478983075,342437929,253851896,506723686,826982901,850993004,281524777,335124125,831885825,794510998,459182041,687826752,176913794,51778602,467661612,766841316,530565422,585727093,57037633,352261760,821664957,525009741,930912899,862585536,723965664,325654191,405207960,439286805,258383018,399657898,814160997,156685589,232878088,793007249,849373329,815964510,930256966,603310803,507593960,172663703,98592195,845454892,395173076,298600082,559470881,239492558,262558627,933984197,26190859,734754981,93679201,901012200,296314255,482945426,969399921,549790919,204860545,12796496,733944880,390308131,514909581,287850611,276377878,430370938,173327033,791374560,42487074,863536484,277958415,330085107,439694951,213400899,87711685,941001237,91526259,488653873,151587126,548632854,723016181,624598439,226037161,849427990,698800404,971709330,492556242,503956609,72328055,298512300,360921915,158441460,578281408,10170771,895734006,957066061,220032417,758148545,17429207,16160997,813634401,711478797,787856466,6124382,585360199,256697631,535627155,606363592,344935441,439654360,781776701,750914143,722109618,599889140,476441850,569066621,249505418,378724543,23442892,805264924,746274970,268143556,708352715,124499436,261092309,14154383,702681924,279500777,119605078,162409080,482993766,919743344,513777277,577044232,534288690,950267449,834960135,35525254,744258367,409019646,344419653,496060622,686427,732395324,730758662,267484771,610203245,832630110,618685557,605476224,605960951,585503488,889511108,239213044,48618257,495934156,679262255,903051276,608215430,960012499,153113458,822156840,193689295,194510121,971593260,852332287,744003327,241867058,855994997,745501399,934358190,97687934,236452401,771197353,326874829,960226945,54243480,843535094,338632388,370352397,213877264,329062753,680657107,978241661,70870487,769096870,302468402,611739162,105431215,725217928,609263260,898511780,516033468,943661955,675000594,727502504,335681622,837624899,508109104,391084838,865305285,356630111,251763384,39404807,234570777,783289003,576745427,13683763,49977725,295150360,816517603,914639908,361467247,728410243,220700549,488850318,317706056,28342501,548233933,30152053,822031350,732404520,808182682,978253719,425252326,764212774,252496553,501149294,187759375,469088200,937766348,966603929,209329826,874155362,479518350,235055622,746437172,502470551,20315216,336352734,260127812,411240830,314507677,307748879,371923997,69992964,711071860,998108147,901448539,608483073,497114671,652416995,146646766,593613015,607751167,594534607,826928106,971066860,317728397,702027451,482323481,424941199,758772950,953301346,329517269,972731857,590966162,575131890,606613430,376473395,14534129,841834757,216128649,937218173,173443695,961866466,368422845,301475554,904255646,292936064,811024410,894500091,589663920,731600680,41290220,480126470,733040274,190442399,450855902,93590789,220063354,385738026,819940250,825835001,918970477,236807248,184734169,660141865,589377405,135632659,204845221,589066074,560181358,636909760,105995677,736578893,211970692,202133226,748180416,146565471,22551157,199407716,626455013,285059648,557573067,289054929,965356358,524017633,16040454,760277220,605758087,616465403,687577576,962947463,53537654,222192635,138280801,671611124,558054382,841107747,315942142,383903790,364874574,802078984,905525799,936768771,895933893,12311146,561807246,5204332,448068515,432318787,377419783,681882078,243004375,824961944,380899510,757014701,117705277,171499657,608472973,415480036,895132402,989060327,508317813,938895457,394420234,423013848,521760614,275687357,970636140,228628862,836097356,568801408,832310570,539780878,28268880,769988730,896843308,739163172,725864578,358194916,223748380,801530683,711992071,791658883,565526113,833213590,457971949,773813478,177494005,541374709,687036641,24372431,926175695,568223718,334037820,226570560,86657257,77686605,887340528,971271032,506371142,674022135,305120517,421675814,172180439,144148673,370478905,434361944,971382745,540371923,861435048,792816218,538928617,693439029,734691589,500968979,331122177,635084875,918252374,489013694,604291883,458442081,439333949,299973652,168211693,572340550,471312440,924723491,726441322,547892759,390910019,152297618,841924716,686666607,208604370,620507710,816915026,415845803,21366825,214212296,363722416,614481406,240972429,550714048,117504727,205136202,404974106,843545852,731467677,511035715,107493819,378596734,48845279,597540532,72005238,682638073,72479728,888884962,105823186,820497090,283346095,561820329,85662680,735570592,638004706,4001952,857859400,859567715,879703363,788304820,615931163,440419564,285774528,210428494,500482055,926270206,264162622,500621694,463031468,285453562,798441099,157858896,562505251,290409638,220539846,801909155,852911449,481144636,622913425,42602204,786430113,844427376}; int res3[MAXN]={0,0,0,1,2,3,5,10,20,38,70,128,234,427,776,1404,2531,4550,8161,14608,26099,46550,82901,147441,261913,464759,823902,1459287,2582615,4567357,8072082,14257631,25169443,44410452,78325112,138082349,243339192,428683436,754961473,330948082,343083303,124014552,255437967,761567678,444634666,465929692,384505191,964462574,364565309,716624820,954814151,48443269,265971989,336464119,759067912,649461348,381804952,578764524,636219548,990306036,50773311,784635969,675352409,818810094,115419427,654353487,947585638,858697532,860355580,748252249,867936452,159719219,879320280,459922470,869363308,820308532,562479760,165746288,908845580,527436504,940798527,206798460,569540743,386179728,490265547,755883012,82075130,161407329,932136351,985084494,335097768,949537893,20522109,225087249,647377387,158615541,228042662,346374796,357951816,731972822,323154939,275720863,832722268,590528910,372413726,611272772,813270000,384542187,933046357,659396619,499068725,363387290,705726585,457358817,299471015,482871040,486283801,785627091,926954853,910139361,393637337,870838195,41368468,450207220,357745362,777428661,745957064,641645403,981059215,303897124,168632986,150391998,470508972,129683706,142380404,997385167,560513988,214507010,391053701,601766680,25807472,309863774,663469367,979626851,11930786,47219891,806178681,662382541,393407762,841771770,693035542,587628759,712677006,569365738,439215784,484124686,984558084,274503522,281517367,854573626,518317104,857734681,263821960,790967858,990686029,871805267,774553414,316227747,605097261,192150261,490939701,313965167,642032704,693070516,602995879,930151258,272252497,310910977,693401773,855387485,249207651,761084193,475681948,209720038,818897438,789800233,968765983,851015536,405794605,692944011,477442589,75918114,418342334,697396170,562559832,813688920,241784628,676122415,847401819,627400796,371954184,617520685,432531271,213394976,145965943,637398047,4497218,302652995,685569572,307192429,909528802,113215625,214424983,729518480,454268691,990729016,952189688,660686050,346404648,261817506,100158558,821139679,604171518,822074902,996064165,245639780,918384389,661457735,323773878,648830706,55060230,943867948,63536942,973834110,149109034,441087359,81176062,296060879,750240755,511247119,590416841,667580224,525846112,490381486,906449467,149924234,964026603,69896524,785987940,313476952,216775094,57589127,667565022,103284520,657735271,551617326,281792308,72821602,549840023,846141595,887127414,687306744,214843801,716566597,873870594,301351175,465494300,578936749,89255049,232509760,217668007,720734555,149686550,914824197,216101024,597475376,639489525,573831274,525934929,214041215,989267116,901985039,153589611,127352533,859081516,335028013,381424673,320628381,71683264,711200221,656961770,167060195,863117369,187059746,120232985,327862047,576059977,209338468,287080056,322330246,64968579,970673975,576257594,498589129,20921952,997107724,980560940,371209779,650407035,189635242,267472637,440830839,416337464,715188033,125009577,673668734,331911855,230304985,310147565,344823149,738749937,196447305,878025761,932790754,697497591,486405682,866018913,747219614,575074614,531531375,956283568,939769042,159520377,20437139,208983640,628037426,526375956,163532640,415653223,710910749,673388374,71967667,702082319,548414048,528411111,813261216,312749405,606132169,644483649,192775499,472586690,719459667,607073451,736061722,801262765,459078162,53493643,631739860,53926218,93524874,711888377,896877388,635115551,57665659,805729706,591725069,265082760,973171298,335194010,249998434,486126565,693300066,134475770,678121875,517171299,707387935,394521140,632556132,430504241,507473514,952268479,449092916,806674363,93088662,154932452,324595907,214829902,186867882,37855179,583141673,350874401,669754309,122401891,986330582,134557584,76625892,289252552,592103982,211476261,313907588,442144349,409365318,749947627,221391632,846860761,657410317,867388463,537397127,654267176,41146514,153983580,510513602,686176518,383235173,734450322,284652688,871032525,359371328,949302466,396470066,4396931,345706843,668955340,366149868,362313210,350242962,978639976,568234312,379517470,638014929,804766884,159630817,297613077,194060128,347183655,846908178,688482053,74016725,647514647,449082484,203554334,22260334,583899961,61420214,563866942,366961712,949135272,531338078,632567828,271160385,179628140,45672732,244668192,10091284,268021435,604253596,232800833,243471469,254721458,9200001,910392196,483487046,384449630,929897694,15105116,269860823,295885190,961728646,365273511,155502479,464343946,786141690,468008531,464713054,302619621,512333163,145618558,940669523,69569692,21239114,410489148,45126306,370219806,950837114,94343909,965601409,666501397,696325921,803382209,923150876,197086800,74945956,132582700,442718333,139838724,335237059,651087772,151962144,707481261,680436419,291109677,857857127,841145529,100241071,932728795,310105861,203491573,147361821,933105598,573620003,542787305,277630337,598198934,306230530,146918071,283750200,279784121,671897383,151649025,960722944,298631875,691154321,804301830,878947824,67516869,142511790,599591663,709449578,50217584,660725434,740984992,301912445,710806478,480132606,356303781,365905493,83196473,803460661,765612077,333611127,101948087,553669888,653652830,88006637,619591829,582569772,953100123,42263643,129072753,681343497,205070859,295914165,435337134,585110320,203313196,232892442,994381121,85532638,677458411,659752409,391447964,856946659,704167057,719393794,90094859,436537732,272476820,238432292,449193794,780621938,8696141,188856434,310744729,105327525,910359884,515239754,534387413,261938003,609956012,395632146,449989012,24315330,907518669,67480630,986505466,378077420,135150350,738266246,878773055,173281208,380708801,660413637,481557062,243315209,591794648,908044726,880131246,342747224,22908323,787924578,411668009,775512332,162209402,909183925,616964039,619100610,846105773,139662345,812324624,542440790,381816864,212707591,733071053,961473354,875837167,322747929,2106214,624240436,907035526,596788540,651790993,759689685,351246632,623813705,572159311,815303884,541903346,642099991,218679575,796168137,137597024,275040159,906070792,951208130,245314668,692419425,313344427,645612346,358940055,538525158,205275938,223677423,613112400,34797947,336132590,733525938,306390857,835497000,860666986,574874369,268007551,346127411,665114483,442421640,420405938,108366984,136406019,525613959,861608198,114946384,509744478,164690295,945456677,647136890,933795284,997367593,959821916,937518239,245773996,923223285,282509916,37749967,607200536,502083326,366869975,812177710,666798859,767084973,465573875,493926058,736697068,555440229,424085930,694047809,740045509,95343842,246988986,126193344,188798603,572207964,245438491,343154913,412394414,362074813,687471999,94583526,562140373,86615301,769979051,450990199,716673321,685899191,537735630,469673811,880804328,986392041,511668275,22729465,571666740,788736963,236485369,616802612,356463279,262362225,283667507,89792703,83484837,712650179,710374284,422154986,754168040,336464959,784897325,971387773,922213682,69697459,24688760,148018391,421534234,46352238,224535139,556212180,73303518,682440667,856118375,978938652,668367025,972164605,897319098,889754063,893929695,233913934,936450865,445961275,571716738,927542323,407035207,426058816,18144758,627088609,917433988,92845187,14097476,836701649,856577032,977138162,127170882,409627553,137839247,734174309,949706270,255354956,453513481,711991285,494772585,108873268,79964030,566876425,828709930,857604356,806519941,624387081,691489288,995228124,745101440,436572485,193371848,13725639,655693802,196284334,837381619,927959989,97146738,774559493,934856315,418068339,453021104,425779897,594982344,996775276,384048447,702062390,912310379,737824014,390320362,309508964,444068130,799120435,771401031,325641862,122858914,271469241,767813812,989101922,107791927,218801730,169352096,300883369,573088345,11462016,665896334,807168522,788829530,179063201,944557232,811404606,736175185,795131167,733979931,665364580,714973624,78016526,5459869,124610978,695792970,124938977,901703170,453282980,430075975,686113349,75004768,945817495,237671262,387791526,1918705,153412649,508827396,981985628,542266212,659153027,739514008,391408575,709700788,804019002,333502402,649443899,889918318,661166369,397887823,536072682,162998500,523420523,583098200,304565732,209672468,855131793,624385566,578039264,180780928,174836142,306059131,942363896,638689808,848805056,95955057,280684635,706024249,918013669,493187452,545824313,370413400,311811679,274838922,705950309,24104416,286487935,499443294,650515091,246708377,413234886,459799968,53486837,586834190,408576167,637069589,634256465,575143379,868327369,47874829,764633220,565649185,590782089,770964880,85211279,943803916,98851300,812897039,471779284,702576847,220368056,155343527,210641784,847703368,421005336,345485568,39102504,213938945,714152813,295330861,110445742,699817352,666377273,883588655,24436206,192174273,826077408,429262051,748531387,364389500,402175807,649915367,716132436,100035186,499939891,897573494,44680981,617496579,664848236,259611658,548053713,82012489,528922169,757893294,956223886,804831356,420033806,119760890,757810471,79441395,912604946,162409535,538746528,533610043,443895679,350106359,118184,757884011,741561268,265020103,958320121,348313268,366904257,660769319,983479339,670579258,694710182,376067774,76257992,489647794,645848139,263538647,121096243,758197797,544508758,469526893,56024515,106167869,446501134,582658907,385447560,933244703,924426766,460289758,945845542,533265198,771348513,323088376,962767049,298034500,431792911,926205574,593698171,962405021,403539867,850505354,818230755,159983387,875816689,905699072,114958483,709979609,741794122,927850813,394265123,210379612,130873333,228311006,493579893,629852545,692018237,685476287}; int res4[MAXN]={0,0,0,0,1,2,3,4,6,11,21,38,65,108,179,299,502,842,1406,2337,3872,6403,10575,17445,28742,47293,77720,127578,209210,342768,561131,917910,1500476,2451158,4001723,6529439,10648199,17356589,28278426,46053430,74971606,122003157,198470205,322759763,524725744,852830409,387483949,254564842,661152716,944926347,652493266,667455733,426101873,254931158,925080402,554902600,53998185,482926045,872333119,399610346,396616685,571726178,270448845,6296730,343722895,444525777,685782802,132976669,87171935,819527116,935061057,111223449,726838553,112702931,307647808,110284465,682817383,315248035,50357963,412639931,196462589,293883088,646832658,621201684,519553169,695015617,756352056,138916078,405556318,129019185,745886013,256518346,238357257,93700789,876546662,675221300,797084544,492162410,680713044,482195332,95055891,374031662,150357481,479859003,169206155,700210862,231254840,283509924,810729597,874870283,3797923,91004413,551565282,643235506,520000225,127655543,460120869,706805396,594940590,362189441,610911133,34440071,231522434,803224147,585297737,604388008,130450686,983162388,212024105,690724724,11280384,360783633,829413205,546283367,124303027,914977390,441745773,374612066,802245523,879350509,346840832,253142084,4772858,26431766,864185602,455062947,638598179,570949103,613290430,349174476,451281575,930748429,632841716,336908693,426999442,393904321,753939479,634730758,200971339,427155083,628727478,400423049,202761757,414656586,658203660,345315804,848674457,785455918,783378475,316650253,715356613,361757417,710997257,160018676,155965275,412190871,805371196,231424122,909301439,158580736,325537676,218789289,768119627,574085132,308864057,483235775,760684582,806351580,310490075,4466263,943526933,291361468,851974278,775837494,163354000,4589151,104808862,534817654,187857481,923992711,33407684,532552221,221881353,39355608,374721509,277681671,839523920,285519613,555961577,648487803,252904762,376661809,698208053,169557274,791993988,763776553,711261705,52436777,852424828,432655734,54167765,647427998,831116076,667462194,272932680,65761484,973921826,319559277,403412200,433800820,274307220,506694760,220957187,915395443,784469404,245449099,268045660,882364382,841276921,384622211,397311379,700148686,134858928,678945830,125263235,751088755,378623635,223019206,128167398,620631733,709800169,485260493,633512327,367372116,329076500,65234473,955007927,214813409,243354401,735343694,830058303,553399131,699151209,967718173,62198450,951500193,451289497,670325957,932509320,352415809,891264602,146125326,499965259,479690199,932104240,91187508,326807077,806451858,443769061,433477034,609129974,626633979,62146935,64518739,233258811,867109879,718222829,76335991,529182130,692110242,232696928,475367007,287026689,104382676,581261044,734762654,774969725,955712607,505685741,753520969,119323123,756389030,230421492,584176378,944987217,54448492,797894152,280439619,731679488,22858561,642689196,231324686,543757920,202139470,937495241,985680344,989445929,929609718,188809056,891528704,206361139,639585722,756043038,942122996,654168258,86069198,301975706,931839638,309672092,800165774,639311502,501508754,279204311,69550799,344944920,647511240,524328869,139198414,351697625,896068229,606466707,344881513,241187531,11571431,219096616,96541822,919883617,650636979,658445236,815301962,265891475,761751777,232582842,808068804,969400172,613376120,4644748,825523286,640549893,808083004,156422184,454675452,92906943,829656958,348669192,452740161,412546700,294956851,237780748,587971648,680357308,533442077,317335057,321256907,531249888,23703430,266290491,643251656,376955863,492679493,516606577,542093712,830602087,851105468,339097068,670031820,844205586,478218964,890209343,197405847,654103466,990585023,322088839,92672352,122824067,418111956,378935577,944320160,559799928,536243073,126360317,527358943,501941323,97533030,914573863,606146113,258454459,590741086,631974853,378989198,133014835,334055532,715263095,508187538,47513338,861741218,522835329,553890480,258886166,828334837,245728663,985590108,66933908,989121099,112703521,433520930,64495164,36720700,595195800,139575928,584295664,433530748,126325393,559419236,85786914,293495915,983723583,948065868,668604531,815985180,794693959,637769256,845629924,19457560,718085374,219340229,73356774,492417466,365342375,110173537,659061169,21598342,199806343,805147202,907461090,119181768,184378959,729850638,198082777,968346116,369974591,859224208,495505660,648537622,505764631,785727249,713524024,976441778,516122421,27652634,415709009,75928908,360273351,365306833,248486685,600680253,932601173,583654243,460915742,404668673,628008199,282615634,694939097,240906824,36577884,974509030,557853650,711431447,342252342,119525829,217519328,329452166,953357474,177897483,575619763,502900173,127083640,382358626,858960383,634100883,676734178,332207069,618631517,500120881,408591,892965534,819717712,782624629,363408168,476367966,133572353,791785528,66949111,715870777,685836103,644399390,94449506,162664348,197666884,720638056,941058068,111109568,346789906,538283600,115037607,53862765,185921537,167907343,273437922,580648762,613626195,591071648,166874755,203356930,438179323,93316160,760393057,821901371,735191689,960887418,802550468,801483824,541846962,332051803,315566840,646949489,557555883,331310657,532647280,466382208,559428136,139222922,488371556,737403636,259852929,512490236,880389701,885215482,752038894,150108343,453143838,302193600,94559220,359177381,550462260,691662999,408387736,986262820,964992457,304208299,183276962,127191481,562016763,124696213,653826675,191338522,341633338,364640828,308631931,13433021,809332051,955362795,376047807,20365272,499618427,528218119,75453408,296756850,397963064,158101198,463552798,20866647,66685887,876869925,406816729,326623986,751755820,656094774,336038463,730543629,658152338,851741172,422128643,559971452,380478628,42675754,688761107,74415417,466117255,1814112,786267896,232591644,929009544,242087938,879691125,778571776,707764320,836940577,276899189,932706218,773692380,65207512,337768287,772342319,172352996,260389254,357185359,649635288,517621055,217283226,636340283,532667386,657720097,997813224,831699258,275854616,499604787,601931523,171611026,259874505,776905567,635094747,89681747,546632460,90432310,68865047,165338836,490412349,983982603,330523072,126819481,230127878,348168316,117939847,406791337,677012038,222222882,13258391,861241067,956190042,509088983,900056755,701066796,377703379,419943710,393316557,98203397,754146510,869239718,735712830,406629762,914802253,330811972,507048642,461920447,755575906,939109815,360685784,168105385,221714864,693964671,554413794,884191330,938050733,878244110,732997750,27379887,308252356,514689263,689182986,672245222,844559520,562569113,194583084,150782448,811788908,986674815,426011636,425866329,642564413,106558430,57039582,365340420,531127957,702908328,774540274,59933368,657170298,890515813,880009347,800507828,987132748,195341357,861160946,340254086,118458778,312152853,626392998,157111084,305093669,202106792,318854941,600150022,484292295,655662632,457010263,985462084,951939325,648833509,83634725,300303958,909537428,206181423,288965339,324650299,667211949,796905725,16948353,282451505,513267570,810209031,943632279,530737742,873093339,640004643,601211744,799670381,206572784,454382513,985961248,732085723,533223291,406099058,852109819,271511018,525668316,401392823,872475035,475025279,814192108,423491033,641996480,685254440,363628856,965052742,260671848,574337689,220012411,250365037,911818247,522795843,61255862,856458623,295412779,76301870,199978556,633263898,993108057,966817983,403627313,742154426,804237845,653216604,351337391,125685525,195356516,295033816,825108968,709471224,497894320,261243313,875815170,654765717,38646258,149882671,645527073,373124167,233033528,960006277,146336671,114330596,897548827,495548477,77402433,405922038,472949246,663786914,200611700,886272252,901482462,386458517,452154411,630455883,525712058,65127024,559092345,815980243,583939675,67239336,680642903,111255162,679185245,410508930,108107812,961328092,303329185,175264022,682470644,375052078,330991459,966045587,455934802,681895641,16080602,464518751,397191907,87251015,275335041,595324449,313542311,476730915,706903425,241678350,379022343,864664993,870795169,662341726,814324906,542601659,451572909,742884415,524112237,457028994,95730382,683040387,675209135,350500156,300293240,320544163,816035999,755420601,604433870,79796874,757377752,462236128,15430315,471948141,400067821,776260002,697188039,404985220,436913452,492531245,800213691,904510567,987268057,179840783,107810638,750006206,457101542,224110511,398728098,979814086,840843172,985812809,709913212,14600977,832471052,209923080,821783628,110891881,625264375,151861325,277042375,790665829,372256607,101090333,457328107,89885199,986172138,728812291,517947755,182157265,297647245,180206220,932113966,125158450,558818721,271773743,205041014,92175786,164572924,875890586,2699004,553100312,557946296,309941617,880917179,980257812,103210126,775019232,219947468,998125245,673826355,818824179,22193344,91437381,88086177,333768246,901005278,568373355,904336004,983479723,630399420,67427020,192427037,230464744,380282922,295747308,538674957,369312674,85734408,231285720,376750269,813902361,79301290,637114435,93582917,799095445,859929375,413777414,556360455,157859799,873652893,133418346,800935561,702830564,434577048,388229793,493790286,767029109,130086314,676184214,745963373,195203578,429083823,694576425,557145862,986341690,352296736,706042969,56384277,821086166,733118761,15651828,178153676,587413702,185570900,73276118,895606488,375004412,837947594,361507110,227764086,134094325,827561446,917331054,339095136,512198620,313459108,959919036,38921985,982847444,481766512,861011404,809837036,972357425,902159734,272935804,244853710,724190686}; int res5[MAXN]={0,0,0,0,0,1,2,3,4,5,7,12,22,39,65,103,159,245,382,603,957,1516,2388,3740,5835,9088,14149,22027,34279,53303,82795,128460,199112,308368,477251,738189,1141163,1763165,2722751,4202429,6483086,9996905,15408673,23740677,36564512,56295593,86645287,133314909,205060794,315328593,484760605,745041902,146554839,760402348,704567449,154643483,378186049,789942031,26665263,57434008,373982108,262660265,224701580,626209334,691897223,21736362,913696854,940078556,390801950,631013182,898511422,883386335,709609884,831704060,293566697,260461958,622336972,912411676,859291067,434661633,820486471,205496574,211193455,336228767,529334671,884622078,47135125,650674785,165433799,380944629,885841493,415923634,744479033,791115124,747670450,268542380,432810575,99589400,988605444,289174012,273367737,538641922,412435131,200699097,50304525,452118057,596680866,129567387,116241142,609372428,987762743,651803229,589049154,218487248,716894262,607725923,127962160,473246352,678563393,223818124,237425231,880110233,118759245,9267444,590768945,993793667,838575877,838918293,483200478,922335444,601201543,983510017,253690863,269892220,325054274,154176533,438127052,610512756,896403866,824406980,810202860,897059190,487997082,730776082,262392220,89425081,224886580,847047945,681345965,492224868,802220116,929265319,89363401,702334137,651205699,28799973,152924417,966602743,55247545,102920697,69594037,284760875,586488901,686247115,823653912,466906173,221138845,873617144,133106213,480024186,840629488,686656735,214305706,535032382,770240950,318797918,606505954,8583844,494310071,614439090,662264521,142949964,723256265,60679343,986955629,134458043,165028482,671750700,97617889,730260567,59972086,8541548,719294836,9353965,752303832,745640623,961306677,592524561,496988868,468728528,274789566,93206461,729597590,960840394,893224478,780576699,976004879,703395901,5182349,717533953,869268273,473946105,290204938,451687292,117911522,401608083,527256959,404346474,794017926,305706955,946506867,320689929,143197022,106297959,83419128,81203855,565425769,656308721,656892316,230812309,767169996,220927492,312432620,138709156,170008664,330693319,343758944,918411740,483579521,744069577,513551949,815025858,868042468,130066832,600425166,319772201,33786261,427920964,229768643,97172540,401228991,243138109,580350523,591863660,796366015,616085336,126226744,399609415,254246874,142162650,226413916,572712260,459050158,924054320,32532195,273760789,984581281,179450385,583142983,893594001,441044500,929908595,449039945,314091569,35755374,232437679,428952738,135458728,55339676,511369081,266112769,112432026,421347581,838206107,445541770,121484808,900261985,946586135,856739339,470084110,370187098,49454992,256487920,449914456,813666394,77839189,909944023,392938268,168573568,180336885,968866036,178231577,613092287,770416432,224271247,744440130,225736455,290582897,121689408,746919536,381911623,293856897,118148215,225140686,775156673,509888515,706280979,608352902,362831774,720480346,314636851,37837435,656101428,378897647,640863931,942914726,639872328,402629895,293323318,653203358,684050653,704489014,456011589,215990272,480021783,244748430,219189175,193165932,291655395,858819876,592121940,210115792,934361086,659721546,652991407,337511369,937436132,455697039,802403521,868545475,641941130,124941677,940012166,527305221,208110379,77414943,307797793,177832158,611175442,594816197,525697715,708399850,325046227,815441798,210959625,823622390,95877447,837605334,997326102,685988869,540238103,547757787,116897176,216669362,945824872,888438721,120309157,332735842,475176900,658024827,148524913,169376683,667090358,385360899,816368206,856281982,347325758,18627497,962242444,733609517,544763454,519250549,242628376,85935322,134914209,522967349,730335094,800400281,626738101,464526714,380080957,53341071,323497501,407838038,203682930,560898992,643612838,238462528,739254970,442258727,446824232,760845562,576509351,178827681,551373016,979563600,798936258,509001967,657350529,610953969,120397839,931003841,314390181,285863383,928951315,138659784,678655324,394633269,775375951,917283706,540526874,140029917,784227285,73177330,738226596,829537739,710941978,90325055,965119504,585256394,78721598,247573441,43667912,624512631,320458642,333522913,586655273,594492840,193340553,150724093,81132299,77518761,978281277,927376380,388527004,834802287,450018317,796423278,797992449,740481723,257858727,55268548,660467190,12793815,709761636,483187283,77983058,876864584,26307951,954276450,779884553,253437724,97184405,925797793,475511184,441938386,583090596,597134531,660432541,629005735,538901292,237720657,365488637,388947081,800058010,463625455,527494291,776046867,721170080,495905588,242642668,215871565,19102645,768100720,719377747,125734599,971328789,776340127,55403793,746519540,952651604,426683069,102524293,326696818,565481522,492849934,436443408,220528022,641415140,8222754,577966968,365087993,807036585,721299792,177879550,826642075,251939648,465107285,389361103,315866304,263820301,641415707,57917901,807489334,183352817,315773555,962976177,101549508,606172880,928548399,583849878,94769968,345226912,22153096,185282466,861674258,951158724,982234110,549610895,550987810,956736442,81489243,491014056,889011072,925573268,903883002,387068613,985608956,608015579,233203930,867658718,11262919,693862640,602289179,552232535,447613251,803373424,797287118,384586132,176319027,537284611,372195438,669522827,955414298,949791746,594011101,423237327,105623769,959506004,620950477,899254255,904789866,412145840,549288242,469582517,795756966,902375574,966305901,192154176,232691984,312283774,938852779,455043891,901807594,752680552,861849133,875529583,970650602,178029687,665745064,38610441,743185009,280150206,878308332,264271039,568677484,282443823,179789508,956111300,981285077,660423031,687830545,607567233,746097956,679407335,618513820,207992114,48816184,673293698,672949362,453331626,413979177,168317742,755449388,630721114,718954746,289205824,372982781,582973255,977748700,444033194,104931600,665112929,305934787,757281292,378120762,67567142,531181035,84975009,346130965,935855363,269421344,494677931,962220106,514250127,268108090,35423354,194034678,726331627,856502191,745407889,831584473,690655359,168547717,117016557,230175511,888280494,409840549,304023227,444818053,484978957,41488123,302877422,4856708,330311595,494600660,895110015,263929320,63510865,518104948,871209240,954641276,761505061,379343721,976618452,950268543,826203635,687227200,884864367,501051640,451920712,61054397,579500766,822016198,975665765,4127992,904981038,427710606,259178711,836586199,882029071,411130448,870970748,63255976,15331271,994606421,219568405,407586710,516771009,734775965,203171258,447361598,792120049,575471242,100414836,12074566,985397483,359147979,593130707,814075748,540490108,536088858,579316237,913644952,57782307,913674167,156379422,780082969,767329926,601422092,473148663,131376627,553184507,884387585,564033516,854355968,929805887,358536106,598080309,598235952,662986479,20726306,899858401,148473744,291167272,118973671,919133255,868728960,671916191,696575830,293299510,803647147,675508598,452920378,606509192,111026569,304427071,882425423,937315886,169448246,304435115,817912577,457106191,149955938,23859782,678047254,887333359,622801482,148970576,25998291,607687403,282299128,692684521,344982729,731669612,383903854,945358307,6335686,501489825,201583707,844295470,739650360,318850691,252358295,506524425,463588346,315390830,241391616,452867471,336326783,98494903,695926772,317975130,189548456,242411107,450739633,40850442,778282409,466591191,880256679,799454122,439600730,847534735,853828506,772228183,904957460,329981518,569640364,737650053,988089827,721217755,40950871,715023754,413644467,955195260,954459733,185290427,30747673,684894682,473378169,29131841,947884610,637629878,209386667,303555773,505193748,575166693,223041878,775375979,283521769,948312450,924275810,857269649,239638692,211100308,722028320,687176020,709066224,573585553,327956779,864439874,124179738,624473771,929988294,96476311,635287343,846378170,302829196,910917966,673041750,491670607,451193179,427702717,69816644,398325553,549839460,221324179,417736741,525551983,370570500,613195470,765135274,930048122,221975677,328481972,677126509,452550617,536848030,534363492,463727564,31472936,994587700,87600138,324792235,350559546,47534270,653217142,481336640,575827957,382528961,339821289,436284850,795300980,941459322,53138790,813937175,160214437,766303314,881917273,926582574,553692206,309660016,149905493,3883843,294656080,903640101,609619137,240786533,955287213,485142529,383774342,67874753,661392281,153914184,422809209,238432450,616477054,661414040,43593739,148189825,201846075,154825856,118831527,544796967,791156618,465012264,779905640,246762142,182811844,147556355,796686371,656091532,884569537,146754178,55103348,147509930,389759546,545324520,531938867,762640276,336643316,885109690,451534902,930431415,151716537,468814686,412427903,112409561,81963005,955456976,446332869,646694270,149929878,118566776,959968592,454616160,232264823,524357383,219958225,462579290,966286213,933302960,714848572,430164391,30453488,313300776,347826337,245212825,338828936,560828626,948318030,8109181,917716470,209430148,299455395,872684137,138498985,473551510,248225573,667471469,662192872,385498086,742454370,232783022,225701622,14530989,318700182,84885450,547968029,334077192,695104517,535510597,348102546,42146494,312293797,527194582,95264904,552518319,208987742,279026472,167278747,875940366,119316102,343229048,569408059,737315398,897841635,361735897,397213378,51571746,33565296,819016802,305551242,139406148,815809757,210609610,586408400,816019369,455411968,851455792,863904931,16587713,843859839,845142165,541615313,11706688,874606102,984940542,226405876,889464438,887198760}; void sol(int m){ if(vis[m])return; vis[m]=1; if(m<=5){ if(m==1)for(int i=1;i<=N;i++)res[m][i]=res1[i]; if(m==2)for(int i=1;i<=N;i++)res[m][i]=res2[i]; if(m==3)for(int i=1;i<=N;i++)res[m][i]=res3[i]; if(m==4)for(int i=1;i<=N;i++)res[m][i]=res4[i]; if(m==5)for(int i=1;i<=N;i++)res[m][i]=res5[i]; return; } k=N/m;ans=0; memset(f,0,sizeof(f)); for(int mn=m;mn<=N;mn++){ for(int i=mn;i<=N;i++)add(f[i][i==mn],1); } for(int i=0;i<=N;i++)add(res[m][i],f[i][1]); for(int i=2;i<=k;i++){ swap(f,g); for(int j=0;j<=N;j++){ for(int a=m;a+j<=N;a++){ add(f[a+j][0],g[j][0]*(a-m)%Mod); add(f[a+j][1],g[j][0]); add(f[a+j][1],g[j][1]*(a-m+1)%Mod); } g[j][0]=g[j][1]=0; } for(int i=0;i<=N;i++)add(res[m][i],f[i][1]); } for(int i=1;i<=N;i++)add(res[m][i],res[m][i-1]); } void slv(){ n=read(),m=read(); sol(m); printf("%lld\n",res[m][n]); } signed main(){ int _=read();while(_--) slv(); return 0; }