Poor Men

This is the first challenge from the Web & Crypto section of DSO-NUS CTF 2021. The challenge introduced a different variation of RSA that is safe from accidentally generated non-prime p and q

Statement

I followed the description in the section 5.3 to implement the cryptosystem. However, my friend who is a crypto expert told me that there’s something wrong about this, can you figure it out?

A research paper on the attack, data.txt is attached with the question.

PDF

Observation

This is a very generous crypto challenge. The description and the algorithm of the modified RSA is clearly stated in the research paper.

I will breifly explain how this RSA differs from the textbook RSA。

In textbook RSA, we encrypt with

\[c \equiv m^{e} \text{ (mod } N)\]

and decrypt with

\[m \equiv c^{d} \text{ (mod } N)\]

In this variation of RSA, we encrypt with

\[c \equiv 2^{m \cdot e} \text{ (mod } N)\]

and decrypt with

\[m \equiv \log_2c^{d} \text{ (mod } N)\]

Also in section 5.3 of the paper, it describes another method of the cryptosystem, which is to split the message \(M\) into several part and encrypt them seperately.

We use \(\circ\) notation to describe concatenation of string

\[M = M_{1} \circ M_{2} \circ ... \circ M_{k}\]

Then for \(i\) in \((1,2,...,k)\) we encrypt with

\[c_{i} \equiv 2^{m_{i} \cdot e} \text{ (mod } N)\]

decrypt with

\[m_{i} \equiv \log_2c_{i}^{d} \text{ (mod } N)\]

Solution

Since in the question statement it has clearly stated the person used section 5.3 to implement the cryptosystem and there’s something wrong about it.

What I did is making a wild guess that the person split a message with length N into N part and encrypt them one character at a time.

The reason I made this guess is that this method of encryption is very vulnerable. In fact, we can just brute force each character by replacing \(m_{i}\) with an ascii character and check if the condition \(c_{i} \equiv 2^{m_{i} \cdot e} \text{ (mod } N)\) is valid with a small time complexity.

Turns out my guess was right! :tada:

Here’s the python code for the complete solution.

