Skip to content

11084: 【原1084】二哥的宠物

题目

题目描述

author: 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1084

Description

二哥养了很多宠物,而且宠物们的关系很好,每个宠物都可以通过一系列它直接认识的或者间接认识的宠物,来认识任意一个其他的宠物。也就是说,所有宠物是连通的,不存在孤立的一个或几个宠物。

二哥时常担心宠物们联合起来对付他,但是他听不懂宠物的语言,所以他想知道这些宠物最多有多少种互相认识的可能。

比如,如果二哥有三只宠物,那么一共有四种可能:

Input Format

输入包含多行,每行为一个整数 n,表示二哥拥有的宠物的个数,满足 \(1 \leq n \leq 100\)。

输入的末尾会有一个整数 0,表示输入的结束。

Output Format

对输入的每一行中的 n,输出在这一情况下的结果。

Hint

此题必须在运行时刻得出结果,选手程序会经过人工评判后计分。

Sample Input

1
2
3
4
0

Sample Output

1
1
4
38

FineArtz's solution

/* 二哥的宠物 */
#include <iostream>
#include <string>
using namespace std;

string a[101] = {"0", "1", "1", "4", "38", "728", "26704", "1866256", "251548592", "66296291072", "34496488594816", "35641657548953344", "73354596206766622208", "301272202649664088951808", "2471648811030443735290891264", "40527680937730480234609755344896", "1328578958335783201008338986845427712", "87089689052447182841791388989051400978432", "11416413520434522308788674285713247919244640256", "2992938411601818037370034280152893935458466172698624", "1569215570739406346256547210377768575765884983264804405248", "1645471602537064877722485517800176164374001516327306287561310208", "3450836972295011606260171491426093685143754611532806996347023345844224", "14473931784581530777452916362195345689326195578125463551466449404195748970496", "121416458387840348322477378286414146687038407628418077332783529218671227143860518912", "2037032940914341967692256158580080063148397956869956844427355893688994716051486372603625472", "68351532186533737864736355381396298734910952426503780423683990730318777915378756861378792989392896", "4586995386487343986845036190980325929492297212632066142611360844233962960637520118252235915249481987129344", "615656218382741242234508631976838051282411931197630362747033724174222395343543109861028695816566950855890811486208", "165263974343528091996230919398813154847833461047104477666952257939564080953537482898938408257044203946031706125367800496128", "88725425253946309579607515290733826999038832348034303708272765654674479763074364231597119435621862686597717341418971119460584259584", "95268202520385449790227094691687836722278710954949736428196756305746453532341035148366531266372862653739009088659598082113309304400438624256", "204586909944926298207861553173799965921067126517774603507480126827588404754232387878919170016875623577048105576068684204467114231315623298308706926592", "878694093745349914731889727208157807680003171098920968952145189548012830636076748530741378813207711246134152874638123892704663922045456803250047261786444398592", "7547924819767483287594694542205326068855891655862820018679189530528628155893698967796630219069788201405972928386025644172169109953194652176102437455457970998547197198336", "129672361263353660216004848405397154497075914498088480263529787446798464815868889966259599220355751574955667311875199310825316757090836792227021420332597263591744872066219249762304", "4455508410978470003213152055317479855991723332650114280703483486331017198541367912550307040027205813596014620050254013798901452927850711294962075802234712748298505435020109941966616435621888", "306180206751230090930313674296749763317292930219833760674864513181351793147422958983304199997791891477494238067606067864147691875149221011750587805454462256284237767964756224079011437145490032917741568", "42081087200752140195116730773102052524009718837902621183664949269856744858385083976643391056195246283737633254986683196506525739229100562028667655727478159896469450443625002559600024194689577683162985133342982144", "11567161173227696466220457283329529101751379197153495724502457893891478829937149071434453800538222228465001645119757350054456753856800058471020811256328606811309950183460999195585736337722940242137574318489684508433109221376", "6359114105601017351375465630036218352726964545083913061809864302427743340641476112983635151514041188995967358659226381513838435962182371853731281705837980150384424607870600516842502175922529566100381861494213531965265765000213275082752", "6991919901710702396948942815573257427744311018004588489866790612959056357721564695830748688904669995738081555372234543689358610668809196548322563461899302515136978058611651369187392760821440875968116963440793130046454847480988052748303630065467392", "15375394465098365435098131065240195173750887603455691084898736566282027607324662718653380384318359771738669872579070523864682029424324656980343742654131923883848453279046887366030428581980234722002609397042921130626427482776226373410811403774539364168814821376", "67621699984704009571087635348261788647460730411971168452281282746962798999895717916292043207408657855232972628889146834646084600650980317820241001687549180689983916950502853108787655643356237905731863505593837387547463783553663104052737827256888296815897621036524900450304", "594806763388137870319868932592503661181879874998563369872608575294390559331829154567126246824792929668641338543467328561106071308881273503814138669414317911219402066314092130747535752627679688399993515689603622744525243838714230998285264232171322066511990049433899384262102238508351488", "10463951242026625501784363274596214619943325701401522513836100192928357652762255136769619473700702276949844553770347735730521468871772581157963359677917896206658361141741863952608795675733168160935829452838892433190712974942475048711118429563334205007874224852816312589287727030417085994911901155328", "368167554019320956145827247050509963076959450983143444578072117098399777382502455552633802915095691807005512740224345254318634273382517137823997743877511866703540358482988273801636313118482363728678083259725882776454656507629131210255280738244476783496709369751571318821222548711309212127848471930415455355797504", "25907488423318455274080473672019976083009208996271003791416218114322853582878049179546761491016196610119349803222490393175612695149120594742502991139032865749979736985340247224801444473477196529096332604358326020598992443433363048888842556850935198901353471923472154386768107635993449205071378228596636214817388982756553261056", "3646154850293767810262810894999553363628589110640769385457986485984919161321600546344826908488589572223649058216506920510786720770519258252897810249930214560211056122090333850686659187132094273815095247787669459869137017783625755540375408272361426098383313551230976557640520636974573279383371834513917048967432546435999569365350430111956992", "1026301351570055077911628972867042177680735585635225345203536190737910863123857244548313982876228994987864700400759811456244128889754306386459557887432298148719591734971030611474690885904247396313959818854940592795291449937598794070517570167551607950979266237997797283563645242105244737520881371410960067902176629829514256225641238164014573644333472284672", "577756298062641319815321284633539861082132919998722885657507672188606317696301924134068233518707877841769252356274834883678320922291785288952259324960085933885572481476441044041666245632947630667669900623389069655523344952222114179660086674251300523449279256078271770682664276058349275922600493471476178420154378012048571333436567365397136152469165480980158369042006016", "650495762166495477049126323135876318273689681848540624671370401580424011707162281131874777891951503105221076274206308369224621272710248847898644721591374081392315437731137521644741106470103228306068513445077567577759224701817392098928890368445616786745312044636747096695167005610121205887220109397673253742184348518525369694090203109381704783091461721987447307918039340904839741702144", "1464786236049590434905743465154834598132355497608894876510808585746419735067502787890582396494347558422474842415011089660246867245007266628607389880573882877099589550204678203845246689309630827338361387275704277378981317198263843596236997858716498559366445563601411902505934820064618988319029356625117742223082330892236724944835950440451959043477212107968975925814225544648469704696327244310651076608", "6596810746850441581553741638437133878444100984914995111203228311198422920021730076302736770058507457561739633654821527052663625754699898928864908678172201480861483296508425461830100080632973981464823469287933878068177995869539554196618389179088255964611967766110824001442691305558890492766731389138330826914817901785290963600400486344007295383644067266812831967815359419564822489294496368074103199128409309873963008", "59418788842699007286030480482037551781086816518719458901529650548505461981736007647325052554252104577614821998495391611146285973896536304263518428421038283628014629967780363129922753302892370100289203385250328504710452844933297300223410448320574275700175842947863734545488809774714537227937142556380919033925693467413145184453004990132273599027454926341233079086397901429129121226567105760262121249035781279641457326197323348312064", "1070393741163144887106615725518187221164827267699838924941429042678015413882651446929712001300151465871728577307205707021448851664333385933136430832515358732818320497413305015116049899373739367567209398371486986269029698657375971164924756243534674819543255950500591340656293625482134115970340292836556047012322113544254716741475859208792966031290424379672317719493307898931567517548584798871734411473994613033976601216732790555673242528784890986496", "38564998830736461475232360560156337966477348543296912889954776563675952005803759329026012158190250656580460811860874628507378311411897292577254418389448910905327056052797875798842792071073082430615801921085131131904757124588213704965920153847872450901008531674129047768773427247462524176465028689131927919136292147469532989878308252810375908959339599706002710056647586337338708479719120400093637067181749947785834158813571780515974374915817776558307508219923136512", "2778901029818375590546117527113114484672357455708956458559767524713958201136583184473289527084437311422003736261722974999190979804089170182702556345446090853597627957791428943237561460453948820826044402874700085219613186824681247053637361670079745545538760409994919879728163876182404159565945053379193278698412233683308535462584192461927046046954945918295926157611800368404072086536709250328493882019435613967167210380399155555522069960451187550123144941460117476399723285873426432", "400481844556464920523193301963548462516578084749184743083267818116741738265896446803172276592132293252437641736702255678378020196583340296017305874056519669809172152689985358609594809953605859607651136943082150984660224920236376533603437055104197777495922382739000180430899893144169886679392314610966836210270498841529621493656328107364628256418118251142035446109798082585681169855601232173112571965711982733300383206840363094872481786693475424067353434014392840965058481963714484088640289118355456", "115431032698441259178673461431539816804206560773290015329752057694361406287772982036348831580901053883786820225009164463194923913410481248523137503562832299161248644837345953402272735282023494552277991382048997937502814909766236452236042332348226712434481947847353513149957685283099674458330104764410900543839986538076131534512057453216182889638360661447159929719038137745297045422073030824702000367475935702409104944531286067327756014628229036477812226374985599170883462080044700596715126592005803474078444367642624", "66541459948504530753768001471967959005419270466392022376423196257352976210252231110776428917476541274201459799058134101431331651507589475543199220149255661274003622762600440522835716155938101196289870455661584211035932845926991202557502792508928257976034266748831325772712875897333588717997864632732269693862392376895484988100730881126788959023903443606984779460581668713024441641390541816676610856286270482222156605510545493102132623215776624360768719348650259733692284804333540615561426033624780283661594114483349878253572218421248", "76717080122566093821769685096126348533333473476467287384688464345938248178907664863997779681772756752248435944393141184684335502950038499120052644845523026290523967017049073841718549772543323063556827399978478369606041313091683152436264099738986001869449728241878051097299490346519709940072925771948423485287163683973638746946665903940559428339549671501951366758811934677713877697895985005675231034179471691071272017966072759772829253585757141696413574898893832700332786265611996951692169618777516061171657897591184709381293230866625925902597785387008", "176897542887905871219682320710977054236195649885063012362481396897734368357286640762534683869872454244965040941272673502081845723150073431314902876590063750291880747723373712553100967508591749025216728994450514913101518001942052715995996702853037108622706150538094527668150620325050600397804418215191951248956872701409360022148099889945949951861965724898241732379974444442496212430718580253162145373014620079716222565944061670809250442497036511157273485606161593361700328707960218011162454162007820030744669545335519576035998639857914596707003622015954868692249187713024", "815795925230314728472279878236737085279030008004087855200500253014521127932527128885526410079762726469052612960044757453969861227317756805998981185503567039023299711652054131188006022549457417220933970982834312592735950018140458892761438537780953919908520972424194333073566878903608241070602967242198518658785846712295881224990958086451508342599371247161586427138348503778645201994004844323438189596157833085813059876353232318194433926472472721167826033215849712613785917626426916362350843199290384456011109377462267805156630427320614561083409274195307889411889718484406121375645508304896", "7524389324549354397801356452497913315011856161220801079509832008387666589604883373478014222580188830567037081935247887471482015360231314985337371942258260203939385162133586803144818348737122953633073095311149299883377463508309942219401299471541246964546345431980238535104248587410994668651719506647795652245245554349367125874876857244463618620318409144382509135849823322281027831591776097430363314021419414112824899028177671521886101096498126608165633326609228360352179238517061393227845320505045325556800426634899317480155864592599566076697068950579585675093167699329114669170699282474246401375197684826112", "138800484180914219712302326702802178157199288232020595807277716126392223926378591106707444859275463719229793836868708566284214501034414350853953266220225267143110257976471425551046069188570083369926289319954847285366348113154356458064601023126402119434759466643127870774164330686826589960109594089450465218173504187629454166226956526893875704969830626191585408807750322734960949314956738111993543735454414687779759714418712814531990126168027465140158764806953148937003185611158186683710455705012527082070237294364612667375625499788792257633923591324431260942827864659312843059529051940423114231494336335031596966318114835791872", "5120834017984591508986196650065047859699487038531864872635535284283315978236936642420834010902075350279505030004929465260242709345543639607773292077878134208602538275675583291265091714165339973428948005412040306127424871883645428230099148597465376635988368766640399372989825771523406030249994650100922593829267846687164394890395819287595146104752914215989543479798744485929580105447067545921706479084744307701783961846379120774460652838797753591500884374455393738762296647298620272890585944839720089999678022333082241138676080978538250644075914296491130999134389552091536501062762239568676983303712605272693429283100038671180467889093013820932096", "377850858294830139838638168215802092780038016602930573386515946416793198547039558262312467737983791635617168394411969746507772874148609641823047539163751702795222543019832005050328750907817266011479872405194806971268312167361692167252264172308895865348006664059299281805475888130387673484492108151111580147260086383832520506586231416515603233997674460633596201408249791703064288265123527797821759134838692448305207214785761264716189372084001112451765465433790033294520780568581946672132819009648620644554402766169507017541323003802706124203538173216779197391804429690913463400974547381070314833068900826395193921989122329834973335902668475423445184142471801333612544", "55760944647969803670700104936214276703418163826995146359366204907044372012038677422264811105212208511896356887262636526183807942536962683892431622381836246229948915236688130772335083840340164566252593033456468067431824060655193648039047729492243521453659694976501348803027093149539558317506748282678449645476135444887620474073150584355618406489856724494778877248633096276333595253012324971556730152755517558771607015456132912441957343723080458999749642050073369491042934979499196330203687831072108842525817786487718330792237747903510779174647553481994747676505530130774120520992243739532835809026595726937806053709668585200132001928488893296032814032593470714031341128788015283655671808", "16457726003670133055417812568315364737988338091091158251312218326569690437329616374734311914582020944472605890775510313408995229945334428903149322954095977105538611859157732272142218910153195403882467339866867514689726296672183682245219818625526941796560720064398728108321973000668550555252478306592014867281505767941252819608443162177328479455349999796039100621984127936729292132133658786719597197026368569007070051265672548312538134671161616981076484145578090055142565698834977734201790225311549466577004090807674343450549348281679151820330720056062429425106600701862306503156298835813445970932240447683526593536474768158583387967420140597105075176709672146585790993414230521376105364124607719448434966528", "9714926707998003497718782308204867881257332841251319104019251661662078248472412849177443834719209846072890969112505190791521670568847217287900651388254009260893186449634906395947258912533825379952975574267692934453193448473582640346042005495779590606640145643546455897110212759693094531702427850930065930059087543375832598108458827966338082930996711422212365503397867678374095016967422223554998394728346746184104609217211434235921413989212902495715550346122809777850604006668985053310528899731071820378305013097600934873846566724277063928654788793525614245817619281114401978980664096560907385299343778407890641151612145820588886332311587915398642804667189516333751031708296465506171453584391360087376886911691929540273723408384", "11469361067346228139061290587410929131577014568110496688276418026955029594788581734004182558070243437294012019588007382083610607182844994696799404722615974341317582970970611119434169515561820251265423739294548120506992391634591611979489654468463805254079641813986025304493914559074598262421276707860129809170482330724144138654242163986215204652850047416839186796163611459903547291938328181880669569697402627328163780396917201828272931792001080746707586621220450566380523358637421182469701231595854399029891888218578194053518468936172836983839399973914348397348853954542155795507799041130970804676688024813219676288924903523361447196493001392106550459363194374483729803668023599952850411152543047134333298142753046466271137690851320100397548574867456", "27081263142182923705501438690346729644366169641890975200940224634899233357027305456098025828938256775730428250700042672061879467659775786109270214017400414730550717646764413685560504054752678761496333535462048459532310810850944499706114710087119300200386999778156133504707983214878525514030819131644566263775100878971333483921191196677604836038344345713681506795660383625847999025848387503252627087123810199602209736789251013592140350653789925166247304234275183401500965673264564118890108142386036612704878688584239891999402890249937747483538525730024451957228223487693576454809145508346713566109971233755721615615541699881507959564802699414518867803796875388820464217613358292766134784246846225933733964457118146376268664384930394850083875401244024404677211216194568192", "127887649376417730093987279874959223434721837246292331790917063950188729173028315759621896868158290081514515507040745144760792797823633908454006170576076502414693250894106361156560785379061367900176197886105345551337014727607175137429409356509566678878892301335749917768757736874986255879172148219235433109220536222947985410156430631198989839450653517682104192025553044438491302114330030708413109133455822728120385022163636885141373386501141437603043967266969398520991275859042260783846015712638067373948888022989044395018434846317186459497805536942698964388726979258686557435667015119532122951846919014762751763697421103190009550551618834333461563415885034137500289032913017481647033658280717154859412697249820107204787634625302450046563003063271237239035013300852448256747732484360232763392", "1207864697976360344004012227247920888639797409727122316897149158619548357003386839595277447480050222229755160424883841049667706398252985767648761505658798805705483818948145043846805798252718763198773949764524391311922585251930658943514880587114466091998359273880405562907971318653747449298492952317155131191389647143269756802329984760064400111534136685383016769482782470510189713148691904881460827613361492986302460604018243380460062237283777296680408995854722178672186340582248073608246597487997996727778923589063949568687445482828106340010509284144324249363087064053541676878960707338041805779222724163855812417132661743952010731862369503046986946390659365322689414219648115087529954241488153772440114952646316128087077458262160905070776858191151099418724403865049128440558534241986453577283804960401031258177536", "22815919062260124281152347745317946282499579478225597764574987977890436887342808688976104870501061001773054587258294277087629301404254109854698281411452483911515333869047289946682697200251295383986440024239768987066961455306194374925383606676134093060944618688873828831817047682632360199699859850429151216871375843121094838459770748652491707914440551120759984840014318213588376033324534706939152455147493348994191284132793119476478152895835885120922180961499244045197171870808185699701000954429438301547575023578186676196514302877768734218786100354676154662786362643297064588417951625865838644112663945438422903965631834834286845607775985393677609226691814900584152243827917896815053685577316437526380790714230190441356975781684843354219992565785219238182282944422109986937230806375424197394063092770725539384275108964882307216209608704", "861961051643870695033992674309167199578105149265233755210531854655231695397841004315959353027863558941657347500708643835423572563996478981306319460173986864777848780732983020805504470333843984052335038327425867973338726313713394015863184128736960592170557471580379096716220939019137394671906098154759362286405347117756282996324206888088511302786754450046253062823707670337933613136463847028931076142175904578261359112314542477854319529897272403096490917617306617230616929156849561255541209838477962351678643611991108950807979740003711227545873058144232220086179444498450303055818969391304322654078530378763631851290884183055211356745609244035732915526643359273101408520908814846151929353857331307333376242939350958475788986570007129909972502782539037568776176785630826524683118125938788719786452442536511157641824521635493463680327860150633805208792583897088", "65127935677153380382865185934274607003809960083882113575904452876844683838733438985378527792717887288633549869389571008816175507184003390016151103667922703813694168133543286906006619259801862725474132003554787212850475990051192824704286086540817697867429105927870186318285789727070512775058927469565476598274691716076624233000916216924267413077907582882858390035886551173428350967423049718850381838273593522869951186720847511491298899945704308588400058202402152809162079122392664547523094139833577784509259690805435447849929045565614525326648793526939236259772149276548447129383535568258395264132188956867234872718835130548777951150687288332054343674708520307204427672825585402265653936878224215857325219693714506068560692809753122953929706240310498642459877441196692449645157645608368089254403626888143912472399649232865837206145663257925780776465599877881580977029065444654317568", "9841855377288937415447390527231202153455842504453720133695252668347974830556252658165124696077028515425450817398864910351369537663145194651524976959489344422342678620249318340219396467577024661445943481570099095051466855916105352197401418823197333060719088251811727514193408994320463954214844162261862784685360298544690445126145717267192561783034685015351169199621832667438357641444674326219345728642642810383270263207024107718687791371935471036611514436885033062917586993481519048858779374906457859727159564998688713546817221409312620181458595605735567354514662070437659126186571537250777009752135321513030182853798578098183302050213033735441339449132035723102074102608058173098386835602150956587572082729353578408870524492053406609959895082296706792813195516720142380910984191192058619168004260360406908231467668856024213138928977873340747895988011573647696979952041806565288571629194205319609339346944", "2974518269629418528183287790477136251735910545127811453581427978652616595356264947596803694136956008490398064656516155566449480802126524149773164759834362082131166150716512353779536812482810691172500096955277388103877578185522501050975722169225735084006254948179019599295302692801913945714653547245381255101505823092605145670553437793402069282072525939401386025809950055516559950442695132557924347603342238606705629548222231798775806790816221090616893894075208306706441784819763638100453946855836708310557947239099829716518949394166020681049804222110845249797452263905896008961178967788697771854957750815454116222278431207930315307657684846475482296389849704058050160567727933075981675002752008068830293647504821134818557279858111732545257603978153335616168268017033759698373368401020455509630395172047291096383128279778093350191660686534827468465888318399898946663053750353392007034469364011320175688955268074582072057057509376", "1797985968535216664944496004358374343509215650341798479179149327882744856269384291198729303430246126786296404980032302297595321012017030109348902525782020152869169168103786838160971087949766031760966165088431500871032856892630935020296595275794596862255427336247497580566862623617828330908541493541620179354512119159465555098806510076367231285395350427706814288025394425311199341223803743711901601363242903937561139477254670558878981639393540138916953147434506441014886808593769334222234806383248792522888870969370949886460255917591946332579170909412934639579841074787276447361698764837594275020389043099798673018624087957854927708503877067844690693442538677396545931297397648367060721363215700703756001913096856289455202558557910153695779883053213934571432082681799264975524318394406468304991326159530064043518011450002265972635234478858907973613954232713746104325413245975244731376790951869506877730874537309836484170950393167194460275028036788682752", "2173631660667039668984700210504885053440928931228016968965086163132981468236861730220650615341556676372390169253173663975604972422799230677469382999040739918660505042707350940039158107159615121292539651123423839519892067444431141415696638802524213998886911802250235334571816037172981430612313299911451638833319256606144115247938014691467553565583171950286615569501171685975138361651226678322938521468241227063106367669095067595036366075438176281290762289972128921040048601125493529421744568045636939974591348776120862370258685194871440497997150914743247310031723729047398691202330795910597987059012621074699271039180200868097247527739438513318700030869621175396951306037350507573405975936434558250220627536245142479496350755496129335743086027107995603956511019080962065525636789266925387728572058586368191713971116529410717355420618449465142442751933353701890082063024439478090834757150128353040614478610732917566732586611767430096272067443300328432386109177489664665391726592", "5255518873824416903687803876194048725247752898708723075400668615965863831097504375635433308251233312048766247203558991200300620604352830581371079358415600051856585617870548568853727962171206228838685195506282971294399499303895277316297475177391396052015391373638242535040410011356735654520539030774295796715732427912629667212872847331320104357084583959675197253788558473621399678098642683473186288639035344063284608566440925823269704605624728610522888231646442049910695279679867245611325888962734642379522278023969951318701822462788591894615137353613973715030604692169572118664406895529953104274682423559238462070772015190463321220193526066575719162798151641256508174006193296918203760563494424336058173574113652876628387389451824223353697906827208646762120751479222210763512531024245609024917500334574939012212142182012886145075543595440047786301032733174842410966880567247632878258658501902293739821318940798139131150532395191264792406363668485361473716058166829221766502063622860809609374204952576", "25414129848153344382239046897534255136864521417635453001949051913908008017589994776563072587258641569635169539843558219339898856799795550740114907758401382615586013383249715747685160392075349258895929797263710613473430715202959682477495625471587772024353861775261592839627899201402421403611533883626952118240064757854923766827852704270112197847296922231727833551789394804850015287585616422446284637918585983652563298394561000416031695531401833364842751130703739822989388553144317621145745267154316694067048460653278566883611037700900712951971174897018912094363532275197525030498768913128642048052245473015542133101610800292377142229909140813067890327977587612374256490950151387690850702665871528622422488218998292603704602845544390430472959633468730170707212307541907704068706263624064757253792800438322442280680208276567472614596049578405156513315480908601331728074386844924953235857764254017071297807352372985532421088761665700077101926014576813351504491800867886066292771827600730820974245370379226881215895758057875963904", "245790382051771145194669866894836910650556797239594091009564556094208680880385711256968483532036630553012696778687561627507545193814498941635315835729920960696181542215264784065507701869720671223676101099353987093462192745536443134197781431963673038992527374561993263849109824317641227672017365759894960530209333364608880281716979214697744534329835952620212452175318901237502886135186934978829477739282741742463317312408182343727949724617066098419258568662187079326746979739256946508422770714367934068496850270170914550232625314799613867752312747219996567995096961698243188569100429655378495055153354475585733921880831879481810931891716484123049081788090773434225820431784823304849740004530328772651097505402025158298202188494201095511281651444752927982930763983954415168881036388577694117158262320578043318594452254802839305491844927280242797782517788247605610352883705938120703000495886781538988526418037366343673014976532093358437076518455391019224639618634791307581630232102879919570031098419290868853038999379573603903698174015732092112667148288", "4754277425205284348419700021630306277819594231233501230274079687799467644054135605503230129926332349420230389354913481405631900846560126740972623150513354604812764296700223272603691459770389554281239817726014489139642075985146416079527934723846940733028576245558806856190369354829628769259495000019520989386279686123550085284290723479476495490251306436556499879513551255369276501430084910060650993432598538521963629786218092168813008486686208663842405885584127376723206295073712408381830384872882201818580321523948863465001771326380631696080635169634702135509782794877790215871455710398557059080949521117364655342307459593315672499574566292033600369306924572956925857747918561084493161074930593618524757397139122151276957016232310604754600441814037150264405820812712473632113348468670018469205747317973765171453782809770173332276553416124997311925329492467790550540501909006793762652043767805766864940022827298142023240656641608308615139677412693510719636885245539823207642584410041148586299456069104425074059269820037128974415771475065750800677599200925738481518877425532928", "183922199454132071495017823964418310581035406572387504095987895436081451427269845904015231638351142645264081103180227541271451365150525668792523811951920983449796386090707905234081639758289351098916600319954314214739003095905554767950528555878593983004951826460936168704827155870671617785932969020911837828609522973050883825772466142655647998378335201711464031707332067150969028021867868389473054701483504799207493496645907024311973634384571281857910076605223416442905086352637873582453410486641390607011647949375681392616293062480185677371974876115847216728138297648805710092860746366490654417856746317198280144869511204123264164871277050086466424866703174359826517646856972142290028705846976532181422669511747014463404242288528973412024975676890338662938337757856074384364339356083599371465548188364416530842160345010023360362483494062918047030071997896814424896606706549895245984904287294230594215953285058745214997435008275358198968506044384302940532876166219914266007756627767084845862423632952768871427161354405086474339970874829101971565739027195569986512650622291178085460852417483570155618304", "14230290926106362696122823080900243390433637603738005980259256943076641934110047856047930936624261107065873276268866892129520861084943649470982048717667479189501485633082120086890043142529883906164212808832912392961907330376138246467342868411536805615807438750065284882454125993437721429983886048307606930604235628569909434642167805909036554588490943154103935654425049741224775566548184310090004630537149855892839604622098137866677563942134239018715827888851797693649972687262803167679273941031847686625493987462422961116672112718087518225845931540765028692301246265348320493394163085411775758928448982724437500928134715366069109427038422359115771379766765196397901369125451039366900914606586395405788872163194382539222468491685209309855588395152929300280637903265687859426941368397203392235565456592313650006533521900447920576960664398554574517989911235388198873021876268539325888745001742701006972571124700950509875664721962959074741875601534435168338346227795552921813004231344377034549191699793014816843400294624064798743130698839294408616753325638646891105123642086095450609986686265602874213403600381488503940327309049856", "2202030863513312636321648671199054913516907653916117901691073240331946949863609577429103609768169530057061150257812445918850882107295806716261922661873456575008462513930989865443088129815261641695694727139738398910795613789657579567145298371226907217165026098057292665267014375216701372544800681475251578425365803666392971936154604673186923792317585313347474824913333286141786013706495579188805111583422817277983447913522288753851140140298470878371671693168302912742449635443426252167133192325519362889999795065866161674664045744937691390513161259299795724130181676271790579219732523976512872421586460443531041590095088702197493073534521730651562660076260725779111547176801999555637621415828252121886867337943124107994539715634932451000531052857363478368528085250607996565755450014011136148530448605458410763120164515711184313904476263429889138719447777588955617173003740328837793642742694803800382429624785218054344673298995026566192583108066449617442357672139272143399705781655242683874485399562078829739034234890154629296748941812930969047270839666047356933906313878622053623830144119219493279649297348864882853168553417766003229354994299768397627392", "681495543421322523798250098264197076688919625958868418051257990807837505987067866825123436248548151617593050477933088878988725616693867642608945945631683668808920027335934509944595182753117263717153639384270889156418840143434508108959849341896430415323256371070439120964777671194974820410861700069983389120638933918384576328554056534884715070073463424017931484262224244178189712770038390094700448535327494765406085737371568739744341162316251925288406054781369086525369352729762667669545632444718852477943084555268217269638560935219999355178152037404795500578151227281876968952880289646845711858918761125794160153470339887122101679017501147006350697819037781317970228904772048069836759470844867315694361705735640487911731623505352045680782420840435221438759307816194240462082712870054773448930061307949400029335513342976500230415962364278988431128471484008507777022768323222041382259130004343803395915550804325522392895772799286658817920775143921572624046023809896700137235863078674317453334741645449227070394628081947440649638541663098093102136271335498004902830344217486971653700556946784724621786596785109259982139470453695479515213359593022702300618283691568046193527092150272", "421825309897901792033244672821110328299858989707320804064743460440378944278718899967483820889500393998461711016514890252423164387537957829397741981629563196442380706822615641303536830456737698720856576796868658302341222149714994387839750913288493530488399884211939106903442707727486907385104784548836801887386742034876056259719489444284360238544475786244576709606346211662844260424616033577969445316367204486111572367285640386091135291959984634422111712349759041118545253088840329164781300635291094309773199799826699372727611147119659553696450965456120066708558577226901489783972447442763036558587711792714453122484632779364568230182763680136226900406180666607672585851460988484857124096940950351734765101605500343045700786559855265307726320299273751542009158879475999601867487052671938980988256280155920054084490029016709123154004397781949851274185859499943694823590844099419935550431660671065019508782626806522506993199944432863289827772158833515744104897499056696354128803738029780167294572595638534858576429012401607594066492590155477361329834229701436120365111259179709996155203535570930542745295974256870862760463624390717318046431243895818155132716064271455360415503340367605714430365452122210697216", "522194440706576253345876316972208990580919049498421082022576245723338982949140665003069105356289960330012593457390089303605667555601975047929042951212257072969361472940671364497640560926303318696033977690013916299289897514430165053790577048324222670321529537703571049002002781496203041840885524183107689558500581565215216577563341157701608110023823872559743334999271082619563560280418676667879029748783809416089306700738269364207260585249367415340646003895272439817409712720628709186805339184886626135322714400892646570899815363346885190935443883452361028600618727769686519016015986764715716391321987102312006857869149534994401613005059522899531855293803271313823719971973219135479955395552948879584294859168854149701603115968970497705944630998036477284824110938251324804171310134265550546919153058666691227110757309673571239737301459200948415973231968942428964722213969080035992841969252161263696664840384740535815264710623196642175113986088252118165109143235875193394237324905378681185642555776110635771578478214224063683755982931585626906161982220149238402132222785443508999378746610588801774393984778889853240279610734678193984258732940104186823817787172451622424479651829089774622333472658481415909711059052348233311555046866944", "1292890812885812375326210375759313154211806521142431703162139930204968350236396725479547430643054992083384091678994104761926923090140278035592984448790716805009586451615907562797344555527547953445569311346246656769519102613509006067117867848915904121110567926032487744880576751263549555669836582853473577131677246570878306726999866626996407253193693750074690839456622301350210262608948487854303552851457588750397583838082565400229544094825591011830544878252598176845253713291152353908500013649150377819823624076948121475534934827830863105098168949697035713668331158385332977381594870339821974004772810156175706056012478014462296965405817213211526586897970505560483618297113724652703794740872652190327308714457458457671976780831051175817949061815796584223532376976086077476481020253820853076974471059429483166667385436819022696990718396965711803590967567007032387580746632670642413715993429910692606590587827599844803982723137238986268051229340705304873811721964082001288954293134307920127141244439259670441346023410871394876521183127283057449596610425438679047943453709142013860841099237821998572066845392465348422795746000762231545335664623042607618925127125687803489756219911499975270654928221265205667650525684108930707566429764080749180245487621238064939008", "6402085214782279240215667419755299131524078858723655272948045632556476258728081241282224086781391936405539025009341590521693193386436490558248164393639913596873843138484718638733705545361161459118962635989994244912935782863002854452377442507617461316723550726006230344853562913627216388293856589795406711937391467566905042511687052944700963643661331442779802427261444468463746079440195054078750317913034432559960393187084518849088424684193033209762743037198319778223351150580968633827175119987765536804793455915510742702612201851443845921999214636047945678379752799393177469410571489245952655702508168565110193630939307909000782817948038441995201513210380008881955309548003770230868600243884200147184249133532135457066512231145258757869051682728759963857462438544040369800435760020981848338630787860638556405691711659197515718952391739002729042333111853089655129001219247291883199006831601000416411759400499972543122010466340378214154214264753389820650904928827549477270321278381079187818606788531124987988392956165916193914784801268268235648908517360393026575942019266375548137727501265090469564111477799597596462831665874541952688731042519741567723389896236895946383694712621870846145560224747919013358384009198985492354234309963979256675597935679594702431599530353132865618694486622208", "63403180978367415821309274946297067883877259318587866180545192179873251234024057122438043938346934018064402935929079725551013124750893668732866656438958416877428659544947175649222226350410354053304037407285263027742656926195684920350873977031531977117393899620145508261471596492667990267374247119411938906051221560288163888494940827408883645041289107923326280594975299582732093176297559093243319651847663381189148739254118740760683251268770860610364971014257718132322662993400462723041979552544043247309413454403017490412923702397366293918458594927220825783569515516498613647493542268637194003350434213617513461273400338809813920895663463363247859385737241337948895731991543335318621562472121750689097894229554250127034442715997616911313974856673940304231994761018954589749398269172339562324862795012955362211949117823507377780394667326502146542683401056903289898178853920495032817341587170762830228787960209813642366205321384101719785933919351423732356316716472524486444036272429428153831673413788549230823082493754465058942259000583671702976617386677699167861858091938074365982017699085450997562670768862704782078193633647021017872847941986726359652935580704732361989006186837416869603398747869170555637398488742768464768452034024359320496406508094293240522745199848449629940597204965057665414817199919279965732864", "1255829381618851745843939813162800704298382133625846814224576543837929306862487043403613671691796278314758724772891576106178879232671738229170952547575146504508999388463189077390718663065465139512563257376721686308667894337081904473700501451284072606805263409406162948187574343746459682980041852684213198304781289243877974712637944889033542516361940449303697964287412064454816314869415430215941969303231295534182937231337233928794493597318564192804797309557098139190130815956634614416930803981119285633896897477273820223265909390628295335746137224340995704708759288876800112737285539324537940458904632694853367688632930078926069962806962151985488848240208636811697886816181397641065060234508220101117574005754861073847528126195807422137989781827241548062333268861770114890971921143176307587625777432801329694125042082997858291756521028910278742226462503170935773824014532726362279487804852642625914063586084317328008408237653234716716056792097957687674162407334579817410344391534511456377332909067033131887491200492635061656303435842265594631198130167892273698894118908473502560911713314815766049451261795858816213523278903054857664316894475748404017820593032620658376301987967016324223870860747215810014131438047371746755894742158573728541978843161985626931648804227861987028287101265196697102807792583599996464364915511454252370644570101252096", "49748527168543236721217601181701787859412164184544981614021132152531407544755875595715223534937387027814400236784519752457163875312653024878808819261897816182049857562175142502664920126662282397287500919615856683661037726718551357866517035838294570557312647785183961656447017236408492576412491933241124498007986482023687708270806909964726962454428889809121509126703306096801309583649294538265745551262893038667109768947942584564986046357259555432390720779636591426560199120727335150844849791136385442593615377298690191141619484579081882966457602567673475027107757696120192807009449746430724720362204881883533358914349307829848269869773943199352024084642105643418234794472904996993789612991098814405633839362168444219985270745390334404281633531610515239911600270124765918723756244113179536100218842580810350953235956905299884158637846183854907123681882696681963760189001542900172446562530778777599312587511581507032388059832452415715329931134942694903849614695379375686995163260981165532882315572043312707177653268134629524148679542470830862853196065894885604510044117513694327827461877798923014301568856988500200842727469644981284082974998272244853501444493758472723476216286626588118926382688627409464658264654757634470533785470480202198639301517931585656134842389907260888628356169810472955154515203224997997562067268287191747713068764885441400545692502662653596833677312", "3941484395354638233538289175687367867592105475775706532607033481929862522953984448984124904076414779518065278170783738324688922152389130205437011719923988459918771927989210378507306385597674277709820835943850912312152185369810430427235293842952042618038177698910452587876065686843021184453985614615401176263423364407780619503789421456129207959050468910855420316069710275776886905782248938603902750169283607018303335844945658961365762587223541329787394772159734244936768703203377414117876498328023783201742397734284557793518805392879159072376728619721788157628888344885071289254492212066462609897371427802672624420468887108637999413923906918609154894786217991242150407245961961210264630635727082083499613184110924860468687904057567797574662878324087753939198982072282100267692628525208200651528096222226725761759777593209326929086554425269126423894387884436123797407184297632756634823932612007791785650341799222376223152005096407550736174028700944082763172420809390328542708804075250570034803026246036242639836615637887046181963204853103334122812628083321526481217092301247280493561517877165608935730379717606928307804713776181202402762892404134887938937031472708163645278187958477215529193445999427556392813076702686366226841259047880288438181039317934007049986967628669913469712745089488991641441449029377170846478308256948772452974369303745729777296889496265230364682344462873485908123670305342226432", "624553132445188374261017074910616651175684707033259989385970576608272316008064282918553047835861650538769914221991117220314396825604654124698761475620179598269259451407347168821591908915006873583380941955761610066160419567573390994630710233968901049175302599016666711451478872117095481672759695244736634085608900894427917277279996666119899843535724293953977717958753458753357574723232246031618566245134658698123460418782651119733400238852030909225084923720522062420308747615009191365697834033073271039095844599773798762889402205099782304958420658723821787855439775874016767512412532198575938481672972682436959872295438912425558239249896718667429033268570400796096855935950685905131932457788106766442890916357395897157536035262349579159094919232732624415986912959633675763868654888183379449084913996554618036170262832802999896987764687885078128708244981252908659559465878438903039807006949176027373201571918960978899368559454220738639019793775514107863498115935799189994914365281539305546543929936288848983376399359033566087234260524743328530634575237604448475923058984710325860168462459215792962475145307334652023116341661884016135961156794587175220705121250776592668568939514651460613351346012177225037868348882433579230141987465079270609005162061040175430229143459252137656401517672603677784011449981446402694557290874473546041589279084003029095969861040882648929229818815574607038430536241540767276013988435192299755547347910656", "197928788304640974341464850666479258600695049180808534124773095918685736886422750739311447234778847629379668922704179983751531364810359217713950668062565097782274752622181167719275215689807351092393652552210337871389593058507678810223056187979434630641203353919939495644767541545786906958837361968513995391044381927429678621588331901314460099470258669197354576703557407380031846807594524889233271913479072348055039559544348544781413192221607714121652514827686561139424546526972239487807277994496241865504072090118208118502668454523872999822924264148549447534537779884400733379795206408770083054875651690478960015238056556281653478045174894788418982313952718858245870557399909731671315524677379965742000641203192670806788653922982959777967379801448037982832956836725494414074449883228976663077489903296666163245859454357672076855154287795385752729475959381491602479668526791941876464824655451499200095483798976893981760998404467355203056966910895989444496771910506370624957508433199903387685562868293528306920853313928386878452173404723245851705283387042199433227699011440553292089827210283867137777224255168276367800718781387589924414286880529284397361540991020952506223721979879403820291922270484166768214979758659415044167154680904882962898181811062835177741059706090419385648245030626512884839233314262775620355296399275958674182930499283811645655644832080683138115417619825958599349430173169550456628534028988718669931851398764813092655430959864659914522624", "125452273648412141401139200773089339811437122262323352216462286700734387627331522885709312904647210371328794107858418293356140610389233010890575674923332327423429917033308833625087865757067009121643735335562957720919464360279849562024268481514680519466433342816295305461792608710076067024418040646132922593872156786882042514851134725907407734998659047116141535192232282791034794601497425933135733739224548153792567839779141913680549722028773475603674523853169051845195421079685934332310882053907313995168923535704556709136009686053259752740308577712484995569783650846269720521608249582420017860918845622644663874987575160515268766971368721963159046529551370104575096202684311358624098672672476994761800126366704378281769378475834662925454186722285874859694872242026068795039642380038691501013387521486053366727435218916045301026547623117868196574350026663672938544838421549439678291079144887169351257353939537143880911795509769485297854345823362270660712007071953958048732807833151699233932553517365602355625760928908188344900652899469143373311896574182769657272933821876553379518700197938172155010185719146936187180903250543579433005278984692348282568379624191843385007057047580846112172322370992146748764340302424100769640802926078370838482052406435490036434092467614465282934547622486501083341846045800849550829377015688082924233744178977266360888077466658752803757886543953371541948150838050857811138739570190403175194723845806878286855221273591078542964296886759202533689916185534005248"};

int main(){
    int n;
    cin >> n;
    while (n != 0){
        cout << a[n] << endl;
        cin >> n;
    }
    return 0;
}