1 1
2 1
3 2
4 9
5 1331
6 3224179360000
7 348414297354956334043085401797347258376901025074126347562215651
8 1788857759555832122065401249031168409829350986883351160165154295474849248762293103138613334538006716385373315366963499252477453813368265843325930950491743308180759938065672808453836131724108423430353999196353078179290654626211059500663575222487400475844848486785384836295591654495240784222131135234355240885462785201187335309181750702685337214479408269782880174037024879541401
9 58617955124043971328589431103517478750024637327007824844145626189777655610603485119311304767015892627697743083371637830637358484314581579790774340187509378094415799038930203329563275341430122293332729021884057386559382986117781365796903971639711417889951377927585386607186589178714002819888357209648259087648594225843870900877535464801758894601774260293883817202273428282332997735923548175760428856328722147953738558243385721152722526711564884218319462619210159439156886113200625309312507899317559762858301513591376859487191779775575081445258498788346405242481189226384298265539997297666510819511694580266543716401136625447929957400851117750269147726816570634682289479958536694096941247902824038691047733737370320250672328136456476304771826323634177664419329513916454433460512968685748540346891341675665300325701793707100613509218556110478873895134683643805514945882422269599963065411239532263390048615573011408974390566744174846936662850182795745186632350629480802014464837439901240625050851712486507596191632130385768277625283376841373725114843881533030269016074338345430824402982237274243112466573983661595987231421834493277367535725427254959748583979033241112021764027121618670092472688676926378107522966873411512878244929334890195753594245239835818503374629460958311652475777293024132957589648709162438633185052636748741940773421563567830944732352546801480589750685752281165819464197444958241543005391754123823763353989241403880164522190418279082471525333411790482232027113917745410704306903529945411493105905933243534411866624342711984348398055956363094179071533352665390029834003805241558740359212617698418071769510321970162822738249623745296225300592815934375000720930260441940064620923554161205817242976194756257268146981295457077878871665748945227776096243686238205757357345841968623262710354216964970199098241839301019522528550511060462115173934802158532131390409084736785669476946742296423016953489068344281028193196526425225524630598423993801594523092705807088273430487406956420940391294721796806019834739086425319714260404619859645769672914705323741989067431328697135235007710534712844662225864625698149026605454658945276136057660786971318033564798996328850826590266096690200061808310709744543865359371375083509390788872669674778033102184512626587748784572819889892717481136747314205005164647734569509325924553673999721265984506086009351923151937896014386397782081172037806468915287384633340960269219245411463140239676652971612013092676343953111603377799818047805619535210567365126427701874240116556685745999164032449178001339902914044054134130935877635700166170895558363458731168996582528150945520864590377238528
10 139394395456443650636808119688506192467390290724868192524547085016460163917664710603246084768443267812237216206241452377116896850513997670280634597808534098394973584224949799651889466247566814200817645511481787199631128120306952502329691171478010227656341167864014864545556064311394932619530827095628690254218871774856142310002442557453757674053326351754338685352786587594095815269659045401346006675569034248693127668438412855572654051937731969049466224025613717709864066231755158601891545642729106248707457898335552086056603096258498076353326978560225369898780400484293466987102801873271180509736589388059945676676255594921279334520674903501925163958148571425220553645247192835854707425233443171710349845500422669419969939111211575705153239026564473462065618465007550558164408698768816083388367518748779728794065420465049935713941256106034460140236374882629503526254473082542698129976864346929584855528613079662228126301945437721895738963238929235882729212062820647310841345033466280178133116267223568128863250291867847327997883709796381420061894694118383459703318670382483861727948021838215329734051568841571881910942969073469209463346965895368887314058273260640708996506208824287791669906194552562286230864232480468976228811429061422776441226645618402938775367826302844706365619802392290246126523002401260446924004877004517106141220875622301432194090091759908252482978376237922608252700505523161906411890164071013823908851708401239891381384856498320272779217877261783879494063622950773119043962788984475845237237426073294384764890170366730767972317716901846283280804789160775593558171188323148470207610848070274694948611818284791001699663902337697389739246239165127675140790050900353066526641442173082502295913516861419950103586676238702658320468265568422818418943602711398351368435833509382879048564323569366787536124636763774837613724107042235128819847612968458553026456363350182128201857973845625771997416787973391847840808751807761425918649473025839703218741212547189576413912729852440126093767048205584310288696330423805113743430397206496953730703811362132857801144334380237645612766784123897646176055333847947675570679260639471579893765812325516317779114145890959963599371964685023524137132905494925757888053448674861024046880523403909232460175286717121650980950777103208686281136781084681328152964254077778253229438023422439282141040516937563853624873540350816507884769085704371199334858235641598522871511524520309674444944590528452022892849205641068859840037216006443783255069540117648219849780903996416134925636766213002492589811925841309713242511257384163661607785431904743496656926013344030112207432978002610409544773746831834180863645184588613821676027928550278158331504727755538134298059678294371664088332372540167649300635666477146071490580299696938094482720722878770854906575397482642828158019141699112051242280383939083669459583569759980228600513261126568401569113277522035422982284228436796869150619703083878396870494510631667629152440572648741139723996052978334029936055049580181872653461224115471422417752813469529821199663956247138197643330957964534621241725799760968877179676323730690008728488928618231131017850835045465907306496903896588302632229113520914303998705877247143519130064761318169050945435243934564417450227509628703640404744246690058649267092201996177884824588056288952019982963278994676803757915495718932642291607490730268858810621139829429831515697769001435250065685185156073721823343167461367908613039245307156976722305590854364103479429661138179404577001667839302546464597282935216127936398246769832745044350552602861615789990422102722498056471719151997006029303568195465905727590988299653403356273293818484528312715182584413326710918419599090516033180650686725941561461969007941897444592111965256108298111620131291870917088976944841899688263059886937452225308626246073162787419364929230915506755188963152016980313117427876850869636198821697010572835465611575591755187997842841165019671773701121778954946502170890729000602867657296689812307480491445122009888416876336244557608467293013114473978798554235678176256713508212157822558996398085539022226340965153625006189626441872375341711002447285060004940370451460509584392106689083306973342917156454750170364857962850667356967325720164225775859006933575908258949739037698572984908670765526345835813869595533084213895690448882798162460521725578855512174580184980940408450814451876926129558058398642665503747054731979314741285407239112418623000076914639519848958547045078557856207077349316951430617044321782567394467730007459355173036749768887371260587920452838754480311477911720291829709280402639191994722456291352274828612456456614228469840876067647498717766932934951977963691574374605432217179754999480864873871826580292389301584470916741047891835077210954196612961817592543595471431300513938926205850274418223476546201844147214439544192635329525367064936026206477260215149715508348084804659345595713078000090337184351149761348795105503337196650865623821923965797932332596097041078537381530742469700262153056885787425619075810149018063402105790883696411374045432842334022709577463161671970476517081645979519618591657767078148561993529294699806998524949979215109983769545109988925358813391517133052137802973103518686868575287388791140062367551095769516887641935487487510332541991541706922053747213644835087123679055944112160690371869593581194815797928870853582600440291500608490170125099709140503937494575117827194779139033657273017003334943331768434115879189473234674579883352308311873478544470865789396886916325822443978578343045704510888919052747673713713061398132732327298100974885592455657771010878138759233207730439471749093267816630669023629829838152156796494181564283965836481703763606803038489742657484105353093044634399993006936357763409409181032853804653939914920297401892288444958182904357380308328864643008674363631698558699283762220905074547325474518345665317158054019256520512549571362094814957974629862657415713042656058149218296904792450293984596589426250262733015690775602212764026543822113320006070516109706657636063773496597793397954026174269494522587717465242908220506949430924181727477831265732805070342227238665243156686169731395662076735944892183438618779659152648775536687932414207126148140166904095858535363779487694686073477781018304194649446615109450999103933117372038860254316066074698124573257331601730647206228806272968898762321948752783166067360200009660951290133139589681969093332958948425938165914441819370997475539127448624385771865878030700974247262353096889608376338323780974029571632564915101559676529815251207741057297261061038428661560778849399906158356829775870102183743195425282820955652390838076393000405358187890161654643558691031299137277612632005045431643127626963561767691015118557130508658583159699499912427199875223308068242919028850263015502182354286162072707332842210753190566987691149110713104643239112440065389021387863320871891689273214920191724148768245009817722674650879158658386273455274946121348195903589519172322110805689631580147345171996410394131263523310791371864756502858608932442357158211053912536005224172748896633373477488681684029530468894226780520632681049050371245544443779476240473337723037208002667354198540331340199003880339449191074173147258160708953089605614244620210059884494545615493879303968984238741182623292090572395019815044487483051126709854538072519149761044376667106384362825351901146093638487732394956569263817553444272030053619463356832106268295186747434331934643321672094808403456365124161611251298178984120758243086129958825761288083622715324915838984827720852010172106413844869835668764669047520399961852353530708861084951986602904083161975092057251057057906593547501915681339763825735299777738309968251154294557903261014258743035130528243824924622876177655034604114253971235822368145056168741840458186206838652980859283006520228566310042960904748788035835827163848013545554038995645235737881796474691653935306052918136333048669697775192893064937517545756939080259561980899386500666360165416466719100771344814270392123284685057861663722061862607367141184983851683445584948158064312141663815765237681328068563074218813822927567435264580876500103029391307889663685270996371878144334201205017047669112993421480037920384939770186875375003746330119296292390794214163708515160987649671879739538837741183576681412068692812351510280517692703241523457239975437841105813923058730355848265990356759357636147395656864521366394453070178601971731573741740208583451586025038130694278981657096712991965480075643555265672939615280268057017798548200464991813394268036345640316848300190222536346955169810832260252698131865403901693832268566566850317773924363416769070938823366273190986689265783670262968593021565228544563271810636432838670943736086058369235580841184206539104821647869448598494938382839964701256830081234984708416421622226547644831724389545402030584519492302477912456027177797448348377506726409202639527188405284404221610771088318932988374064106332010782891283174179967516998264476224812769277959222829400503626451341373092057348630483798303931666886594539936756791932722533430153005676710420742193869164463931861176360700945258066987841976141417027336778372839289342999036638407326865847298036223113291640988231278469258938757194827832932558262124584511545554564264094206387816024907708698841560993920421050271050853703507723477416024723850013919531586257015427909269988294907738858364909880085020635913187850092113704641490880553197513739639566128984997249452637673668203027308382490714955945932814866225626676711199996499153948616877088920030366784767078705545577819828402543574547081942271599515602386565053635803030854754627166641863934918082487503838588741908444128124284880857732193039891605539477789287816257119951368705691178156259946852396519258752420555263049027030301158511056440115991644911671232327296087614667170444160058195998736907793660349773581128313967157548353582365074559802710915264440146010347723205804269493850046160151658784480097427865522758269911675774462566858818016053777432631458278940571728435055807802441640254133150583535625411117388812909078747827781286999656073318588751196279708347772243398072956038715345794942277081344494608265402094030649285895603219853767053515833362071561887638819902265464510856782215043173864110199265179507888341965173748435165178305820185275097092172780995282761404491095914224098606869591838483461828530572055559428632021629329169551044460012377151888987585507745197513259170019597605350223627539410217757979397447973854509395442278708919193796533851729042566760473375491499166344542831060775087173828378276661148666880732771039618661247602689555387623776946680872043493541323331993523053151657969840440453476568329244328316347333046012107757979459799926188996051264048138652615955541342780110887691044175794847474871022206548840139187638037668018864228987629104853270366674991770677524659212479650024817966375936139158199037389150674929153411336295407281652506931534685362094804839782742234188031597857319996833408720516189603361544569219857153400705614986352838363473480263737635564416750643532101926749204095579038670607577866336417397221029146990017028864508738449700413165484665182149745554665084184635842261633992113407170203250766246319864804636362716893170142399509207424683946381867203509203087588207312866010054212796013011826272687417117908698609188914738461831850654424989286764688695557872787547739970512999453157406652970603027941832596358254297852165756689604770316475784430812452024701515924307390213116315840294769861304463822928304978727808743952853384011161133200667548592979373148335949952112079448598621656987265936371834886773610775515191403068084300826430434231100612371858287951705047909022919507770488671900920190523700942089465057733129328136560285591683347456456245681006418798056306629886224067398066108073598130029735370030042728498824784979930264839317895822608546412213611472128542548627527633856518446716021410851375208438854922818244691045054270108630131874282418050184860628528688000079552870434814511494650598932052409940921583088146671770705567026123035538785943314363803878263148705474272290335543032175276190001446033257033970610943164670111974698710771048110412932025842548672658349707192602210894602188608646346559277357635337398825119119444878733044781118543183992436485902466951323609452090413034077904049741498296067918034151828754663964240596972657064001301523255681514993557024234416616147848547021225493235370663063096482722456889685038141105326129796326432207097129061680721812489923305577488685840728409547971207955251904722818403197694278750376152613931442455730715080880752200699758764288830427044696673327336486100230814177386088568033349035466337070059754822533866669517295786348108399628640921613598527879665776997123176287767058318330130883753635839604095053880108869854015324915288301454824870489051279261786500486246186336848566367020947257825110703132520011370135467764333383039165197310925866435273853654456584542187842498801529256301975577589746490149424762817396684896887011293054567286381778180158639134882548281730699141218977325104623904295941975732052479798074944703553805806602717327057770495379016022705978901330884195940941050072392281627317487362568001525098590726862319051515346760057553963819618677461407726317483380442520089228631840175281027889844782214200223832097063236252255313397724101223613098379742478407445701696373286643367888279779769483508611182157386861329108258840067319003032514005601303042031393963686463071046022589823051955011913405317766054018307554686478648421580663200950153890643943284611344792932977093256758118472008628870629318376764966755300038239104574191452850702899994701758142677250294305427562911853678446369157073910216946026061898135727736689670781692252833184788948616736431692336710597170392108863849551592228685019309264006838329139944098084077244496126023641833185174500132855923687964719069415841419755042540158863208754360223557841010553753577141637854847400646823428888586336756136403910200497669334239386560620284160021426483214748553415224702651281698929736263063049736141153745900118524304179649397739080726777118204912587781015431370935528087582001010455688343518674715558953146688937078948112965505258461380968671012934879990843653592734170991999734398634393050994097734283836137043710005984162328415265501394038793580354230953002054747571213228881584394165356068271137007647878098641175174646913225310446229317252723216057087621668315269246523011640451611832115802628061558815033033860305352444358400372491194121043244770401191565530392240543714288384160755090396710500663749863101378763225619114643808323606130335187311705757313699220078965385856969544072017310991705012059260829632627223760242665023390810785498801654830472174447876618588286877615285282671567007036120102539594390176358664959828052811922711191157485286134495524959273247443785542403224275585654006347400934213451628713723569933318150552049792430981735455023919238933227542410700462133044625243676944555310372221559449069716920284960191210271909927752361294413193024670781452707478877666603267160809542979830193166732614423764232899747004073401447061036628471909211187044502194790578778968603722221361265526477943485044537152371339006285675141363936210787124701908923955584770984376707119285518721420408293232281036446656874124787146105389565680749011254824898465075587872846295618955846343179832108293486358387820307415953177425833183195112184041418597816788160654012202945753054041990591947843694809930774635332179779400012404141932940692075672143280985471839132495162952532550754641741725925282146596432703056104239085262334111669923164773526861570131935098645416156652727436693142844870623364211639686393292379056246903646593118204489115414245806215682409534483029712914008983604241488028159057276298421816134333173191275022690032324832229533277922821103702908601589589949933624266097059650635954855658884624402044435867818954463846696958402015959848368807543545042135331950285685148017102481963122536437665232945638938692911416044136289601950500912852234026798475182413194919127509601093460699050420437592028341754193167366537875264421251608737417515095962746955457676456016960275303443644176929719106034632109231227741661812825960470331749875405387638142416048871822278743301714563562554638647101834186423743550046978696455322398855947100255775588322989832368037633290991584623481921923191087155105338179530963387763621905958222030572330422795401663913045993693863233637179121127200957041296303878457073239094177067266250188122261015870788861486586323566591290936281711311809495240058762574947731561417563740117404585004618098069538232731499447505429655316570611429446873636952520165522227053723417929763177882723971153378437557815755490479942467193426649053104125784376043147147163101283600893834786416917097109908500165848479252041216989396541667280870763448956506545092753908527362050096865558514608219995215115687373171077546997402778056949527568222925247114563079767487385430275218326961523325353610630395451609102578935870423001305571294950759247972216492446611703292821238189874260246859870537691892702778517915894805462516698806161177975231663939748934096034027600214426343580427445642338289287019946364919708016933070224163608224519057213508053151006268812365538070257985586319406756827073014082959513416370108060788897913793055141663045504016620182024163344142777955544805916638785077223948165425597212625299147995645516184563719068877408838422827378745160026053324890281615857170931829410048952052652910612361208935727044080903815238468801686638259231665981831366390376808514756020327274812211535041281778287757193351421403853870334976579739229300670876253117825514490744441898966989808537956736566257868803075031513855145765629282706643785059712693854771568804619833674528621682746640404718163513098443448305991343747648806840062650694297613165412070752230159682303949481599045496250640098375298167008560178888271171847198028217393626869496137074465215970518062893772147145024955178471317936482271315677529036737443976667207292598983177713696405913864922041165368376132588087311040171785976430826030665227100008489807852680117906262912714717911898140848560186743834831409309393287160637185399853153616139981706698601042713027576669985444911742373726349848149379756450441082486679020353689975924800257263769907318643092509964613459157515840134159229048699653081773887207183124806667659882992850864260929741263674920326299240512052311809672647248755942623426422622047585904306130912742326389227851548916088282464750553307998833872791979555002939516915880697111459649840475648859400357458625550103016989803479715068252310376205743724509294614436034912435138724752446233247715411499785702336241030594332036854688754146286125921462471270296249668283417301189456770571077328667999772415914262801350509550833307638837452626123277332121477151328304904081687234818472220678603015544106118400406998790735051804476462555283332960311691238268944003363970231923371689397974393710216773816886151128398091358738337110849515691280218074370135447495358508810995877867900658086557018985469093184028603323491728183640006478119142345526795219123755874405084505788147241497407732108154518655594280149332956415561480030895925199122794149337835821651922349626003241359109171118941031781549241681058317356939918884062276733842253233582435828531598138532739088624954243218674885828200264689710696276143735797419644550257233188178282581474680083911240245539598630097152966877961674639734981479470718936942745540105647282263131235215338850720398453195336615304325221263310278435827096701747967763823553297047305864067198100262621405756522618929147472357904746561124685904104044085998625814327609536136733742687908773512998173122870569629843201322070627129899229822707549237172692591860863517490988972202358713160822344863577830760818516155770244033530626003354559332355933773611876767151216424892448775445436892754626471589582053346076644073907521805462946676658883426989210614353088295455306327805351506086399914132965124046848765683242723145357053748176843148440937147116416519270134996790712047784130634938846695103768008603534519406425963309622218051565305925067968607436590661414637877038642628576892830325913092597860914978288897232443419009951004519205133833440443547833215156672395599014723866004573536593877686579021005665009196064697954472177426154626742410712981400407084255147542545225077952610039982143816331087131968345176810073482188742533631561829671754057526823537517861476836788045600079295631119318081069097127622293080021285525542378878703442162927266589835060410209620544906895946058233971764908650848662988562244275182044380765853777041692189082477023690537245901612112111678772717140561825322351987554408620721236579452973872301424732652010726972186851417549652490697795863012023974310609565875845509322989156421685519932575822530547774999252649965909813545440292139693109525095262677617235739175304967781539951753961150297690463597216262687836940041235415137723593300171482227615479426044164924935268401244507780761890918846172391999591155838835524345635907200895642559603405761