pubkeys = [(65537, 396661998399135299695532142421765220358207378840457565423111520684012433959418240796402605357413554510338887719884009093303633359615187675232520907561351153414942201110976298984329719715038205538772742240266101312812196260453121848991042403695788572428319936895211901202359042686181093128472411344729758681247241221764453859267233319475864744583802444857200325247791829859262583646654562553165985582249338884318894918784935977904990059719169594342845229276106041219234727865854760627360781162836103719186225177461857088908675884588018582979934609793490239558781110254350871535598482515828949049893843852549545091589520204851281660006734141906466755937860065860019593803266967674183966375187416421910269668317017279488183248820432730951625792410780372146367651856405518295086961068129170217683022426761580857886861875565412656538865133518110686211177504606515033138686261373865477006608764047282340514933286452655061638598746781357829612464431953924153749322637696296456102415459060283534603911105261678217243061672378559031203100461884529384881870099048229036196280144140681887082480727946201116897940884732824406755645713550705535566902295954502187235798505147879218341663619900025951312127956860736211355281646056404548969828023441), (65537, 444458046540782226826799972190894243548712083448559428207775889645421034407558282947897723883439523077856910932381882281765531197386963705648723922818014142825866825848625894431313641119379806000713949793901263428655433771564764090440600609305564630000270206950332500612985465225653355695961011512387792689556199605421206518238160145205672370189738339014515926988836556156505529755944270804283451462563151748423866769769562862420857934762980668869010361308293657781306220086809608282568872425348570130922009592086793075087324730857641107854781850426236792207688300194772162200420513316238286613734091409837403000866835872218122991228474776461837959735064006653207954092366009626981815927709471618148125703279243642792552003271271960617705752761189319379303867224644754697869214655080319324928557942422135248845860599585389246730449402709374116804763517915842679180768689969451619542287953968333519051279796704234079536971772185575772666054356969460028225114725019160581444221325203757345236497904686608039991468011120623135476388954196690685364571220875693673029600381007772126139527116430360960983544509159275448468744353043544095217387746669207873624266175736985644304816578545801640174279751466963890908122409572745402980627433537), (65537, 309514930033040511028728669272717916576273375254134059979040548570619791564405136035115975403545320639898290210126551466766212949736855607935144264941123101903522966050711259699599945296386267731466279503691483937453517017241805693764845816867884570595568454829263183032591851054025016195845600517153535232081517310986788806004967793558194185748638463442262046699369053979807022796172626052030156998167737100958519099751085926806752718861093799639134362769430556881543981219228091072345245043221598791757916653937971559388736557918498378186098772545985547847209561978149734184316604979157218885355359442396327367148535956473705500352897650517272516467904283682170045988221728219680112477332945713786678748704400222504843215322113002196510054824485635752779891025209920868172494016121177807290110452453177571637712084050974140892507693633278355882492216502856137767287221380970928323175968884227330763118571926530044183667866429363784170992619492252777550184243061657824249047016519377892983587843528119294360709647726729881879372965423286303211985665915582972216648831250874685570264078790238840092299465614292713328542519557252851455724622768551438816019005966707649570882060553897347227666263053876305266063490161281625164189118979), (65537, 735586511821646777271716140067069421351206450944216756689805870148576071176818577574571503998001491497732146781020626853920927451920685588238740569242695571085384975987801253833584517483310197667366036999470277273783625722936609156884185565609549170721392238119406733440914489965974387455646719129207805311535320936233520515725893013564678765483802209100614119547033212750802719707946233073378649465199962761014718710696200996440475295686963664803088490425627734089110259679238240070595167213935110238933905099246260557924425808411869064457483425554278281169129988671833095024604986010867206171822042190810651595994761735058895521574128841611074811973264904461432231807707124136553401356281906067185363068789216873251932650150059464316380229786796839793108924111257747143842736922161403980286353281915790166237926442398200326421101544806717600236154180186729224985887824982722252374438119504258213662184386550966251942417842707879356144619473387634056035410622060518022860411099579884176896779327027700004841679566089548891740551318590229012222783105667134167179596421653975470714530952799226613897750634620007928014500095842654175464370079196649959010290462131838586466098539002138915443950740285353663497986009563277890374488495979), (65537, 716987206381152238869662515167731668004262402657739009363725613612581393837207837982825780861088792626614140970786832603269979661128891461220466821459875179000348296376613686841020275348336995302023934495617523872414517909710307634065473170096015495275440444317323278512703855799725939707408109115180246311433870562924585760493652161578559837890607777498619973084313513012375971435419340507041278504638989554077982248220633430014173192718098220067779031461534699457221518922587478818775319831614954612727308943009637841830232814919786168909110177081287429356753619634446942797406669407879214716280190889939288209554651454336136160270585894880831649001119749768377719301807198589879018196729462870615201668663493603485666426376573679749663804777481395804859635824025924566555476567257461318767844770143845929727545416475497240728233981010948783472317317517168005926895295690231751682626267181394639526767814634877174306191411887928421974280138872453425483575639539356792192107744151031195547315200747803216359108859154277344388808914746756982105967701557345401951108329489161647539825999009499552358463231613391432346133868863088814924113486569948060504288077516581875007167622155138656275124638423809979794733200930243484587864052767), (65537, 841025268781299358956682212899609283781379459136355408880464588049223561657049459115795451811270726121871233413126239749722269608236038193403062308288470497626206875546791186715369115355862377498033715137969505487753827292685550973585137328691173897615774890577225479029107926332149359155748794413887190651408500457813802657863408350987755858191683941615405192382263673161060595192691871286757226539409194916615610417675385740013708934302524132413564471849240253060235646724410652673326472282074650250598972126851087715436453382537072470726225503414894172502961769248336250707699436705661570012753514940198888827904535315862836418950930601667328593813472531218920925777585075256084684990725159615198139334339906470524643402320929346566663858325716836441807861021720838327386653397552113384061845348863073469402240907574607714674872206111946303940669749141412344807809458618318084143695731648187645352696481584703356967690527758870977636316838808302406642861919123641503336023107960044528602516945528473224050463817714057040457504290772227401566710742668412691944469627542966558105837712500978729740446187138404135211995161459364898907249967692049817964782056522093347432793515962688506341362090135728829150974923915525605351356572023), (65537, 391549102838835425945785202704733402466386077621818139199200349346491481903144178937504408229597422307700009424906538199125811901193862736573824592083789964068259166115677740655562881415683355215659803086102577502552803710518521346390543732458675673646644104684726891655860678470956888151441079989131819192796177954257136850057441089537902791909542547622450259644115199456346217566054734452924645500853155600038127575888348942127741624222924671958345694073034152837232693803805556586323080115806339187917787556882090475732998004557409299854646895926929809488150336222851297782356312521003088318816673903829520820143822405783559772538071866142291127767531157061533270398045922465319797008802549914144090789368694915316928062665785929971500461768029517805997132929214032878556417861172283476640734406497290541578957222778841608520862523254361285161168733196572254968208406327421964014134238457884978322813611902167667549738037210324518673974517801132834957253031391410266594632552196790699160514269681908721228899700873965604145630675690012608838788143271240462451396661039241741723444437263099382616410809505065336558895058517161833203482808850397422511156095135673948353009376128329002010862548754586893346174538915207158232589765289), (65537, 518291014848207508543050370007305735612452736302443872312479477980097401230293204294583190404927937449322292416534843259611841261264062319631552189337967667615396757086185255980854145517170073188840199313708675855392762925703826094941884788196298869090197585150642616103284937223723829333599699152476777464737716668223411557222838458853550244812850912329833675820091662774563795220580989381491489318526842501289933647079836562915201302214817512660056109229003805107436664755317277926218702234126750945170977011302270540851630393351645014984932688729482456174495782671633748945782741586972294907297695336716410968519142196528050549627651776863408136035398906083911751615688562884400770908632884076534919655320181013018921993754667706693654026417977035586260611426446185292525621892707556689405409395372251699586091656740452624602344687059117942798637516158486319141393323014761628483606886122875978094672740943982633927892100235252699019258466414427576290149909966917438158836863106607970062000259507293589532765380081124776115420559728906424671132109204475228239704493909925210264110433411027189966670748342228976369136550430779769462673081214223673192381014525005237925022601995122650921377283323377813109843316534389545811288367523), (65537, 497576571110211301630792630032240653412326070130562699733523437143023790333700650669559383174377639264967863663190062667902896008205278119330884772866118116829507448757939191298557609768550760991344989716047312412445799826480495660632891608869530730027929619582013650045991202533511451879061610126381115475319130831406076344416188137638302856501575322046764932518414331517763828387141030352741269120776601805866156132508790094908883713147928178446777644743137304663869281222806737747389822439446532605891537448252878310998274371445469409392419447205131437756586711835530871933670941745332331317692076873013285774350763776535278737659923359482510373184993667255964491130416743047430942159486582029890364053643898213334752739380656236605235214873986809076572006884448796654390136871822177084664299519787512415327667013309961365065731653174187265371498953197736024298451386907784819447518272264183787331568456986033394259446865525078466371271671891970677968700094344529666479746108957115682715651737555403032807009403571032524340538332910326686333440989349496137012212046903820527576615653821941932976670743510085343926874848300585445705108874958638445760541921463873550721853900653435098018493970759697002102217485523307297673642675957), (65537, 320151543398393839895506022733821634633387750144317177410865128912861486241698580275530530598263909453760187798734630631018128001243753659615613654633439926756719454968416600777607429306789411999685185327201451648174543257183837627177600562874558580669723897507794939182663622190259614568179634051302132192240620052523931837560359944781896397528277605297036156323023675403769512434643454444834168163890117178330251519196254825820190820217000197948717572805553379135447968084833955877889025083160661486130284336006254840793303772133153351456747543970497766105673075755935732717500198386940625934845789308200424742471042632389240476321786659065251389463605862868643118162382414283445827291617104136712930922013069692213994638070622440792139085617213692480723127122905260915451907492453966876339257919034618098233798964083564452524498865957227285656552670155231153187911063111871511600256643065727892142475861746025541654408960257993020730166800676894344131023973018494985456186290499241443296952156366771796992987802297694223306656915904876305891118187345178747475311280543025774782437446131124084990178831956689856163370799076611828236727935268649934476680647419045315071049320806337259116654326940665384086207409812238375090747258891), (65537, 662232320528758926625557910165842815236411088383519776297290062298572678331848921440920657485063145639483680363385615378879276626672751149886331212510634602855889405638284291939382586783177824156779608379378223482591700315387809197584101532905814686636428270865622614988484483107850901809728211573444871834968825635649934443130293951813643686383349653830675062859501400473492077181830433622096666774222701261079500997769755151115647207964277868310520689049875772178948104887394632514121575985381844061219426254333894869808927579506392263083063722778621278488006803356503408655650159867751107948757707098394972888013957433846030736804715324144693330972912953058788996933412243414074936476735705841468264151575753562209500414291668771027746973083233126792368974445544698158316978162518459760545250556459077564524956499070934125807647771760845330984937665679897398140966341579574567449214929007191562115909790355849691977369335914251136586602579864462386731366292468736856990485454573350705728968974809472953776806271192337012437980470309512008028536421071112399855660120377795895070374264725187152804698856722669970942169763795433432496819626663023499008390605588309334946234538431709486340119587131014398135143803935285867843840395467), (65537, 460139050131308477208872180429660740943751613372206636452449007008269196198720649751599787194204042564630066227433610800718639559980277616374644454891544339784507268415367251663899827075454121753889110977908499753156316157878495638572456104341860671904942007697447649041034042097769918769781828159623295161200438656172953789161047854920481525563434040892022065025552770034596276602170369219769368776949746320076323800661602593821571433465676233730814902553128252414244580965895617458609907362084151394990671088255913273936691368701009035580262895093457758680968429017571990457560834693498043680786017976550380420683901836351276267463456346793546367705432028112251947809466657146795584422980465322781547366293444533737426603768381526211942461311713817276947579856791905124498465430524153968233902088496999986700723989828221001584252480019562930558136469547194590277804310637684241776058474725559629557489865603440646302002510677722567252643935998385804071160365962234663979019221259196454585817378144893023169998663274123287531733698331287418090443738920184121696383812016597955450485325231376867710322670902395083457937371425447461883256214481818998544095062287731563036658775398861207095814756138154112527330007651255836662129607783), (65537, 354379462266527335136885759057904365186619254943293168318991244609177889020773034643326071167908455764989477856484346333658943184650713441345993836830382587196034986090193906686509675087421308015513841994917423928952603506606269386169674234872233587334632597722933156759874931069093198924282089710656648546153504511396546399043578232476342415455707036070882825617650857737005313429937655499359233897232357005489025751807702433269950288640596579815666448997118755432315353951275869610233825955200084252056971353745574946471587576528960336409293543526819512818759016078998786248463605027375757435756450868826878357819772369286533920771517649165488733716362794167286664640781077497511921162020537434944899229776508659039264775497328628743278590383993864383655730044188890860622658460615995430959952556155492684348234628927235625280302688359876576976884235840068337868670661194856358141645741893057000895932820976055849659642032546357114181289371274140069254714459913071385794647828220155714277344000241687866087598176449013902125434011774475614032022502605066160398445662593414950319913124352526055787786575690817751836033550573286493786006711787677640261731370016339039800110571350197077220413037758206558067192867343130247723743656609), (65537, 567817297562442792257288470777534527951562308719779267032415594900934219501239815579857881710228629785729642980572335859701282547444618439103131193798438595644916450181699224580838367229486113952080099469389856585182802345504204988105981016158264474793756854614363729353098129654914205413173787377537452639518117442095427652169113529268836897133817884305419091436738836896983354828528478708680125542314847435577749856466501680796356670200025525589323738576911871741259305537135819189854066070617891883444934158661738922671724379256950896861132378475136356143443101842960839483305422209389198360314266750950770478266653679611753398776449841238464866603242509999209757754726678567646694245700009265125676676949661337102918152072544159211109715997231904961708553114825109224527033030635049733007008679489027861596119894890091032910112168175027494782459432009831940193696836321462936628331266176652007786646482381765343980100410897690782875004074195232914995598672241076570699636647334419435944096797188739728621100013173940996316335487276701341324946651854593152833503469419333030213968169085531958150758065911766988793277166248894903197717393739540237563816016313838141930572079802241077497312229500143127400344377372694448337992215263), (65537, 629547562786094111728788911860134378808199701240096283059094083448121126255818974050720651106917026090383151343088869177864165790420505546167927957257694545174511970757239939711606107699484293811951467109687701881594507781109830274985394149789228641869371894771160350371981779350550074788561695765622951732649640866180138844611495128099072473993380005798927563618456793478017143441028850752288999832236681141550784884631609860856303136464886707271086181080446676723525080881963787148828428626160068299549197744748481772298724445400330464038740900441071397676336374126828160609412904878954197744482565980158603386643665490164557391594169042813604069506099737109246687031783853062091494434623232041813854698264945431122358745272134779031955665257347815068049003439663845309167955326688219560751911741842517089186617368045000471382572645370429512043573097646968391258327058620021122589551709761858330642674074447606190859785348288039493574077383821622501394122372978440347592711589807566370011194365733974976575779151610379531964362392925028629663059045262777761782292344659473258746522151578760106088793218565377406807931400899713684045036368378805412491940368283198121193162411203981423268473488460383493197619044803410590370169379343), (65537, 562556855588259109318762211122033606375818268034490047333663963839902032614528093910542880175818877395610999552330480074288706432296672037268041726828583667589219516856905046506928353144149256925071527167988168257924971753418865535605289870804474301539869198729131610340251623186581259965732077023533767229272155899545438783675482104134559796645653685642113093838253842795766089565552633691314948332385656893207513790622933350470707912985889289009628038384311956127196528890414308911085772498502719657257375475233898524845255531764390536150072641969047670188425664852155258271668256689234196206172649322201172645748755434829631216971740949197118173267643395412817955294771672078844525036381980500218827205056830532001132067739943088506329667608954552976725361613403941311758841678599499191802322889283234065232444854684297901770438571513312874944904903568943782076847000658216019416424570723133226987166389809665251513539948149044958842442153932938849386342117325348777660911437066268127510459359243543802175036510135270401142494926377350345173491885361369818077655380509046835352082720992148431312050419199099950015910513511728729437434139956907661980251224648596179335636416552267788933385203308584896338600005509561313797867765753), (65537, 675501335263925306805992546792091725954878027710241985756300829353772149655848766648664002583014071333538861890020549982963795928251544671939933607985355110855631041149326276782414567569556660397387282479339087465688564915599663278517695455166434496248846734498554871420990438886453238370055188088418791431511393978132645287561787496304426387596042332707983219528050432333211157792830637860091132418090747852291335221484124049485877446380310600865469391030103813522697892782027906553168946435113522302846152582613364688525413334327008903592734562413646916442747302286851935863809202541096305757294972097245659336301780043511393233431843855225680355722694800091048406655563702179342480049542011879756552043217950332633262776903609568644493992071253656449001707792764886962072992724588869116588398105124240254721106337258699624443436220658912569119725381529057418804598514664440663124609950684402033524364503318790281075194046791756228441517876635392333412482831701599456481551955129453141345017233828572439406530809342659713715379950145666123187256934374720399843833941858760632314175019382352552139599048487414621363587223085277914275174303263061099564495123292912441016009888919698421109444567476752371658197664964925718016193007753), (65537, 980496472410024777212397321021296092175532243695886073779390564012186823320943735733918144462243815171732064940891452887668434766129838794586456284233350201565109337878138811301618123163361722759834616293991419441097831336323322801692926528134891017974664677802182101196767804022411535472536740140239287133673564563692701229091817855367935937934048270086191373252225127388035021017764252839261743191474979467376292306507156823625821958543392663789488925808699812102203497597620349741169416126916306575634440810965661569109297266294667190950075016726495746344591929692726875905951093929468932948581469282740892485086481302565736095795066851455308060032506740393150168671224196940586770382629458564203340170011451978798426913628339341025355367778600389475035331058379864352785443738313959940764372848429641786431863232139071700170913989082686356578715172583237669786487488262962219942219226248258448425159528786827848078106146792504619045046809187123143305325953631572823221979006460089223258408076290906648789869277112331101412992581466765343810617358511789787020659970160647228604458750543371629871846901714703984111379728485887265606810619741408124393080732514355173245219201828425915072073069638520629020503964625471924703551685491), (65537, 625347963211021461946841858612217806887723405390413975085819125143024211908188077394095558036742322549375045394335122129364367191859168052218471401922200904427224817704299954247817931289329236332562489072856552123869577182121608647761656227184093142194879183939841443276666989086385908760901371863814492898213307680584011319400116435970844498100182167970055967132455732241384618742584111822560469269335278180246002079033189852006037990083795674418546772759912717573140827072290651260675584798722211269096090975302952492894045939830108017149159265924178530273702815468339460859698097299465373761382293483766958796368248769193692642330102749218331422788366066278092568834207452663141019414067390369319450539663340749699771643529738424482242033591696937219071204449803077087790440706164893866757199848702524309539263885140871810051941495857392375884203734759423361425653194772059937900126750732140133436363421938252661829812358831086787984650384246257617602338730023294200021004498583616279249627819014681211269752360981064969262214469059924530949115908352304549649950623558011709911361876209627898904895741121849675863428405954735469813023145455780030750574892901443350993574460327723706971165430193135149870248755160445793588968744551), (65537, 365385490046291601726445892414939556871817602202552817877027094555330174375327685049239782283332712914121264622349533062420298384397099174316329414216830075365098900678562045059364219061606688990927512033473904384613822639405404820412055396719801355341569915803874293949504089681741605162229131773473579521944573840510062361929334415208472350005627757738307052463203675382553220949845836389390439000874705579113396291209263839366593444462542597425490842302923846750560024539800714847624210811193567966760006152918780843389103721727548064598904320528356784993625303165298303145120209398876587234626256686352545565134276138954827271462186079469190833763517762938156725560167554097683863453925496474324881056018981444172813008174097760352298120605485027721557994067503909509181533980016090779283166015230842298527952880475230487340995796866950904712540838726222339583414024255435616261309114528754980069901987446124063656810135258855491682798642724198930333007564523821157812631686606742056497011633808884885958093205589252117859353155996068473155042012348237109469755215982143353807676516509871183998343404165557536918734959697527248969437319815833790098306408116682983353515727115716427040293188864325247857979575554191666880468083321), (65537, 718468543613776874192203376906618461254267218459514837981266858454949190959552788386923865887869208900806264574778617132482085658463534255777697319600237949852229432722681696805017235436745151540374120714387701603782732005841716291149864793536783668945476938918025757794377063373394420993212773434997846086904304486038252788607693953633124352935797440963215991656039189032112984901361852269881699022638421869250077309180474853548898220975279230330504553779193433051144394895386101870089794816757112938912161785145894518679691215354209474503088051037956576541481088686459297072639202929347028484302394198502088681130100018787212023860134995941407863274049391552518627219531319294774125920080855332901215858809465002240907052312409265022818732278074015435465463236076478893200615612787810453878645852921887046123549366009578812804397650083342539208701431170830451122458085820773749139722973085437939090808832022058447034738750531724112160679563452045774440339195537271474803290029830655244289729670543950001294284097752856309573065016658877201181528639460824372402439687740308564189689298212695074143253694534948357946495253384137399678931658925656128320331900019451929387915021201842051171085984641650054474160874923423589551237037603), (65537, 580257404170984424243801218390287131573440710728854996066039251222526082779546941114845715284607458792796731292923451805554297140804954946935771273761561105229829583397555701563444139149352636699298306565266278877422473254261579324656974587593675141108539815357782598655144842217941844963835411098334017331852447494810535465388472979439773536837340402840292263809664852861940747926503076898863226268332580333261455559809053476590276438067063670583643183032879551808758569759036847881247238487721683950458287992507173994024837529525158953010910145385201026305161602978438444031944089475641404086073620629556855799625133911394625221500839197046684980368613148921923391401124338550272965104932050522026987084895784460433937563770228815138528834367497228560166043562834510755838279645601669956384592802803961066711307961302450309750519641233178354864127614329143567340924020440871809686464786539494650132437857966910473234474338664680686083863520962941760619230751697499208187902167062290591382389285602396426455223813600701577985435464275188676186282275473858402539871724140022433379221045829693022199957059267861695109063265979759027542383403258096415651603557470448085025200941008350625403999869282113279586211531330622087016115441501), (65537, 678352584676606482446122757504164831377155410368755238809129946224297487014852843692729724032709621189136110003252050197142629471142246061884610619505574890223334339936105953966770832996584565595596756486389841815114898292093662868334679810067768655747221797575812688449074790781097544038923022553393063057885159273570062757207086141139863136702164880525782650141435105560222618294716603810592076171840420932257567789434156963253096458412211861502152933919430715145522406496751789880492224834828333639005561391703096880500242694993027921510732250703371842576428268941548785895263452416499869924060189309862531714551785137178594009596989717665196284191866534563884233844898401876080748838063445187346931665510159409568929576401052062874329735331894082123294476681433256908630162660632452276441611549463241485292924166642632124582990693549111643571677203040075728875383487211220291602461813327108268692474368903172252233181835897089399924010237656192609141750610412072627086045476828471253821101881724550298563129006582098385243080044460222363356994412908592248358312542666519261010558009983816910294633274639654142296028027270054986649783353447611753192990275012606335522408202771318665069276045300627620857341422120779804976543494627), (65537, 483369602150122062790034115992516002749108986762431541617692381850424827196840619273881688874835473875718555485937856271377615970928553573696865500689456246677869457952125965607135479223416738675791165892927850862992322972846044492088145736853216547328291331688556943571112068726763342056997036057955757771213797953235172901394993424568108813617871904659146205392656143718391430665550880652115816658445724708159105606675636192355984802848247219966261498733010803792456550326750182665664927610793614095195481962254310741177053491098540525860129023936298690834483655126966593338541364801630894421538225351801699830116991498569396418544248865727242990550169568870214036894987306173763073315310881113973763712495843162722464411761558067554267234583780923825974527488757104976720270983354141215505214121244876121526602823988597461374880458771924187284080670552990722882666036227221191744371752175579940125218918373386417047776279677091749554043516127571417491650368205197142295654940139733517499040975306452653808747803904870479384936829249922878674660251728333597713967290437273181489957965564368274603795053791416498538454709921751758272222076191710710563028070281288444127985912662262715810906848567026250660437462461567825710624174391), (65537, 787714575779170429749639341068146463756939524999035666941934926960967516105658322521124306666474980169723615206541108049102632493624813179218670103649852414555769463735039860097432551341701223168930194879642505883828124899607114957844187599583405050708976139385659610253190623727087479065615411020387531058775470053785158318745235462746044574895121122756333667704097294839974136867723559321750192069394002423749933108222028520483327284930442402188532582036497627935152742459388702848830813945737271049433989019923086285782531212706399130581605370669329967502650843751289931959430627697569564060774023759328863213449570693322920790326219439329862329047384143071871299692667118194743533844508974409702972194875981474594756458617913884948301994735096747469403268728824705115926537691794337739959327112908139901266117364733079234104641855119787140361571616457494931058114225352728865254273148349521983577401250822050491666510290187655911258356926152083863985700071920990703556349896532006462788117081893996649230272238555853815983743985550342580225143900819354415506538127987717246793175159721377531288626863842609041088982140565580123126940484752253208731183828078442985519577713869030266088670760001608938437756210034277827071029195511), (65537, 660893036986373377710256099184856827162253980092980753326350442058409524547835759689883814248972972727778365574230019467031045086941872476069045125200367617271114592141505088019521190310783312778852854664733693942624508224389899861127886583338990739273228321833572584516559575759361950525826328052466859060609051493247862368257086615049259684646527442513261568064915872007815264642831388734988726964623588727782225578827586995714251214139041841494895199655902349715809416970768558044885085153837967329908916638360439638473498823179603611172889701897748622915774190292592222314745203960330067230938440053389385795775982850911411501011919325251398368462270721167283745703580172005856634390112506058546820822221881531597528948195733129862606993948036338366809126574113343085406824375051058825292144271575668259020728111901752962899466551128079902961967664000037277318937176331465855419054431246224401107739850921819410609412299861252565977459982765029730698476960144282643186227375169399764221619623430520734204295730010559526803316534541629540948238466210806547669778307686231012563171243717083488207412141342495830902910902048418783170629868826966533523266844616996466987332116363232168490234700302064264336048677995869366355933903543), (65537, 741086657734461023529992643849677438663415197800233037333558453056783997652872268620249537803464558763163716564759524095656248183150436056425089523399901115245296279408974594706209292100344238405621662542160302843629470547893591814616115111383140325037303266331141555613118653894003817164600773695067133383960790711852815214269143895445336848846489490702312788282817750743401705613333942025962912744483740446788371995775671965832564422571912351380595305004593272328865744328885458765038044047463085323147931713550144982537781105034784777393104797774610033135799794252505174334038312504655039832938114045526815163402400128628684769611391789407018014967850115104338654460178000729104243464813278386719756967142070233289017910836365993899415548799177888441583477752606036973928190313886998337512742520290770284834118069442603652634550118548030048251902762280394780338944690936496301290619318300255535290604353926219580644656037198874911994194274906794716936925516834909139576609452287202223902918275585852021836053054465772759877184301717776514733369598885333602137685058237609224474230520062349854719190025831163648131925544197870866001607632817582270824847780830518529538040163733437912293225285521049858015477828615904594815922568651), (65537, 357611577466316747404667402040221746023654444899566186917328414240050559503107602408159201758889005283824992006186764871405003096389928362781283359235711632177784468503711958897311954581481565267305265521220459915862379558150306213217162017480673924986822396526945180974874440037626312503104211601931100155363530456339513940152893924507245080016474645098743570286340049995903128017602761265141484720561902240941204988512137385884805642065893308394984644900594403697234617056953667099226561657495787103012440159302261087922497658855332386859770281718571855797670003731608277837616194768995337496738727414531387216262179924618551165954034486674053648134989608685095073197385595593919435755089615097051906588123930994080052606719220972924809712102006524085286208062257837694462901045380134320939547132559723421313515081721547898169358734241093734277314878221352406765594155054156291578542730000346905964554853253375166262584959220845301280520442877836872982293119239233395742310350872572792305122748983218924819845225778385306706923912016557297790691851685410619188889591305334672405802575015228550332491885750424853153298045180107408376428925338320016890068432018462674455870001624713420968759067627094455036985979413189438224353270123), (65537, 429725272894332071603445481998764332888658610794231786488851438595790205719840888943475748678265295640211303215550408716563308330506968946260634798721609021033088847435670983164870019264020223780759768330222139425298579471471799561738012922118110370966891442938210614259155174613344536275602348986100257096671909266092035004716900723328804311225889207367358226576344119920982256815602524971787494990951366482329974881106263654758408884155956094348405226015500719718010278812756166476971150879176568303489734834431265101965487954796092544800609936440172566354989209235598639298449300025645477773501920951371259282818883946289448199245785228694985395781140240158576997362283543994292148288008040966447428587063449069737971648504566042284103581068029934747619333424470447164851478077251465517168985773797375476815789303005595456739206573572730713833976300932217808997423803421671273308647707744165373031217322253948311267758808874945909998748714647834933633215792722500870743672006272696178698427669450536265193707213321028089792880549003610783181111900342551655241794376462145658720904314389674002084220427934335162333369441027089197343469495913329692216570553495144590472002974988701520651628321732793332061909583470947197770432191289), (65537, 735902290756004123232371049943433067978328528355271432111497246106285865483157675629995347336241147469603856625659534908944582775787697190262121440361625642596416149821766025016644104705666199667292860277815183052111505720878609389301587802314009851826583045988085104642381056411639871192985470242014192796768491362084418784122490173725369607801485541590327982358557330527602566619688199804472588950510905962107877210906399310462862149671002283379287160808691369922526328727183388636346751811418676493913427348615161063120473359935494561372157192162669102840178236629143080677466204818780633818671725476299887656568975006252857659433103033202147490850564782181787954824333216255795702066752488106552855871341742642821136020813280190943380082364729170429826690843910728999941876755187305044393220955457776878553533547018360339544297151262101371363916809574958327125798957323272760099902584753946111628794547402835485415954396795472921041725603678274549271531778278956746586335498761106993663702810052646850666230529745278130037148151403213684520557989181334066642543331984165327157043340344591353013310627605021914940798743994513400492067024652843556536704583554226001049225538914943726823609183003804414856693337113474319834750788569), (65537, 619841339359273126262809168625264976393992883120593660959768040417292736995080013392036771504935473480811640004377321498117865817270507227139967195968437490738046417896614610019885308628262071213426397447376616833278170390868675373379219150837251746935186388277542136889232582009638611027758482116670589477919651028953217370232626482816814679892136629621685817370150923882598744452391977750585571427773638431881673824367417904569543242576721813177188909520682640496669945523720534107536440072772255872252439911561159418051982515151506011473112828031937134016941173845141239666301341090783998229480239826097965598714414570145201186512509699138179189917142282387852075251048381898390877737388440347252525963842481416762640058424046431232830195480929091504663327837272881970843627987136881771044980132065235743017457429625572428171925276919834985865864295145264704004947014775006308066912027264178505921252138949298050485508179875706964428781302528924450351250611410506646933534167421559183542926857892126178464107864093825483951820925781913562320000945581499629259565215423834891925483589197013565047913045592299403431560046681885531076093024543115383033966940812603394516908073080974680450883158361112790950778476627757707766486876077), (65537, 801980100974354491642708917586025291351674926328132551675472339893725561572710143157671451500147004738571553269004139863819490109448347981034592701462953814356565211317791074067074263580187878972521079632692990727371346806805809578548595209594056685876741575720442187352624694911010883289854592941955985868987705732403219976600373886498360055259854828612524168133065478126268084501136830577583167433707157127366554214686946581855164435901312221410600302241747105350517697809334115876163577302969049430162412658310945870900408458508256732152843911090714325197986778725576887201172062631751158755331415139489119007890211902517650522310823294963561279209176267137002865196653257590643131534514723689184046182226694632562734869478739109936482768286289472770053697200134536195580502766649932402127276262143085792393054593060348773939733792284405883180382219483134907599584423736783402114362652538893066558551793396649563735258879525355412166765220600209936099522311729843577828580837198654833395592187806315075683823524490787960062273878444378501823791536475060239581401179554762532373251757751719507053287658747831123102355116833499042070003797451800280735476944561078669039587110087553456147959810178147967324979990873846816875047450421), (65537, 366175817362997825036134701871064602380225511813871040056228039789573358616967466873441458485339515178929722662527834131241538816321865865115650866691748432667253553565938003068243397691554527297566964312592613392411816354472014968371135562768919419700463753739030055477381512153201251047687964500203427033230724357927952655679404585693658432423814379759728925929692132252864168004723080472265011790027778605182653740983206829892431682896915066029595024129339252050965150411142368469975256164949377164452652778801519265388877134400125147550155063981017871626771803919573791455167484121849127596584000786889514193960292754366626814994100290043030983053866722351482144426145300030632713413640194773345169438432871327139092439182767681589565274717659067294916502006720788486089260513505113340054115293978998368223176715648951935429959613143535703914135297362754075506811735374726820150447292980957691488049634241147618610626526180885724411952911999022888279719283626956419896788530256940869657650640763482000805307388198783981707733151019441231088230115942892639413576285661111313506371014334290537517098067909435335790290073160792768352958818948986549820157260552506518497117309953867775619570356200751525647060226255520046839909352089), (65537, 549703784068783092425304688483216912897379834381685107434419223636615185347914076046378609188664581239726065081218584242546769249732987959821861093201232419204692998619351158828425632633110437872426987471172151617570958747442844159525795819653346194432704469205796859640181492598962339078771455822461797749443292445856860603105762654568016192710595162480820274877104606995325405535060777580409449302462043022583705316978856612518408458181816445523117554361231792309869682500896445347901947178108372202554468131982841443818735959537385104362503206196947944976056567031001550469571382939101236112530063163268688437821901113459539624848179237483561238974750475840309757417306397940856651086043491776076556642933241758845513409896472171316592568895891299931511019241841956326856803257434630598396246758815776592932500419677624692932833263628217165823874539418548929113559481666929305848271864073513807692919674347515745243939907477186561305557186583862227323717457790992910721740622108077043869771917276182301426378020479768451331400901937570334082077129990875471700048984538134792199256716108326478136321443602354179947017220787823418510905642277734799150796811317283749253892732779480223689174628668957170326041006489216335188048554757), (65537, 556161903879557287515938728815638307194964860000891018457406928542012974926953840579996824674168725915207701741005150862851310668542843670963076815697267131075017221253167290030090306512213520028227153161739401250148920077621238544554871626228223527381602411383167831280862277097963792726476185159522300669799681339373982306791973636196914847808919351833302145704108133847933768913938187637563456070108672366662659710617128727558823378966672884888117963421170938161376307185081643905029096996914361489411160682794729942029249426270824596953573338209553366912547759014602497139278735499119277428580422796176411010131423048978542953849816798279561841221836539872232765749179809897137130774215718784096284614150975840644092965284492806255689576954443040451347356125277823594636869394196058179662151506357348823529441938727900652136493171853899061678784271004617054059833682294850032032445034994178253284778024354097711181566272813103290616324857077406415546459271593929299956388612425231384805273913083813136046402150694804814497051245234337262944984710796084566146569301094785676328132725964724756961529969392889450720243738182734869927053633806832431485772768456256794449214913092197072786660307326113617373594397849096008873652508277), (65537, 591031769076296681179458919676084864471878946039754984501036831242074060159236796738223030639012497372365031861217100156195419402419126664800956941156718575264566619414120418102408007754702068056248405418219131158577322279628621673540400872812114663544096020367828788356247307743792963120382013605565373192598544571431294125516610809592336314864021090367329623881966437299877563055701982265407895897814321390397900191350295832017330194902760926589797124080940595921664193105109939737561617045652551805624632193572551401885616305795056313647389185083903331501083079035019796265390347105952854721968487851228777498331788038591271431584785174540344389263113679382666301437605248570132108855422357826899402158996588730731241631024937878709361358747605115088939382003919961485835532905747085465767803120126299689865272749785491524417398105182960616605154991138094528610750257486104448342810266674067447300579363024462964442781025524471750970331464107554342316861658842301999115031364732487035667699823091218586870535133732564953298714763884176829318913912470864046414682344952889069720960941108210396154474793407516057179684567924448096244073182959776563461620629154187213692209663196377418678485020387523418683140049658408742723365752687), (65537, 416444019052914771811065441983414548874356716121972032718333384468983941098129624032841785415799861611678608931536318263615069713831722002292019082590199896987371557860664072195028136298970763212377864759707728924090944408309259335124526083586200781734257040245858817068187420520571183594906621082218699591936855075342494111163246653849742951750805699996513795670896095891966395368533321989900591286304234565150798323326655442654972495635145910663236935274823726397686059809334683960324279156370522348169193366586174316408217860752853751204771625883893918054956945532983111632076606763517335330957241114047048548854708567292689470937984618736252915259942163863149043190733466341950775430674866521380853061837550002092548638507318964701091218936157854470924478342991387374649501578442766814768461397219112207597552303684216731155608838833561590390395474170380538969793165619473523108740570412653229951339295988270806646535666447977347088475816301859023539120359566121095583310461813221345339080619993761325772650547026617171490510702189068293186029365165247277237416258770577418298464837661528354751019940369006178236338807112014178726433587486465921209690174037906012101402001945034826238206667792885161845493346879914717662608947363), (65537, 609859434269921158944259128952289509056984050974833862505157780436733350302172597786107205337294055125840694553794183024669538979766485229049746138291851921501776827680168431294624125363732263224754412382231549097062533069269773894301066221696984946239987342699114491872914816231137084230110834793611186848537885937504226910491867984193234429387491752828611692018771017321201393923383299170795500297673350806716018669091238556209326513139784544728767206144724347216962959852400098031021917931822456361747792369053017942463444024170416830669985894903894982899932396108403452615091735334861956508766207495170607097563876868250230901244215129214721556795466389418479255599928927900272750223772888920021115142809382843796638928851754345719624307739606639161972240052011996506911472651999844433783570020769063003599836309769809503441518126346207800693538761625187513340537581271269710677486821646238831897052142637236529953639165609016331540848095312230819714750892692239467576198569085260792960202045387602426806953887637116025838460382354338473964187763274764661750779428242566190134868873192310350548221762453400869645769116613496975947717331406366297937256638841936866151954554689015145134609180676655965124218243458924720970766760381), (65537, 773045071835360152542195862631264911527673081056476109769045109864285036149446474184497834653772980566125084798176637207334056846276098598096294673629473076221119043874196620222448907049181065190662242480601432831517781581329070255981856544377368550695900827392299739358039181259011202730037618943772613061512508619384722548847760683870517530134128108168557784189118343360014253570900767727340293754705316437028529828617418102585070426309910082793439236048111601572511932102136921557312250257971638959339366355173270687115558953658580141053831181419453362061371305590545545529729434107959123589741258301713916076212620796574583644549195895397974616613308637704095843811550169987450071021796311537361039231663937956596051964462063380798034989538071933810834756986912823142849829990832982351834757273492804328644359042295991654759241401671529673496398961331973024327887137067803674253812576403318624753842069897039053321404831257064810072848443423417652358250681243152253647706718120775712957891613927186137483897374447725497677203312371654542520562010228628946136304131041538260510048937417038490340440708214785399871040349919321939337246759016935249277799262967704432884503093329085282566951299344087281833491334989069599019670338209), (65537, 532182502189841089091845438691023708524094822438014318973075255822098888019673785530256760295389825708456433503390179459450550099662199327849183359354844360892319021879410805866514450492601384338618689427421179499683380930378149184266273873825666446196880084742134429257349997471528367620120891133987717450053367570092855462633586655714468808735670086157667638413052375060982724363693945911548633780700203270724286552972225251141439451575227849556153712798752361209984564249216615728863283809359827304364296171815807792391137486150950335160315117597566253593425080691763460771783246059064420645552929728119433240898049416149080517336786648277605559813469187827607699707639607778900775309350443580309777788496690930459804387315415032246520787192100553129835957751955761152166097668712311494488832404017752667434086334446742204028069374882331546205060001629496443882791713207177793583652038241264969620597284526652061670408593942141002786689735502497493586841836273087260086188538371171761466324827886709889793157276374950042001898122812800654622826742618894118040247054886314834283577656862629844215713261745981610200428048416571028368116272986889836233206114456212489235576016260352584493530493604621098275819176955856426254884952599), (65537, 506872552097321563607345247158019659135199366927916729671469483226118375659757835926047014807062280619489266281019156205057211790142060441201255363624722905994469341159385707340507944049590841378108215886662647136111131483608372963272512299352811389859021575410565952072800457514030687668269566120137566430795659717347787631272298650373025758393505264632256029963819437860876605827241657354112887777743048677021865772317297419865373317074529891292421775392423252090925656594318079934290560404519690463594669006946332278986629217630612898373577301179772595553859449529600062106581355996597052334664495660305457658983573604629925597439100953132711296150635089645679842231204695879283697525390887346595656372316674869735161480887223679478139900857027175995738732180471553816342092076889532372119719417857700820577353183463840572227236082917865498642386540052324759810421818093440022025432467703339330637451440470672496926326727823206935601499457565379809372388897597421043214093275474153005023103526053285577284858505541444938839274213381620612930271280704423184780454529650571735126445651409850055701531405313697219514083117135823269104904608489546444295632734165162542715682840840479762531944701156068834299976573574767491707614354719), (65537, 785483444394842458601988723366178185574708615362583464923009722411457375523185173556863822870326945139979182890935597818464566835818293922826306420505117177040572710582357062505263937351834361437294394473794275165445663597748880268224702523688817003752213231948520584528910310990707823955721255964893157063017682302226825503747714479321997299468815881915685309195892744762036443333613496038186824461343408283402905178038789679885634993159624471661131852813645229782531102337987415498121933862829115318265493402829514570245512552700784227244542120226733225903599933955108197341411112887573504969544694593620205351754021511951519656192000006988489630893225967562142289806740272792303002096069684936456137250589255516023772116801777397417983616631784408238711122827882846537138369820337070356769333966196214282649608203298359389801169527156908212265573941272648931205760347706199020734629432057083443202110021148298769664386927496379950528584837697673772106198683185552372192621344904413261583549284952907038556117355472409395803019943240277899974425348481402008738122770279438634368670633249710663990539908747996505747807405608138141613728835324760212243077055657095815774259338364235362909033883313941055310669357354680030557811466241), (65537, 511842277376630625651338505702323962133884571931604283394886346394524151087694807060149972502954658419714641352915413851958991667844419653880770663232434749730149305410683900255923404033253522940583633208804745891206110752234228716374268823205027772652690111377408798054800975503108914227283156206636549112374414664271002055257707956944920947413641102689082137580674069792723257259902974868117955293320354709381338219302970614373688380166069742595648788593331448717488631174247045633471108958515653578577735669495900529277363376259229223835233901784866045312353019290216103100455490462474483959910636212708647532487633618974801989349984544934625878162566712263559632575749504834800165712182423453678272866397538852974283108197966860338330940017453811810936246199680420248098825353098401315797681991601178995543180891959022459619236809048573259786243259982054703140030531549571764236956565883522299643765044972008988829207838742320998059942405638685344291786000137424040682015119817607615641545704480682186377974187453114311947813375414597056534051867696738864732195151290823867190780225848264696898495213669746265912558312531115546805126219570202343879257025506561180321019237853789071047430608579890191640739634239395850680722914437), (65537, 688163579465566524580546135714477440610908067265818421767939818345792540944308844320039344764351691265314837560092178976581783342255026198658900215779828164011705840474608012110511590058084111861061912611405692816458860541100093953179578134082692166693502687686987718562558213613784348444304046213438095853703591028570498866729840588034047483050332422450318222202072346560763853114462613174407678891632586176432704267397626981530975810961856214376056576528575128483222770253076234262858001797308018953483457897603740161713652923598483020097540422748309095044116041445781722143305082188534225872067750962520548689768468137848812048811569388632092782195294053362167625249122445749438088938291484862026559449022649537566577268372567481804368309163014628817715328999669032380617192875852626759194660777326303859992419129877662465924155265802171351169875552867374193411902787268491451536850465965325079227708174195519086201178050690781072993925452198361608915434832464042800778160457739189770143560136786853941029376973410774362626838005862720300136277315662315430324791048913790713096050826003248819612530212979310175031306263888042576419106614516696777193313514087217905864407411216071574084117791968935360881134327421220388255936863733), (65537, 541924323037162277180065352615704829472248229079987060927423113660593707821140874292583669313429056596694625133281838642817166499156802036885028514528705198340625286067184299250931972783318450577126684006493813052847740476330849737629061592531257324491551355635423191732126739348574831068859103731171318553629100158357153103501800404750090708967665944204980317687783081246137308626956769793864157314113986926608700728023680466802184443738232428550088433429012200260312474519498712201721680305471490082304472501829468569301875858574080711396937808050808123178454817338784827843928630063759450987119785259169589976285810116513624124687563099878523042743854495426616374714317812100912406557849972486220568196558860888251920190207347713633594333931683809436830528909741459874002563051939675976865662340203328806404601926385963399974102563586037411790244687488233083659557328933480986442357803643680720893267647586384577302159952086339116338561649696082045574884452075275124612261102813323126625728864506988020914296339209530367177126480606995217222321575113776146627474049968489914291444113899160436510245453184968874673754394990097891228979638244618840147824891894109900086789912869855697411878052710351961977950412129283003156099177633), (65537, 670380487719392789128056162197237768187323151457817753235754433399492408662574046962580281935191243174385772574731941556124175890548231434019840402636103348851148746755965443224367482817972984334090514350755244469571086657318792924241690370796409955722835969175637478285916370554535034157056185655624252745289643415989857739602113674788507545336104868897965224810041589016713689383132665025868898795192612613122011823620208387812585201242594696288453250759769026220408950011767835479734945506759089339655721010894012926036042605382899791528443079909407872817670119796406345344493335201178832334751386819199089663553957754962320984098770941909536976367395657519195696655217256041281791653193864311609313234876014848515015512636282893442945766778632402525520713952572169252953688070505516680105560895149487090249498845535955882276828993862502653239506772632178700971960800446124377338176774855566418431512532903335111535776942047459484018727037114129704143653159934651215473307609438880375638851172900022461115236063183746819100141246982216521437976691141274194761032470353315297776904753639198306927809433397705034118434447433324416840325728085381038495104302706279309320008092286839786443971051230248500229251522702050857411266683959), (65537, 625259044343461944190490551715657610723858834676122481394057074036628350437650492842690486537488268249386654438899696328399811034961356027025268053096011623149893893377343784681146480339838227960759857218458572347701211984040231228769474394740745221691595684943666238534542851284851602964685766013820854935635647535920657404269834487386192510121742238663497675830654580967782791918317381674975889329378952108069286618118036817094658190210385936943960443515206666839909353218053564424315296034400594033049303927289512296338990765703325150757425369737162709639550836696655991555417278197245493331291646908654471348004205238130707927487413249297889282669023479418822537252247862597221404258791335683840343720726516743555599029511288230841105819638835367584431492227265781216593707642344060721721415587528866816607837962510959855152739916524430326319451772680934602035252057214251556583492127011183647500872408039389486110069854702274761097793287969576031158391915951410772064169611504248570687707625111884857925833406214870819461921270358452147099930419291226755128634443846595700879832937099162577671947249398690889310524245001021288210174274444875586326259321237602588957971371360735452569835747366857909206127672901438747937800069513), (65537, 597864845196879981775010379736535077532680625852635606890620547754961709527051357688067083736972322730061472439696283252884099295908912762731301488116011513946034615311192602803333845949190898063645810900150510728250165684383822224082210826499185705876261340317427060705375565612283240193700775755341738085258261717440877584590434648765916371713105033103526352926289311417504861500335720502169206949206172785549560576131521154469776152714840731513070062226787056513771572354883756317337793336898505629574693273525094399946916774730551759775392519442341732822232087188169274764340923805199336013644108690000318167384010936537172256824031755832616580582208685133641082453211767600326235799828285916441220893706087950930262754200386765270475169615880793804824755425625169369673490817030419542439392284805159729207692195707605410720540371038484500627333353219288505717808291063368392893155603384574298414666592873486096937281072292132574340668508537956784938722029713264005347303737028802438410421234567880734708337098994553575111880392113160132877158146884164489552729497144843003170891300667546660486400208589004971259062778420417346638685184954664484094479601283809258132392282562659428765287385146321743848075465097655252152299142477), (65537, 370289520639862528641997508303943682528952960199100116703366967464434242100042437299066249229988375580216777243613922349108325535732164574651522282838797251187164157315175821617534463493339877336031450240877231137447251448791075632025640160119519849103580718070707917443220977176108597010557682564064107622453615779532512616657821487187085260242838942838603458217455470726374682315827163228884649478240852816623509321484176011467255360950277706835979827336643217931966551871366069461126908055792568519893375698833274855520545639169188265773995341846065533023921420195696072295656023045763600807225045641025145349336021745870833904968668329681358495246720784039359794194665270761119467499813921311573522072119702848297027809089193797378128815010532312554557731462503518495796001501464243652363103297503493259428241337215171354748315995387479218643972965289134603587594116906902716501145264955275694149713844787439913330895918400444011889533708386303925877438728019725770921620396362474503598364885188998788535250690295473489618326021163520950654153823758614905114193693634917697386691788633415484514385367562842594224510098196044742860121331628756427841187160795961922855255073132203430599338972610812128629061431976989664908403566611), (65537, 773612114298213840116526474656871252943835813419669006795910448111153448460986789725503716189695809533655311254992992324662755111935817407835337861687724306578025782240454034864932826531616656238133168675642695692343626708218269288327010539066305469304551571351837297099967215768946943106443869219428446706861082797710624479213383339978607588606833524582566280510935251362936611387720645963298838797328532163225410566110882586491520353564638822302777048352935915759645904763055016413854004540927964654476684532879677391462630189356628845286082500792810359633678178961538622173843539256896542383987601313263156794950440589401351616129784389281010389133779529109240428784225710400213609420060827434156102477204932304934855485512015978392598175828992702592201389938490506383138922161667522096411196194021243277146292876616056794094331041868627907293576822834104606742146097909465196348531445373362820564770260393971613996663294712358078923066328822906452243309414088278999212178454500693752205041192416088731306027909793232516800234477432776605631398677581205713537892752022609997596826487017056241738756274677448034400448611394867714869956808096440650315190505143405301943046700266161373623725079280335962226255450821588764558767425739), (65537, 875261566092424969771265506951728883741537673065105882245196649198679898735462190157930348456037915804181681416358716157338392770927507586595833808468776911300331443371653212833759380363053526443710810242400856663466725561825399422631630156367669792033640092415541345347641940071285069105888883591475095219904793814926023991110368368032917123518586807886145701645582450059945514091769267172931789046994621013958654764651755170254930749917554978149738212197142203945678078490383148249171649552139438225084085108929456095870944517703174213812362076967383773776534143936589419590342960735432184319400481432585738267862736886137596272561007435196534017599553118911525901660168544776960170614576184522575709377217264841872837443189407197113188249204406055747845960490230351154829402692319484808223914306539208193627726550529285376903109365427268025776015312073582967605608064865413595590800533310671007711906294690775938328937195383203939470051082642980986113046062203238468922041398956345589959363521956172576702409565870879071304576279438810317785174064937645834034413194987649963119971425530957096995422677855627116334341654020566830749223947480132986930619609916192974477660775324216105457400849066007091857861440827234111147334107627), (65537, 479546275665616665027112196388400078006924285234453937641611805964716959070399393671787425966170094677714813192785527828591604089251850161879422012310102094798623112849520941096621028468027381721861600973879145892913323984715291480503962056068093394914326149940117827669065755456528645450002334020416495655410475948444296568724699282595290545481526024826089875626183108860577406010423633171280565393428461874444264409125043970132312843422472037403078506695442578684941050736061100575454726138150091663455212829429557795173246402192309123253266124233636760589639422170931723500420406335194405553024507958098796055442559797803303617207301598002701241059410825189262526188948733004984355324167659455188425718504459582849167298439659172657088452826661248977211730122817906859914149067331950641739490631358298228565969058200350342771999890312313643223732390267545087779531697003268174791690995125003710323962742461616381375089107201371398391865558759693857936677512680581607996817696186711814413822092284443298385263558731203836384451000083073427655855696047987275321626494909158514163454240894603934960973519092789142023586964329229208190943255682169690369662556489622491373823152119369851317705376291740480277340763814579186033598149661), (65537, 627470838443713526667461451672117692060121251479749307373072966971638627343440031970426090495049840762816913492842192663174986998163419201561279849730038812844020783571977051032803180062956206656372050758719783927625932747933338410621106233502839700654599632364488908100880259900787559771537724438249053418659549830438466294471582198971951928720192278727168947177684242713974749851195300205493743922152825374618683812040107996903778001574944018074076560725549861168379856065115869102622699922980676783140496232881629676514958927072762571783706734147992545932271779524914418978237802749992904531094199381336047141273053931348696200862759152423855123962440438691604557868206034557088409934498499858395126257457461427609775404817881909075089746587080777260856075742957873096270729549073976316992094268969650108234772739183464128374434768201873392342147106119919839612241820815995671353559891448588929114444832376042226083745913292710084228206601225474017210635565820523420103534193307062349670561488896287024215470849091726818454685735592103206708591294718652425587567850181633574251491511879004730107133744352434533512700108570579113753515123767939018005744155689417586017662699128941934739054021147781660310040521691904027368418833971), (65537, 925601555856100590203057655153658744078368141233317033823602911260524548521099033195316159522689749204088785458741768100089510046553354944248158765747808496387160624665149976334025653866014629497034509646571871345288407256296926122292946698962288707898024120604144391070598542163462648278638576742290325909782829018327481442434708083860053200890166112479395627198237243209899406225903103517470642891623596455204814558062647055794120209959751336234111469841180500444989353071334300765121681594298558249295683006129229971177558970167075109472446368145228216770837570851332981243280865562514465862678939350858551043900500559084678379813932882943286920891284466900009024005190798812385343797512980983107140388718520114701088388592415421284332028276137497000712328371068594756038976381284850795009879988239389792568562025950270783637468401701758924809949191141971215801099112390369464279555444906563945980661385647310640758707965191219602334172227946586231042496833323193491051123336935047158206865246250035289591664212888549512480903087587501179124413388654309193368540683883491021204062827593766845314428246632208787044204140952393198010058514289277843240632688286796853272341540383511801525062293115849758844545251308110937782896743539), (65537, 539846205810830410032471878097056382481246132516256334226387144853396784686892759499996721492580643521407647427961618345956074320594733516211059887389096043053709098713579989431961496392208889821640467230894547539773958305061880484580500879162071006135391636409392156789837629807601550469964592260603555436176289460391761462485060129028965569708777722051277183714592729249095451631938374570725996341668908522447431059739035286445658284089587437461606885953093614234718635295842671210641428484732786973194889254704136118306037612842199818867563097490523671742996614304107881391501256275635963553854577992019946795950544096057759414615933101903602559332501471063278804329783253563009388191867519515053785914493370735086319325515566553120929700869502264540095977083893850306357179197694851592794058503509942146489649353959092800941512254466954790590114038443143858290393385081943002195619329854472813141543742369487963007711376193976474303884925517449052133724082380570901800726859298793203988137458752313539362851892417256722255762508666572362020535408779890464488980634654458424748632623448125515805919209645829435192207460293772747130142044796396806860321464673738807735838567350537691547875474871302096162861517931426363120347123053), (65537, 511360613249699650162975973702895048179287714278874412578865355835300140163632961764495670657420438308770238383807164434032543592161407940674578491811566344414260135256552656865044294953154465644214802248157275174419101835176292256560480421809403638349462276278010127045377065176161482588284298319603063852238832680010726767900156682276363945953923075805439014585742289905032509805354289073536842801376600819468425155137510907705437636597449369185279524795360651636821530386771270781236142069608159128851038463684610555723755537597475406256397145225416546681049113952860606670991615277986438681898582086190097305174846034463419204382304849435324943277623525396934818499399084619061982929133276999251700009051584241398495648320450242538174339689269277818414131714711210546888602436422580117836006808519953471743193971006082311545587803221561993449772669703719166782467796581293453644936164211823571776462960039036883937952961472346436000961955989650002035675007975034778538113784650708131472733490682913617705710059049913564529121845028729632654563273991977691305830518908500682536272847087083068449393193635974528118796341809288466671116854101666850718279782234220066412100653859678198369557222019914951120762293325749779050415234097), (65537, 427133412044883789455489243044007228647104688182419563749762039462138401857938967696865622101809400422292633876776758677673150895444463888958117408294652398166183113097490853579255117604531040482027738215624076459317239913869982307602680625036573657791459222567159737455320706652474590827262704675615047558239827476480697875884925094490421880738535063465581486580839961899263616526529381464657723304668677038518429361444338948679704680218940101430925387066517713914936027437545537410881103037226456892960357701718282791489641924365360051054341783725329160319906707263572145743708412034127042714976138356394774874617662979326843060367105722348876838595721641448059811931221523414138308417046479040360730355512006823337928320026819312904082951117942725626456085445799273414251723542543179489652865463964737307781551690920027681593534463366043540247162957240812944895976993887543955927916779252904368571638090948355107504616142596318010586957573641904636355129922622618247336094018081323677754454686915951584685713531584073487817914197289822438420988762550526954024237767017596140757671934824947459199494374890949292939694080716897976874173074815200225669386980879813221079876381836980726223449923350649545883850199215738102180006433987), (65537, 842541161509794184843283049898574087505741008200731559722390732132834747880374048116106997404420339024746930679871476461077515727945452656751767653303952270689380817355496488923203307510062379718583225366971513495611868130186344590059572148718915384627765519753110294161818479923759758602020722809166806118399906380635689458706780507831758644506579587408923809516109375879084322399412644121512768914636109322687885142722061164190042165653297199609740555388194175010692584246211249077421625059401600631149809295395044995355850926420417115674816839462847008637273845747389744446023742522667877388001919766525312364654983575251259022945786124556974953980784770096116859929295351784994872836513754051674862417245422629271220910114233104521788900086926040276642944172673034194238785198207975496963629040698164399684723926171196068374677420381851476159238629359577290083208505113338933642706025885712021840922418968171846304259697640760299066025400593633191303333012231277534113229651011050962464148935899445726241471942783969125546436012050399799620351214831581246974783402839080739800323563302926489752343423106728293387725227193667539748404566364742921429054831458944677087351703863920652989331649861831589662026275171974094983159213251), (65537, 632018686947136870295013487954848444145713890850155317088103299390324449001631658689002139270669884100415015489745256727688367536563025551130802102584660614294301444762429270277973789095738011310642665238630624614332244291306933398922158928294911552524912290665747694883838279922151420202439638492621564028654345097062828886145179843794990908173646300481608211546525600075087141366072816829425872126564189375211831604606877076052164356418451959651128593455369037263981283504581129444246451262841186050955847104067265589674852346014447250787778164133839364239625878269427540748804129333229873861455272132940254273749435188888883048800947731721945308614794000393438528818597065624169758841017006929250053581197423013944174804735137530765121453803408501732719355194892948758641717980799740086836141943073741778664621643591155164633161807392016386089673850219275676080463307076881625757640425538245019009317925343142450452889697818950284453585411442388980732621658319199558060971207917064512778117909499751451145503294243622572896732155143053124455101558894206316466014637892591190315809993772030766463424958721995986625430928719956358837158540181812736848781589784480606979444090684198018389948822414550675769669293785769192364600718003), (65537, 642898325619456308929856830503044859571353823842432598834546228209225701432195197372949276159603465960965412462530443233448976630981160162997578112630253068743194109156312439325167593911160252889106804368033452686110941633039007105096005800294918547953183522109775235103561039990385928571545039331311053525737575979441397540239545843758892115600270305061561827243598023871361712677082359200691377852226224185237895637457414076032254684657940136318763592996176656328932877612553964629050398055648902053635444972600004660117150115030012303172618230060605471440664476995618044141077822948497901306790980633107299944508798336370556512072274026963567895948791268655350451016182726860629486315236693148715244569587551823143551771603934106902146538944088988654525481238910815615702802131123994169107075585918003507591228802403421836867845465945555112715043155459470284469746091082378848097755605038791908560213768073911954529407274325575447439992083190079923196751734597397318665251756605432788960663600541625649502438179868003040995978802814408368900455131443267983691981702110695894299078637628832781504172253777372155435329421860556825031173082560639191382573187266927375970118014007369532302031493392476947462933254872511913015072562231), (65537, 505725580348503629782322352407202473997272811089769904508510103865601199473270372663729719390879427088593086582130685586483416648898928612974496476303955847370529302863054874261005375932010596866559281480890671315646262642390818635193357903002080535335054830530112425312888084037097696893414482447511564398999376260693754153224178159410060105911318868851375049639678344027152008960333845720511822789339066514139451292810061578397650997276271077345865177769981543543543241249158501861118562460082770468878502172296138892827130383539927590211809444732676639220201628235676301480312137766352831728024425866690491838076675827748410880697628632949919965371921187348658400148205174053548857933540985076014950981116303445261195441088167412144237011097902194291007395028876002078961309087151054313049098689717812881209563055295594588911617134956428844298915589535773460956113962320655880134486548507455124132369988784028830835632921686184232200489554552545729455394005338924513192159192108025259906257319528750999950976771189555627719507884248015958814757084046922198109282154139980636338766345555646398518608039474612016415614083815414957176665354005235315149495111524980149405240781483402267096259277781701656758092426648711109208501772063), (65537, 548394201102610794982625163780195970613016703068553225644665109176960183484286201357091736556961977982032105914079180462660284480864942528203727514042550356966511736613245667367920418017467323860316612955767662939796879239950847709491466978547544536998701995292761216810701285624833255624008235776555882990778760404679163362166462783602891214559475624187544966824681617211219608206580170755201657301311035076858591531062111534646080415054475035453518616007795420826958838151310184959557017851290255655897842761470960709721796867339270981040388135245188966731064786660303945678126890414870465749877827197686135349691653210872641864525503333761858549702732404815720774678076839320029819468539744636176098173680210095378948600992831259094994644294242929532243719602200450982130048519289060386693923418616133182919972751787552971019403026864637712324890389963932556557236375982032988689596645595235669234597664784113368982329394080176447567497833770500283326946028571175191992559047573539959888831573071513977931041852006139755283536565553259395855369821574239194217639262035162471316197642196373936664903589315542180986368993362995858769880592770124166509071911029049680278078528626619229171170917657079070851376284411761917197949361029), (65537, 626453923361857774588338539527388370843882021063744483305485805545801051660655047451774693162298602340379964970865660006400246419767618060611876926511228176236666814956645235751961980980843952981209384691948854938645171069050387402119366856024234930205080788496765216359410229757383809253071070242276549872460105818855010738878641570605333258097915686606710139723100805430677874100932137079525300546406513099720395358858921995914040132885933692832873328900781544846001916711389645053742296745366129965562710436970505520488623712934279117985005092046101327697367231869165172959359375243076606011014240209377243086438576517589189512291128335233173285079824800180288909758106182487262506612979083826823555883695578387786000274239795203555651914846102413848524264134380172808248129036812922237536552630371267903898809774992954214096933814634733227773943886876885621302166045527751493354578657605476870013729977385129249464837840861424802486503399594635043382989922226416125661203119765588809573796235161224177253142525539195563386669366574005158066049316995311789967519949273548794290900538839575632776342630873869458660900553274016699319418305086400478132831152498311333923524393091469582717891552292295431286072942269177225316241220581), (65537, 645526935815420956313806767515283321632589882657191372697989016280253790166900242646247165436720380762498236992734894197677113916852441068279115784851260132439916714092925424025212893804755520222210014285280222818866713774705674838482456520961123492624097233431453594106198230289188850835277297664151588359771831024272121967918130181416171771916728145397072356086608608464553661115627770447854878950783362157673942038302124262986175720501614538124291010444245439299044272915565922369335360232206079760101438113973171160869570010748134902786719065760808907053011691121995123106471989095086755767159155994978929961334406139335912495933988936470058394134629400643498656892139803224859918764395520052694461308761343979176233660207619905329973672522404505094304994003873667757194892740383756109286891792666270054775315845014298724624808452782540433217173962366580279400728644127926993271810109693151442475969543838298922370559472200071941038893475157502074754470630260010633105073550380849810024858625693611619980941434264276070748473713467525635396924261638702348713257511179780328608727765649519360574687114733843202901434634882969176139971335773857393714693240179793117340592578289916975350559766317585729907635633107030855342027575127), (65537, 517654325059473182339086095793827337042577773679260495535396902296778029659964368109098089806381470283821262162999438031151716753038643328316493985563956362942366869461106385907146549907215991781062116178787104004210565198840575997384593136224082573243453459099369786234872670573073096754299696822473069824334225697821453661409686129200841437527451316028171335701796956407423374638734529002602178392387783366341572148004751093797299919344634783248971364588643485265544458062565665437031844445943018882197705926037671131983557602689156414414928818140687654708343194709972310073435283938264303885991016548583631086097421891462487079042179020701733431731331787089660303362131876930046052925169607436654402226579927082336672219904260697524975688607642552923540131388361341196081884053470858961042181746872089263444852845566028718887293702320086782320695920751951131629200039496537243983673846174136831301815664163556039317085956268341109786840126419364411353273331396471593158922003409452874115119623973433496167133328250320884172059679767195255423216758141501738992868139344014843756745225759695699290646629314721916736228373036065491333095996232277191010379865378364950642487961906348289494681324337633933686258389298234214396248726883), (65537, 492237041201993964543548868977270792683439214458323178748019300917839790746112264584840754559665119344061142898282131091077870806326639120711783117788658296805716431160715257724946686981185186804607450914263350669168817699543849216942654817546529085877161037810608424041595363675449476479356360654219895774443797376483213511799495154980230490930806617930048920580230003502944708554401335060338506368050373522200742689776345003592723013634726310391034120939544719452352436600594032031992596121744875725422738985069260780435960363308740336263746297457884689751643096870144543105844938670467850101439980020531000209290807140762715108282128813663212704520165343018995303191697331911775030250599624729562614404586057005933994882802414023119769614309794190713641959492809908680553324983582099228960197925215283395170916961706933079270387871752834002639684384757513735889205197339151575084020555607481140274888753567055796973291008283968880722421298249098252240019359841388697933589563805538464137644830064672954421537330555364691865615358647736464136348538360677125860325136180396889912853718118909319836199713518698802368456004176094637311902261072863586674946504225762370182434574746353447802963586797602549691214751209722230568241908199), (65537, 692746512432874983652734543982935305157819436423705779657202532252985227079201368037533732354099565824046465128459689337868410793029917851352533173732793081405348188436299314424521098252106339241945575802485388780790389797384402452560256850307580783651294869893170991540789786893988381182467449928058269734597056275632782976472815742466054344342144194448092181183247072268605619633500615089008537135411812653639080171364463715257011104831735339919600270491358664545293642554682187284535227231535269404800093295792904876017073921560703225963468986214700052998425229701405156123140828821178211346448737614373589922964963286536798768663744041223142236599275555287267640872175645242939364641112732504094312038369722982629661640217738201196831638815032246887638244622236281824484557670316920307919545893486929817294799389928440099492338351219046076836233269133494926201385496931849713432336097067871275374749654328777889626291094807231947527532311456712333579152661648303907925024875825824951750600531459224380575506030191558357037590778770892960446071535463807022571248677079358782321495906520443531652643614151301510683064321289372538988580374736844410170362219266029996072549242371965125268580919867900194585572643580407654088643084853), (65537, 665791675494314951127785975303071096973197255027116421509127475054209161139213840727087444964939458283538147630216708929054954662750853423987942413965066227154752231383253739109363136864486510650939421111379494765030910189372516447843565409780032821831360700992618348435553325461271659025768189195224760921472347489431660777401096970880560001448217148750820887559168491575907238617864013478363115173078290341410318542090465882671423942582071009531604012605260020046198027753120025637777903830855865339354985053300967414809124018910021481685619289438806054220671458108665326746033340909426106135665379167140932384437144469544227262464182777128771835234127755840805264652054040970226177625431057855647651581646191438365837887341977219460505085169341360410558872824918409111782610973304584604314405666013698578953531675393386323284734478321514220588461324605975457660697352800560951390493941365451221149871306263718133182209790978741411255034940049639330643409330623067980616956262543900018777460191208889729409327069218122653199285642242028527394811149780488251458652082892460574642933977618634948246806295076021273056706209231383329483966284351198720682932599374463207430683450001860952637609503595713122712032298124976518526134780873), (65537, 612927307548822005792399272637024680122388799939458880533823943560697339777720236229324593300857175929577912431972206350517191388996601031599494551289315395158890226352893790318306937191181245982434526056201467602438371666278329847495903882077511133914531198244278026923226538539523544315568535583987908191043246868772367932861947777045191064762837575302362198395848120885495944350633795900853028174693446778712376529293717259007900529887488942664844540394658434603096865610310454645929677041903531740395739027590434968770110140744911477947232173616858568955278818880260263699952905821571477547315688363762965726434644191090070396068407547333001975157361887158966063643781618178563356892467377547779371758167074089163599199602786760353478749617298082208311426166915690336418680205154208832397049644133462662829243228654436561908164578349348237414167811377507821152609742254536516960705724105674162961568630624789112168044125962517650689330921607467391542209498049141382954241925937927721673843838511796027051438975876769195545044895681852033156988377348924268015619707536342041229127375592806657166454216789742441254027132482509322061532013463713040738383184520149851810499135349931656761100173374905467736510869115226185064417190503), (65537, 786871940849570073486619690679279241808054359614489301996991422339173673043474753940430680841357331201848337862453941389549145895775717455855139824315003079056269119392017935410949223933043170347085136876074492062229995258861102234202276211720761492990345142487780423706523153995712271851910356079214038107600348706870534591857009557205029407093917999157228487007919976184810253593537838826373698854507351953965660013403915271295223400714269651002741649962755113465122147628009983037333114883844301900362683775202252854303451663309310543266068095463117205811858782667043498442171271293361478109898880434198865974112294485750874603275026799736131820058193261892049350847036411719378338912418368288087504561553009546371261128454271264077513112347246775581676436090389982406255478719541637189666306456402929466370442241127524582721812075604212123586995154749816850574503337466975781363885723566461038715713856895052040607492536992183367825631549416423690869420255047967179825143566685540603202566530363884713321224890059830408040615199152711765489048221933137626563465304564836329190981838387863770023917785969198105984262118103233021329623897117258271802219363109856756657937964632269781476257522945023887044143423828009871960061457471), (65537, 830230881521216478646121591925418773456482666698024363831065972184538134546270637421663570526390345792139544260984814319101139530815746528443876776262915471180597175696605823832827084613333057343925274314231895360191584232103174179520884302953164993601815550869201318448318551042448309349524200825147817712493166156324141743284240213535454716320130616797325062088104096053809798916464378136713024005244526142495767411479821145782808223842152403170281022437152903819180412140841970334447063556382012210269024778807471022089323232251704966446552649726644604565293701224987183453950937243204647981997349232331803924180509309196605773785591138140142593405002490223649698866506660390281559603348617296155845621325255394376993782645690566416481236006058453620510037543227100692934936952818699871112674297934813529101300140768456668060352403571790419824638048133263791456850476760906326027356846350076903758166072174577891369068408195809789829836333484595003071590835477027246685654886895751696387617689862978174769339115555547464493485711318816133510095756850257442448273497619397758898650483140203594686933289055384940783672164542350238997995601470430788079465919636435769681075746641066879684701779695123869218865716181656556931476682983), (65537, 439131665394298439889130198792846969103698032652444220798027632331069569073125161683560271290142471146192984732347533532011463467794212244531252173993544020368313913081621264593162410811393900263212963346468574097019864994668006523502740908737519165700346846635841864730783362509103328290157004812099670750030277361854467190017742709249250386154408762479813602654168521476843773214495788870449102686307025312544164768444726502624070245709151288552478259276516415664320899317072162127965978960153056937494619169900267673910986262719923809610564966827573787614738952707589948079895768396946424876402806709724075989317748632718105765354855196294680674489822041470214463666035303894116907423538563616248409760607072765181840189547267187761561660629333598762360244646578284672249551543867132576773826489397958993396480044902773422331117959767659831180244368605903915782104909869722365261844770854698081311120141489323311661908620117903595671767286369401130313611448390181537676272028494977718033566177258024427232105902902970654497162998477474845510600690372697211556575236144279751241202222238047781352509052150999938763056624682050232399918599456658785128003082832519191770595933843486228505926027726002057157921488734622050121417605703), (65537, 756663455034002226794582812304652619873538961826023126543396121468206441624281940704397319025714766495695766541558382511200227978405185058411267731353464983186944099497888040804549042337875938183544780808012559265170092597617891572327446147317434238306206183791208415642232263465587597096240895950236905875611177919120662460132522880501629904681766822138149436338593377608175448103647381013457824500424627106389247697704233625389939689873045397711604638585285907344295743209237995922334583123276011654435410560162581028581293233717350419841250570175931709658062184670802086199934515733467129441420092510936196293945903326927708927239490441046525523435621449875223231157924870723721951220925056520791983591110162145465039081415063610748254959549576874243585201961251961972583656858378216050005830525371135729631049750828659155756984393849194581372102003202406144902173228295651465511170042184107112351753555746874137922200548446930668488848029117826392750450867416062757719583009694382146425723638243638684204824389495321646567826857073689585672012126629602522029858060828332903344012907764222562713177576009138488066113370204533348902404169776384473690408005923212725024983604537445810223659825443432910207507338024396912380945003769)]
cs = [129235473000262322625498235858344008251328735768543649365530869795111991433171887805272719839373397996097189807477948615741359605105953434211955040964380775788990732050457067000865914532660426561941765061796384084888608904186639361770388729826150819499562182255355496026568562125273111503490870738829023827851205863329440774601444236317469165028775886852525333747788046351648175406973112296261695779181230211841822100481777663668250216924376237868956560551944746431429405769869659875491191224435495532680456067671505291746922512900755005026729190818752798674696741883556533649243535203335565031191027295099069392687880248356333441790875851544053115772378899829314375295295265432117224681696707227386999694350433858460585105674012523163814784149206427751438374532733900435623860126704967829256521767956606830376970466389617482896487567823766175080149113211993870766390941598245544850334453407718408599019633985208218369419354287584983349527246759867555372462841957734764877385660659286116583341918482231907613909459871141775163831378485809513427071056033734004746459967954744697034337179093321620051298991870036885565414327128727030483390540746469099014883001111884061714521508493285582623440850126575514271327905893430931479683881407, 312366754150109211637399574918834155034376613010226299743155097321529609203795226615073898644125495848235848966234476853351051354582942425428712793850782684594166530855081773456604620299397630910335745622678368954248286272466019732439208776530163824855086810787646276977963006429982175896818056083638954699100174867650158067465804416837010256582400184691730965722593361707254277352255814718308118199858205954784758348528674664768470621062247120360753271897889960108524568769831764191094284778113408299613353204213498958990387590096024006783047946509540611486071248952941192879999601593367369609732875927931938426208941876654593955631790427931814008155054763692387409469246913435038513997164930391379405666018113010316235387718033064492235062552790455096172862855166745424476303845489227847556494200776288801575476978227161966028600283983656087574428494911440877356806134826122079482240549558045648225684650578147211746004976798111015820320523892476750263031166894460026122579758347909542381557835205537121745180881145299812733933775880960393266255250598716126191956024291246906651033240956741730907520731129280248482244052445949152603083204598970759580994553487592371027965987551083353087154521638117240433433510753752799364057036858, 80823532509757138842911319221813902060451933299912621220158872475271961929202759569850281813904687421619227323355121964794658822479818501519922901925346351963227010735714175122103350910582239011924012123570170840893001395760382261954565197598583370352703018480209508205159271322763808937449539376007936954299174385463542338331747039083106664595144562846364865674394425685233557374367668570128299252131050404710905790431344698516772112674254978562695876036456545236737169469832325980181806658841081210657944623137110620116099993017974048478866240633432293224020729414447159290324276805306722488535934506230683109111849749751409793352895141293549563680573292560702246999393804109367866049322221534815630119591113998871465275312580630316444885078952476027793337889492503247689515144405808360394387615451155838976750250727337700743157102588019757659194460383346295753532401814739892203346464871519881775195750918493256241510004067991448738056894593752976769539781228746722960052648400427800921904654124840787099145425865942864899276121303468368911618782005416488067181000915487079511722112605829050333658130384811246559475966829496197371798782265548253961241364906163270182115563903250518719576000387523785065975075329878026901683767714, 417827984719559315831875519927768642247191757608046540502059667590425804241347309707449529580138624164613982381108006437821344760451733819306044555324474052995846817035743576230671415454615890581576462982565241320172081124107968818514694066281071418992429259598473067823789170813572310768410097711777317051854854654044079039794728881091515238590402799529207746541962920024717559262843079685978864486301423475457971101125321095805208180260617954980152780258265826592555379989625397905324357120478650922152269363274111818144739948238504666820861981899529817244381819085603067106559873169726237350515455870039277450373733860743638386055201988610174052728228902291510729656962332865808659111883904256203607251052058128278225190008906725763523340963350456814155949282027911893998836685929267151831127308510747070162303219638564113655809350322721790350634389516709277124398422955519488680352506906996461898339871559358287221034834818187007700640881706465248070071262222617534500213713764320596784120985276333639499367701827393128429524923656533626701156881449873979739159301574460202975026615110405184730454398713102050246503241588097362252282268336138816172205940432459265436469626666259509470195659452614174548847149479105297211247984586, 493831651865097973001120108038819083085056646450678278634719262275426149913191650848921100023560642524312729411016491313177122892352841858560494452434908444614891480489917746124965246907705029524293925327986128685618835768518970103008409926798344478582279170105194836232301241847663684692988635231735823120074694936168166726011461471364775741206474838674710858256112148343393025541847950253547053025089073461395003392978751313353876666125798744354420121173261610180579027710498135419300957422399211309461948428086667876415742360997642259686449775321947758423652495619928254653732217600415039630164199025469384267744339887004053389285911504005668827525163795913112748663399126123374692788027807393945031867766569276248743361348854178680646437555278527830345697219229814468646478496139066571265933376012134168401071772488257048192743559628059183407556146766722166598324186072816619255349748668360526404045299396936001445907112115395068814083470289106649529598242055186147131122553844438947384499043455725842089974701918760360947152142295371410527125532792646149087023173308804091870346425173379490243013981918575236698066252441830899134107500059320670782613527007589990164985976734155605886890317710117047300908674230550624389249434495, 42573992820539836221493601787807754740736496315206447436425764943529166377880434056437390049506959289132335150808680752305672693597991730065910595038472729317645549931605629973084484831139560891464759069680822279450155609472631646272142796970063512023093999055449437858739892054379387887467016289429958538237944653815343457819472413092816948346991733745154307383757203911590198948960333171747117971942631243168845307115926620509234417321192491754070192090687731507291846608486721738534294127764112296513396997322329990805776419347922065561436670339409914359185323094796499738404121364600476160405834676330635509511898232543531544280029615225755454204603745782582781300589892063590447382331194007710720705410978180406980575228487952540725898588531368286794375499113201967946694193595049451122816503058028650810518184940444041629407894438845914405335751029309802204501991062602021231517610350512031841784925838133257774972507775902371513503697858910725956327593959374111777467022592072612329510257310450589100883389979652190442425759793958393457075024501891721069354739057976325997411568197403168942613352823300973288896789338467087956816421515608536363459626770416709195915572605562547380488772831512207079147112238732521409861504646, 83894007796562486664173680679930730379780533593790669838920051469991215579987297860656446483312706614987689918331481423187046899386599839344843914027017982598220421975735912895827313030898383781046329827388194482569485175925292973794938990200507415375143883652965257136011105907228137360390918182857692528072367681588682119075053285627807392594336017660316453230404033935729112813541331461211158567770250361324509405550956720875236064494808462607924050556691646433301994410864376660135025542793323146419798919039431600616711857444468091173710955525032409335819812895594265388574075820613662407033446960979358765359452304107679016942583072234344621816225977336747488048852973325675318498772072036443376833374487087500969115204352740804116385163651884702397061319703988815254670846725503062986595261144196794829775811925475301336346431459346637995407590560660872856336288263400202312358263901132070801465842118141061103765743422490137327079934040909063674460765439122555797668547666825388656416591630417013840226542386863023576116164652793831791549325915742605283194544027829754781700886197173482815113979448172201799182938737006091480850394012462858941689835237745684119745636370829973504272009929023824912011989722408814068549636153, 273669748198256933455836185079250964071671688995628465211094097548859965888140723395780147911065443090987294612096521805826894244867050186984983721329892155264340925737142630145171040570958107634137493273595291923920549633222595313752037960629761372558523615486738185716287934175592062722548272262108802873008868075932231374067038868452175583017671727088401903986088647205388245451936833548846354523569124187741324071702513583337323516914912450774163979323735719559205086403253878059021511700729586679448175939944001722023718188142819440359444022380769368461933508186441377209186113840110721166286803010050453450339817172237056754424147945411354848155849493132189684920694240635813918754683795508021956314605871413573599440466540540304710443230423109201508431150181327527124218436675305809462821542624368691929985931994910926649086878943797386163655980957196065882984743395579338930226426293041160277322547500368864044734077347358703317741088846449050967442367089717918897120818396784754095813590258052759441158655288623493225112320787140792289696465669304197521125857861406129737367742401359634846117235195415254332361643162606722288125781554510149334151566287154770469939872556716915969861928420449767501268740056030530821980368866, 41479591070128729544949898849139033908957102547916589285427632863325043575685114104275255654085407312325896603354056081153843529112973460933710056267658659018434991846687920457373190919226034604052459049734638279652470372802738012746086632327337002022284078045151446998857831746973728835068120480767836090057280695637761285487535287406871047211378428756173231746001659891190402740118321661866561642397150357818026112732164906615495098098422569088873688641541880732702656725628999916466075219488267476105449192738902048118958987646843328643657828268535060668017568678475061988617754852931760324876985742318658392684501619177104465596026169686546150451175214392999140600284421390368206231006307776567880541620763172300062481254779270804462429613139329329144221108832364842155347563587668600671735522477092531778693453904020792239383968285668267769403405640333835534843689249520017925651483242388769567883481777197973923400532826469934165992727856023796755957282612456040776307883883016859777732072294086813709924240912252384806996914662626555578098732218213955158497929688638954028579804216767382914865270851784457410940485853765989320458923208674409530535601191492278366255994617134927934924045544470350075746630183088316355967614289, 107182739855373028619188611037155938581146814636474329331852887565233206453215858762264260684742685237225587242355374953920355115121300764383284854252127631984825503860355516486563922848623882658469422800444592561288325387205286077399736874792901931236564420247885264632896194426131923751853355600225142716505875387609711208889598914084601620776318672148169037665728344963025176206115442378892261768202338689494956905578795649344513275970472011107817530379670427962389775344820597922100805067250091285698030712171347692489627822846061137778337129467750574058547999308767355106644857312871039201516951399479095346454152818181632573209033429386230817922389118525205531671402355559206834358143910467238267156331325127248430577515454231594814355510997937251238931750555069189129680818723622497038569888968620957940445452745495051766863205867627613832629490972513645432916961999995360086105754496279585597930783754684499774399328608229736610191477731898822689722129776326738451889629673532202161720262397034785972762038490840681660142338261335442277239982860766693336539106639508897324162941427246391867495053134166016551418548184672958909666473393929469595390858415328561035639810385974236112239970969352464370172369379566555849493654404, 267749625630588540171065359099824929973430544396941141846492676835729762532276580687648497612427263392020401585516488929565531079158406933584890341900531199214527032911454548987848179098686513132017804930260794151212434998121776989255530891567414823709877216898831084974908439473758946602148728534214847372236798257828998249780100509081443867393427845604730365419468979060586204861489176882796062188732059014653075125258741799881319101099784383605091131217203508712791913207982043721608035217479289907328508396670396763847755266005985601073256142420044543877069183205319109608939203330999239927692629971485657333519244097061007292636813543648533998668625715658092840319045005618255569302652558544328492986739040500009817860225823026134440784360844063077904052868928986871179528962424847868103211832929736898904605484444992212160551141784031041200327366862132461526023416708548393774004666859758578079291262312744293392793893547962407189714441804506185393409414994015751701642348754216820298131248770800357320020011389285207704426983924154281129491137680783197230273890238431497755447025031840635933240478564499559800272002133815055244773152368181484275879341109578006269225181180952275874646488299598996500533151409419804755603337511, 141948870054136582447711851179507569752267691866116491411819948543998119375807453530911468277124260434826018371555339936466506598028068209707516686373011853626966961681363686068212008977405156453649291668309279082300704011420671943981223565912746621067350711844936373174079041296235652835019148865679134952365033957184268579882275072756423083190500751744092821066062735512068474518114266968420624389338111833111903970168020284969420452300934564795008102873617553607342079949895940233981731266796564776434439670605232997725243098450621082178891394131700673339771956030289205438338560052825810348552487562176784833920565296549318440912134439993701537302214298423046141081549985354259106393032030603049579906313012141659896605931776381801791251126720340117084256993597166240995871568402131250922370305820859150629672560884640548824549536664021327598742396067393389016853058027728797436588083850502265596511722127200927181549884238521473736460622066429563104577267604369486562436116820112400794637511747595912746445032941217896771318668653171129195489486403048260397015197393142053768443845148623265400434446039731268908099404055166367477630073103850378440469092409336980387438684963402996215670393793476596402401542882939521393269859226, 131425515283495881545091144770732322807555481313037098168074745597725521186035335052158486967346075825833953219740648073514440839179630200536488749549331810802172777755002436242880729101976249242410699577085271595198640510516415540404156462396096378580538954895898851875795238037308190771232785734408638351670137224532583450890943271469289675643388644904016858013448715095805890271748186569545565536900988275467304417383807669282105555606845957281769286596287774089134491145403323051747209247569335052917286257425772677998668569354526163751678807099718274328966606379632576103780612501073731005921888217356949976510562003340215014915070659055561948586630044143308477785394612935008784174099744692549654983252009202466826976876813896658071630400038249611554591751843082140883511183992417656044147625106503609153160843233101557476011665954480103143090467032587693548837029142269452486781746596622421647678685803685723043802457192251175706763811695630235568807917493430617219422971093256855741822025241477909900439798286775937558838091643163661834265451335578984049171317197274659185844257495499789265825065156442257277503810797111403323571389236958306861492938768318850865629433663408405871366714053586306192182703655524887128882217965, 536128243563997721391168276429836062218652205352031205982860325942443215356590286320718086518911725054891378940045182748663247743937612460524622526101736749970125993705729411384342715893185123481893325910368940872807639840904151528680647595827348784217862725995969872449744273613220251973496146444616048837332686146934529435692783628047319382194018614428503916011187477704147182830786314057669842847551921834791221086164538986353847363375874690433442649596185600596868503358981477009114481371615138139178472016610760400255269405540197884534402168096063959832963615950555363969884223491056520297794664420480964063418607933208401516004059764900211238890210885934021717038161541401920428173422264256436977608691120511403701258244925389401096408709028526542242093203182034503970701887318581817573618282785565271582590101617391379108228377547242012071678206131260427430249638856417057422246902353769929526777144214172051726855371147826311683033886979145003899993927709113555862753226283953087507442077639381880603528828515931900623802997316343052100342500668650626005971613088198734980429526090322913197537185879512635658431210147649956581350298980608669630329709211776042401271362578955167665642724669201086711511780228197208895447984979, 192903503590157341410253671542960997331159951552879883685605623417277385279319171954988846281020559976461732299299294244355740367830505616793771689514277659310782264179799989774443721747926379905212822976605806844813244980721560371939619083762366623721876680578935852392669926998527058337268359040710059471953162539970552784401195069027643912261469174640230983857936492961119519655186398980014301034579040846600479169597547875701567732642903975208619651208447098730976306881614391913481200550351227144931727044055083289555518426515386851983765187009527286095690408412210905082021346125634083590222260508421343001375052088264599969973442225660675763246333922922785449191121185971808788536337108413026521568256154533271396155792281039293515347012810500831474430687818071570281920723607627997939702930690620609777807278539407383125612957859161360979994789202500275821544588180303314312906699459796431042913848616379989835018541317236850096361019071440830019998470134647430817807329309384675687197692836786412749854484772659972227909734696355019195159210762509969634209171157351821930841728438392086986208172125922054913575927344238981384696045481712581523846867430724218419044439550235185238667437798542889062793483046949669048517143162, 127480671325349516304956342473473599854533139186662399237998544817560765522029689661361379737117679108044929080226175815102796598599740428530357276702050010870108537628280057369121184501958492818773563993943123953768048637140952598077936116476953670840178537200193010472088227199008324139668818535967632556654143691630873052892351127485226969355931566573238545610711956416002674443285762568492637772553617816950320602498729057901754073382275547998578529064309901016384243548040761924132589009397875587920378728852545610986273353182315760325123827822043251649522221647807017772003330920890509748909415589185102462212549995281661827617997758362429826420225558713798510374350127063254394971250603929561327005055333917354611241779875114440399803450180102839510746809428325183605740436269991301047749684783213884968404367384040857207408309339450342746294935729452033133885493910222607327213335263453845807709258362599576060361915780977925498244751960347634074745690712733914148488481935742945424793634550094695368009626107039544145423019168605152684829107640751296928652404532008021120162065471848144798049929661036288242743186932600167942549783383467492076020706091243082155741200211256411644981668751117540130663047896723500855396103065, 455761526600654559671858546855426697124072578854093551841056316395756056947422724592959954431543554565398002553603877094475408290752775282845305512965282599508358722026614171004861391680051076804462195291408568154726384676247201703268236187268807619583304288318627184937397756589260098042164204165696685436895318297593307146414314141502282101960231120588281235723020133028234058304131707549884386661680002094510014760879060289615101801305202171160935431354834189734900797471392073348986731485279762548147287003976751512169859648578349853571613769709998344029992695936296223920514574768748337011814210096087011758640783201912369669843013407654027802143608954941552341478972343250259083181670073572286189077620725281789921325241657576971636473197581238582298122735378798661451485769360078344181252104071402416375715188062674829163056188224233269552842316467596134757652459933474348284647946554037300502842663871942088287493715625931730069598025752695603489498328443787967100952008356989081230219033303363385328328059610918163952057221766742696690281216216707799391740061804671840684072637222028007078409289150779596332062552309291803172311334503907749830557543464796025407834967922808633133841296978839501352363640463224871561372228812, 399061437010392133174619297329372173083492080311216767794972719797886290884804799843771647702237684025230969851113757958710754669581551836944275538667323019593701530517285203957641182772554517597871344500446354318545898036133291464953947404353870249040857819402480777389375126212935532073991012832921569106051020886324523093904253662505984526021994332867791251511352769216654407328487634146725718472422080203985020594080409957141320400563519994136397115002792927638901245233259882159309768808337205219976516450086549019393264327505737139419349857512646052252022252657896070038155832261934778283708470430359104941130459685394553801996367052403823971051643806514571955471422231555951953304789231873039265588733975541431380178471900559758989799629598001620631646446843951764317873034836485447970941726598482378593689965811858834507178298983533831752256613248267091674121394591230335283525491957481253309014459988520058717503253728976855333097207475877463113261272583063227666839819834879560789522216850229845862826751725794150940427275001780068501015004307840178838843897260713811113157978309816788871782856426027257889623771872390086798913137605151336349787128026049433356711914556121958477844692379918470608101165958387657311918946302, 68679937954451914032222435903727588004103834645079766340108046905800537152372621993245524518241637117525299759390147996047306615033646118322077826999216479879489597863415908764617624684412974965969793355433681165786758477767484356187572614317364876728354681993168633453948528057333792987112946748000248935668286075879861361101765291087241088123514380535216493654830516646782186122290957086718067058258725798482807282396152194528466509254741204368497841861972104123121502521708395870053548989012339923944966171037259006968288556283142846827130166849226165373128316018939120548805199720969170759515711601876102808575501312401939276686928145456953416475565765125298270628527437158829807360097676979327988152346662322195788320986871992156197444545218382027959095490681708922315924893307982930588880785526338308650062207841612514987354552682716846452035806646151830114516512457351450551426364246114732824382154748367150718913241211927272085502435935896045972193707304417983364943048691802383393980962696313754585160416420304165852757863118154476930892344141996293088649596628509892123329283872234065702864002075694002819582602040375330737998810739027093418255907364220914788930505827827364438323523822385287533375784246559165625198192186, 1722282696710233860779493833488229360215432086205277477738262624623937025387509140459178233314634597039301568240629051293502914278476075343523699763675076661336148393763170466343970450951561011138835707934568615700002968493386593476454787989238273397141879640148569256988960456729688660193973288132510592559799989831302965816527376857219964367127757264094375731838015268315701695787171851543408971521479255745932703856959311311750801453677891613872306040814794110325097889676941728820480901834629056514568396063856095401182826744015535798154707070846375553886132165849837079752285786384518648067230772600128629774380356095767239630651086003524257479322397324572682784704763216350304790637630181758289045240713234210863763825104940938566405731431971822488627682131325005929313450318493772858528901032723684592726338162422267336682753884528184433602511169913220438243272370874406975396318071806786609196591383855641715167810307868511465174178770512381519952370019602428685237558289164877814416390995153622799766567735295966947189858465769501016488262800622681460028550496238902402626147577615510368292854974774277262946355501930901084063232961816380368651429994989432773359264128497071706351834315058365756639940453846911559829070086, 622360555142508644635137301804839077223405022563886019784867327455588617494972748742713468185688505638452701457122228313626346761316418001616540172869567562825896400892224815551708939290462295302408008971711371036715770044270480560273926941682513155481823516790163978543883353152174679719818440621906262586631665912508714083283612948070393951007148375350530818983313959309235598619027505911088786970408299284172253111738269362193152655369493392392989663599242868304678920771413944225876005415140525446651872110767208550106609999351128103344293095638980550308185113801847260585898878398919967973431047233452095025257098667045814487362764118928829373138930512741273784803716077923815791770080392718812313349946807948414171390102559417422451487737150419164806809845217962692051611584445973538229987820757130499546766892293967546905758512404499102435465880652458451893722222736086489669774921678197042797556192816496876029382079019066103471295725806675784471612419329432403215293342194486763094255908194253421145064250253071110635508692968638411651421450511162061168382189613772033125024048863259799105242067572003812247037432206760723018322280089857549017625831820422789299641119618778673533458658740841101188520491495889523745346971918, 55923413741310998552073466998788557541677140407984945812995173417184259397837700671334876859103624732428131094489633053289743885297249926979837990950198569193712934060740132126808930878315751907118949218631621152294319387084988206563881038989606881163739197538665788340295419110013020987104247095098289400192065801460049196032282904453613435765832836192269195808711597102566854502091663454195825040427022442290165043105444093278591563432869098989630614501172447168180266429780274044776051289799377483380852756297277289119775328825835651257648875920822608783341886423382779596740474068464615804459878188152302641984041834645504744976051532741107449293473665083885305675554947063470890632291197931989676593011981307812652378541821346074970706724295368758447879904336076206770145317034609454784598973195885415600681015827814748284429108947244200379423402901492934356389413039272935629051840990229248445813139918070349348494774200687962081757016809614126596471865403455454869562904632175518469424376984765279768754024326013103497464071138217837004379018987122364521152998205447638456318882653108842115479770756001874334450523199364471657854105089714214101975482415973244258607421348358394868974208790422442721913987283534425071933542992, 377389915590764168733299435866624724028840060888220923519675661514053765484549312092156093674113043035143290102725814748295772990542289419861487517335162983018000015812095426793866385617428542528423699889572346076532191658019386965070763663475178249233543171703987407018249948895548701516474331274813204820574264002757500185530691699728700955839484584503606357187081082341008269224194762062864761737782075650962664545370135780498861997392557794825086093926230116578017873170500356096256290349201076653236003444362220444292185926734316076713701936594801569838794724758062603030370803354903574464157632572502795715431700212486637673559207246804968056994866428903573833288162870032848992507627332429308068279881078106298049617062123583173504980170064202477337623813293990318831379244426660019043499694665043081704188837711211082214163977337582145356953189070100246202724125301507522619902877006832510762748886037560136190621456129950603020616278633665116381850763456635805449056890883543073888512928503581412811729291383099475497287289411841187991615451692042420440145572295197186482444418105813441308815868413699019484684119256462056801775466109794491796107330581320700860990647211309636530551533280021407611492909400497450009606113569, 44208265151182025018100873996485190335931126422773923539209161018657113613141162873966743201041849967756547690836287351657570915413305618449446787257158802846931013456567574280114267698266858903959432998900014193672261973429948475521353951344159855454815837086959539968790989341454470415410455322494349058546031345210038166600454287197428283524434984083922456013107753627792346308697996775638057440467166308368159077247914967446540590352151002255364863201390577092685565900580085406630234005649985102708627381494744573912876265299869916673796908123812526581677846116987402116800477892168044495222021811110125935000401963379579934517023302414165213471321486256398565664902629036857911810470872688819556616050443473450103203281047924209820003887901300678048500690314374211724891603440961482389011040482165668170865613950977536986822265252405288327584077087956608585179515047240561129822410719345832549398346357471302704081593488174583789924574605721185418431233462436295160944633521154044206616582146915906336221264107656244224877877419046828538860896420848881565781737890077501217721429882037879831003398733909712721143085436942639233110965918059670044135244224601008891188557857756276711307049074200441134991944730119350321198235527, 37186994350300278627673282823434437702747667513134849122995401175252199717793439496177561384794553632560609868483200122873825147264597434958591321461847390397169191214328852185677498273810167021113072296646938171953404550578483303523397934931638999689060930077024729992129717481358687091914503244392184275514964233683460222488201176783671705073642018623786883953153670009139413380021650368974228987862280273328802670010098709680510044366501958854307641869779943826098805890662718000912337726736712563381267038062193644324873325363671142022329934542239753680218776815736670605375176044029848241383937276533186250521563469244562992444872726640432202307278482347068358037291569512433205683242162207364764703142570965292027843045155174374638192692503048830405169652460099204931626066346920701211841322743030541148661526318910379068903947443639335679601403652999928231293422838557530770720008535611829830211406431862693012293295430134814173044557339017312134558851261350929120175625099385943370719909150996016664230521642092716868570730828620196539605644437215809613871533087265033415958939135950740463150490422104194383305032136426719186217123470252679982801171676641550377238940292082599074042884911361468389719801395118297783577924790, 447962769221989394255387988123826349780496181841922534470302508988597150776820751478433772374453925755034508519596599414449887418466778795618522148687948302304945029142135834233008107247880595391509080225637429281192270145912895279284416118888218927499572658694285211115151260071468244563286257713949163282438293643457052362647907952818359178537078418256962082558690661014308156692514070692868291037405526122342824098284223469027895396740557660818590887879802962535835217705043983859065323120945438714031251052632909283680933123469023890924355132310772102768343904003893018605749014673419061998641054592311148889160099165649304478245650940374798938082180384623590599218217293156263147004200735595770350800857024733475213574739502760096616480248660946010399482907729932691414572018180449225189833876775760937279408915981341620412222189111071328433714431343799089420837707150878432833028119964231693742313524038834119751610840836713172540343903056559418718856152668906907740363091366391272358256234274277758526318302121909492004464059041881574895414619568492407864300473613068994881202067765337249176140180582009151843889148367025687758661442629903207500607264980751614245026758620977882805611265542427797252001750480445025491535324730, 575308717080236879695154611899893779786635311466050606398951517715718658408213133533875049803037251652656162426030717865908891116738809056437334587918343860126264807589242479060054758451127058196905210046908400882546538786402010306483298251726982729637677346015709877646397371589485710213049606673468799394867256041435801588403466573953446342734661101433223502596893180484057963005577323775293127783185010841498671866430834363955993723398280075514710212403837856977198910522220821681639388007144772528757913095039339852040347783308240571298889235862655204225406186155685268254635982353421415016114443908119370678029436874344156582480712694106679910446866785323002896791655327822078151082202451038904968535748578724544338706137534576784952364815423452181216187967564079321626088075871901739309318210907625727111831138980972507851015991891309681655064160401246792895435403236356701798376642100808145801720722485635809078560797621267875692241273621215786977408203556051802226758043335811826071199509291723756590904350412048985986198675095999529598270396169699316237474752148018766854059711894771309533519053472248639589037295761853082503059789061487861814871897492080571007875817027301338311518029410212581482785203135667127728422775220, 13626828685343313642179503428162174962241731433165049289302325716945110506355553924945169292585849815527729096009646353895366336450666877901603033605944413429803716380962110766197696721647730677081728501305955376022894155782194275551063963234005757227366029588380940769804044207955687320569341092936989509754681587034761769104165434714763036348653036776695942930147643511464389341411702567277697120924740414065702388426575424300711782336278010959180302268597747354795504790197705093469619024201621819750689419008366497071472251288826936048016377485679552790329070747718554497870525294391009034495003337872733771462175337039697526179701663074537967573372488271039989063340852449111419059463790694236214872172280780781742105623506761412850079978127765250344983183714796913142819211993811977439949240005180009714916549911243537958721673488169095220025669010998429889454654940205376348552908988670630832328008912232057699490515398674004200533189401440544507549453842757767886716372591906956156114459586668773986494389294346233368575137069421921664311211352654470726189296687577736948141018730408250211799237064779005638339851894834074675304129681947324808888119530885725849958628203177539556259097764857906180245227342664741456621328600, 81653253003710548211270152897970105417521222418405769251932780275526107918356039856119175119147484191878141643164368403400283795514760605630339469629980246797547979353449621271537701247974440714270653304438511068130046526834077276121234716943834283626135107606851915747338857331632684201301246832011133086781229845234374039624600184102763162350438481095851731210762707073986364181089324521368528101329524630519047086676371566960031116746321695711711350043742299869284360139378358377898297723632157989796546121228527441670599580564361610433622081504175525477537365870482847307873563794545228686023593332254977677787789017696549955631045856349545370717352561348881916901733162095083482422457489658300923226338501310148542132814207992355525397377764447838606397934812042017895443915495016796035623587705138009295590140706816358592012195427533082318092430979614587292746186357529687063883148821018379753057975244197183865836817372702287237231712176879895367457725295431989716134554212543974902816230408569399770628798719303756130376796889328024337482582266751095274221525783289133838248455221917127434153936800939932883556579643386509059098264481081510711007997168707808347468107644925521540935896613582162303898836562680642764215347865, 670043456499031167709352112993818346162276680957987248829017564238253242783060110256513231870591368873904567740887194016215797268938277729671088716188258631475156937968425885476289461949255621780191978565032240817197894135376749341034208504462137096928902135547565478909875214262841373200130277365313161220301086273040296679214827528415696601243875385883800688790388008758417827496287689062465120736466256193257408749869018912517549560040166129524006334845467237068429998081785908482466617806140668460542554936304235314634211681894505191844847403238809074506515942684656779384977645517804738807792387256878001840878000377214159822066267741557511519804667747178151216123838485273507743755679107226475133714015875085925568955025498742548257259434333658177553658872178970603002930620236037260816092944759571212612658816011415538752461491167118184967731608120777080529488035560714313439383444547837799232977149841080745126687471067885164401400652174128308323597454940593620302635647821345413263297800671327732379898652413162408327094668770351820899438936728339261481109670111717491892809786812261542952197949669184128331737421296655410455492343713290248070264225617612078617490137882324184283843979756337927879502022855077958393838873142, 276642844413656736545664785211624562348996647743177064207554512227585164830021269415029383441063286327640714516046675386330975328481034140837138286115982237760743528065008308220277595910981482761495827685496531539129145815319059457709337777029936666260210820459835440086955664622269483485270303469593238779632523593355256134673077520612071253664771950615948364334399371558350844272396173806973090473622684962079818052742522891138792520942293822408141100111893735136004744392099833110654307523505196680288653948077785029175056949444663821971740623354319038667862873967087296786457099033801030549805721036185056863699884839415381043620997133512139340302323085479923652164847051902088675414534359871371760314408939549173652333980795750860429181246671043096288475091117940127961132910967944662317990474732513891248182863560304643348968247812989988443737427566291408958255699901903910010045502464833719126438530989907289199835350499339206029987073248939883887676356559589213729488512580305317914425679583361353405354678705130182070432414223103191675559735378686412612412433945879629457082928755455103692824777057016691070324514131781009785086446766949898424650688181369787509715585606936259170007724448690157718140964069245013864546106711, 17630684077166848445446486389529234991782693313441652867585178922488171862262813383861418396279200086274384083479341615737307224364838126848929405558070790234411035731307791707671295233768747081228747944507917849334247381354012789605880112825421380947656281444917201284809081167050271492500405582443310120644108920438528859592015029791020729015506968487111074400985637541372099329744751983764922154489847348623294297409466764032869614590327099433946292333834716911451981934219106779588796751326329084147593313924396595670770476496606340620578955546483204761439059835380987942386147281240442602175957879931631820646949567024293790360578855946246046894159993187172600240532880001117913352884970460803815010411119348904615916407831719693821669216004825085988749308341846479324502354287632144596542217442833228855711035588603543503321119879391241101266351816167197174056318602663243553153553117516672189059942568080778974493557098365635790415332353008943132388137058575233670407269863936608908299827141233605211371624786418598148314764838601801231914090993177013715648988503805660070170225571688014316991317846186194516967941689448690457216835399572442733318081428459555345574683222593910090635948913427010370650901979017283255772662887, 19550967667860545618345453763466770410356801519334020777294893387122152716159763374216689246371630136156927391208799382963401331241780392216987389228930971872699252232666589527321744401479082965458594758286144240216730258403756509430949501707370715005454802063683661097982901772655909819050420160821128824216890864525262648845333268496357628404427150180863832942737079737727407007428021654049596138141615317635731917360478522297987913120275315250657682417466927532296960597287649725301489665900133526727335495905913079842485208010505404172649573065240993956915881964890191028754541796102195808882710382393731878224721549511878442907958919821410997782145221487745355520650917594521290632277233557977070533484126206999885402912577278401910616492769272526034403450785567134152776030424053470190146349284932626900768332334473415343017825875898224775019634613046885256303062200384674525977793915108702558904176829170313381215281031771987966689003049791739270575730825194617843785900929365039187796649036619280482341128557645741286562137300937777000413169975008127754272006749554897935048620349830678099577819059895998132283968527913619837751374285149928253130490541845434494152381481651261592364757817689087326525270803438048409111348713, 543031725840084992614311358199730206761886241827710984680786734961398526911835694030865749490381988191420663836335334654393231154322480910356889905638510252671182309518033092451312573155883877987289238504507223519260067699802630735510987247814220880786975483006476062567093425367448824334933996311021437847456779284510399146622818786563145692043309154044921128476335976064326389128251306837346587182620442470495396248092228201411780987226370603710395552001268938362955315644539336319382647031064334512545697127247131854121463561638553981082269523457005459357218325728013610963664164762607615659660389605957282219220036328751147282854971205227828899021336490211804730033144499371459664761121272803551608791755197220991042406623002708252554669900003714105200791364900359228384067730950703093741396302516930922228508201538915379444260105511056839558799548964769734092494966146304827208336717599612451230976033898841782430016872985365415834808247336679887675682198998628235232187084750497926700276324855338508609887811414466823693266878794550739434333000917821194472879481420361398657202851596742275464757106597314922399883100633780440088241318260634798407615244309671512109392418027405773579740683873414624817095726828784088716738970671, 182042222828431018120939236793473910287275367895999992826866366819447951314130499050134228444914418860893158139694148218787231730979102542829567930117218955711387211734329812376785871228517087100748677109992111595319280776781827899246809000718620108917957152227272181889930341216178777219552651111244529676274366871442966886990740322027509344702991687911950756754343072153143277351564988891035068647957353109991609306751989074424491304996790106247135990398979285829128176981283350034894182860234310221895512019504745637681297239673722214651906637578474895420159018913404531997313388673318862702325271188955078873365792898189110193262775166956260477716630446104959481804127207256335886511321054267946526320801758765953223134862294131402139785277868094413602553060159138892009378086552778874200963489978142360244770167706637809169253069216439915934371287170253232457416680528671370052112097446381139548912361204766208762583732520251506460815366289927293075440832848699814158978422779797286402634943352897717515811877537689852858046393992735604173909194675183186745802329095770351340954231605266812412717384900490750068788607010959972848633991652765245231390129853310635802315840632627604759611137622755951654019092167730815995359397951, 370145577711251153074109009262756918708380861176184850218245116073873082849925105851491433851651493389767396460108619894188091820596307149375743861489169624788876011437614898571102329388823913584288147034882527422067464681134904305484327614000818185909579601788402205286137897060269133062199931736421126676584003767831534917150450798370652509384638023234689316175697522815610836005318938678623167096156555042314512807172025752538835783538363747846321321136920609497238776075947308657008616439621343515993393919146156009304742729425986210125499552847383298405856764205185045613523514231595894623446814127040003996318947482897589632382139456990397383165397446028109472878277859972870775774109290681307751670112703735019465723623380035992541981849235815357138600258519847804522578213843706868880410290646010592139948570965486597040424003903151043840261147783523279225804324174266733447548137309661415216732269619604059112533799874186499254264131802430137068583731292864559531769593406000950340198368033929838665038708697117642043084905531482029986055405632929177863520665426075186215712777083764238177987694118310242668412007273526379032491417281244236668941136202292668602038012950040730974781859332527750896296838480620305912780728714, 217805484393823929363658890089443014729788589254344157587541724309558708072252133931602005045532352440892813154804577570081365426215812102108841943548262439402779711727513395266529897767015504023680012223483644240189839802319965114318700537947235991150836141799314114440745035135484861745963395290841204999900666868410050896053778826164821744365308348717425006967359668661014225461890846011162038330757366638274277469199222897012915011460814741420409103487119539864397735507531459868480742722428119706072250157616536536045770425454190802972906372338720196294581875711858417584091335070020577798419256047272110397319931387832547299485056330596081770533177185061065743667418429627872217596654556713830859563003858512585143059104899736685805135576509754668584835488891211856588443709209549592983490236460237371487424044677171901026501980042116493249621645855609330618330211254871063502058391106125240483250720590882018937498954099242409516346985732039067411520980570831495040881271540744274420269098328185674916876145634092842093664048377534489720299614827397516567969020417260371847176359396976151716792717511228283896491510593700493088258321985171955026559915272710921382139362418184580547490268384586952779853089839760884906315433195, 582697455762521725606820793084836997058796938593121705296573372367209168364738921353153734744835032393026225787105999547222042057253582877503478880830684464910019986817108248826392666340986172704029024733366355974143856611773729872053847716929735739540443071407263849107319096630462209998615156338649942561573539705803965137349676673144682376863905917386040450500157150935246219281567319270383922208687376540381976525039905942095528411417086951962438507101904949666745631550765746389113225786767278795424627554694067847765421925704816446811228307690033272714406846250475408529769592410638740634007666235630682289846986023662903424646311810637936286189198166322128003507765942268191283159141152431138959938615350402617952983675730970771170620503474347389244084639708622790585976093465646517107574378458065386868980215419006366791958480711607850637307290394434399259275336348913754991019045437582258903917404133300034424844301773951653304921911976129334299856775821514974462013550154058787813339153465032348561877061457040197041465898980475543957056638052270456586580630291720018652134559746980060273955423456435927162982710335210388510774063385269239148019966171261387715682388783678566089781126396165166476139367993555282726184180595, 224199978876184548999921622093470310926491229699987786306672794106666966090700755217108979067356571864684392674997637316487030925288950814194185067156829068373305183118530175122995993785128965896613861566228035924264566718195526080541369755535823247546031075945772248095275899893514885735593863537649903084076765005560568032019118558086833313850884008793928515922462801977270861370735331526816471981002657981285148998744476644135089351139877310080763475609735055277868646581114539520456048751842217358927293546081222772290716189556828833474610748123967717907979074757543870414603169512230905995911141695749226288217870230178439411474426563920004710454414905619847609660605815551503358172978031751505770919217292877077264674824738680325083807091450940744956800668573079654498375320130078208603549302877741776385528778299230014377582894391130217827573670516737648830750861075267773487247140572170702402431272771468111109677717963905879657378063884510861216562313736410728477296821545132247055694122862845654084066018454978421230164024704205918732526498056284608424511169798528635839086952020309104634046792349796902430112476281930134169948868167560503844296450786805644171348830962563265214052155331589816328434073707792891755212323607, 316950463662498052285122247829842690188451620383834055089510007473707174283078686032518168846184392475426130734767624932564825518744782749748059723671430160954555162340175581973770552915397240055678269866475282216570685544651072913291133302278468136949053427877334504878755735118249272362300547025171935981229406873892655731423742725169028074461508460770661932223623667811022447263822777433807791425740619158095793200234477750694962792166190878578541857187742442699795865066494303680952109506354558559106747906729862649660981867459378584562035077906487250502418129165142133708144761799076560641825705462641473637826422148005476067308380291605231131888324142344943246201027857119464623309571767802603064880309996221467783802090441471234208075117516950567176946090229511869586475300178552675619163913142751283373898537273579282552853833802598925996611387158704240610408638653964629255256093509193218739287164907970839643797399011837550954871659822176462481259591629881072741121258255252227577637311348141361870321752760479704511035345777210832574550035307743436245302268109766187333531482855321768599773815900722665065661383282491125148427719018079946247423130345787996261370213513802044236226397237403214385371504068910832458689495868, 453031161834044539027613774813580549822102770980050431152204225821102467851659509557401135639462583909639887844553849977974617565521394970938715138752309483008265928536130071294812169665045845096897045680465802887878286883930668018483228550691819275339942365725610488987870545194865404106144608061671980455438951050393507630419655004236580296698013224389190894281951018399459975738861367478837588526029563554868011471342971467830354595623763165575015702610833136537352888801388140913464669836759851377546007144634315292275303436012049168963987461070558475333273238656213586803832103340055438082927654384030074850847474911263108081765440545302144451781093325776879062516451503643292374676005276426110772476410724790006832067366997513993464166010239481780420671600261390593028237563415581848731456476772143483990783745292464648015815566417820662561130237345775024012918497422470203918738291449055053535078742120381948002755912731910118692844862626714108855655704550795167632258986635587029897775553540920212282166691479176178859226466445166032786893193619601830874580141619498814187651875274690890866756125271996989112211698531571336870274534640940402728008022422804147693971774658719861338906253348257108220944647572651164109817399453, 416521311807973685550468122721097802190300813871196649943880644771543048589414561360265697710975650901039393055350306175018170900688420410824082934216252621546763314093490743088410636285446552386769327624151835474108135625873748230694567336674071477471635310914448835609720409712890854707872223936407265390554589840737152229227764382496975447970574424276179292085402335694055700289605052132348013866495587430829985435954491383463308068968199494815707978462349352877216225565452852604399995890815057251428440394085782034186064854491009692599463108560757010024880195186757212281703132324444782762902300921563312752099674304015495843172263768862617335377419717570869894957492492133061137275708735614256702702947395251786058765781028561719366934851691009932212605762192057334911914986433753387157963812882742022966402582282603175801018776213617256015001934775082751476541367704267645220092927954070376919169726938969109627596710720373746827248851295867056237283404946815298916566922049515971319744773367706150727745953027124997284607947435147269639908904019500382768304282282812108642886430323538744567890481385531561060313673637337287730784883818295158405337537574993623294387907561186634381047953169555185406600908542177284046170353659, 28739827526039153350299525551536900868952257560917988475137227826560291577420755793871201275709879017597043756384530549821961044582100324236626157125378019400628082371553193976594578800307472722346947520115487758650693574640135952105200429125219437632208028745478028793826751058880639943427271425287423743443580381415847910177363797091105929977728134664251952777445639593254435790677036819018294906302635693807355383266692631713531267942089365949505048724198518434155604682043064778376716444558613400782475235147916034090686090789789447766030872949840519793113379394557627519441526386951308030991044503649882905008080546537775024955600010859345983954529368677227766445885600258214620935058966148149507490466187858595891111234581329170485347371758321648924158997187336479642121762571255870389537590249988779979193158771553093996699485930358244436399928786516024800918146095223353052579337028295506654744668411950186685065385194355773974138911488017157679086181640097794305308866475284174204676172203352041477611546009296629765947192279047387201813094318952495732300320697592804252949276752089573531909170340276196267700364871797480750046541675775083122686464219469136192638398688132822756363075083440746837942515940593197358177085778, 217611047130820466345277060843237944344279120602795427793682406812370806710771372976886583231116677068556818964726721521281666003435305255247457593161708578812991804821881691663590225693491950950020469771710244089495689413631142333299002803756379349701008776887766830721316185213977201412994721521998874036042367277345928990427650953669968171496700710585293635274892266392263127416606065231534249452215393731380995672959110441057390624884020314921257193436497949495438009648236958974432910901342857191326396110358951471329124714190741963171533510121002899927400920756731236940595552461849480770526458892361008640248660032599986089492478906661082305384445140568878704487617277188986232554395140006156444286462714672735936427229954476348092286485467569550386655735404574446135712985705372716544922977277044755932710910949743663927426057170981139214024497181480027279565815912666381445679610661874751362479286262272830320754664670014558222604180826581523456258439163951038621918679315002964902479742971495660359161098811553153274122232806396365510247632024901308712854011187143445560119827424137713474012438482754785677994729566434522442843273359397072096127933705554289166617516049459348067892966526372443554790248905325096010188326164, 490064793067734490345364773095445344860682562004070461589927194386729272092471475979313466091358474586031953336775950207214373532401368984044189895116060361889755688805377111205211605065450998617794023186555910123367429821550481683606415954939868023358683507266926986174518788314751921240665614430147374473656737184133673404565662707256403738296986376009685625663427038725364813195921303650670385384512348043440474782246370743768478636149687951599127507353673642226029096269265284211770740825571861568454067204699287989541962079664887931567695102374522106172607342779996031188705920659440582296833885149121187201727362445867960922234857517987252722797240643906346037318353153612579729901777303628407271252475895368281900432395241862723239459983215709449278170538971555346929716851483040699423131128306849711305049702240892489521902233448776991475733189221769227044943909809490355041235671691325641709760423045869267624983800194147308888984031767028953195067182498170302086149273052236144177868099784035650489092633881557154282105354931443546710964389688102028741134513334166592545343307589987858744261695293764084190284885563766725734441485463790212257614344164050174764351120955599449559079082137221228933250378052134419352355973308, 513658976489727519006770678915198971183200909260337927160831083800845833175310656693333919575797367339621575308196380644480382341531994528979414287757111505808745830360459107150571447757699000459300900509858099112180531912553588961652758138234870344137617787231964374512092338524753249028389243470064728649045903820316983307287935961900475274486151732133383897807606359942555015884412056230386801079029716726000201235066614487573697062104294449800017212672285007794622180811579218348353819429311000593361819796978140925302337237503572249124448625321063939339425840813664290644296326768742843658772923886568187279661493283836478820953021550662195856308723109748559845559390939186487514906018266852432497371237704827249517132052598869434886114691459174982794741082108314143738859412423569977594541210179446165546927450219015081431152874280503178298307857642375360905133854188149609487752738331657124498853112802176696928602659898484316228806075911137575101690375980668131793619855886352545939857046333968468425089554147808952486617395292256735581221305080443935820273237076917560241464825688565790831464178960145605859551739888570113804860396406205066609972115451163040080958451099907468372362639846719862402951977942997733227494187962, 69439204234081977165711436459719009006915721272755206816773840433683687925710506854144798091774631181078157272334415059128692082295980826749348844605500004159531733442475560458665383869151279288179903519528211474819488182028196011324012616256340992096382533261543828310905700999447346121727885245669098808591193387110171806355765995942914858417616627874613848586373385363037795663699116245494216816090573403687136513868443905288013630163800841600518659889625568158445167905272451775051002133600707994482102929134352214086530345298744392261834814062621871279624455116799308105328492150891093580726418910704777823337410722295253292293212349927176637612133243574113175947763873211075604410286038972698014020147473932983120508143987914340614626179291118267405977737745055840217404521723900864270172954266278337369403597897816313248567178806034485525240656386514945981349669746648075765569850988483720940055881991108434346957276151791130259582884411190472804342269239121448278557272149202016108580014605723250750768691920770555763933815313050662567738984719056339574277785010327642864294883112419290174023036065153051701087397202024693878494497175621641641664147099280724086909898101217165182496682204594639194347102300909906341846563338, 589366566090089172306217158100976232926912010558362681838216078224748241670184228610491396309565070105375357659934535022857779552051289268178898470392604774349369612115893494612826447300121886177511669249380158768348746721961384611109357102419950691484481899719417217860615021186679300871388169419911026238511726109455781441360110113194301843769023184076079712860909749175406001142704648112776560764200048833348137906113226717464237041485539384722694545419482107268202730940697763621783467259330789447242788590588996883397891839442464965701111867049391791524834280763609827692577356613861568452312203400284543491339321171948849978309166655833429368180571676874576706582292127251281168963630995849669157614901146625052799621090788016982355415841717417407298510566406290298361235248159787758688900538649072519519234052511518616415974629138157462775232170840152265224542894283267943479165858964299216784982620752651361631398650278008084799269094886465780909073304796845995341680368501521855094813563672103272971549320847742374331041225212746230811683715651321294465302939473515225596168130051397648016199487722054754794595967889638313150397536259807982664172522255152895139223516494504884939654353395964183561636701858595502545719282653, 246308811440869162698267610152639456961439077524914094948027047513859964680363550771611986915019765294863516206045362017607086985766647328199713828556669255473941527788288876029176729080529074984546817965441927776986104375199480025862907765539844411777334782763177694706501407820982950585094441670817413097004156852076823669112701114567113542974024303043683940642182041243628193327972374131613254246032510202999660331189736038151887169905253180834049937911878773541694034894445381724267086326490241490142271634285389287041704572463763107912340543365425194533860929788329325190752251419885691621994699509226219077977301636930462798830298785964416514177985676133155515718993800798441584502275973320494029540394478722049323049501694111612221912186903795196764960169656585280372667619238372970048788996131563305128395367110861647168231111733821790602056176034006742169822619005932763174542326131661124858546415024474337530903308384968629021134034227183142012799308160781865506395409921496787062181129946536976883318447184755161029701045550470986229109714404018158032897991034599113638087813869378936981931230783602636297715372223807033903242209385043648417830703571649641826981723150454480749167707114252920629328992463170071839943876825, 641073412623540025744405073708910685513849302427933147076407592994279279811291449928209546532259534858315855825714174072892416791745808957771023819213647799268641515952725590729352681876720961597682485525932697407191190992116328828972661586072314065056147393921133960485032377472642514277854743648483593283728305988759086912759025214642553050045439791184642426052559236253923938644912772020938627151477850375101165014368296107810693642008069172746991046774132291745574075610115525273435814394985835070372308214646305662851333567079712643178545695300294510652675913950325406744897480234137880287689518991062334929408237764530932112454775259125045386787304167121953012300031773032863353178644147893166837764315913886281501590417099822773225916972724240197564146835869112834371567811450897005059933100353971353377375808136679737186325624785120129938760573199417802448217604211408838718159372669412456313001465246994970532513996563020010101434393748389596209693161051858684341495774200503758460199056973929483383990342735284154135680289407101043460548196019475905703446614021090403773715639946364908188066318784570265184991745756414571858461128483532656373455410997678306117843614025906129054884681598521814822218054808138202152956205104, 610002838330192855589882986959040320652104932026254651119562311274013019684736889096388876400942156859099355103586734172937288954536872131385142967343936874792279154414248398879591071188621608074333006264327164107601799810609095891329119321503219902264789217622940972189284290146992209712993834653902163935194188550018903014634369733797851058684102396209008281843632602010989746354391442419815336160411536770694817338485672353969905034066990801138020377271243949736065619525033016706169979818111221479451721947734567061655519720107963734527394959477166586001399995876937552531267279725620036375622868998952637006282078054474367127103369557556481240003050288582479583402336125165293755209401858457484469253099108303028504973681503643841378595799947226235095420340506017340093138078532495870942781297121999093269191358184316562432930511882446571178272808913668482316731870196553505722992524280931797723392550798448890135157680275901329923879499127513774809385182070131394786715251793157973109365738180580855446971117095509668008672195538982269282914368671152682626642153864423773057576497833224812241990444483664542823586107309021336708855431975582506761077799097075241692438434695206476113128263317686254482417397192288052941869078933, 270452784516582773828669140207727878799176943296043783394835586243651177829361772823177335437254116427643773238503697434473227091565560352460793467387799075317130207093170809590752620513700443684732284274998446619433298479185200797826990441187693416534083887305276214326454768451211022375155717891997614410411742587172762258387993850852311898085909858385186897543776720768101022818074807256325730384304870772226722353856923876017876074872597033486372619065399747673373013110121225269377323837545703314491726366097672377866923597373578959725567925538596959435245621562769697644555137799327853036829892651296473540767056205325304166133517405337529901389301661391313347622571731075916260867633915065631348983715178329817202794845403869196289223735699170308044928258436903349632052231369854492191380778811136629656574456610631931700250083589115694931980899915372755151454825830381887559972815548953979831560013534473393275680066361166749463383870307712113288746232255819307860399135353958781268086936158594512827656976943392735550771020896035538606949860319249990006555195413273080389161987139243840191228208675395282853353091998543747581587594474026101524297495550548232019549588296171736134956900430978728744608690095083183316413181561, 174477429673263315799303739855228620843852066381786653675863115897580296594739277798345257971174832499928243596906919514756146344190732530625698427656771148899681345260660664131111354760185436389961762606745006921567407563440666041299016126874944364876160667792341853759977330172513477674407870881657592967747086489777574146460111100363885530922999977857144858025602431117901834017852462207377430006830688482429458135988019777049502471648334258839165318524006801421912017932576346187607912246000524324826180423725724347665614806282022249481306825733220664824963988955165492970259089865428296554927681627520966795457040750197948372695346127071022793270721042375205521954460098866992720182372474014715119085839116618362707605897028296006071266353266578875349626535246276115385645467033383701526174544244926943070108940499274518124889865253699879170893886344497560012961999611100528357971877331252429243261045220645207704966557914446298216396376552139184709359824329564579105116109526059634747485507787791977026351977348178008241444668830399895225575436118312521782258540578644877735775983274833024623357321760520032274678290535735490969699613309630748917845386890802881225875043087178040224059251874383181478914359534264389579000873798, 69995601491975758055409258221535178070380807022713085371125618232920773081638217145003737442745970418582336512316223191796664626039103751058262394349873770181678186484753554329413292874629691436649713821386469383011656730040331985334844288421369295742164686005215264791066328924247258983837528557966696902916787226431111523382558278740023643535778970806909263937518556231427749860963717967832396385348001227716113886404587210369417542126983525266830998312022750055100984604410497852172138577432214757273775299359337436066040112234185229027235707568952838510620796144214708602812460381793723900479681162587732427160630866256723752636643980600731284037570798989867417797432007088484424856817373703724209840042623908231634905296410420407722434837563417032252078359373545837652064554016772009476854246277099668954302221904183115411657774588568131033817730298650840921130649424604760041854489190110611946586585117510472198254243913526706761326133299995431591262333042484297803305615726791461739349000455052284718786443773794963875344848899056858792502550592367452894756221591849673149437993855863038244889194809761063806148948039153875273163112706820412334963515600129530043341000063777065637112744429532752298533869323108325317519480351, 329178623396244794914942467844536015319495959934360504705904866418642835598768297249395049949596652476390437270874907626748481115948072815971756080412573407731839221247310303368980488296839290382232388442354588172601023917862905081866137331394492868832570349667714408803964408193861005093942687343317428295123651841242239915194077702613163327644201798604104873039662060433912337058655404150614120268649835476407540910763507486542791224106111389352050415074597438006318758961407894523865729111645414341054936020967656235226375578349526668710067257072052506698288903984439629375008984175412611236787747802878305904702859029298834665661031967085493351853598659615828653512853860335205212733278274141338088119474503902524286204159966909588641301251927584549117139025211963085381897668150299053167019522139486983268105033743611103758526065300896264565795595755033173926679252834516542057661337724216421327316165439940878308515777152507820872711474338659086315357840447222358445944740611912760553931558856720694004176316890190642201900487960830400965919251485912232709055914555693198212885882354304206575919101609107040219418905004591143744402032120997172197642380697509696278475997459100690245081465910799835115258255365321779191365588418, 86277962306485595445094984118896727894666446570054247182800786903364876009934641103873121042764224217714766523631599432381019766621421402555227991016949034753313480113748111601420554116618479735547299719975489843708803311185579095241172781571682262331700528183927244410905503954299684365584142524749899468278687316424730813719412293283963754129663499137675659319051912245325435974206718551202773757225227735948951539715100859603667484273871625161479331093026640653569991284173709190306270766372099121915695335766185092718966206718621628951795214093421250965146444565593231280191469998682479268683518345657257217694854017606180405701692206920165306827361309257417065125473832547927615767403897266980567058722072519398949072097789687376149813759665624114595249448506114908927549946479192827934462433180775519887558230414491533622817283187604650118177494407887577064201751771524914513515124516094972553229736480533654753939940018779167277871789242152554784931447122387432565693952389996622099658689315784211218375568004864036785023954458309594336073741720345788770660821144999711401899410307930130105803145187702876130659596412230651033543962576767797919742477254676330419816341228336423181418976582074921317331265863363521575663346789, 347767917151684421263825538727746936164097035125078805549206489955173558614760561079151261607531767721659615609637197544297048385740586304172647009303938136932413630041024467026464155024434389362716990691755519830280532976579402846260204552337502344315600785833873882392339661256076605526213008923480048068792310584843303369458146914877063987148546120946887503754404733196888283262791151337954844960187172891389551553353877698974606407596871980196811035271700577613337021347011663098512524656267204765118244982730089005370354468744893249110602264092722446982764366096763106624991026668413809347313727324963824394292411034501436333982195831649675493749213394331402911030243809665894148870453305160453544380450497427735461083706747301063589101230533518655431821212614982328232777773561011732205722943407529362725142050709844952044138503010956730089251092171280244427409445093724057207044709180028375913410711850240951506838899729239075998488300655565951787150850543561900464960202108364185689218740098213893465682120571019954119333391995085200124202093071690399300637626504868922836077299811157338608525525347630196604091226938190811417060750573326230022621990939499789406765045938970384125687792742200485700296417971792333744971803819, 144936570234575053442232004299671139866350024116890881801818980119673424107889487217592539514394562673673864929497211491791883005660300961737883296468656531654721532187625152070605575103892249103385608865944827327824890254962217468533731383281785124749952629780318251993677868900375412324703480664898764485103199696416375692062707128128879912560885693449047358518893019732784175667829104500864911926256338443107390741066115163122888564460443734981485585611670675166662200092333574969181111173552552932056988469191991951723987039184684431275765859829455328391671592454104021387735699713516620838002775252500962404748656158912904344370399832640417535081666497883737746737453443277182717774623926466888703699443273782265880007818612143490542394175601693535472274012039447031056337621569787425179058175130695472621003323296119088224498606259226142046072676408791203068924944590528665885744754683288993099249596067257454318027648721066008694264081562836070813110324252154571564865017704968119176977456588871119956101867944369408217782974819768815522090930758445273587442654131186165230134706642844917099393715708938644303949361694596219819706741391978369248462439433079281615318775900562346672950599861454082636649418480718746150155431196, 55616715168278288643894416854084020511046428112004514466138402371444428756939038506204280823299679405658172380808336613985973260296840791085955112607881594154229165840836159987159119570902668143502639900391945767758584503404082594080490096037518417173851094340935860922715018696075571876041209090386900518370566559432215167995033526695678526574372044712446506714018627253684170317831125320349990321137715996243346642239372427591719957307034945732123578648682638005835736332950921935700178972667526577597814534583585526270648705050239613075154024988494376763476951535019114328776103118050008330230420636548619484671537171032915160859760019365282607781476591108932922464112024933691153746807526804194011861058889089663589427501341003861817699086746751825175077429384845078208844361375956566112459780870246248884319886316044193019241473284679610593536601560041372899647590280102250782737275802227362200741795016264185282391640832760820496590843259290877670033483904724575176617858086519158951830285854848487464438554493430118597843704958338891078440111761936031829582778448397974846391379482615308841933713626224536428459727018127943436370726850709903767811763221563891341629109506696792929998278282981007712253053286729165633907171116, 33401623402594538867234637400162311405706480233276562588758571266128573537605975355004398351197220627323067912528856511900801083009498465857309945161412716439247267709048744014797199125484939576471842648261939142920413355502025142647387065406266752292538989254970045274741778272624406084369604578037991935249385614067468624868220593625892436993139715700384717870975219726783321251788621147621621634076017859690233108594157325160894104916091897395350035500581559314868920365366135283373070542488607367922982272382134916342245055906975732685801181788834557547454473167058186600006544693846483231945394302469717692056537098287124820960982200474582948472561234699334965252290513689254381148758377617223518043799587876719108973813871847371754361225602036621140298210710765828009031046411341833503002622273649110629275937408169173872676291324815245338475479608245326486952321725558235636574267622658308379147696828647336863007512113381968814595025066376026490706864646064228068130100075672611360556484572267021304148165476472115943815480589609275160978745589887420373354555205942109192842802312626536978606014502517262316009065656215051656764890701279179519321404270647871677005431652886658174572644034670275289501462414720812929426213240, 404911062311334644335392071477663655878065768136139377613581520691794451497989616946905535889187578193565316891586542653553301926606381811256197367967255067176513608764199559711882944845523288029477226129903668275877698243325734954263912989303332802484684989196446264964524754106728618632060916755682419699560742212550637480753389376352817688131533636349612131575423616692553103984171296248004050134351728670180252679964272554031787715351268292210025293728072153985043527195697978712376009955597282812949565568460650543410403475571591886901977045853910650413794977574509315661725397172192938840452260156601114421145719326768632058869527365873219548990465864419548904001538374436323487722313876586988702783785146349199066882442525131867167420724692216457192508222418100773145529175131356986079680469461238724155201261242358351398158689290228867233787368861462248545747171023255626737333147555786163681632507212014544257918399469047590915508468388504804332462652318654364994180167743549347995956187036144422714391303989371420047639756488344724920886929129233085120361149180241623159486910462219041763914482016615589718251986229616252000594045116249254202143096431302235674563319612616333976311828912763558314087117144888896278173444315, 335960291040524048057258389548866282212973883953968977814277623946939832036892896304002465851832238638570272481994757883768022900846977558219535740484692133550749862625018529139424528545603650357687701918549692535795107681599045140684636828224037888736357737476274556474548756439009391937281995300415699415789127244360294210910340744515659461232238797655198759009156935607065729462405979143123941984844158128786673266301495156969768498331409869898198529069973709005673617273951522751562157628454752585950515462632114430344301800854663669753387178360194577303801783259082498231790412198031131973488179978282753698462204926956541286121175472938915798766858855748696237602923653170291923058334220427143068808228073752905905398208718362718491261711621781659268610573743878966477962043836430957219061991059362146443662535445493946263417195012869437283562810884008285008495030482552154588505939132830543375799380604066306969942992229213024333993848292337655326025741803233390350216585246301348729999965161892751908524360233737929439004756663531699763742107950037307978479124397031788315703865749889436264669252073487937244576163854997516661154611035411409264289705197787616551619282132125130539143892922864484430256359142624186750897543235, 616515802899300249397426506470229108313661892952712296341014013872428822017232165027718999909860718975574188196468562532680182908791554688050941031303036255858429032784918365999288326218429956943414519386528094446347589270316215829591402122392753989223709271890479398709469245710028315753019732338127263098127670000815223819381533332391530719542179354668271588032202735682174371641545647527074242689106712101909433039811572632280793454481490058279431176663672260702437287805925380323597432955481619202681917212158809377849386947849811327801917874653928914524982778234227540048565829376384672015798678897783570584048129511194264935562254168438173356738084914400481474808167735095910859198106006816048176949654456871484845930272287262182427158946280443631600583126479212015168547227039753297706257643156699801570206328096744913198079288675631223383186555040386263092956149811319980030877041694620539514707905034883495058920351751497726733406520210677938455472126068201886304243108016356669054802952139677058988038614039312592338878130831038131960066521156573275992678059413135151153715927110650927017333002138432448237991033471134140600627371931225222339676704043748997231877255393766962667781464825338764572694405491664989889384388307, 417439617481204432978467858198821390866493311935621810046303841392364662411309735838697878153617442145324982062289861673918119422775403520090645664350791949638189966460844417650140356822666458558261452793052426255171809358210038754994432332564082621354774001142964983920504507920900623753317861386733298311388101411718571482968705646853961791729073548808140606572771303596766626572992311152778711600644409841651532130234504383244747484211308809255838887095807226763018856501895618419668549845687806285646114559990149227360260739138349406314142784978600433949540805300769083111406424842193426042913083812125321249038395829002864452302839603910295506838114464101889098719350831894475976519854663799565564225707749602541506284706486520258401317008903345131421207833501569362331140699618865378598757200094566413482112127324039086374077709320843117761666765151781697345081952562326091184786461776077543190833174793896972538272771404313590803164677696616730668396653073020751771913234807137438422678283958553454351451317089542001042692795474501288926785870446837072794965833001518225665461225621183027639059899299312208056772498725360995348498876608278089106923935542965444034668777027309867173321069580981403495641986723971529034944149200, 131167054825094951995711798427057985422765066308207590696032195990414481823313412957399897974825791390619031881702979281604007650487916260606467904348697514565909051256392561068076464578424581830479344053600451100364330670073244076068391108041480437738193788416364206026995277412195742744220012388145563152011464740926101111186728706693562372521245425795700630899838514208447031920033418985238613785190400874378320633960642675437776624889394817192843657049732954292492520398851809156020882914518788164846340615396463962520218177008888064473594477142149563688142228823145489967873234104194471318004833039990685646077550368798940097201501803272828869893567182039267049285550983710297270146233458246165868829557216595026575773762464650035898858451497296293668172432858179079700666315609261506972610962709294744583273379582449952336170104249408833242401069035047208774484739596946382043443284769203745311515647847456448263439169861940365097120403821891910337883087352504941627864967336387954915273645550571807972371798528509595337206461995305522125322447506275872323103599555880731966582291709115532928352196647915310771865170322926509893914725065032864605555418027659309569168798057997857665363216432891190995985864095984558007738051665, 373700649752015615118306643490865477143893099903754794999736283928942238713000592335650549582451008779589404367120048021152029103340822764890952232087771227355719493810962328140551404528861091579478268567237340670299343318207538653461241262719118987359179147674306298429779504686473755328038028264019027358934712329709590894951663888311022671274092724772507497388638346923515467505978812928514908038026540077041896744057526189203099698955683952515696504044378440751437346282843088284914650799457532535293970452321670026325675590834169963621075115994991669184326434273192587497554930617463378140211461360359848197013227482340512114581070900577700777233646012033744872958300904864471013915468376220413968317411788769971409845908732266364706981203141827235080662769112136650895565374640845895329286483552365193129048486091500294964122604875145681682150101854630026933454031035001278910268535287910454194068717012981007453417207463621577772249935302615656603248088492385833559758206747691434796752732235793404121980886917494936359578198691460447929606851038374609414166265804450348434728802859235600799349800277763951848242540632128341390494297748905227925853753579850725069890475768861546837355594101800722164280617570934073048210500156, 487277797092491517924955379446517012606865209045967235596770732703750996879653743179919797895540623421585497773237218560789792814224176897784816308718283754434883050118969726597640841498230898191625696266402878146654936231946392895859688067633090297110486265729396920585904523122485963894700695475498606654508631198891063834969013506401839977670744500035993535362189901514544511316861854741485030665537207470690679685955350478936080132618346643625742370759607428214269362860230124214060621267205862720839007113855748486214551097051826971309547792472802174908092654788069728865603096811232951716738749176417564185237443572310539009756328173592544641908430344968746290089450602290538334031224052321626997531021286875566473823080486323172315027618797893328446782642576370322732631499278783150974470780479815572695771836888393169080852999488447031341844994247955668063053009015903877274843862205370658021359590314070026791818406334352815498993327122960893625943757780131722196469587794337113496195700481720946326025411628755390026801967473644127971502173708648913182990151862454205689637085143640166787822732341827611788819948631925511188778509909507621884400042511701906639638112396627395205872938371936001295060702371646057723585645380, 215560629156372039152888400496555948310376037232701973674931835456557657761208965043196672482795325156682568509727562337196419959713357611728661100012637304057254874748740675236417304858662530123371984551612417258265505228407005373741387831755973328805892740948411915415399948929456024243891479434283640505338502856448306730658235022118946825762030486772260785393979945560113983048195555170341907795141578216992136909233526861550474758578505552458399236831091712355595094219818813011453184950845729339795172186030647895882059112420483410082185845828926732689176290288665972138692619985681980676378919461667740586668732774801898158513547172672031198797750402633351841064402171596256475902743507672527184801780373220337852306194294842829341576073197949258881239095931281839224472377746289731661097267906759798691309131399547114124322797521182991351649209833565905055158706131500300023853315925175642852610927975103002643387094285071706594838434516633851693626638309473393052394315103508365453310679193232603663100953883716202186361874228197830062931295202666742566719000792413107867900594248071875943537555529415885532672701328124130776606604489135402139252966804613526626837099985557334871717332885224889629232761964603071277153365627, 437057858451389109819466944076408249653459351616281048079390374022535414002877998577139660654735981053412046929859498661332708810278087660227186348289235705906531704282955449748017246810843766647877991691850110236156721895007504111210096065066805256899145807265079698970260292717204173180170247956121134670553857399074190298397478162265361453868201223414436113466385385530442849510585593747546740672275445353122324269560795908406347607344232940946001711666671575681803756172879817457330895166532491666740022676925892032916405768267230129955332839131557931447198791672543323030991842620661492024633539900845884772275616538277307632045627946090548322356122195078940182821042496409788484729110355068480580006008832173407637175071207581299879826541007389589012918396786117948301524686604014589161047701395245685653380637286359640302794185571653409731076340634593069635894333356225962283541805137193253799346160453447543244094458838612357251085707416594664052651356194130713872492313781415474816529870505088638794960914671917322605827592771117823833945850608999371373028837510026835014305746283037868665809264698025328802966974773116869583985198900048398033232881389790924762632526813418968386439288503544192557465019298900777313421389825, 344530686458460355122621879934582208090059296746433954053326131545008917312323170406858087611532884910282596361649039600453381168497159881330355468002006141504144549977606585691846211922288776830836510249760422924009310989128028182902979865839658844157082839899732501655882098203288339759327089093334033181607966594409651229307250468571329966665751310625172738775385592085078640241160920000541191584400362418772050029177345181580336174147780019331073900142964304279486210650402225590421280347725277397239913099237151844140004562921357212982189830662825301956532909069121432495585283546069776850048303402848516997653502679666244007085818737608749960429460663030259193475620174950068456489819170276345136348314014277702458407586531712121741821966826008851640118987466842216214134935832837576988609878496371790259158733020960523043522236916846858269090914463527013310250000920929745051891620336482659188307685053968435799671011842568919011185379548090931788352658760132031655327947991949048209281551378577146292657200173601414153467572917297791311059445249612291856250124077734899253690286816097840267463266065517009541823753591440450911776532309979384499325688689698549485430621736643374382914848188369529456171123292153675672483331377, 798481815181376664006994468699273672962309926447080098236356575915549459794995225546272751535978598969843244212066648971292783490721783545025345032090878527517551140176141280507431781072953351272525406836775214704343469215051884965745270432831221842945256173852063109853774471474594801889529265545876230743633517198967120304422994276971958462303263440010983942723815847308609944115578877491083893280491275348667404890630283463314419217774250740383221971759725366488155000648784218323096528227732833369689385510009771243823739959716495334382092123301195458784217066990025847241113379105678786527250217266983418983782399204826150801179533912530534912259781700055384637778656165218442080268614804700175076775099029221482003318115107200397556913205587910446797441335838813503571816217299437665888333098338386747311038213301977510915414799109227278560709452266977196379405450026294745859381296532818104112093375792202257621051351923933522948196574125253201243622718931396361534850934903461011970005795285934005994784681735380470279527319581755478511645905446605999315827830421204081385751944649446833472244789302380756344695010418013100362398273479638770312080190188046867553683195693684366710008507963216267033969186852602215198417634965, 380397969886454072783831355402548909513669669690849010372255160843803381950476667200172988228233871480056441635899850702590832749966052960732712361062967062582043449960729668992599544571123010337361385280245174569690396371604229569603045425694035846208342659321802558826038462683157067772346856955434217674865921284440201398812550288283460931858900629864224103495359129820121231676151886415770149857769793753651954756192668685672616915803152505629532514857074475867281004188168619505499472287465949400887575542524922225329742480936757347942760545893038153015250485208232015877083937183719180956681728035414347221753079077046149213755001309184315323317819152158653170959821356385036343249040513586052432426320639298417379568085725646396455954668466458794207110371865428061250684324291139697538439773278831429332352357558292358846895761229662706051386631666585652063315517466552687681778138778981117445729382872315374885914310770607745281341273852059830621372691745085697527627381049720703777939557157237448410355916973120462034691822346016853960502792642735835741673753890467845819177997279493893734767360826610008604869789667410791998618467427781313944008685847557457575582467856010936128174235765387797385879467415552259681809441551, 88467193361449044435780918789693915902054132163470888912106936259681283085274153478921811773281683354573800749267889955332857770452346580054656360495234484464298564198581966399633885545623516375359562136483955576416692796620041208987487945410463475703004260996984490057885338548505213206448878251512924887428195775635084120124394397072062695891722119295937598671917199628767204705865832343528142984431500443479838478509470205408482967938769922428700413783708938390193453809085832368739455495105642842356287342614913541233163282156883001313771824102898937864749527193741851793577564765364568072104373532513898316075500366695994519021232223287266376704890698291208653689331334495450642868642567311523036957836096907541467746418034375894107177540565443499950733296118869462616014649243433126978147215883673472276740414344054948208644079182183614665774484644402475788078762630726918447192404822349271188738371684488740934852988732383577336934099542571522412779076162790623709536347774178594043600446782629913002554582578748478746023266738572303752592025947290512678436963241400420623492787618493744078953536320164818511245512458539075491253398669493285009441844380555697005895387450176151087001729969473733415885323657845496272391997020]

for i in range(len(pubkeys)):
    for j in range(32,127):
        if cs[i] == pow(2,pubkeys[i][0]*j,pubkeys[i][1]):
            print(chr(j),end='')
            break

flag : DSO-NUS{983945f1246c3c60b9f49ead20ab97f11ff917215dc93da04bfbb2db7197f3d3}

Updated: