poseidon.py

"""
As an example, p is set to 21888242871839275222246405745257275088548364400416034343698204186575808495617 when working with the ALT_BN128 curve supported by Ethereum.
"""
fieldsize = 21888242871839275222246405745257275088548364400416034343698204186575808495617

"""
// https://eprint.iacr.org/2019/458.pdf
from "./constants.zok" import POSEIDON_C, POSEIDON_M;
"""
POSEIDON_C = [
    [
      4417881134626180770308697923359573201005643519861877412381846989312604493735,
      5433650512959517612316327474713065966758808864213826738576266661723522780033,
      13641176377184356099764086973022553863760045607496549923679278773208775739952,
      17949713444224994136330421782109149544629237834775211751417461773584374506783,
      13765628375339178273710281891027109699578766420463125835325926111705201856003,
      19179513468172002314585757290678967643352171735526887944518845346318719730387,
      5157412437176756884543472904098424903141745259452875378101256928559722612176,
      535160875740282236955320458485730000677124519901643397458212725410971557409,
      1050793453380762984940163090920066886770841063557081906093018330633089036729,
      10665495010329663932664894101216428400933984666065399374198502106997623173873,
      19965634623406616956648724894636666805991993496469370618546874926025059150737,
      13007250030070838431593222885902415182312449212965120303174723305710127422213,
      16877538715074991604507979123743768693428157847423939051086744213162455276374,
      18211747749504876135588847560312685184956239426147543810126553367063157141465,
      18151553319826126919739798892854572062191241985315767086020821632812331245635,
      19957033149976712666746140949846950406660099037474791840946955175819555930825,
      3469514863538261843186854830917934449567467100548474599735384052339577040841,
      989698510043911779243192466312362856042600749099921773896924315611668507708,
      12568377015646290945235387813564567111330046038050864455358059568128000172201,
      20856104135605479600325529349246932565148587186338606236677138505306779314172,
      8206918720503535523121349917159924938835810381723474192155637697065780938424,
      1309058477013932989380617265069188723120054926187607548493110334522527703566,
      14076116939332667074621703729512195584105250395163383769419390236426287710606,
      10153498892749751942204288991871286290442690932856658983589258153608012428674,
      18202499207234128286137597834010475797175973146805180988367589376893530181575,
      12739388830157083522877690211447248168864006284243907142044329113461613743052,
      15123358710467780770838026754240340042441262572309759635224051333176022613949,
      19925004701844594370904593774447343836015483888496504201331110250494635362184,
      10352416606816998476681131583320899030072315953910679608943150613208329645891,
      10567371822366244361703342347428230537114808440249611395507235283708966113221,
      5635498582763880627392290206431559361272660937399944184533035305989295959602,
      11866432933224219174041051738704352719163271639958083608224676028593315904909,
      5795020705294401441272215064554385591292330721703923167136157291459784140431,
      9482202378699252817564375087302794636287866584767523335624368774856230692758,
      4245237636894546151746468406560945873445548423466753843402086544922216329298,
      12000500941313982757584712677991730019124834399479314697467598397927435905133,
      7596790274058425558167520209857956363736666939016807569082239187494363541787,
      2484867918246116343205467273440098378820186751202461278013576281097918148877,
      18312645949449997391810445935615409295369169383463185688973803378104013950190,
      15320686572748723004980855263301182130424010735782762814513954166519592552733,
      12618438900597948888520621062416758747872180395546164387827245287017031303859,
      17438141672027706116733201008397064011774368832458707512367404736905021019585,
      6374197807230665998865688675365359100400438034755781666913068586172586548950,
      2189398913433273865510950346186699930188746169476472274335177556702504595264,
      6268495580028970231803791523870131137294646402347399003576649137450213034606,
      17896250365994900261202920044129628104272791547990619503076839618914047059275,
      13692156312448722528008862371944543449350293305158722920787736248435893008873,
      15234446864368744483209945022439268713300180233589581910497691316744177619376,
      1572426502623310766593681563281600503979671244997798691029595521622402217227,
      80103447810215150918585162168214870083573048458555897999822831203653996617,
      8228820324013669567851850635126713973797711779951230446503353812192849106342,
      5375851433746509614045812476958526065449377558695752132494533666370449415873,
      12115998939203497346386774317892338270561208357481805380546938146796257365018,
      9764067909645821279940531410531154041386008396840887338272986634350423466622,
      8538708244538850542384936174629541085495830544298260335345008245230827876882,
      7140127896620013355910287215441004676619168261422440177712039790284719613114,
      14297402962228458726038826185823085337698917275385741292940049024977027409762,
      6667115556431351074165934212337261254608231545257434281887966406956835140819,
      20226761165244293291042617464655196752671169026542832236139342122602741090001,
      12038289506489256655759141386763477208196694421666339040483042079632134429119,
      19027757334170818571203982241812412991528769934917288000224335655934473717551,
      16272152964456553579565580463468069884359929612321610357528838696790370074720,
      2500392889689246014710135696485946334448570271481948765283016105301740284071,
      8595254970528530312401637448610398388203855633951264114100575485022581946023,
      11635945688914011450976408058407206367914559009113158286982919675551688078198,
      614739068603482619581328040478536306925147663946742687395148680260956671871,
      18692271780377861570175282183255720350972693125537599213951106550953176268753,
      4987059230784976306647166378298632695585915319042844495357753339378260807164,
      21851403978498723616722415377430107676258664746210815234490134600998983955497,
      9830635451186415300891533983087800047564037813328875992115573428596207326204,
      4842706106434537116860242620706030229206345167233200482994958847436425185478,
      6422235064906823218421386871122109085799298052314922856340127798647926126490,
      4564364104986856861943331689105797031330091877115997069096365671501473357846,
      1944043894089780613038197112872830569538541856657037469098448708685350671343,
      21179865974855950600518216085229498748425990426231530451599322283119880194955,
      14296697761894107574369608843560006996183955751502547883167824879840894933162,
      12274619649702218570450581712439138337725246879938860735460378251639845671898,
      16371396450276899401411886674029075408418848209575273031725505038938314070356,
      3702561221750983937578095019779188631407216522704543451228773892695044653565,
      19721616877735564664624984774636557499099875603996426215495516594530838681980,
      6383350109027696789969911008057747025018308755462287526819231672217685282429,
      20860583956177367265984596617324237471765572961978977333122281041544719622905,
      5766390934595026947545001478457407504285452477687752470140790011329357286275,
      4043175758319898049344746138515323336207420888499903387536875603879441092484,
      15579382179133608217098622223834161692266188678101563820988612253342538956534,
      1864640783252634743892105383926602930909039567065240010338908865509831749824,
      15943719865023133586707144161652035291705809358178262514871056013754142625673,
      2326415993032390211558498780803238091925402878871059708106213703504162832999,
      19995326402773833553207196590622808505547443523750970375738981396588337910289,
      5143583711361588952673350526320181330406047695593201009385718506918735286622,
      15436006486881920976813738625999473183944244531070780793506388892313517319583,
      16660446760173633166698660166238066533278664023818938868110282615200613695857,
      4966065365695755376133119391352131079892396024584848298231004326013366253934,
      20683781957411705574951987677641476019618457561419278856689645563561076926702,
      17280836839165902792086432296371645107551519324565649849400948918605456875699,
      17045635513701208892073056357048619435743564064921155892004135325530808465371,
      17055032967194400710390142791334572297458033582458169295920670679093585707295,
      15727174639569115300068198908071514334002742825679221638729902577962862163505,
      1001755657610446661315902885492677747789366510875120894840818704741370398633,
      18638547332826171619311285502376343504539399518545103511265465604926625041234,
      6751954224763196429755298529194402870632445298969935050224267844020826420799,
      3526747115904224771452549517614107688674036840088422555827581348280834879405,
      15705897908180497062880001271426561999724005008972544196300715293701537574122,
      574386695213920937259007343820417029802510752426579750428758189312416867750,
      15973040855000600860816974646787367136127946402908768408978806375685439868553,
      20934130413948796333037139460875996342810005558806621330680156931816867321122,
      6918585327145564636398173845411579411526758237572034236476079610890705810764,
      14158163500813182062258176233162498241310167509137716527054939926126453647182,
      4164602626597695668474100217150111342272610479949122406544277384862187287433,
      12146526846507496913615390662823936206892812880963914267275606265272996025304,
      10153527926900017763244212043512822363696541810586522108597162891799345289938,
      13564663485965299104296214940873270349072051793008946663855767889066202733588,
      5612449256997576125867742696783020582952387615430650198777254717398552960096,
      12151885480032032868507892738683067544172874895736290365318623681886999930120,
      380452237704664384810613424095477896605414037288009963200982915188629772177,
      9067557551252570188533509616805287919563636482030947363841198066124642069518,
      21280306817619711661335268484199763923870315733198162896599997188206277056900,
      5567165819557297006750252582140767993422097822227408837378089569369734876257,
      10411936321072105429908396649383171465939606386380071222095155850987201580137,
      21338390051413922944780864872652000187403217966653363270851298678606449622266,
      12156296560457833712186127325312904760045212412680904475497938949653569234473,
      4271647814574748734312113971565139132510281260328947438246615707172526380757,
      9061738206062369647211128232833114177054715885442782773131292534862178874950,
      10134551893627587797380445583959894183158393780166496661696555422178052339133,
      8932270237664043612366044102088319242789325050842783721780970129656616386103,
      3339412934966886386194449782756711637636784424032779155216609410591712750636,
      9704903972004596791086522314847373103670545861209569267884026709445485704400,
      17467570179597572575614276429760169990940929887711661192333523245667228809456
    ],
    [
      6745197990210204598374042828761989596302876299545964402857411729872131034734,
      426281677759936592021316809065178817848084678679510574715894138690250139748,
      4014188762916583598888942667424965430287497824629657219807941460227372577781,
      21328925083209914769191926116470334003273872494252651254811226518870906634704,
      19525217621804205041825319248827370085205895195618474548469181956339322154226,
      1402547928439424661186498190603111095981986484908825517071607587179649375482,
      18320863691943690091503704046057443633081959680694199244583676572077409194605,
      17709820605501892134371743295301255810542620360751268064484461849423726103416,
      15970119011175710804034336110979394557344217932580634635707518729185096681010,
      9818625905832534778628436765635714771300533913823445439412501514317783880744,
      6235167673500273618358172865171408902079591030551453531218774338170981503478,
      12575685815457815780909564540589853169226710664203625668068862277336357031324,
      7381963244739421891665696965695211188125933529845348367882277882370864309593,
      14214782117460029685087903971105962785460806586237411939435376993762368956406,
      13382692957873425730537487257409819532582973556007555550953772737680185788165,
      2203881792421502412097043743980777162333765109810562102330023625047867378813,
      2916799379096386059941979057020673941967403377243798575982519638429287573544,
      4341714036313630002881786446132415875360643644216758539961571543427269293497,
      2340590164268886572738332390117165591168622939528604352383836760095320678310,
      5222233506067684445011741833180208249846813936652202885155168684515636170204,
      7963328565263035669460582454204125526132426321764384712313576357234706922961,
      1394121618978136816716817287892553782094854454366447781505650417569234586889,
      20251767894547536128245030306810919879363877532719496013176573522769484883301,
      141695147295366035069589946372747683366709960920818122842195372849143476473,
      15919677773886738212551540894030218900525794162097204800782557234189587084981,
      2616624285043480955310772600732442182691089413248613225596630696960447611520,
      4740655602437503003625476760295930165628853341577914460831224100471301981787,
      19201590924623513311141753466125212569043677014481753075022686585593991810752,
      12116486795864712158501385780203500958268173542001460756053597574143933465696,
      8481222075475748672358154589993007112877289817336436741649507712124418867136,
      5181207870440376967537721398591028675236553829547043817076573656878024336014,
      1576305643467537308202593927724028147293702201461402534316403041563704263752,
      2555752030748925341265856133642532487884589978209403118872788051695546807407,
      18840924862590752659304250828416640310422888056457367520753407434927494649454,
      14593453114436356872569019099482380600010961031449147888385564231161572479535,
      20826991704411880672028799007667199259549645488279985687894219600551387252871,
      9159011389589751902277217485643457078922343616356921337993871236707687166408,
      5605846325255071220412087261490782205304876403716989785167758520729893194481,
      1148784255964739709393622058074925404369763692117037208398835319441214134867,
      20945896491956417459309978192328611958993484165135279604807006821513499894540,
      229312996389666104692157009189660162223783309871515463857687414818018508814,
      21184391300727296923488439338697060571987191396173649012875080956309403646776,
      21853424399738097885762888601689700621597911601971608617330124755808946442758,
      12776298811140222029408960445729157525018582422120161448937390282915768616621,
      7556638921712565671493830639474905252516049452878366640087648712509680826732,
      19042212131548710076857572964084011858520620377048961573689299061399932349935,
      12871359356889933725034558434803294882039795794349132643274844130484166679697,
      3313271555224009399457959221795880655466141771467177849716499564904543504032,
      15080780006046305940429266707255063673138269243146576829483541808378091931472,
      21300668809180077730195066774916591829321297484129506780637389508430384679582,
      20480395468049323836126447690964858840772494303543046543729776750771407319822,
      10034492246236387932307199011778078115444704411143703430822959320969550003883,
      19584962776865783763416938001503258436032522042569001300175637333222729790225,
      20155726818439649091211122042505326538030503429443841583127932647435472711802,
      13313554736139368941495919643765094930693458639277286513236143495391474916777,
      14606609055603079181113315307204024259649959674048912770003912154260692161833,
      5563317320536360357019805881367133322562055054443943486481491020841431450882,
      10535419877021741166931390532371024954143141727751832596925779759801808223060,
      12025323200952647772051708095132262602424463606315130667435888188024371598063,
      2906495834492762782415522961458044920178260121151056598901462871824771097354,
      19131970618309428864375891649512521128588657129006772405220584460225143887876,
      8896386073442729425831367074375892129571226824899294414632856215758860965449,
      7748212315898910829925509969895667732958278025359537472413515465768989125274,
      422974903473869924285294686399247660575841594104291551918957116218939002865,
      6398251826151191010634405259351528880538837895394722626439957170031528482771,
      18978082967849498068717608127246258727629855559346799025101476822814831852169,
      19150742296744826773994641927898928595714611370355487304294875666791554590142,
      12896891575271590393203506752066427004153880610948642373943666975402674068209,
      9546270356416926575977159110423162512143435321217584886616658624852959369669,
      2159256158967802519099187112783460402410585039950369442740637803310736339200,
      8911064487437952102278704807713767893452045491852457406400757953039127292263,
      745203718271072817124702263707270113474103371777640557877379939715613501668,
      19313999467876585876087962875809436559985619524211587308123441305315685710594,
      13254105126478921521101199309550428567648131468564858698707378705299481802310,
      1842081783060652110083740461228060164332599013503094142244413855982571335453,
      9630707582521938235113899367442877106957117302212260601089037887382200262598,
      5066637850921463603001689152130702510691309665971848984551789224031532240292,
      4222575506342961001052323857466868245596202202118237252286417317084494678062,
      2919565560395273474653456663643621058897649501626354982855207508310069954086,
      6828792324689892364977311977277548750189770865063718432946006481461319858171,
      2245543836264212411244499299744964607957732316191654500700776604707526766099,
      19602444885919216544870739287153239096493385668743835386720501338355679311704,
      8239538512351936341605373169291864076963368674911219628966947078336484944367,
      15053013456316196458870481299866861595818749671771356646798978105863499965417,
      7173615418515925804810790963571435428017065786053377450925733428353831789901,
      8239211677777829016346247446855147819062679124993100113886842075069166957042,
      15330855478780269194281285878526984092296288422420009233557393252489043181621,
      10014883178425964324400942419088813432808659204697623248101862794157084619079,
      14014440630268834826103915635277409547403899966106389064645466381170788813506,
      3580284508947993352601712737893796312152276667249521401778537893620670305946,
      2559754020964039399020874042785294258009596917335212876725104742182177996988,
      14898657953331064524657146359621913343900897440154577299309964768812788279359,
      2094037260225570753385567402013028115218264157081728958845544426054943497065,
      18051086536715129874440142649831636862614413764019212222493256578581754875930,
      21680659279808524976004872421382255670910633119979692059689680820959727969489,
      13950668739013333802529221454188102772764935019081479852094403697438884885176,
      9703845704528288130475698300068368924202959408694460208903346143576482802458,
      12064310080154762977097567536495874701200266107682637369509532768346427148165,
      16970760937630487134309762150133050221647250855182482010338640862111040175223,
      9790997389841527686594908620011261506072956332346095631818178387333642218087,
      16314772317774781682315680698375079500119933343877658265473913556101283387175,
      82044870826814863425230825851780076663078706675282523830353041968943811739,
      21696416499108261787701615667919260888528264686979598953977501999747075085778,
      327771579314982889069767086599893095509690747425186236545716715062234528958,
      4606746338794869835346679399457321301521448510419912225455957310754258695442,
      64499140292086295251085369317820027058256893294990556166497635237544139149,
      10455028514626281809317431738697215395754892241565963900707779591201786416553,
      10421411526406559029881814534127830959833724368842872558146891658647152404488,
      18848084335930758908929996602136129516563864917028006334090900573158639401697,
      13844582069112758573505569452838731733665881813247931940917033313637916625267,
      13488838454403536473492810836925746129625931018303120152441617863324950564617,
      15742141787658576773362201234656079648895020623294182888893044264221895077688,
      6756884846734501741323584200608866954194124526254904154220230538416015199997,
      7860026400080412708388991924996537435137213401947704476935669541906823414404,
      7871040688194276447149361970364037034145427598711982334898258974993423182255,
      20758972836260983284101736686981180669442461217558708348216227791678564394086,
      21723241881201839361054939276225528403036494340235482225557493179929400043949,
      19428469330241922173653014973246050805326196062205770999171646238586440011910,
      7969200143746252148180468265998213908636952110398450526104077406933642389443,
      10950417916542216146808986264475443189195561844878185034086477052349738113024,
      18149233917533571579549129116652755182249709970669448788972210488823719849654,
      3729796741814967444466779622727009306670204996071028061336690366291718751463,
      5172504399789702452458550583224415301790558941194337190035441508103183388987,
      6686473297578275808822003704722284278892335730899287687997898239052863590235,
      19426913098142877404613120616123695099909113097119499573837343516470853338513,
      5120337081764243150760446206763109494847464512045895114970710519826059751800,
      5055737465570446530938379301905385631528718027725177854815404507095601126720,
      14235578612970484492268974539959119923625505766550088220840324058885914976980,
      653592517890187950103239281291172267359747551606210609563961204572842639923,
      5507360526092411682502736946959369987101940689834541471605074817375175870579,
      7864202866011437199771472205361912625244234597659755013419363091895334445453,
      21294659996736305811805196472076519801392453844037698272479731199885739891648,
      13767183507040326119772335839274719411331242166231012705169069242737428254651,
      810181532076738148308457416289197585577119693706380535394811298325092337781,
      14232321930654703053193240133923161848171310212544136614525040874814292190478,
      16796904728299128263054838299534612533844352058851230375569421467352578781209,
      16256310366973209550759123431979563367001604350120872788217761535379268327259,
      19791658638819031543640174069980007021961272701723090073894685478509001321817,
      7046232469803978873754056165670086532908888046886780200907660308846356865119,
      16001732848952745747636754668380555263330934909183814105655567108556497219752,
      9737276123084413897604802930591512772593843242069849260396983774140735981896,
      11410895086919039954381533622971292904413121053792570364694836768885182251535,
      19098362474249267294548762387533474746422711206129028436248281690105483603471,
      11013788190750472643548844759298623898218957233582881400726340624764440203586,
      2206958256327295151076063922661677909471794458896944583339625762978736821035,
      7171889270225471948987523104033632910444398328090760036609063776968837717795,
      2510237900514902891152324520472140114359583819338640775472608119384714834368,
      8825275525296082671615660088137472022727508654813239986303576303490504107418,
      1481125575303576470988538039195271612778457110700618040436600537924912146613,
      16268684562967416784133317570130804847322980788316762518215429249893668424280,
      4681491452239189664806745521067158092729838954919425311759965958272644506354,
      3131438137839074317765338377823608627360421824842227925080193892542578675835,
      7930402370812046914611776451748034256998580373012248216998696754202474945793,
      8973151117361309058790078507956716669068786070949641445408234962176963060145,
      10223139291409280771165469989652431067575076252562753663259473331031932716923,
      2232089286698717316374057160056566551249777684520809735680538268209217819725,
      16930089744400890347392540468934821520000065594669279286854302439710657571308,
      21739597952486540111798430281275997558482064077591840966152905690279247146674,
      7508315029150148468008716674010060103310093296969466203204862163743615534994,
      11418894863682894988747041469969889669847284797234703818032750410328384432224,
      10895338268862022698088163806301557188640023613155321294365781481663489837917,
      18644184384117747990653304688839904082421784959872380449968500304556054962449,
      7414443845282852488299349772251184564170443662081877445177167932875038836497,
      5391299369598751507276083947272874512197023231529277107201098701900193273851,
      10329906873896253554985208009869159014028187242848161393978194008068001342262,
      4711719500416619550464783480084256452493890461073147512131129596065578741786,
      11943219201565014805519989716407790139241726526989183705078747065985453201504,
      4298705349772984837150885571712355513879480272326239023123910904259614053334,
      9999044003322463509208400801275356671266978396985433172455084837770460579627,
      4908416131442887573991189028182614782884545304889259793974797565686968097291,
      11963412684806827200577486696316210731159599844307091475104710684559519773777,
      20129916000261129180023520480843084814481184380399868943565043864970719708502,
      12884788430473747619080473633364244616344003003135883061507342348586143092592,
      20286808211545908191036106582330883564479538831989852602050135926112143921015,
      16282045180030846845043407450751207026423331632332114205316676731302016331498,
      4332932669439410887701725251009073017227450696965904037736403407953448682093,
      11105712698773407689561953778861118250080830258196150686012791790342360778288,
      21853934471586954540926699232107176721894655187276984175226220218852955976831,
      9807888223112768841912392164376763820266226276821186661925633831143729724792,
      13411808896854134882869416756427789378942943805153730705795307450368858622668,
      17906847067500673080192335286161014930416613104209700445088168479205894040011,
      14554387648466176616800733804942239711702169161888492380425023505790070369632,
      4264116751358967409634966292436919795665643055548061693088119780787376143967,
      2401104597023440271473786738539405349187326308074330930748109868990675625380,
      12251645483867233248963286274239998200789646392205783056343767189806123148785,
      15331181254680049984374210433775713530849624954688899814297733641575188164316,
      13108834590369183125338853868477110922788848506677889928217413952560148766472,
      6843160824078397950058285123048455551935389277899379615286104657075620692224,
      10151103286206275742153883485231683504642432930275602063393479013696349676320,
      7074320081443088514060123546121507442501369977071685257650287261047855962224,
      11413928794424774638606755585641504971720734248726394295158115188173278890938,
      7312756097842145322667451519888915975561412209738441762091369106604423801080,
      7181677521425162567568557182629489303281861794357882492140051324529826589361,
      15123155547166304758320442783720138372005699143801247333941013553002921430306,
      13409242754315411433193860530743374419854094495153957441316635981078068351329
    ],
    [
      11633431549750490989983886834189948010834808234699737327785600195936805266405,
      17353750182810071758476407404624088842693631054828301270920107619055744005334,
      11575173631114898451293296430061690731976535592475236587664058405912382527658,
      9724643380371653925020965751082872123058642683375812487991079305063678725624,
      20936725237749945635418633443468987188819556232926135747685274666391889856770,
      6427758822462294912934022562310355233516927282963039741999349770315205779230,
      16782979953202249973699352594809882974187694538612412531558950864304931387798,
      8979171037234948998646722737761679613767384188475887657669871981433930833742,
      5428827536651017352121626533783677797977876323745420084354839999137145767736,
      507241738797493565802569310165979445570507129759637903167193063764556368390,
      6711578168107599474498163409443059675558516582274824463959700553865920673097,
      2197359304646916921018958991647650011119043556688567376178243393652789311643,
      4634703622846121403803831560584049007806112989824652272428991253572845447400,
      17008376818199175111793852447685303011746023680921106348278379453039148937791,
      18430784755956196942937899353653692286521408688385681805132578732731487278753,
      4573768376486344895797915946239137669624900197544620153250805961657870918727,
      5624865188680173294191042415227598609140934495743721047183803859030618890703,
      8228252753786907198149068514193371173033070694924002912950645971088002709521,
      17586714789554691446538331362711502394998837215506284064347036653995353304693,
      12985198716830497423350597750558817467658937953000235442251074063454897365701,
      13480076116139680784838493959937969792577589073830107110893279354229821035984,
      480609231761423388761863647137314056373740727639536352979673303078459561332,
      19503345496799249258956440299354839375920540225688429628121751361906635419276,
      16837818502122887883669221005435922946567532037624537243846974433811447595173,
      5492108497278641078569490709794391352213168666744080628008171695469579703581,
      11365311159988448419785032079155356000691294261495515880484003277443744617083,
      13876891705632851072613751905778242936713392247975808888614530203269491723653,
      10660388389107698747692475159023710744797290186015856503629656779989214850043,
      18876318870401623474401728758498150977988613254023317877612912724282285739292,
      15543349138237018307536452195922365893694804703361435879256942490123776892424,
      2839988449157209999638903652853828318645773519300826410959678570041742458201,
      7566039810305694135184226097163626060317478635973510706368412858136696413063,
      6344830340705033582410486810600848473125256338903726340728639711688240744220,
      12475357769019880256619207099578191648078162511547701737481203260317463892731,
      13337401254840718303633782478677852514218549070508887338718446132574012311307,
      21161869193849404954234950798647336336709035097706159414187214758702055364571,
      20671052961616073313397254362345395594858011165315285344464242404604146448678,
      2772189387845778213446441819361180378678387127454165972767013098872140927416,
      3339032002224218054945450150550795352855387702520990006196627537441898997147,
      14919705931281848425960108279746818433850049439186607267862213649460469542157,
      17056699976793486403099510941807022658662936611123286147276760381688934087770,
      16144580075268719403964467603213740327573316872987042261854346306108421013323,
      15582343953927413680541644067712456296539774919658221087452235772880573393376,
      17528510080741946423534916423363640132610906812668323263058626230135522155749,
      3190600034239022251529646836642735752388641846393941612827022280601486805721,
      8463814172152682468446984305780323150741498069701538916468821815030498611418,
      16533435971270903741871235576178437313873873358463959658178441562520661055273,
      11845696835505436397913764735273748291716405946246049903478361223369666046634,
      18391057370973634202531308463652130631065370546571735004701144829951670507215,
      262537877325812689820791215463881982531707709719292538608229687240243203710,
      2187234489894387585309965540987639130975753519805550941279098789852422770021,
      19189656350920455659006418422409390013967064310525314160026356916172976152967,
      15839474183930359560478122372067744245080413846070743460407578046890458719219,
      1805019124769763805045852541831585930225376844141668951787801647576910524592,
      323592203814803486950280155834638828455175703393817797003361354810251742052,
      9780393509796825017346015868945480913627956475147371732521398519483580624282,
      14009429785059642386335012561867511048847749030947687313594053997432177705759,
      13749550162460745037234826077137388777330401847577727796245150843898019635981,
      19497187499283431845443758879472819384797584633472792651343926414232528405311,
      3708428802547661961864524194762556064568867603968214870300574294082023305587,
      1339414413482882567499652761996854155383863472782829777976929310155400981782,
      6396261245879814100794661157306877072718690153118140891315137894471052482309,
      2069661495404347929962833138824526893650803079024564477269192079629046031674,
      15793521554502133342917616035884588152451122589545915605459159078589855944361,
      17053424498357819626596285492499512504457128907932827007302385782133229252374,
      13658536470391360399708067455536748955260723760813498481671323619545320978896,
      21546095668130239633971575351786704948662094117932406102037724221634677838565,
      21411726238386979516934941789127061362496195649331822900487557574597304399109,
      1944776378988765673004063363506638781964264107780425928778257145151172817981,
      15590719714223718537172639598316570285163081746016049278954513732528516468773,
      1351266421179051765004709939353170430290500926943038391678843253157009556309,
      6772476224477167317130064764757502335545080109882028900432703947986275397548,
      10670120969725161535937685539136065944959698664551200616467222887025111751992,
      4731853626374224678749618809759140702342195350742653173378450474772131006181,
      14473527495914528513885847341981310373531349450901830749157165104135412062812,
      16937191362061486658876740597821783333355021670608822932942683228741190786143,
      5656559696428674390125424316117443507583679061659043998559560535270557939546,
      8897648276515725841133578021896617755369443750194849587616503841335248902806,
      14938684446722672719637788054570691068799510611164812175626676768545923371470,
      15284149043690546115252102390417391226617211133644099356880071475803043461465,
      2623479025068612775740107497276979457946709347831661908218182874823658838107,
      6809791961761836061129379546794905411734858375517368211894790874813684813988,
      2417620338751920563196799065781703780495622795713803712576790485412779971775,
      4445143310792944321746901285176579692343442786777464604312772017806735512661,
      1429019233589939118995503267516676481141938536269008901607126781291273208629,
      19874283200702583165110559932895904979843482162236139561356679724680604144459,
      13426632171723830006915194799390005513190035492503509233177687891041405113055,
      10582332261829184460912611488470654685922576576939233092337240630493625631748,
      21233753931561918964692715735079738969202507286592442257083521969358109931739,
      15570526832729960536088203016939646235070527502823725736220985057263010426410,
      9379993197409194016084018867205217180276068758980710078281820842068357746159,
      20771047769547788232530761122022227554484215799917531852224053856574439035591,
      20468066117407230615347036860121267564735050776924839007390915936603720868039,
      5488458379783632930817704196671117722181776789793038046303454621235628350505,
      1394272944960494549436156060041871735938329188644910029274839018389507786995,
      5147716541319265558364686380685869814344975511061045836883803841066664401308,
      14583556014436264794011679557180458872925270147116325433110111823036572987256,
      11881598145635709076820802010238799308467020773223027240974808290357539410246,
      1566675577370566803714158020143436746360531503329117352692311127363508063658,
      212097210828847555076368799807292486212366234848453077606919035866276438405,
      7447795983723838393344606913699113402588250391491430720006009618589586043349,
      7626475329478847982857743246276194948757851985510858890691733676098590062312,
      148936322117705719734052984176402258788283488576388928671173547788498414614,
      15456385653678559339152734484033356164266089951521103188900320352052358038156,
      18207029603568083031075933940507782729612798852390383193518574746240484434885,
      2783356767974552799246444090988849933848968900471538294757665724820698962027,
      2721136724873145834448711197875719736776242904173494370334510875996324906822,
      2101139679159828164567502977338446902934095964116292264803779234163802308621,
      8995221857405946029753863203034191016106353727035116779995228902499254557482,
      502050382895618998241481591846956281507455925731652006822624065608151015665,
      4998642074447347292230083981705092465562944918178587362047610976950173759150,
      9349925422548495396957991080641322437286312278286826683803695584372829655908,
      11780347248050333407713097022607360765169543706092266937432199545936788840710,
      17875657248128792902343900636176628524337469245418171053476833541334867949063,
      10366707960411170224546487410133378396211437543372531210718212258701730218585,
      16918708725327525329474486073529093971911689155838787615544405646587858805834,
      18845394288827839099791436411179859406694814287249240544635770075956540806104,
      9838806160073701591447223014625214979004281138811495046618998465898136914308,
      10285680425916086863571101560978592912547567902925573205991454216988033815759,
      1292119286233210185026381033809498665433650491423040630240164455269575958565,
      2665524343601461489082054230426835550060387413710679950970616347092017688857,
      13502286133892103192305476866434484921895765252706158317341618311553476426306,
      686854655578191041672292972738875170071982317195092845673566320025160026512,
      9315942923163981372372434957632152754092082859001311184186702151150554806508,
      17166793131238158480636170455452575971861309825745828685724097210995239015581,
      4443784618760852757287735236046535266034706880634443644576653970979377878608,
      21470445782021672615018345703580059646973568891521510437236903770708690160080,
      6932852445473908850835611723958058203645654625170962537129706393570586565567,
      17078326120157725640173982185667969009350208542843294226397809921509565607842,
      19251873001736801921864956728611772738233338338726553113352118847732921831266,
      13062907978694932362695258750558734366820802962383346229947907261606619788585,
      16576609187793673559170206379939616900133457644695219057683704871664434872406,
      17140499059660867342372156843620845644831519603574612796639429147195776838516,
      16226688173010504218547945848523900236290532501559570164276462499487632388445,
      2806068123803905806401128967330263340459046260107112845068533446899070326517,
      17788735370835052317224182711467216134690146479710634688273650370951230404901,
      9840665370904113434661468973557421114403401847108482949465899631150766783733,
      17357287363046228581837055771327121704742940914150998420465281177406182088510,
      8956082469997974864521346025916496675956939495318858500685756691488425559998,
      10583741436561099911914917245130852199607666337956354910388730829023746895549,
      15241902639811607164983030447109332729761435946009172128089506810551693978973,
      10889882303914055687481932975789161945462141459528413507160087442461090813788,
      19789561133254944544821898921133697408237804586549835559829396563401674817160,
      20741336668287037026472434608739333171202674306575625457456116338034432647230,
      17864073449995977742930566850933082711031717858550870842712972350665650521079,
      6017691253505466300212182439349954426085752315661098358839308909771637792741,
      5209125836207196173669497054522582922896061838702136844305036341250990710540,
      8138726312837322624537330169363664364899441867118983214176695868443641051381,
      15491983986041746833254372934846748393213690608865689646440909282144232382678,
      5054332867608171303802774230688792431028169804536607979111644888500809938980,
      15427030776591294577308915282298854681562344215287630895931797573417982096417,
      21754057982677295571284116502193272661309010996970316384923307174180521790164,
      16265286590463120486705206231835953324076688991892805307349612983237844034032,
      17679791107777049796013011282788633179411040182820636236163074053597517790779,
      4281652562868629887097957174897458165728741859103571825874408386197225591996,
      9168010397863299719604788533602757515513214141450093775967322808686129400625,
      17584182367226175071087689123358883902969885218985589531538416263709138156515,
      15671512310414658663135385639435845966109237059155734764323312289873534719186,
      10536294659491685326297777845632759824567028904726211134518740400643540109527,
      13431319759608247201135260841651365578663315527795431484765940626659812285319,
      9584697124715190200241839387725546204368618031045071660911490086723434692561,
      5180327104839158483066851400960171505063442195966219343315555549982472660055,
      18888217223053385111625483360538133292128748730565502371803782424772027937822,
      19535732913737027522540340630296365525208404217634392013266346283017745945894,
      8577759627886344995887423695190093296190181539234301534326157005220006624466,
      16793670928407147476673650839110019799844249677846432113010280456483595763987,
      13926032620965299897272071104154310460519723329016284975305942957859374938463,
      4794697578055472890255676575927616606591024075768967985031137397587590174501,
      3529566190782060578446859853852791941913086545101307988176595267965876143250,
      3975008029239568933166738482470827494289192118694622729549964538823092192163,
      17739094873244464728483944474780943281491793683051033330476367597242349886622,
      7367136451127531266518046223598095299278392589059366687082785080179161005418,
      11175297939460631138047404082172242706491354303440776362693987984031241399771,
      21687543815463985355165197827968086406938428974327951792877419032069230058777,
      21156136641989461785420005321350884477682466566148802533375726181416623358719,
      17347558768803521970212188258074365309929638984714303299899732035040892048478,
      16293716234695956076322008955071091921491953458541407305955104663269677475740,
      4206144021605871396668976569508168522675546062304959729829228403361714668567,
      19988050626299122864942213847548542155670073758974734015174045163059179151544,
      747972634423324369570795147739377097591383105262743308036321386836856106229,
      4612470951309047869982067912468200581649949743307592869671537990797895413707,
      9630852913694079049153027193127278569487291430069466630362958024525616303220,
      17941539917430916523930519432495442476511211427972760202450248798031711471474,
      20332911350443969653703295317915788278109458962706923653715140186132935894113,
      21764801803055897327474057344100833670291402543384934706514147201527191846513,
      18792043166429470991157980448329308661526906138700725174612608941551872082876,
      12308177224490762720061048892842527800271687977085172836705858261595655154325,
      6234555076867437297776538521925679658360922070165740193866337972293380196151,
      4651047048822067434403056477377459986292934655827821636179452835839127581305,
      4762047093602693619418269784972874862577325737690375448572644958129932507374,
      12373514879531674477721132062882065826558811149582829246378921774344318418269,
      452512704634345955634014968317367844987135264395068376894497483188243356523,
      21642936370936057063268550589361090955573362743817395689260298777690935495218,
      16170209200627740434842090607802586195654207376087117044989637541681675086276,
      11682826760471401430136435257946377996085824742031456481961511737883954750045,
      20628055165039718158878805520495324869838279647796500565701893698896698211929,
      16438375313036818694140277721632185529697783132872683043559674569424388375143,
      4855690425141732729622202649174026736476144238882856677953515240716341676853,
      11680269552161854836013784579325442981497075865007420427279871128110023581360,
      7052688838948398479718163301866620773458411881591190572311273079833122884040,
      10339199500986679207942447430230758709198802637648680544816596214595887890122,
      16310974164366557619327768780809157500356605306298690718711623172209302167675,
      4572051236178600578566286373491186377601851723137133424312445102215267283375,
      20933392620931420860078756859763708025350478446661033451436796955762857910093,
      10145870387395991071594748880090507240612313913083518483680901820696866812598,
      11173854866888110108878560284050142518686158431744851782991510385755602063727,
      3895357290105797542988795070918100785105415165483657264407967118738833241858,
      16358886674154007883356717944805100413481233709808000948036974385803613296849,
      10544067501284177518983466437755150442726536257903869254459488412549270232123,
      10495171258604974589451578238018388630585794890815982293891430761424812600427,
      13820724103604550843562070971473423552484851063169471886037640613650155173554,
      2334954333435579600152488915208745055087482119087065911968347050969338669409,
      15100284614446277058846085121308897497066957549089629374506920751044105723791,
      8493821960754696376711287628276980042183127459347650448500304251148421115590,
      18612435536889941393944858783110719304584209891406420832295898519317994950798,
      362101794940079733974215941991047456600874474038781578925062694203564740952,
      11020033081956343850903875701444955317664141075326494650405276926536449284939,
      9396289482656518627529185765935649373549564165735162258912975312413185691167,
      6879055176150676925438486069371149089824290576271090206945130252868108043422,
      12466610601804566637227883322591924115458766539177061670432424956205788935144,
      6570302110526154075173287644133038486970998888099669190857256824048085590052,
      20997862990590350605775941983360263378441519274215787225587679916056749626824,
      2642485040919927233352421501444361753154137311893617974318977215281720542724,
      18832940311494549247524002614969382413324906834787422940144532352384742506504,
      18751288968473015103659806087408412890105261892140397690496125593160830694164,
      13938622158186434739533995447553824444480420613323252752005511269934155122652,
      12878982657080117316101160964182202074759312554860119090514406868768962707099,
      13757859113119127982418426758782225628393556023865807897214601826218702003247,
      11817871682869491875135867072669251115204978941736982465520516648114811792373,
      11336448548896065624515261709306933490181794458266726453198857687608284871020,
      194970717714150352477887371297168267861902418496792228400198694925721020795,
      4999282817977533227652305360183045040853565298259070645110453061034932285549,
      17094174197873140035316532568922652294881600587639905417701074492648767414173,
      8484251464872873032022789624790167173458682056313339863651348894878144808746,
      10260366716129057466862964875306868898686918428814373470382979997177852668590,
      549263552864476084904464374701167884060947403076520259964592729731619317724,
      10052714818439832487575851829190658679562445501271745818931448693381812170889,
      1735373362835209096342827192021124337509188507323448903608623506589963950966,
      7998373949540733111485892137806629484517602009122941425332571732658301689428,
      9035170288660659483243066011612158174896974797912618405030929911180945246244,
      6458619567307414386633203375143968061892762498463026121155477954682976784731,
      12314261817227551876673777186352972884847144237148169773300066404053441924532,
      19869454329688183813243851218196625862680921049019496233616575272637276975230,
      20326917073492686652690019138603910654692396590122884746951129061818467704300,
      20403270805536666081472738304916561119325397964511536801752236086414818653063,
      2865941730880218719188224311916978807415673142487507504983320505748719154068,
      20614246027521726470902405957496110178017768563127335842405314212897493119848,
      12060194341463088508348622863463208827312128863463014006529428845777217660299,
      1128906798719793375274166820235650701301189774851381709919492584451845983197,
      19670876372911656158743764425809421400123168087389888660308456184201759209723,
      5647230694522866559497222129254930524469944430191328619422533907417776118543,
      318629082509194371490189248876734616088516535434806492900653650176451776632,
      13685970881538585172319228162662520285656571966985351768743970447782846353365,
      8283840607829148567836919316142994745766280854211662326632930274668867638198,
      8968895518159422029900464138741638511289476298837958524156654785428413265371,
      10061801991000917366002570579819627134666386452411986168205986791283562415829
    ],
    [
      6652655389322448471317061533546982911992554640679550674058582942754771150993,
      2411464732857349694082092299330329691469354396507353145272547491824343787723,
      21491443688002139478732659842894153142870918973450440713149176834049574486740,
      20196926676989483530222124573030747187074792043523478381149800153065505592963,
      12986278951352369831003505493892366673723882190521699331613883287145355738793,
      21126146258242782643168619000295062005037298340836817770565977031890883232034,
      15509665795506578582538177431401381655815033647735781734613703976071034655246,
      6989769181472743404364681671283889685042701491627165526899522083327752110839,
      7062179885254277466334896166987547257487047183881628199983668518000910197987,
      13842521112365108087725039904948872289730786568469683976372377853164252494752,
      3830559505943186272618534143266118508463381443414165428900505002474439179836,
      17704863473432653834041116667846189591617394753001613253930974854399793083900,
      875580502229441633079974792778818749112423694973231971690365132230865385439,
      1971134273535892826573832061354985059300866001765691176219451252512658771248,
      4865738840363990164915013008693722144676933915103280504727326977328013515878,
      1148603338028060679975883868174895825055359423662532941509525326937127571764,
      17506086433923270253695698017062834613463718526046463655503742220257039588796,
      21580033018107258179208198773211859664893072138803756118939260252922297665067,
      15411900706973212043830142913959920716501447427702082030760032355626616412240,
      12219699506725448409610279620972339448030565224304464695714944121760832152291,
      4525719544192047521328360848269156485222470829314314216955024799558286708479,
      19667371373588322336224317159113441765198420040800065314868656839300028747331,
      18916925604689704279265158984702141998345424765142129953154245912230835240445,
      12789343981741773931665143789673052782408749041041266509485929045869073416222,
      3094428508959717445577232225505810354980663487713729230015754183012845687401,
      18544590634480965569098056786078005630500574069468005220462377474861119476492,
      20990087440247450018723844204951613913840993427110495085701200965767234569705,
      17552251989761134508416634118845221324472178264364440017634233349418103869223,
      21000797802575507763447855752602183842956182733750968489641741136166640639409,
      19292751508591545849778577901067988044973302547209758604667395356943370737868,
      18314088316445539319869442180584299715533304874169767778761887632882728399870,
      15003745150856597539000559910957155642193629735521291045949652201905498569732,
      7839443900003691950104175747634267110464104444913379977500178134209666299140,
      13568305490393393394812598233983935295266242465548739772708079888867621061127,
      6453005227995051361096639028742707098785560656441339640433794156400437698140,
      1420171596348195609536167209221442141824294918625468780931400849866478645240,
      8347329128252205996443084339884155586061343024498283583400215109265013719709,
      7893774494551056447960817286805128884970061671041428326788899872964096959040,
      8970476243368194065341537088653900235777512204874037182428362347342487241690,
      239049405935404678508864874854718951364753739466303321590415544572014148257,
      15772878921699764223771017074289335629553777447709755479885293350677783703695,
      5416082112919155131434995906647355834510201879607888732259087164602171650389,
      4384524908062410354304345761652962203632712291085564157560146286207296352050,
      4210984612917608245844011498198864216639269565627982123611519493203177283139,
      18816442907032290878644773027005263628136050677095986565400687355912498966559,
      21443510232279945782338486087712914668515437675585863788610958361560172084515,
      3234314779308300525339049581669531363375743827111579883853941968586490182859,
      11029499234949696730080035941750777601416171837281021031653841244636590396063,
      11145210633226924132308292113124660576759662647204939721872338908644906571564,
      4583160563963432761409369246361117506465307518522062239686649163525543782173,
      9813992026757562966842771727657080117609486122615087352428596024939855084450,
      10084171857039480706430282187972782725948479260179367780776125786119489581409,
      3874212709197875589640151274548083098712939093643165182881681226579903752816,
      21595542491397091124739711708612983479307589335640792812157875295064235960610,
      2068530815441314105493629066002923150651375034543842424822712297257260726954,
      2673459852071215292298131389250564595426361004231758522146794940265552265806,
      8591046256746588406353455230465605224309754008961178558834659065898923355164,
      1020055192431352394776887540248098706183934464205704158014904833376067287118,
      11085709480582865378042656141271006552092494690130782253913953070642865919312,
      5673844083530503489429922596812992664928167369104420134641855283771127716005,
      10492199162275168254265892158402955076490959375050993042712629236807564461542,
      2280843393156259739329331366624245275580688891778782679394848304764573859886,
      6807797027131305026345508953353882265754363485246407959111359919046340709440,
      12692191384043938397944633973317584101723715998700063415107128429315536223446,
      19818676957110967644349139912613239435706480354664804036688552936554140369382,
      18055602608192644695569077694296748842203151828348990995792087204755925787339,
      20934555391215769430553078793246717148484784880715746179415906355043590089450,
      11420705181439111353998210442417752592951340005396931802449360401461783159557,
      19878854521263746227125001670931867821366047088989510542865511663910116386085,
      8568201846715449867087132677683368912214864824182424933182820310911278496552,
      19198701614488576617610339232794062430644024620523684127268879880793305460015,
      15262122764244854433806270478871594904740306012582364033343126589996733802868,
      6412758421155818207287638337822550233376667015263373809976157264137577776202,
      17371585001641430978766734501830788427263945848682170096055857509304472649262,
      20262970042379497707724791203314262108784948621691331141565359315001027736581,
      3859750447119748295302212198327542106766447958113540005985799287718502362717,
      1172269945800307665458943534144481495673510885455899148864236015097947176746,
      8164247467959680477306326470118519335673181279975551434197731340070491876250,
      4513977811114181395323888111232002391599397736872779927267726121435887238972,
      1075250595927474080680862736233039825365918646878264905022213616210377518447,
      18658420120424372681792175914064174056413842231969276203770574969914576681364,
      17769673440848360838244654765103041739044212539359630263894092078288342647801,
      4319086204044362848967484441065231939136453667264715596505827197873119273506,
      11221173270629292820060668122527062274557317856738971635698169204652845111606,
      8635411372759272135249379415383299350267629947167809163276219879514948820576,
      926977621651476360285369760355547766944001783780761167546467658394097283069,
      17702143780592866375901805387463459229828093905183622296234691441436877570082,
      629612289140842594504574984021125242351317893847688437087866691775821981724,
      19990548577495092294245865870717186004301934545721835081514347926537975465539,
      7124830628609719908679298707909792306162298058570958688501370177898647946696,
      14620227791860703231425817538142948793892390269806790476396226159679984968174,
      18495581997440241868332244230687799183899751339442721677540757155760745277888,
      16922065056093401385376103551657968760602009001905886435813054626317776258714,
      9969610601962874779035054685661667941954971427956866645694064022029705170229,
      15281641269114187762159685323068136816556739502211864119670902056596295644116,
      12114994625438879103001132949163961965524612903017200394727056658298824651596,
      4840986177718281128440833017205097196672382395936939379498412745183060615212,
      12847307562796769659308999092658905656250954898192781948610713494470441775991,
      20290096217351155282642224215178246911041509999959311313223857240001143893317,
      16151664509646153154405691138084115125600386733136285504828908979176781265710,
      13848845391482751436287906247470303487958950799995701248612703022979890932133,
      6335716166231441585596963683321661194889815181545222079376536449814718259931,
      1824302750039354704619545544386637317858342555634601563660279997221547953768,
      11327469654081586239268713126961534952233559223228327222485848924908493444712,
      10077703415170135154603829433031861799853903739210136452726077323833067256620,
      16368073884579385814331927334821006319227867093692644942500207970751483237405,
      10621580796499573269115131164341885791299038227955222944695715163010783205295,
      2099241376651019397894434242565225315652133572870234550073686122343103853816,
      17104632243449417396641550271977294699471083572885397875525767745512335891599,
      1935453754847256492223646005402770357836971113012418013930273797463411526183,
      7492761611332930896292052363224494314920390056637668407353957465667515477934,
      16836705924460095689555600825174696605443212968244843485187771119291716736958,
      16995495500678141665340056658079449793587669420913589967848082091551329904176,
      16097379973857697753436437302681608056543122759719328497348770844548177814262,
      17476569537128329379528694049566216604638194592812108658767104922628767500420,
      17997217989870184804787026924935938133194070033518938653831611194683423549591,
      17573343771046232580761295935281170028624495346579002725814597714902588657750,
      2450087639204541254902859018960918562514681200270997307467560465282168310665,
      17288084325555056222618040923753050382954155896826087372317882602328092535440,
      21837047676579063581498107773514419735425738753079336764356909012851439336687,
      370061273472837873736743292149368449614309676635341873070086681342317566380,
      420725183996224279379885018872359102189091670793820517618337092091910692771,
      4966571645678139143731798992823327185758562224229132271884647901363447388530,
      5039558223429273757296118284876763395391635773837549121798873235133698166026,
      14663152729953724779401067486012084029581847325524052152795817923033297673686,
      7201040456590575809960214033959496417566605177095808543357813677845263237276,
      16872945504528960415453618286121813996587432836152082188694652370255998768595,
      4914824783780909279212078186433590922437371437384817332713271291839616026466,
      17503018483514413315464207189113334433424965178631599286655188843769810245465,
      4087750571011463387872022799241315348852213278729592692674275176152296405923,
      4006961923780091252337105595934918049936238157468198971234322013673884171131,
      4481908842184366902145805444001507554481032302978790080019710161108326487967,
      13532316826436461968093937893872910736305115143550039673102602344678825540956,
      11602986656925867325907196773754426955346837006705269228226729102186031417465,
      15306992574062791537454541745213815567999895856471097922112648012979731636068,
      4497571735611504561173050536899411999551839050319538712220770383407135602945,
      2571242673174714867278075260451133687893879636121064640779554188161591611843,
      7070272070524747733177730083966686149849667613589868731851816020060781720851,
      1308310289745495626002351437755820460104812708071634598163946330870933261232,
      9483468192990391193401121929514821570714432121414330663623018046165053411090,
      7317568349845215930675847155716598288688799068821709820024570206796617676748,
      1918505733423704616434273602054555051755671749253598966287072464475922854850,
      15158168161084905689406532256983805923258003804476527617207287404280855731962,
      6855540174355511438343304861678411868002455139032857270673849263857877330771,
      5989863238360846166935911112885654223487221280254816980802479355446167746774,
      20283337058688740322296928691341300752003492063748410749625272920572074851396,
      18957132189629332408653055312790838576277703952267542471751593810468444454136,
      15764518568966520670995753676429154315765754748131847346608706222194564055358,
      7192524197002826721654253762628934164676539329903087107420445743247046038858,
      142950766663597487919643890566358241353679421113406309294925836697585309311,
      15012262168187689680572958978610204856600235635916074406168861726626292993057,
      20795666834671497603181209610179324236645779324677512349797033323222380300794,
      12650341271833683789775531792948185319868795529390391267833516836256688318306,
      5597700232877580665749288204589530549415282468176625525368428476461504532052,
      20949303924691159143653175365242293984396858344688574262804199947001630916385,
      10746523145835332938672833282581864816136388045771578294905302886974358762209,
      4998982766221590779170630035756820066555357949247521575936385387288356143784,
      6936999580131731861735955554005106460473097800566952971315565150681540640020,
      6670695360676548472482680016233507548657051302712214051977034166870814430578,
      12210816592786563975173850937247594401582085430897698766795696447223454826466,
      14933901149105284237676334791785996160108290333321693498322435129559137152007,
      3848529433916624869590379003597911090976938589461403388133685310398004369431,
      12778805225074604003024964969486878839359935515509480774809299341511161183802,
      3288267180428684202786697419666969564766921974531343432588030535602163038467,
      1272672432174256751826350693883913844502039730140570583479554071765667798207,
      21130828804874452930669244946376257892693846272313548250936991077452679117587,
      21254559353072473881932828401787134230282801383134765683324465204971002861493,
      4116075860631781527931204624078712926526805345818156200756399332393348685924,
      17435888597009729827411190999389277840088354756277916760187756022854497211746,
      15837398163415665169712832984380121382150588321621493928953938599666110830812,
      17988638446757562417082379159769772097890681265659458369075768452342579854303,
      8144561030363576879343874888624208577604401139613622673042754207987577727758,
      20020299925602421262203305284307419339160247406220693128040712457114283033661,
      2945951415037890626891130390523013930737768652394758977777336357159436605764,
      1505954324723537402640844232704189835623922400329086438898375859826553573763,
      11851584491756305117491374581845512067704002072833714119284164514457248861803,
      14471204965036278214508938537949717553799007630471016532866101610339050785912,
      7163557293233604902868673807221391042191134560333950452577270522828534690707,
      17291625782465108601367695465389799786592304061550212130987221355832952230827,
      10240907112109243116543462081552827576656826251172050843989873656917271396422,
      20702261919346727858635106264046787321170414155594199951578791234276181642650,
      16678253307828004252292273162411388452019952018258857370242272543091326285541,
      19810917631941180098047817620026253706643400683524412974923209268916769874447,
      3357220165225360610202375608872621445880880830154732998557832689480921421791,
      4392285438534542495332422274902727975330102148971785438164412161504066619105,
      14642025133729666610167675086855441462580619607677226879159952689184960379911,
      18142623439987890999821892559271093087005885278955082040377769578204898750505,
      11769399023330099592616157336702104329646487200891911089287290893650532639221,
      7261353756299584174448625214367175510387913706095214313669922259027644778060,
      10406994568199070863112470594593301582798997458844791396920771226539013327304,
      7475277967562870216712397220016587384793504784585573136176313471517144184018,
      9598064630327104406929367986473441777975480987434868213697837347643980267620,
      21137410002545951849752865514437404724653771608225272412595423069852350320648,
      12345612867231779996383303763804719815752861524077922121654106906093103051400,
      16461750199070055335468534730937701659470268635084522644824623393184528879703,
      7829250842543018165409887731515254191943527926556191989558018633300783421935,
      19801151644322693878208767560968285812646931156576102755771403150148125880648,
      808770634664491371274943928223981161442027957963181999892266696287962813461,
      2298122748772261447929855283951027113218922003687701626762072351622993276571,
      17407798064458858450209051887305178872029674498718760624162479511390762310526,
      18585562277464562541666582720366573863334618817908062612923861658144918595030,
      733976598693219656339731904831283238690050114241501938501377743874139460889,
      11316063986696838098122262534148335669847478050407756877728672233736962269417,
      17614529714381496379478130066245111825610297227468263851608027100133421612826,
      12110694197729365219340374599835523099651939156213930558791147158357810646901,
      4337343008663255658976574468931581484970687989356019720784093082313510905405,
      1379188959674402095268172673987199124815512095460112504778179157481327937561,
      3116148242507754420428768481157196067508084836097458698846114802493377512591,
      13306507137873332434793374848948087993544118494881134631519748904811343155566,
      18496878480807017010077624766326681523549495609998881196570603040242554712562,
      3940126764022508707486095199473913866137718790062498893812401335738707507732,
      10030078765792498033316282784150304209584388923549357286679864120250994473810,
      18519871685760382462428068450331593474924737719734568498029727699878543899254,
      12599428893576891013523136950822667754415283296587096197120138265392279834128,
      16038578953099895530943034305356008247313649524436132877362941968861459073483,
      14319233878082524834510736727226054073026413911339853399113450188859080424272,
      13710161613540579690732775978855380876556751245265568031703536595040993113748,
      14958726446649273856607176275240008023824615720456760403465034344703779274727,
      20935428111942360630758629263346308597806819928838924586682307174931367773605,
      5826394436548487315966647466017047216786257295199620110266250301500717796281,
      31401797997389676486806123612280306684597605608110075525648021056710776011,
      10784171495708237485952707518956314344821522727746927291389338644844400581452,
      11604345371765580191117799693565193618158448665352599382713281103552305960442,
      1378145039624937931836538950217364481423707761527018494355648047365613434790,
      10284294167221806561993937798090888689421933711157676807977401896199778472860,
      8233695574758520342808807499924062869636681352769371531557726871630696672029,
      6570581391072134029876349038190171593169496519436674767949949730275868319732,
      4026501263908027819614805027945064360196399012004574117767831931274788631138,
      21091098569404004244061462065218203986433580687172854429523306262593782053656,
      20711772916118045406356429185975897495222240215931761100801599257137350834799,
      3165519312799351250309462589160165591299333587158531489859211268084164422251,
      16470663723473939739601217501478624726068461799539012562455639586886033078064,
      15672299304945968727435591100602007503785845873606917887638890765525875123857,
      21393538327627889838198844493522533627143658125568123117776524944297103649079,
      7688819203734248199049004650451546300187194458173935784579101984183800649342,
      6609663518412297884695057080546416278366560290439222127471462938252865438638,
      3476303650597281786976907813110835564442121684386467570637538230409080744769,
      20633582549754495054832414039299188930065286005370053173386561254823483851717,
      18067076834611402459142612082327591538480657933568191619109271502102126814407,
      157209609820117793892254328219308970217366919934739036156851508233236414461,
      1848396116513925340973398423998379465460554039715233953825786874352442451413,
      188642786730195655565401615804782553245486295156304142809552609651873793325,
      540089254487190924787439362270708251103955915909358626209177199653451469720,
      12796274768956950589847157187031845061404119522843128177103898080653493269942,
      1785666356337148874573621868025910291826158842346617719666738769156993598966,
      20649919247042517528354490854561347316237285929352042389729444382153378749538,
      9568390566108569727471722677925269460696523515877621230569682954652430518787,
      8590683334740232786825518158771304803451657249486419816607179533515442407283,
      9321198393538172042803957409292145345834077448228642847843261373640165958582,
      3651905214805616378360839954289447530035139753215923648216350128870943481828,
      1324345422558073117779462079218851558068746895262914344818945294328678893083,
      6666363895154434021620869731925915051086919707989020578203743660669796175288,
      9850757893972463103359995012900314323213006625927501272997539940766979170137,
      10214293226445704940138790188111862069675188797488928722469679760666574484266,
      16862124085118494177559484642483513597285992646267864845521573612482278871023,
      9172340118369291059693735314505606817316211450324955429310200429408035954801,
      1968992755714619414656181112336357119271845800144345284299978250769356388249,
      17192498940296212027365280042755701662136570107224000496521552617655679821443,
      10063385968535643122430064779260670089120686456635080613693015398478175344193,
      20101961459945738562625328882763768836449780661345042148985756598106706734632,
      12704305975772252539534386080950631076046431529894091327218544197389260775334,
      3008242816727585639441748210631464697850194693570485141354082562181236010097,
      7797705698071555811456747812384107102104184812467361013142453143842134807658,
      19323240331433203844038522035479659453946066968727795017745942269828428751105,
      1698137797127320576751729191866734754105401103859852376273763815257758421427,
      17656850887825900397821271738817912328294075224643535784810269137125067875996,
      20755447986835730799031196367323817361150623932048563112034040627213597261325,
      6221130271964372280138992636208062417325313096379273438539556580491430711297,
      11042709376363248213366896208587241517252100440844476816212498352999929578287,
      987361321094619571176752720390429919723900732295551211263814448408232028205,
      15077982986114392945859048373768437818569856001604485167476360943078774679228,
      6278894644165961404521866714059972066255652200107181684047812674333675794053,
      2649747800006903047073625320829560088088800522557851927539477888486006072675,
      2636278052351769676017824297717609512488651850924228608531372135635042762078,
      816232991472315395984098922575496846552245086608787214581606973359616326446,
      14372687274434205592004117128588852491871014819273428668840779210928924573820,
      7351401720390274950322621121981079413650308506660552567079785209176949174210,
      10275293929161727274572318228903710245677747557851999483919909420098936352013,
      14869686444606195206734119702227763209172799407142930791211203702643805341518,
      937617196362766626935279232045712623531859540210120280128165029613358941709,
      21331527351771920568751070369057714014285398281585036009305608379072813379081,
      4305436470381074948146072259605215282335211631970525440530773004228212378618,
      5894273721571292784412707230481346442881109207745969297947253583203466014760,
      6512250441044591603946512492071171861967500633638753443182294740883123881284,
      20863871952569294813936866452848141274047362082838805921071316386912981651979,
      18788566662709810970880679984141390717017951403407913908833463086244783373013,
      7784927597396249543149135503684024377171301321636804832597181795981969626201,
      13818519831569592521516488188127966399245767953522268350556654747680372036664,
      10515208647860053151690062640705322684876580250632027862984821874343071549235,
      797604926079325807488629085866693514275115789253871397971708541758696512985,
      8741784289526985522570446847275649913333939699807282742190607491216732972386,
      20966712704043418981047968701828936463778140093909973286855779694780086635828,
      11359697297415630167449040380538108774924967116147664240213257348125754475868,
      8070907838094569287067982462230761680706116783989613960066342967469297961118,
      1868550288036217638713133945402464194193242298015503906068429633793800456561,
      198709459347510170000840600179608479136663571567208109852828485236018304733,
      1601154135701845545733926027872374554514541574822026314034696802419388627041,
      4363994778006302991481199477873248350039564117453810275561422974475581105893,
      773054378219982710451611471050404495804413666789496412742983455527754059148,
      5209426340109575519362014651321132459061755868557415513439993327176584352934,
      16124961412020675839394907565568143713078242978522632778625312854364651991011,
      20812496670075231301471694692369245988519082317145989298573032859079075730004,
      3312489967581906638742585802390894285073229440039144559060030129184388053832,
      2967475373447822846542676378804990140732835322255774209561143670843223463335,
      19744585401442299381952694102570931935735276268739851233412754166721728873141,
      20026293345566344685499234599699178313754630774489046573312844763673073616936,
      2611303659034102517884318354550433047021831422518437228002960700934925644951,
      6230291832603218406134986471162106408091661326026848531605999413028246206577,
      9126162046556730019959291776456914453189657463686708035601186672661595109020,
      18827736146609035067773173111376739253733288103277133456626928961785293662143,
      2328703958261360872869074208611873245571971231035163763965210852182760438390,
      13796410059666172174899788866809560044715551934510722965495280798363043241416,
      1593663256684781552813616365605526150610454082601584196604084376715746899324,
      1565874145189898288764434737762721576951043839540107044892767693968417810945,
      8709849304563896945461696717753976956465219721409993781555147204068634555572,
      2994256803561260177499267243802460581941891553208150783951937342406846377191,
      10452746656507347152042187616753027475507881362159944564077673851918869542550,
      20130580998875572619695450234900655050996104101008767761546912649074040426200,
      18926933358104691474037431437316089682088433006245222723356764715400831411716,
      3783551594057498940671877156409957274854990650480535806320220142873170375307,
      7919031943604095374667473717154511882451510130166237539514111182596247372692,
      14518552587329209714850286012780632801030157943402419401997576700600952906519,
      4770764028263701271241862755569969531641408032906982530346384375773459918490,
      10866502826034731763529371496585294375373238783964914673031891984092997621879,
      4234148117462322266937279401468367908013627589417699250592523530383852950379,
      10747942066055887965185603234524367638106812660210378090215017248140719240336,
      2587411532912868255102795810490361867789634574022411742057853375399270197531,
      17350061113113681344498080520518808976916692173267298878258722510332360424059,
      16490282364669098969805528215926442920328903121380947471680517193373377657129,
      9274691782659584680377375192682066090127280485689527337429804211265749864190,
      7630965482352419767782717986075793694403609453648729580916814032587325374653,
      9483872310024003776681196467845329825094379763716541754956796450187787638623,
      12182966986735661215639970080491757244218854808156498220088212871061979325833,
      1853790963611367149183440339188924598268644281518961106776656221408171642714,
      17425077915972423995335545370701802959607559878032910147159424242864219303096,
      14571075346526399549826264845894977639678567831720652860528738036970272895919,
      5627701855249158721927849603102149698163511782011562166637339712383551336091,
      3620805686755372260289125555061886982808014642356719556961142525373021656729,
      11556995641752009899073583627136467840237831247117281278719511600076965602980,
      18960242154096055221658318882298412299294886669455506299567210308762501113202
    ],
    [
      9174141306060971809979631725764298697615039980311809306145004207410652431953,
      4847693924685156250211477469465516228032151306221739650606132660616428517315,
      19669833054057639609249840291533340493211768292967819468538893000195036768991,
      19800508893433268850924828171290876015556093796000695603651522426066333836892,
      8244699449852279148780456022144420353408196866113049322676048275081354214716,
      1563672068712965454176533719400672258364596155638916268717470967009721945171,
      12723223712027468580318230235559705540011996847167975439677647504573149248849,
      19944398841194165937952509356635863229327574447452745793253427406349161295763,
      21218058308392585368594275702746106483411305671883946244077923955757637296177,
      18442884961885927579732373746933397748806426938144021013884176466434407012116,
      11138408360119814115926439449668526422561003790198269766757675305576549475808,
      12724564576884231109847024566806896391934587839830522481308995309797961575379,
      4897733190252075532660075013731462724561461746919488679609618967302541674417,
      4797748331306263412471031924618974997396620231469532262170060449304337691527,
      8626839560132907403537141283531395025838110825355541158539075100658769738351,
      6096293906324574249636975851522292408228519044739444932687579741964974917617,
      2351617695830568421216396081605990689071283678701192113347036659596049514149,
      3045682390398203085155257535118136303069379656645406266260961816947178911890,
      6935829264874515341379952008241845470659188886156484974987865751370715745075,
      19847439266968955911971997829840067368072860877451092633069920565944933744280,
      12795097343831149148337906863235678514689648096503928066579129201713661539889,
      10424580232112390318877053133877999442988769389050776486274146627765228950235,
      11651452649618223740363812212607761589812354035139843126315028745587570714609,
      21307929358023177131550002602820591970791247513576735567457471459920519084552,
      2579908580162153663820021562014873149811195641589016321720930006635393981680,
      8198198178555784054784079137247244121807775986273563786249987394640289859893,
      17176088986876377315956611075288620878117708836881362200541916957398026761276,
      671389874397910339333118510595007038137908096657753354622355890021074216004,
      19161949137729278558310070194809106779119877882343914445178348849980058405327,
      10827554013954037091657804154642286174226562252063767377995268439458401752538,
      11693672899474469123468133710607776304784343543318650064064636202512816205843,
      7026547767612627656560992117440221331093280829523426249915938274837157551621,
      14422968137896343032446633683271253661000603582016449215470992885331170459671,
      7685352543184863430081115767111935982586458632527708735083385591291346555502,
      14089009391529192464370954954330128327830078875414722902347666490457756695535,
      8424161061743752192085022963953944100289245618074575727145394775891645849043,
      9809236779073852557054640507912802523501426410996355424610807253990040160483,
      14100245203768962710288059230665566265892855964739454261791429988929622355986,
      7775683622333704945225255741567928967674629526812606133980425422182282014012,
      8739247215686497264451630351996892836638898510934389758205488381695687859658,
      9431876969679115468275053745264413939426444105271849398322497961102606290132,
      257914055321743732506701382989022126153391940932933566664491918941925247878,
      21801414068435960590201256257290267142214176965736081788536576642934903066059,
      9465495933537134443327560834432669768951376466867005153580146079082722525723,
      7862366214258716333873810314803222267215825847232397599183717032713290878315,
      10701164906390193792620967030790214270231326273599373762943959252633779929633,
      11951628827727068395937910010248864431667047516686609553745879936868276916066,
      14268744039571470490378560085356767818183790841094115879980723591887874138419,
      14468215915818797151199796266933432577607248341385185700017147731054148927023,
      1523824033338639123415809477892820349580561577160869448927791050266158538520,
      13559991428776910947424645696251487328999214391124402586267086012691140984198,
      18151203063828433535061866995346135260543721730169485344610433976436663085882,
      13436242600153492361692256644258899977135098134175123174795293078081801647137,
      9384556671429507406657070680351030238568956203341356106463890924933167416522,
      20321079285577981781556986944841048777999006905303986053275199507771332527205,
      13510502130738135726695195328780836716597947131948116750163533622597187969844,
      20903049289119144354363108865308751668897757360882852151457514926552553533040,
      5611953645512225417723205546533389174830971368309601830751921473015551069534,
      8816886019615642422040038431962872654062471314244185285424018745071289038220,
      16751828354835345790163611999302863949792305206769993810746019449909446216365,
      10421654749141018171116296259626916395875529220250947127973888230084671091757,
      6065225315766552671037285757918350882361743810888619479819895087632281975681,
      5737755346739850738724717271213687543479332312420206954339242459110768587128,
      14770522272891919220644639305274656491731294860310497013287297810648680944682,
      2777394791070450473479179489594969793054480209411136328689318984981401732197,
      10039559932930709555975364107098145624058027439566384376771787183526929807647,
      20757756003754261934858081777796652436155530474748550156383127600004580439167,
      13253166894715452480712170898662712132411702335275401581167208877688374856806,
      2037004052447343668129085129987646907388123739343356363273464870501805506884,
      21829471491172175426560705585746893969222010633542962882847909490991398830669,
      5130395545419191392223692116621486075405299333195732914002649716762739787586,
      20333821730990393095934147177227294218344864602777744425090741435432040213391,
      13629653802252084129446975515814037702423511189484562534040643669977716900228,
      18489091892360842692678715136565494502607711254719045543684163289077857041829,
      21380328601365035012832876315565064374684993115210423862017233170195286906080,
      2280052193465635727584791148501382679094142036232980037838088033232747821762,
      21415541711468815972744677841317235994302058341802530962394281077076174148777,
      17146992672828650459975820445250769505470616910596779130798889014378635881076,
      21676475584514120109058208398560066698690773910598518925936412952356431597439,
      18337052978997482578725645166749278142628133291693686105612531426715865276143,
      14864089429815580405957698645045711801464462794754089671996837547347950054532,
      10834607317840698149140890207826430113987295440254355899459691878793978994131,
      1157143498448645320415276909137008396665083714591338741616893578930275511205,
      5027542104048754930085470328670427788489455916338375169351586496298129661248,
      1922685817237874482932428650501872692326329693528175054457715565489676406535,
      3071473720617798005831658342971536643616129392641449174655528578463370685788,
      21091078808046042460442535848913779439792606439995062001271357804782672390627,
      19773167374024045118471391738750949555178717045037157435777574972149053404157,
      6418695831178793575992210834992785624340084513619644969535805236049937971859,
      6317875495482489567338519005308431806047606843913867465201005132273298011425,
      18001249545956637376455848019549801116909661454019565655561439372098476761813,
      15530167556609139699164228289904946047951254183080358784988008899829027775935,
      8702757129830652230304011519426558036441096750485189115358314568895250616455,
      6369986882953061252605652398893489899416599935424066958291402945530517772170,
      6842894437627604179732847187262933342846269043996061072487488027804029200046,
      20951621154051947571647917571547811655800779287153833018533872651413529893817,
      1219277535080749134805291725937516331501172121638812333911793209536894469364,
      11704605822590166851511022757496386950530399074796545751042566537118336773236,
      5983427701962592508775640503988144495847156070437130549832329402380170245893,
      20169091361583397776908351163571343158517532527313940288212943504015977979442,
      3347733015762117176159731683196584632702931062411889821726902331981723958255,
      16217509027282489850987935065936382820558307489954122630844029918951230268972,
      10781269196927764524006466217779648732772805761839205677745819812868343369087,
      10568911823766972365218731330080733630028238366288098114239172953421915095075,
      5568774544682750792074131352530555554984876659733959079036284517928264996437,
      17854353469028651373397049175548228061144941710027186166132671198740388767529,
      6573034112757039329551886086829829282007989555105157401271097204633906940776,
      14069627287078359391137554212536883450595451640858724555679971658981340584258,
      21119713641590541511025673864154852875977162278614553796484277752677323191505,
      12802116677235410441672624559825044917295689876859311183079161588690810005363,
      16037054471696658545113065872215787085337497333273419984439267709950724531124,
      11698654309680908244303850432833183602706804558317993513795996394673734185716,
      15147889780127043019188099948246961619198549928908180192590946633702778981583,
      3657342516407201801006680507925024451922115018712017224805778401726428603983,
      19776786467141868744713630352693556348834540992018636838044610844396164981103,
      7980994848490005281733955776875257044050741738176865989521982608944874160873,
      12415191330803073018395217955802011585094769098717180100014182475381600382452,
      9300986814650530426668152137665814177758578011365736727321578452726378799933,
      4412208980274764197258090802604347599791567698589180187154608728755887977460,
      2582317668924231956058541757507620542434237159213236485179804217989764223164,
      19860814395849792324574773787600734118308975251437485131415273418632757301303,
      2765909129639570206766170018363951893338720647679193401532780051354569922989,
      5402210382809272147099442645489124829067576777592680891367494969197685281513,
      21011104174655621871977821285307554463403659856745964274018020456838460357574,
      7018364707286303918877589672878574811337524823085078243421192184715151775983,
      136380103284908296988715215087018020601815024625535396780012012453684253071,
      15953315437474610448052466140270091879233956524793052736202793153707558909889,
      5912305909658884889781037379491781973092020933879206417274479331390062715252,
      21575635295587180789566592951559325743281772394055590203112195979769645712827,
      1541325805478255472079288730846072146731241030100908414806224735345400173350,
      17207219201921814683730773200330679841907450967511507012179337438654141678023,
      18266907794578843029196926509122804272900478710738403531664855427655744759655,
      1204224895193276222782842236712348692319665277014183965830735736728887994581,
      4023246588034712778784328407820569751989619386134504404739514704773521558127,
      9064437981037864995763386367268294611921404895425171966596873454090899491243,
      18733802217274421976148972926716884457128521840010001893311936746027998476583,
      684088380644531080099595788833220377905013807951051638705160997709156627273,
      11994830816367980341637110785269531718699655485484715851375754143223090344544,
      1831724566362300629700078416489434571462666430381219293205871349415506993475,
      476710745682537342427691635955087951551678644045621275039835625280220347951,
      3586272766499559446129476613035465343616602918105042144185864609818186807939,
      21220348736799044560439132291243370111879983677197111626309132298278891334631,
      13683795063599185801186093771702503913590598475095473714851383723199050309401,
      16118007386401646906425171859166434660243697555307927508268622819509657450614,
      20930641024767526790605168032291665313905337763598128831404465184891980632233,
      8098646212401100552303711812039666794078834386731698810205195111722330322418,
      11585783577173465460243373201831086724911159484415020913089605532852648999143,
      6939053275662244505087635417541857793206828446247848992283188764105131966721,
      12798043540382494855660472922674138947867597503468216532170157050160462426199,
      20713389801600667412553956346192236970217099413304167366340548074880917096741,
      8708207547232102069057776099666995672015399188924281674772351753887161579745,
      16016293152251662056020528248861487281148011452459422778601663166015837379163,
      14324897997637439510797191208789711173129460994362368408063402682894248793270,
      5652996184880208428967511742390474289004021508049280419259474250332590598159,
      9877106633097964013050071703002221796318046172981334418310092241450453368579,
      5385816971548914185604875069230499528103133871233951354186676373318036241822,
      8683091293306949708478955451280670950858818602696102489349595054818146782362,
      16854975838650963077652189417311897888852709425835763860743171659164792100482,
      2485160816649177905834265823672532710299580013309324666453183278408904845122,
      13571692148185502188613896013359942531817915076247598483272449919094247957149,
      11899399615412173136098732970606292047945698835588882297719609812145308198009,
      16827672312681684936590464376780346837611857292837989006980972390576065571472,
      15588237822592586948064701827497915157359094833395277985658706133691498343174,
      18356642512438827417103800170157877145465512961188328254773957819312191285168,
      21642368145757804795143182901389223409544979732781450480847315495418822041608,
      13104082060493963869934085622104709047787444250961437496674916673804812287386,
      1561532086277971111804773016487251313460788916643968126116038406859074212104,
      2718320602791009266532615731130512762296058687816604986701989820504700684864,
      6182683520717583142027400659687593712743548729948584058329789905227082638908,
      5757242145794370726637363237313640925174531077560764545993554185332488520899,
      13688467192244237790806289073845563960119021610896694359815485764764608925981,
      12528461541936459922472167643986446262977222390263675720335825628163511159437,
      4897268894447399415795897967133432014527122426051771866816059363418177665482,
      764332419588242767884018802335623760055144509861323437945071732931233600264,
      11755468878196093893190753985692714003062307843033761257593209352165323938879,
      6006022813561851182403581780143813226749481175437001910923100661321563995672,
      13901542382190510449243772206670622017835690746895066410475076631498053123535,
      17648853891656481911225897080296737974064729032668806126284849597245044343224,
      15106333841965710929952896897521673254279668876709612770907537801609875568099,
      20899315415025260484895459315726322363345188136910564549344894025053466430346,
      1409310408943258102775009950750654615881913956151269414096059752250092035807,
      3899088673345731523976816322438172722785832982334214339521575164464706226294,
      21406686765584824639201351330529610299177537976609066339927938099572420696135,
      9121591670793901722224770893633585291275002987585289305307167711146944200595,
      10711764678410479049841945177317023555168593838022414378232020467195337241279,
      6599257303974597452501135281719536074294806740553273627128065549267140155175,
      2142616913275380526921597026822750992917222975992774063376747381991404337593,
      16361086527663411948363284957489078505159658832010445114438602510508720771278,
      17122647864721668762640781848678028227021534122268561738445496382823789619088,
      21708018685042482318786273055293241752114005312590172460099480713746031274624,
      8303630654111760473056607545365338851734309857718959193970615705292826806179,
      3658686547507488906491014260011151850549759409901579684176172268581462329020,
      7720024124908065424512743488999250878143598904717873371853608249805302871508,
      8805244918657836956533473437651380347005779399042661429698187314657501156241,
      6303681354794120075893215838935586592706844702088252970663343726024171795351,
      21512507181643408509426104627003618425209526633080701556628608990726677651135,
      11835373417333287523801757951049679177935522717858158305516568595764125190183,
      13059698839045014411602727811400239840163533672024084777768305507840091151855,
      17635240655824524168378284083397931667938326555447077097306236826752492079430,
      3374412791113107178205006579112630099131939030015047870738873452427211677886,
      649711083340882271985565833699379436167716866997851102439037906608755280128,
      20002805138014565226408902156524463368767807620908543995020210484077706418135,
      11071355197960433041624284534649121637702414580710232237233568479006159191217,
      1105441595020980635809093220782460032826849883993030969714432603468135735502,
      9652765957610682812348919340146799318537766051849796416434577860126024594091,
      19248299650856496267902926731608572596705132576830681367365128976226233392929,
      15285802367070100569572399512275861017714681455564415244982064571963339715277,
      19970416835730683993734843405673457882587154729456022607061085470691843864556,
      1017865638757684714433500504002748241987153668285974836527484933462490771227,
      17284848056169793253916338792235498052654877955690514601079806604278964099314,
      11718277105372928962350331838305733149270432706448484259807630484543527733952,
      6670793378364949883511003949124179112275066568088468958915163969545409700112,
      17088789393958965094855662340742013087397643056458490270185660553870734946796,
      1930788514812600942005320214284180860980345276633471423966020111188605196111,
      8844343159753729614645407314580317697758296041737296276765583948670245312842,
      16657939543606018325703787748629433167511611178952563626096990460124133990109,
      15333343644239485619497914931918504163396626751908652058758135581206765801100,
      16533875915742793452819179569144271760125646811168930162441077117553849625884,
      19679534317472082858641184998487299940737032844519038845860980362664393659234,
      16385719932525604857740698205965045007053424961009717093945644387917936681719,
      14490521084213123170781774542655088188106794646066074998587858678154251198444,
      6386781978322405984893078797365492485297499058328348606653460996474947075858,
      17508047533433736707046937662428611868296556965172642086594091783148965906980,
      14904597000414815084666285064575232635645852687797347860862157463159487771060,
      14979972442969995336727018758631782107138089738395941038626891064816880204567,
      5299243186271864957800928637599294208954109271450189950375274196644046222516,
      16189884555052883188473617525411302750109401983487269295700675997730645714379,
      1645560170870292006287241616671417605853047420339675073261660626733726665673,
      17866745974872498136933906591373095763114066893081150553715211393380040095383,
      5744849574386643500716045532645657520001448510343827372577217716983339773799,
      14021966200238971589811034967347517039341058556783068950884921208853167419283,
      1201178089866013320759085637098781870734315826415474628546655403142858044361,
      5875644793836087035760988842421852197052681650818034527831700615895391179258,
      10875065950479466897559006840696567433921014267247530366235539292597441428702,
      2221662399199449388725697795500999209427453463134383582414172135385907744785,
      9758513532658579204941116584445291102215928928145103503086996542188799521709,
      20879593323317766577775570558015407573466986714590017262168011643343469361329,
      17225846522404915080676699509636264825833159640824918876741681229188434930856,
      15189442986691997434021855855358620506645387296294217783597931695143376252483,
      15973617135551858849206811241799666696907820418171736027820254766840973764431,
      11888113439449420418408437784450952639345990804839507528208325036625374967083,
      12365920814385241227394825974928370916184942218042429533600397623369545597697,
      11966175169612449906889690852332416255478894176917636726028104087408060623141,
      11163554022908212145274813635928762748847331295589087669583554722521180712379,
      15273476004030808005186443499782264987539818978741159793745891769358221570633,
      2013969196885866182480519514425192091338553670034650196068995589691938248955,
      5008975446746271526106846692137145404766553748264648461545948417006052208130,
      3926749194225734582453671614337621250954608160208554883789519551411469033731,
      1635544156808471185144068767649088695307748439189898784051754434524720057896,
      17144944482517962143604430553750908864860079758005337246916094084534304051981,
      13823503533305241872793740090687668844401004819859520464168798913603662683770,
      16335911272023134851779534303717879370955813837529588982953758998930285394340,
      14467284210444150699969889681308566002886261365990840091849371665183151060295,
      10578205764525658336257882813734672799527733392763965031628376897794294290414,
      18771425328697137255453620743509164311086906349726510394566012237817674245865,
      21804626093983212038528370352039806004465345685985435415809095637323683466452,
      12056805308954301132385034564357716323176447186932453788072119595595483786736,
      14307195735327805282612857510308008767450554777122724855715789120735513378827,
      6848201070063637295416045855906784325422580350462489495889308309540335269587,
      631364713487758647973016689203003205602593076699875191323345338325349259049,
      16214655556434201961140525501007839859074077768660052713461045928979956365067,
      20940788212183642266181811368870506130164462254923655617893660245551698033523,
      8257440848494309435270838240795567828478627302119374684511017376568090372435,
      13701089242130867705897643891164147923878521147124165292045879194108024940909,
      6895272953337895406509859406973110417619874994579965619097329249292199573333,
      530437169778092455975584310016745919549274205817234464915791595041990209639,
      9008612822403008353420189298381046023002474279157557733428254452507266389025,
      14863423501786052071018008300345884780479084379412157784789951872243409629758,
      20091026239041315645045502002997446404106877721183777765607724358538559881231,
      11103877261161399045807234470901399725912406134008627937945079980590775715243,
      21529163495181909351665093277427712610965764606448489357319207727176092439794,
      19540446772694448035410067193880900774391072899517686330271100773183944540294,
      17549510450820803306426739851959754252204444648959723652883552677325100583689,
      12252518814610348662318155253547558779974557529822012236107550517806390105567,
      8058115132085119666951861652409945532276905989404523986413207631657437321956,
      15916100116790431839835734530362130437167135501074855072245598938219364570910,
      14256533476494466694764843270015662315303617568641801280831873052211753536970,
      17865471381417606502707639037418669122823481329049436020149405646709537112534,
      14015711483636570179335132940981982618090553643653746531174110949872682031017,
      6075776171664976866533080327142904134938121198707020111533599997509054627652,
      6357981809351565370498807027309828058036389418343890944791766504532174516243,
      15145296985037303761634018005118672316118004891352906450983918852209191841446,
      2473672396516437070485250176897956191104549656554290725379242542480862701754,
      11059085933391482002269653121188853142706883316754376424538662772943167665341,
      14804069155713123448375113552227724310276294677318593116834685772120057819258,
      10146378656966122923223443263705119557842694560695035707977826044606938090895,
      21828309590915152213768434346306434851424116996828875020020066586363340244814,
      15568879616082229996551157805731419126872501425454775741945679993142071548779,
      17504079509060638501918729619244098692140123800571022969294759717277257664716,
      2998311560047298465700351970612785742605093777116697796464434026101441410385,
      20229972737818088327107446854254558628041027965197447598027135778783710740259,
      14884874200763033520375899992902136897590350894844904733314191389520252900641,
      9619409751736964504139815024141276029474791187139050183491749032619248817404,
      11534029087676783672833531415041588991838838078174102967049055562568798961925,
      17106297093375816944137015955705541133308466659538554159312635106186252148471,
      21676736161168806529097919794022110433487869702564846859065695507460463414524,
      12596447704589377083704857810305080195761099125652005594925931498073219198049,
      310943124066162607352831846280730445558498286205117614171844835745706684432,
      16013029710570597613246104892930389004941711962070683476555063566372534206859,
      14282564976066063966062366540992448474634085812789771416509095817495183298269,
      20757241092771652500911491636894210910134068426068355089789205706892703219255,
      17084251309147907751212619949757520468224028014308500329099194408342072624132,
      14680350698112448759886861002622963534698534998651150537754386791270019720748,
      17739512731440543100681958009173086667000199263945053345384367808940651002571,
      8967486063900234709994801661246451094429250620940593387993430620369318619734,
      3906067814916986286272005884942051451306945488494283077675304366798199289520,
      2517004675157816404807349457307096161030587393097616279110332574293494030636,
      9995302877359286298434340810356550712107485295049220989690824504445305103587,
      12849909876017357260683411536833847986127911582040960825577300322066595609115,
      18074515800779889507358182860997188274134395074469953155084226981497567860114,
      6692811728183968363967959295970424292426462800383828091752006855360167264617,
      17859827663908740084792157440799065184931609649811664442236242315795442091367,
      12243409340804252499520308602187370739653046835019551522661290645230850934962,
      3009118420068966587115224335717185828292538080040896739662684632413054772046,
      15856202298588272962175258696610233941787471472716811521132004805327415486141,
      7549804594729480554341356998842376772514802673462970334329441043324983960866,
      6390806437030742378988258255983502109201709511321162596105974797942236431761,
      17370236522182003753669946647208335160124999930136364231371998757664000198520,
      2261672244214630177095236704932243497157963117166120717011661647779055001646,
      17325026196605130064689259977831126468940872193987407658419640959345091161632,
      3631641025220845885502691330008982895233731506600778684638817282531001457735,
      8656561399441987116927438675277763317789561532507396244334062468892541066084,
      4069166732330197412844703565599514109399373916243310212229125901351402003915,
      19808198732373520522982274785888742523226720967259539531129335924093928174880,
      8555796834031869022510134190573521699378201702450788201649007358450530423866,
      17759660636058865290579521740750449606781204755231964378855563896473545202303,
      1335826395218609619260020055566056869243760115287254209950063597653055872566,
      21596200365241795669701682696176077888309278223833581800772036945674858315765,
      12619752319673193899296833725747186284394167228468888029626464753793997178599,
      17420588547980145067421969830249755561311178399975476925894947008643385243007,
      10337481272389772505654575850886249605422739785111225132545740838911222864209,
      17928431631046752749930349099366498612885288622404560316665023363985966878427,
      3075798659324203306711977985120251896073145961913793478792728028765206521425,
      4639500613932181914847461422373341918892878975546430906324216810326467690534,
      15396322795715441250300995201889120935591602515487993982711884319616897970533,
      6391276937505284102735701938724106665734769352007891548547667448647832351929,
      6811373320779057384916660178551330838095673247430496448933336925226142036083,
      6590973140323934807800215988687710942074412987201753370126190631819398102173,
      19364648614154949386936259588484266535262135334799266379433252509193375956715,
      4702754284612371917466042550086249683933140314858807272591351280832918881874,
      1081036249074169248236179367049085684430282426446509768147097371368406374049,
      18548093223441988703029589168425055383154624592689171393242936199350770119589,
      11098999608073377668352846814752381891400020647878345005629685447730764310163,
      16001262992680194260590639872321865154716987495605624862471107193457192704714,
      21696229443869118415905915570780926763029898831113534481730746953640692230062,
      11716215712634983607563947056324900205144202447594949676250978337464771243867,
      1778908113733035314726603632369389424542091991692308812147944884836647395775,
      4019081204388123040098634987844274011285321286777408246805308194144238418480,
      3473266952388383063447927231564219811787341139731701190625605897592140631276,
      10457881304788072618845101933412333126160339089704353596608910674508961127232,
      14926101732700077295531234099443522459232814784151318061435025890154852791802,
      4036967072197259618286839959572768559469665646019907384624959071646231971399,
      12776716624632228928613396031717959431597335742467953143594165782617234803915,
      18894783424164609284436913400522166453255844750192864579927645453695213022195,
      6303809107919167113924303987533838414137996606980561570652539716097058487126,
      4729698693443803882717817492985796053343431875965792864932005291979914613160,
      1645790034267553926884568714540144778649055395816210525904813567839945991808,
      8138260225269705405100573121045873922755899939885385491610389913906979427176,
      680936760009829486282006800072001712155424246576949107399338687767760991887,
      17240357869291182045663678468827695873425113788704614245279840174870850373113,
      19100963939745621863641468371111320143895293700517367016077996431570157414340,
      16188989656090417148189510820963186890780289777598053654241741803194118100843,
      18027402882394597868782011288920739982398714370069420860949975937357531046151,
      17780529984916796963712255733293310230026423072958099290880849386941451922559,
      20004531511171838591303710792081846238092292916166965045929062171308088520097,
      13855731634251510230399834192704620793850325654395687428672253016405315169901,
      16872938837392115669581040432902657478544143723662502779821325505282093696739,
      2541555081244462826761076743762714962901590548271316707071685417008817634653,
      5136424039269088350807839181761422963254683236279333039713142751702136147963,
      19216238128964101420135465007632926445321991494181045543846024053552797518994,
      18868537488540023742258053821537824724371813776839672880900985865823137839953,
      18246710415801024039719497716350501105591286880983169809863166130543617917249,
      20608694004331631709610739723463009412162748201282986294016482926528443868949,
      11318113915971658853560322943565673154831611543653209084299774855226816037778,
      16240989418312335385576389959938922684406585560688799437547298624184839261343,
      16171299673760267132909753100946681733778389681324959987573199154235691694977,
      8036823955656422391918380552495301547890420665617977624790236120392727764522,
      20269862530534739231936251654244170650781428788816658397167110617927916774329,
      2368678892744667199202318323282128737449992006513656480477288092472671147090,
      4618078962163037429845764284139891171861860687111566735174912070413086829215,
      12695350627501306162901105159009497730633599768443844225981772758225613194238,
      16356283146491744069785034066388746989409816380917535719898337817088223419024,
      6407893217596287850421377738867081146106659458551198123106454022096864887316,
      18168868018352364136212098098453930600797374324006271488950341490483455519349,
      18352629174410142476418438008157117497168118524562206830585500251463010761689,
      4344169393287991961961456515301754172943022039566219343212376057129143739343,
      19424839806870716108478074501405697296961947409763509419111261767390677718987,
      5796037897847804302272999466834285170265203646465480652521088328457333766863,
      17402105801450379889120987010453669096275392789725153915905747267778100864362,
      15540989618743824352651126288511222263828123668208146479603617243655978402205,
      945810410725426921570254447269595873973858272778720657523509910503434094174,
      6962323734045776666289031609372270190654631739266635759799844631053633876675,
      11382945272742312954364642163371436855283161775445664525053938433459897196647,
      18940251871958826726849623572811640436342841713786099464305053400421580490631,
      13969540696178305383564753026163726563325318478290740131984853424331762285147,
      4841983966001277917879506889862519614692143906356361564304719688757862622407,
      8939049562492171082419559182596894186639203815268680721033389307282239000385,
      19265363396776097866041313346787101192508520582744521467413665478819721956884,
      337106861429123598189388456471513480497137213511877011021531147545809512194,
      251367482782327915297484770356856386307188967585026711663629212746150191478,
      19506616511267234489421548744907283107923549136620297132842391511025844759064,
      20633589633280372440758096707466273580151526293980868749421563697429194761212,
      18833062060138888612708634036427140134887774731041742144004707524569102994071,
      2927291160590267909596732410727396533948837350308818016906834558527125752899,
      7095572562193114209617459307511041110255341231707924363346373597653253806883,
      14274988113217913224290208839851596837329960221329537670822013510325939323091,
      9965830780560026128320556230399915681196410289456547935188741323403719404039,
      10333365845496980935202034863900757172839454015352626511769637076650624839070
    ],
    [
      15193892625865514930501893609026366493846449603945567488151250645948827690215,
      8655680243784803430516500496316192098841666200175185895457692057709359214457,
      11710807066713707084726423334946631888369490193496350458331067367713412617049,
      15442364818086019103203999366702499670382575019009657513015496640703659810202,
      1358747428976145481402682338881091555771254635226375581638965497131373838774,
      15658002471767984962034589730824699545808755102240624650914676102923421241582,
      6420480504329990097173256112095253518339231893829818344055438052479612135029,
      15457172495394305353698644252424643614748461590123908880271021612601244389162,
      5745943350537490600340174787616110056830333091917248931684290284533019091654,
      3877253492903478989342845512796806320713689655633086736499730391667425329322,
      11257677301507982757739320943403112189613848490812422490591766717141506751601,
      16906586852467953445509312290627525856126394969718997799028223470195783329296,
      15263589725854108297280528692120758129000336125328939290924952731952242586386,
      21735940039489460025710098364749096267519151075908323637361429746399161905338,
      20023056608360522105358681147781839024069418874082333862551226466128829664291,
      5677500725280079960679484373333947430817198394184436922575072427342643665917,
      3080516739494460477657748111767941482024045797587058388950619118994388252853,
      21486496065617100719537932626843898998311175055335457507845650282870586541596,
      5371049178920102602305531530023787518286335086323221270202212974241707302466,
      3074817222296007572297581554183445947239252698770067839721345984255386069425,
      19180807038569629573914331337874446591506172622522351734982093457681161813141,
      16937785199372956273358037645552299688842385008757508130180245705952406225194,
      1688218397616770248184651775433764527272029131542529408516364801909017591719,
      16315958669815317541884966612581197291281164499674338063931623110684590850347,
      6218230753007070123505625054833158632732536069700963073464625252554943737669,
      17774528060285257656595928889288330429565059134928074258373583886985960212139,
      16197131592052727313460949906369199026477758140133103701908949020106767192893,
      13418604038232148873269488320329340508522225417123160144993642839875173062296,
      7265658443160253752317166706266927598319661172006072732797351716897681315157,
      17200150079219747370109251547638276280610591698078334228421747259741754887,
      8627121890622175767416692555014275717515106888840919734160364408960047296494,
      14546964505431549758350267964924534495477687922558528647552728692912697049247,
      17132720822762740343718421124251772119916072270451579802112353604446214831761,
      234333065870376500756753915306346778417056884715946003873280290982247600083,
      18375643491701271245209094287106352436174133929245169725584150600992143374298,
      5158448692161567615645197008737390561357077078129599243188536485308363800282,
      614161645152783610732075198073600394068518413590650990586931263981193439341,
      12661793104597977909223565537293318966803153852970198322604479648383643541371,
      13041905650419760925682179803296711066088286278603171065755078690359168540579,
      15006023590144168506070897325649191051975999212058008674224953860265667513015,
      4983349941266961584317889823965291023669365981564144622292227613558024302012,
      482274340065333833495445682213681402212945945150526736364263233985449810602,
      3966893131006556898236790392613869798057510088913626163333804949895810673044,
      20923301526284527685000591080290190641416245135554916208054502046381491809443,
      20838692384005825835959734210506718428443540957544929066941550833051093000166,
      8282357714606447781782716442854085217089572080066047419459610560432999443766,
      5410651444876169088887579490283094453001167796545260026969919887357676973543,
      15276966646285075387317940436655285872037988805762800567413073418506412856419,
      15066911464727337689573664613158712498015597773345106524271610486257089622849,
      14583790985054968382519116885383608902981814292128186470697458065499359610203,
      12059090796146479535492139954279038037217093044815277624197659219529427760034,
      7273811886044732271171500579064359282424476926867187108258957006777685922641,
      1463086899665237074608503061872751147444637332808872866814340325832200880984,
      4403177494620214359779479537027014449448686844655371530169401219256448130398,
      10860968418848589590932601250051274256181778387706764281989724391784015147562,
      5268786978207139542368199165627108325282167169564314266747401266496556301775,
      10683355823176907476704511935094343405052640940909677712096702771871787224727,
      12998090263935761477316698114799901126086030852595294916463464609721875730852,
      21401280461419124637791689956622923839426783908187419462727763377498739154778,
      9827224472048063173905906705579289843819400982583185823840008976971109664519,
      6215804144039763858354471461864183189301201862376216122255322421321775987311,
      15461308489200344015891625455653488930440613755785081602434124530381300882814,
      19336334695450889400681207491394600659946256404722006637851709906131899294790,
      1712331165786355540802697725399423752392267480553199895882357858951999960061,
      18153038525983970702748717571053178456148003321236490384959117581005013333018,
      1080183517033034908031748897211289245459330899463186432840251241943892326023,
      8948022108193679628295152361559653763100984324221629445749311939820327674857,
      9553342289560502306921915013446606435600388298465288181461633559299564421155,
      12714965617376828547637017050548818007690047452402682720666099310241001848988,
      10945704657865102635748104464461970844653553427083981539165832149959193156197,
      17511714411688352203059545713591160825310809755917403629838415797949261359373,
      9253691969419856285051096287845246422848295397226841130282244592511676512433,
      12218945350859454581754463621617733341764245716874083264842931063272433793037,
      15268139709971695434346690496076067658968455677120655340969837725391575270485,
      7948825129295102283421620705853168119104356217418364837218892682579042520651,
      6887299291348589691868712194070626390224806410428583073294593431810559288717,
      3610235157455454109573625364057240708256027358184031380521552355839155549623,
      16532488069063334064099666525339953823111673083177894678898823509406678724969,
      19317517725107761280217103201908049748015068578935276576200982249386084367574,
      14980901224290526859762385599553818204548992110637275324411078408232697158492,
      7741797285700915051013289492475875831764653137095445146268474269974647962596,
      11964233864746181868467810392101989052496076326472717372132104394243614334823,
      12746657111181947224582102380049766839578185276220682311596480990298620200286,
      6408726946032901840418309506578019708113712492100046332894630652186614300568,
      20959261828945984489015610988397031913577918654575078054490013338416801523934,
      3173674599420546165852740604987014294355430358334465189504551707066179193914,
      16110281513253204315524614633789708146700074483476149119440509845258215816735,
      17135377580103690088853370572199271964414896742342749305424508776150797285064,
      1405769920008485935711505753346340073052795087429311991287498566024570212365,
      19088073362945853867763169651582894739272002359692597239222895238839593467749,
      19897231284455588615416169252449008151349728648961637517447194842672488184146,
      20476415629812014715153863754869742189693986277342067785614833846523246536739,
      11074321446706734150375041020583051611133090415774365192315805856051215270782,
      15231367549323128694183572409135806408519505225209496441892541205465727777072,
      10515952069292929457050921929301902464262874744159361114100398880194109971971,
      3216370118771824418364829250073852356774095079734089790620447714552849459645,
      1940445924652458480775282556203659335417827058983719042726494187979000691704,
      7899310668555694144370607061960060230071621529123669746309839400642332452086,
      3125410912833939638823760577011271607678545358020637189655641109813198731542,
      2980079409624774815878860133121670095839651294537928173829312563570356348730,
      3766498515736372882285796238406751547889526137955288498682767455795237989580,
      21751217522789414135074956130080241003845828660310903627224390345319859795839,
      4947229586642010378772262640583556676497656670779800090478805824039760706318,
      2168676839236948809859825591626629233985269801981092020040909992251312517552,
      21172906642114648036685108008020762271569381607092920279879047961076646303327,
      882675742500939602754673078407141697482716600335919344527751158504426951699,
      20942968937722199705624825492102184647835614761458159157410261242387423597787,
      21880640497503102067412608072166388563991106464538369680846671301780353850077,
      17593472026567804917122179982860735087124786197105685847979050530954084564297,
      4492875530722152383516030266828166766820778742874238188105265500984280376666,
      6799763500412433367637987497601148507907071065930142757525839585946238894092,
      7812331664758167657763399273963290017340604299019483750344476103319142702775,
      2222332747647756867926707541092465789402467819000336747029352557749400316077,
      20438798382149666667185974604464532451975024544676922060351031604444896151494,
      16155157103796724378615022758633778903205872772589663310774455593497441785913,
      20281325298063880945091623185126257485818350714264176365501683813650871716911,
      4922178080989486450454493110764936742315495846015561426329316977670113220071,
      19579063976700768282784922967523980346960151903154507737857728349662090787824,
      2458828873355000645851832396764221987760639423132968569631493912353159373462,
      21166618206785010755521994106737991950548963896649678270059527421944129497211,
      9131643699583013708059191290958290089892787165715294157378879201986981390031,
      1820371114511473946932363841206094088983972935646887524223011276305844153307,
      7264184404232663540867032945940974372967974872966180860960243405462016972362,
      11228656105550475045610757902396386402555430893045183008968975441800824215261,
      7151503559113638565935009743218857812859208253653498318591469659718664783964,
      16876040581364499037941813142092448836399042253618385783944016186340703846779,
      10334125383426918152464737478646460879481305348617711177774418125714273980769,
      18900559046103390399749767994653107625464807708680067464279674225251110804100,
      18685667289312169245526749652972366835289568864080726348092618145885982989561,
      19970582871354083670567197978171723431124602481748785146813441774826500485907,
      15873472427137024971035326229485784626398898771525077832924901475242073457867,
      9090803292122260583635467396769157643561973206888822931647063181944243467413,
      10156295009710074552070572489422360071526675259143523597882131082376797944708,
      18600630374968456966046654667577076758720435487386724419578803020365834014000,
      21292291483064245088298314957584631356250347533568992016547598449487977536460,
      2784266893057214755054197979675795184619614089277590464548240934105557638370,
      21206743389683892419024645604723431382001453245850423743581664552645211926469,
      7915761821775326316473924816837591351530533394717381318596295803119061411675,
      21881095237485064870468603451853549262304643738646051878343976465227744077912,
      2011784725603622472271597952122938645154942022107573948889667939904597454410,
      21059869383015715705096974077910228193608826877524913363323189378554601804559,
      13660545486380051482020817701263881806531607595506890631732662177505270213284,
      10831091042775967380899180760062457635694790868286967266013231823406639854653,
      149288128407476550494800886735600251983375852319258454101603889073198917321,
      4032475033542195421623899365282946172767274020529645277615759958662043553317,
      17860535012887415629230166789742533149365132198763199254812432302158542514395,
      611194463774512114860065022851497908950074400927073001695280142990812150583,
      5518364261187313845085346561539515049557757056751872639492957432879259341390,
      783263978868449790737487156609432867806742277074765259237378374864740012575,
      19059339826992310300213673274315612374137067865428300882729551175173242291657,
      3179709304184015397125565132235783368222831063701934511986753856772139349894,
      10954198701843076039176000728742415722273043852061382139560487789741501275316,
      16411266672500930935370066093245284646483148609897099268661795671514664627451,
      14614816948231085620934132277599546641612327229810158468490195811014141518325,
      2458257206135880430320027516329707989817636936777744813891328347210486074414,
      13549483340434455515002570470395006683062583844603627042649952800864870013910,
      14465927800403373425828183741641078057513049263889255157342086762479739044711,
      4039391352709218793104596256671892882216573882631238721514928981154171136548,
      12750457082077152291009387792121930725761848879916565703854704756389714536037,
      20703941646953337308096638741387402857948436803334980867971163138332859477843,
      20148755487317949638981041809982361196106823990400472213765926589941031736503,
      19035096428824471222963574043396024781574056587456391309795571372815435282399,
      13597108420431213178364236660710194375344287228654817880431599113069659963625,
      16737817219786305757887002253067607822378794077688837656791543060369162185533,
      5164935079689729145670846016031605160169301936105766707946436049006171651941,
      21653381930704765824477248798502813954284378782353810890869232482999795586793,
      2062605478140760101860087118379474541965619844748678233207247884294051836812,
      6841505950265078437298089354417829781031272459823272323626556598403583002674,
      18723551101558427097952125661588457059960574026361073828482106612260297969553,
      7898804490983679270754258611113569895515918945891808074921872907759024464249,
      10882278698112390755842292529204069263813359338030917602809789513528936860051,
      19447560013395173052961224723195565400117958329259001072560983848146677205053,
      6251288025262210726686494480483550276704856797649458538460443509657307219922,
      13176666617050786358406074057104742181338809005466316548399895981897535342946,
      20703225796049910173111490454489910459787604528779911406172217267261190895618,
      20336720518722954780604743873837334696992422089627753769439653667292899832714,
      21420427865372074512365684526694872695798980614525900481233709853915806389425,
      2498895690812694987926199054702295457557454143930759961192198950277119149872,
      18753512301709603592612141197073246313430368834576850495154922324845448997662,
      13229612292359498096055458608547157785066962647476451239567069089111704445000,
      2690879919643532184588441383789963956137193400890598777054187145581183393168,
      14142396602342548413722428497204107502988046500369932366351553161157672540408,
      20448725195660080278132534867269279218381543910636641344871383714386318629041,
      2559459540570011016181396098001618067535109329950570139376049832813577592045,
      2209294835847631004298393339896770055851570184195462947318472391473531519454,
      14610669112573509857774678749257346364319969641690596877040685661582231189775,
      15281088465087253563674405311018738676067395725444151577815750152538449780965,
      8600553033773805414817363397077178137667131851961144771667772828459236208319,
      2748346039979601666392027583251905158817539034260921486084376270967628661657,
      6854960712378511006304629447898292218014632388505703802374806527561178043857,
      20207552563190343462280438839438087615024485494479390954719687107061991587248,
      10281541252271366635718295778088948309847900730867531177275273130071062184625,
      18855605847424121529776135453072696981767402526737712879984848146282568841809,
      4160214035780913418097601322951078913381556877408879904436917334405689553255,
      2122867135885631508183413043949777333811557914428796322029495785048111325437,
      18793959580906171893053069386015945646795465354959679615181136313144978078417,
      1043591673717355695648236328597936528752358227297053230241551190351813693314,
      15686469257015275311444450012704351019335987785561570672026138336552980987277,
      14048856209379833670666148034655599475317994357805584661156301746235313941815,
      1011563953969880478397969933799483261900428580241502003261587014788238280391,
      19240556623066672446907714818724971233422104071815927265423017590508305430997,
      2121904286573815063480388650799381683473766736407678915747169455786741101182,
      6724437969134367395210139771738563153857495313330774537559578422672993498270,
      20206855573383441961836932177838081339503382415601366823182724056749038447809,
      3659051978213562322887447057085386386485486575515693147713900345497451171308,
      21246119528547168535908718411570119652856799993958321864163737649108920924448,
      10446114322905404392321651684574668727564081327779662579984472408056125404335,
      10052242287865403393859620372179811039720807230902452334457123873762222543944,
      6373462744579965543231173757071025010089494620309953425653057223643612177083,
      11716070974813426833631730493593924834405915845847679294742728105127112594434,
      6451284530793440411577197006976867289209413848762574411101073727224316913966,
      20143217291446069633369261481904349401356557325260758866598205109039367201468,
      7741896897172494958877302103827661518814930985518070029789560123401964418102,
      7414486245715284930410091802521351113719159777210731898112598211035848096490,
      6480506916211642204624111742530825907262535747743645014149694168805302825019,
      18349725066341807634895742572304899830893334427067633858521634672944685466440,
      1838291082333887710851505844271184097051704051003105078056248035350245616867,
      19201915197596065583046168024521824662441686729039260890206806469763190071269,
      11253788423541320580105520117231178489492440242200599071301755928628199128159,
      6048832714406694444296771635481934823208451249770515560893368035838759154821,
      6398008918881249487422929614611145638894557821587972164243877575640548705346,
      7013037564266297435879776776659289982125632651326438965546874242685502904730,
      5942504790082366811245813670914617310604940200824079289270465669331434165301,
      14344789199380317440464969138686896230070901882253997360605407637865754361287,
      19920212380356573378521292048728904573841049083972983190424200459025557666792,
      8983390577894750782268266038315113359711163721228398686939390484499979421166,
      14953991148867572055684497824790735528852361750007063016470842397064705671772,
      5592033578501586280289038012647352732276003389059749788953239057845882297561,
      14076883072716069263619564306953450824526010844333044566762059693672378725675,
      11108270411921226463443318601950168860230077781212396032908932369105145901793,
      3681277588815101350213324449908372578846563884174807724121308021640034446476,
      7194753190480156904207319938161903897566477363779122267985209483435838216959,
      21241255448366937244332942306324590869759761073985963892514045368815880517382,
      6203071960722514588958553813186803009742459823360660333787981951206442471249,
      19041823565851118046937769551785013706136778514067168239416647071096062639366,
      4928136619692555022185087228378238193895894009623071873887735418398682287593,
      16266329364886004534411977872528706660422476743809029518681886596981922182359,
      8814684891729998059175829142248330760704444206534875755023421115211106199303,
      11072277000652722690981202459933101924925520292174200155471966778637063588914,
      15889576313969861857250394875354819627977602318110620311480656842740292435237,
      6934515229262494305594741689326968268143898236690173897991110238064230886755,
      16212991575388366798683594066983659236103186124339324856776288894513503543244,
      21100508914867482363389012032457112622475533432309937238082785660233880354422,
      10381104469089401657446748653199843213201270332853172509558263968565255702795,
      8849389605935865968361613766905708889092097013638425059146677490704442276611,
      4826404934194100291623537890117339503344940312401101713754206109744511979962,
      9981819567268652304810465083896863711149056310505889216307212434682251812603,
      16218484218588441290424553684558267080330286201433140852298971691458926313766,
      21317661296916247018967238829275056855142711494630067664736600708605437812892,
      19523923008662567951910986132173659591346561824926093935331274289896011695634,
      21439241836891927940168832009944210084078628922824257988298290967895179737163,
      3818036890597976956138669961319975835941979944306305168232209375279960168960,
      10212547715001519604442389033695156945619060410131175896383181616280631586732,
      956283172524544133830416114111944076629240232397666924807554743752464221045,
      8545109273807246425343308224167362024331960554428088718932211551700420545275,
      5647769597708100114837534314408246331518385631750569421373379085922684908872,
      21776221280695269311212391423788179027868152904973644113087833004348746215729,
      15989020831232836203074762591626149244364214836699154611339161287030952623233,
      9384665943619921791886218744024370375464874104981653298499433530463000935024,
      15469006121097295841026542766455781293432005131673839148320165243166330403027,
      16103671377537767724271717097892044266704736999841135349844319906338275108222,
      842367229428650719054831004741080336526228967970570607897528985803108607790,
      8752325400224955775788313769797750158375262384121380328719514077259567119347,
      4803861091350023344885030428100876947830986453029412601567992550504530969575,
      7917553047944370948250445233027936387189889293110390303835890604428798853681,
      16378323148632546424902611135263436821435778030958161546757828745002247975096,
      19873719885630097137106352132870659633926425645300622070145979694717581586592,
      20324790419158243246762098227260178678767896786893299456278167341205663612964,
      4358908354524026935988729716331497263147669784003421920394531784876541301801,
      14403952632095852077754539203207047943619815438482171213105824864831554185165,
      16410713482142323347391147127545553384558868490870150984280601225023662513809,
      7304216341846662695189617252648753140769311862815448449926830269690397729157,
      16792943782280077475956215580025612636120139194657275471595325031090407485768,
      18494329391227402645175320826355306995912366111176422593669423022411884295357,
      3277597348237827068690736756050060740435013727549848360800059544123155276133,
      9396765756719511114743964794180256605700037182617127755220919249774110852382,
      5637053961584389263881381098869862042993858662768294676971865632259649027245,
      1752142832257643043564515360000718468888861086573246457619082905919623770956,
      14504506574384680785750882507533398260948836347427103366421836731538357314790,
      18947994518078004413210940685748534988014581551965984303066903086446389273117,
      8931855168578615387850254663107425567403115805663142600825724478150698936342,
      10982092525200624040399870568387498905840578524691489797530932831401946309626,
      4738907023206802373255186532236849256768509848242049657234258536668430260775,
      10888145285628319545262252531874405309329869513560101920454793431198094714989,
      4767721624212785367044047554655794533816937807005608600525762243335180089923,
      4054394679973840378112083329204220302222586590732553688297938891619998137578,
      15390471663419625573793381445844013245022413344196724396864223784781333233143,
      690498740448849288977645176879593806019080276382495160049117613302192708860,
      3326968907274045758110436838010900592335267522219473049427145975873344598768,
      19461545874830130561487975864151403334363998126023624462211037468138940028328,
      2255249425919459031033123095731665691066980364231819200773725596456576056043,
      17139538647342063569964264947811360956712827863014723985947727876623459280539,
      262834317961189780923232082352297808796511874872711860311746704570027370416,
      17784213646586812350819691264737755884800773322574478474130308351003659945289,
      9206479615073686723914227166450906925650471865894639492301222855979337534393,
      5955379232184076713510750681781395826148323482009739159408415185190732125682,
      16345512244217240951729073298135981012471478596479891072149124888060645303490,
      20053701095030547796310908765544502773063879272854547881438596069907281565287,
      11519146559536679602608982593432194283609736022486509747046459824035493513614,
      10868663839942247532249591973192159672852196011910414460124452013501564199585,
      12668355291693420029179738224611760713369106517542315102687346083105601320689,
      4091011252347209563858280520339886760216002486858313383741839652119084430270,
      11416347683590132388448480763970462739172261435271326798646502987745949753371,
      4462763980178675172541782335457125059884067698347130082276003539434128058577,
      21728891122467658477520865529973242372850367356840114983386033432316519759391,
      9556106604731806817435679463077765288658189491612307664294729425381901530224,
      5086982973132652080709554654284904229374030594786774699435814748257879554118,
      2278505454992311041650060186856758463754878439802195559533882189615578260695,
      16123495070352975934848591912315341924608875638550779884194576881433498909405,
      13177225503435100563531015597038445430211235761527278782674200718068329833622,
      11626932451843299545922103072142674578946680165802341368625957942237790110177,
      8872973246419344365802198448930136062421718851114220299577394844231810068090,
      11920016786052130191738519934437207519332291620474831138559948859328822621221,
      2773753221970604083383541092979093729869734021029185810064937974430862835870,
      1194583082499114147792330367943150006952486615245506995832323057119894886077,
      15293312601348482070373672684782686300692505365845870624263228679370968807837,
      2292156760291800990693425534213440357167359161992251338587906324724034592198,
      20920049766730284147153707151387304988393631464951398563908410768221002588086,
      3587899345078220957148828249287269521408604837648269936718299413697642586126,
      5857527906708110948691023855516662527925762284342493618496858248142623857037,
      18312267494676788897591109008609888960798722042916784593521762607767538629817,
      18354455618287562133438807735729369657256664914390381320892039403006410339493,
      18594037435499535688023807489676900345345731643180370940972090155512943637000,
      6361231157299815359812386352981667048590510979947935475914610076041390336883,
      6503045850716008738909204934356093641022474278658078426701342798380459107813,
      15826908470360778431798326530563200301151807861414464213699967513881040969457,
      913167165738148713876672473302437265273760468892350716109373788573860454641,
      5163418960719047707254162004625467116036830361107107814320243058319914687515,
      1852750695670141634014249062360862036043602867770163972096325792863710036947,
      16164029969996795952250343426848596535809001568622155377829217918121790073916,
      42291476149937488089591434144089904529405222471677684973768504172369443350,
      1329340386229357940610579826659090359930768580941108555938139535621252899508,
      14087936453397725507000489457270864434699508074557952952329368237400407748133,
      11454917885298514922755456675259734718428103879515668717779418480236210705323,
      17749966508430836878443008025013283275306943216523661550528505419303121693213,
      16617298839486771009961431205770630163409905047728421465641369616889696635464,
      5622873871440608391107520706189063847917690892897751818294742462879871297589,
      13537715561706278379083684257583804567523085149672090320983273122424669242274,
      12609629910090871112615676094781247031353826207267723991911250780907380059468,
      11881347692420971451998583525696964339513193164613288356598017302547676912004,
      3620434358220496198439193226313617496907852030586214671337652678218740406153,
      16586456872124455799862826347901525401871594428044067424833235946565396779382,
      19602593015746956165116919928045364895525104709835703557292833702385934632182,
      2465427491077301663150648330772125184470808854603184374760649420983178107738,
      12521323976712195518272978277895155774288446093713549157148428964880747896725,
      361951232333654306694462853852464888974834703718677826403016226307188397185,
      20048343816024297162848487251896481827914904696805156112188099141327595641104,
      997638030405613623344188782838773314122493364653596616029491564227193697621,
      10932007654988104622042938184134556963651043067553327861790671211490960094259,
      47171599193060570819891696279547021610376047998583333086685382152080932821,
      14669115378939104862697280661831896914139331878760241858539421915983017116504,
      17868874372855679948405169936193924176514630305572838555185339642210810710203,
      10178296575837129106771098084407669500326673901243393867574658658064222502028,
      11497182727976130924559852428316615034304736115488257034951588831868596612725,
      18847036158089242140209840241495282890278502700082131513222116906134183113862,
      15514518995390761662346743876733004358408187550386554449789531199638765348953,
      11474102901522012346251529527050392650125347221410246734211005177721289856415,
      6612195415835443084676700243243174090072629504450965229103970796390091290688,
      11572474094368358234669561324969692616275099241307798860733942350364532366113,
      3855324911963410548772360326122995145790506408472649961229511965629894550308,
      8802640003128749594245736338745752744580147773009816234644244502373660889677,
      15676839305513015047736600040932186843826469281853634239081282896349443894145,
      11124722103091011602185413968164672678635980457394627450785290630813993266691,
      15087674670944618980358596427703842917302233637812357643695687556421910213028,
      457555060782651847600218200815104907046227486293278645126081160142069992497,
      5340353060455057701755599760342180989590806327490432497082435572367648024359,
      3289809733259936118731355294329652879189400852472418229718273887860572748363,
      1821386174933044868215348232606758690922944887434531299978498726875279584854,
      17399236630582894158137572250502674699298844870791766041927951699287421557453,
      16772722824042046255416248879357647708113647471330900665176012648038469814744,
      331374066696126093678097185404981758791664151917354547180452342655690460271,
      5482079579065945934120471179616600325379965440378196448353560421120276746028,
      11861638874356162254375133266687016527365630872709665703116365332534843803431,
      19751278476934230895840638614095718373810690662562196455711240141902305648888,
      21017623330912840225230534280017695045717261514215145256795880310933667407841,
      9692530233397639077769939390011937602190121885296235066426091743618448584134,
      7914031992737639503490179289412369887137436318696390718781298556229610513180,
      5046304088054212585035723354298412694927209198400753780585596829596665931980,
      12735457541003664856181534137486291132119134214862779086936585300598349629287,
      8144204472889944485922664106370529127382213990656088602566223875490414163362,
      5526161442679804982165840590640681348630369336752481706044759543203459722566,
      4665464612431440885211271075488840033628676516298384234452346107374012633528,
      8451965709652752887539585363308640999657377914501438391781526068371105983117,
      18990458193856163728406448194111866469438835810342179114684453609893347662421,
      14602960690767985987882800342208585041637986661619503513589079723840776294824,
      294650277854196485752526848096008214721988745350555311479128101695333774927,
      9930361494944692931597991649915857642608730961125454734483697613693272941776,
      17972565769620820679641368732920396905240248490243886868922250461473059009007,
      11842743032528966560856860268344505094861546674985872961254820091273444880060,
      2260251491209762630871337015316066081541066308706934094017641769176593121838,
      21336986809148977544823484666876006147697590184356254785752148187171367963063,
      15637234083283356311249527335446193685599985235080555266374006156231977517227,
      7637477891046186378249227336975234440873859617986704147458186423096226771577,
      10435340982947407847927678888878882924793449778165415690957335683641419176012,
      21071574044063633264442120715854514033847137356154103023224485568597330648075,
      20085745552872944745120547909310789275453780111307008151203836541147270866122,
      2369255222739182549768488367357061329939116877812397072967912842660453854658,
      3320710154094663715463854219978294133429318041799642537800174050047893035878,
      2437552820481788519744888712380245016748276158860265401041560980354471184914,
      6687580113987208531705167517979176727449238324356562435678492283111952291541,
      13835828959457330678345759960614663723017667326485961761361157914420441377430,
      1823843951353887792473925888956554516299304358703549730900495356152013614424,
      18229384804985230011714562427207966412342158903455811854157839446374012856695,
      4983049472282717134994110428470567601005310848076496400503178535459679438524,
      2047051967230753763135778305592853785901616983565528680886843131244871631064,
      17059505494771925862841990046823342770591010831955480339095397897088168520686,
      5845823714127413134610517798305104245114036685335948729450609519089263487144,
      19810252752845594230307894817800427820113926573704856490871938876757561680148,
      20741340243371419379519807725035036726040739024854919427690724405113594586449,
      17305746835229988220561638584011917989169628535378748397361130724475478785704,
      16273970657972145440112726408308019138099820274904080726219726815138597785735,
      4927605725478881247988642936459897069651251926499343645614635597380235002430,
      4076655226193629464789557616268492785057128805549395585385432329518368497686,
      18134767316186963456589895259454813585756254459227058992203617493951135964914,
      20798436806114056077588608064161229365173163847083955162560624566238528904361,
      8811900287453512972593412116532745098600991077158875340182906101108258578231,
      1611466530857794066271650650204918615746591649578992581483080164777650137733,
      19520757346022691586967284723955378385034675472244175822936613026597514818901,
      8258287931139503595713718829279050060190693609290797346704848518381891359704,
      13807143439443425137076128013998009581746894329904809421858222329599144124143,
      2034200548964915935625429760202284220693125881760822084201315022529206424506,
      20594375914400911567795140472107624446159181622166676420027082349633992663301,
      17773828019575037451999782968066986504577459910353828196403976545023426528432,
      10645884969014005687699860915213473815514464399964009808411811895545112650817,
      3135829883501342672772973577699379927756997243617424917654928164800203666496,
      21807676600134151299257078976418813484444183016737321278512745883771478511369,
      14168063038909284721702678019083222059818438340503980617872573468231611140141,
      19022539506931505257153342575586362988716958060936788031721967221986624233067,
      919797128086310623571009200546035983274688764270933413427846490906074137487,
      10651353481391913627770814216074873532920753703051075188645774021198634943682,
      21601553598752750925049978818528421110707879819831249175157596816870100048288,
      9544964974935674319204796617933096476421551193682156030394816088243121582636,
      17113833205578964054057051521784698139661258340576694677296240312431808476286,
      9889647672195559279745677506312894570402108521106900082889976819798270827735,
      16028191999932520938901585234936954312994452706490572504997534210876573833649,
      19224701772787524647172128751148104366752057774529591812815327738829591289117,
      8065294760892477625290114823800398061529770004833832691347498933238361039736,
      8385011404987806129246014860479833290406969218526611328586242951296814426438,
      17626526623257098006524211054563886193098683828265081734658432468695686509315,
      9760584950604786147191288118087660976225563461953070125437519145090832114537,
      3282956645059793949082172795607530130101621492305193365378997603911833418463,
      3788543541342252822847978185963388795825378340921321139695221828685330606335,
      5728277403393912877393143174229934529937061751983246730506397742038949251701,
      20532577038632159357383817240596922896191478140446876998140515404169184846609,
      6138500779693128517529525961343097735306947649093633133232282430353593175172,
      16387038830089541476468870208162294639575042754761542956218362331966004300870,
      10184264376398708852688445921404363179240954227345322711923845040842165453208,
      12576299651793170522912156101640799825541149618303513174146382191633847258859,
      1340015400080181141720946234858756484323564628916867888877667239334982793481,
      733959369856163480135680991009606990817015555938726628110611986599242143578,
      11467033813562140192244869512537566463715027496952375979909160849747976831918,
      4619667645046391146577435774790188488541561222783010406420406869960248783331,
      58552761198135931030902257754896948615688045302818928845814661296914920622,
      1199849881730507352706524556330002080538296688430736582840314007371442152147,
      7124502590511184113044595527748024819132713282667933641439666531514739645089,
      8623660134669459112474551498616256867375253975034970808437732784494772311361,
      12655669439191191182341423414424342421477486764113555800095493091893820045534,
      18432703875775002490514477493898870315422995231506677048275960580528644904682,
      15467220287938881354678249472400749704814316816035426814619089032223454845193,
      2851120240492392321044027263769720216640877441121430445737594074121655318176,
      20519914249934881206828098454303256358482675671718589102535780334267934987941,
      17275124961392392047135728713829752470490098022504524438869454049765356211723,
      3323710067527231515807603961736782048796606296990840839366613937968342331886,
      4468708240622802562056471128793253296493002925988003094771284205007772045098,
      9006494818135081033869830730030943407240565201693254355620348420258773924028,
      2624130417875598753127999576825019766166727976335690685433712946223008520912,
      164131399455376615654870570697119442360078693174350746600132391198500093412,
      14931668887432843139264972187415200544679230597820424081936926034478502874299,
      1638753880783574431267395352024193675000113296497173968722590753809640941864,
      15505380865926802396097545843811910443367233632805651511272732002583232431557,
      17973744614207669251901495093091561913998272050499760575282030108740677066624,
      6137688223696761009295745609563284204827706564566466060484103844265403078408,
      14774243062532823236792831566222119634320864630838624098798648826842418775856,
      15864970393171078370207775103899428499600152663946379517190945807315353544891,
      19010063123357565300336230971672519561204810737546730911549311353159512986740,
      12607162829921425080830052984475623157169603642577010527391007035133383807243,
      17803108634879437217723652777640120469990779759700458421844361066182881628345,
      10065874953507223318296028499872542865030107611981933577973812883589535269142,
      3276471432535144390388324850641020151392959100393035635141206272558418581928,
      7532054601401798035926415744768772852833516520318445183340725930886329458991,
      18893822928119227829016544343228228897166113682019317256005502643243867377334,
      15940597493253236451533839310728876441657428995464658827726295547815292644378,
      4268009387843764409267791203070919313017052533005657826253994943184768120896,
      21611251949238422413354051947529388972078300717392131751061464498329326474580,
      12516447001729804412674006874184731098280474050775388553768469608793631490618,
      49838549447142926741568525697026885045023997277705726329780325103507790978,
      19763902910323896567698991616245963026306943100978479625077573937114135803058,
      12029297973430627253212633299020402005457460023136429653800185001711727387314,
      17676997725594777991384952086633589048516371093397126876621255518370680168503,
      10567543371894667303450346380722020266352683222046730266924342174164712049360,
      14583364850544999818712646438016435003942847076919084667364987497592599663937,
      17348091487238815837308569582101875357715798351834275089190053280855958465528,
      8743083090296259283603789316855921930102444739264013461469099560398359267240,
      15114064505647935792598848256320570567717917317803629185764147361301698519005,
      18332675991829764561879941291908436508530604635608341316693114747813051532006,
      1757567731797951053080580099911774643896363235228742197150882457231133285549,
      6526388717947413328592956348507481629843816325885832861915399601868279124246
    ]
  ]

POSEIDON_M = [
    [
      [
        2910766817845651019878574839501801340070030115151021261302834310722729507541,
        19727366863391167538122140361473584127147630672623100827934084310230022599144
      ],
      [
        5776684794125549462448597414050232243778680302179439492664047328281728356345,
        8348174920934122550483593999453880006756108121341067172388445916328941978568
      ]
    ],
    [
      [
        7511745149465107256748700652201246547602992235352608707588321460060273774987,
        10370080108974718697676803824769673834027675643658433702224577712625900127200,
        19705173408229649878903981084052839426532978878058043055305024233888854471533,
      ],
      [
        18732019378264290557468133440468564866454307626475683536618613112504878618481,
        20870176810702568768751421378473869562658540583882454726129544628203806653987,
        7266061498423634438633389053804536045105766754026813321943009179476902321146
      ],
      [
        9131299761947733513298312097611845208338517739621853568979632113419485819303,
        10595341252162738537912664445405114076324478519622938027420701542910180337937,
        11597556804922396090267472882856054602429588299176362916247939723151043581408
      ]
    ],
    [
      [
        16023668707004248971294664614290028914393192768609916554276071736843535714477,
        17849615858846139011678879517964683507928512741474025695659909954675835121177,
        1013663139540921998616312712475594638459213772728467613870351821911056489570,
        13211800058103802189838759488224684841774731021206389709687693993627918500545
      ],
      [
        19204974983793400699898444372535256207646557857575315905278218870961389967884,
        3722304780857845144568029505892077496425786544014166938942516810831732569870,
        11920634922168932145084219049241528148129057802067880076377897257847125830511,
        6085682566123812000257211683010755099394491689511511633947011263229442977967
      ],
      [
        14672613178263529785795301930884172260797190868602674472542654261498546023746,
        20850178060552184587113773087797340350525370429749200838012809627359404457643,
        7082289538076771741936674361200789891432311337766695368327626572220036527624,
        1787876543469562003404632310460227730887431311758627706450615128255538398187
      ],
      [
        21407770160218607278833379114951608489910182969042472165261557405353704846967,
        16058955581309173858487265533260133430557379878452348481750737813742488209262,
        593311177550138061601452020934455734040559402531605836278498327468203888086,
        341662423637860635938968460722645910313598807845686354625820505885069260074
      ]
    ],
    [
      [
        16789463359527776692258765063233607350971630674230623383979223533600140787105,
        17179611066821656668705197789232102741366879862607190942874777813024566441829,
        18653277315487164762584377009009109585010878033606596417396490909822722930739,
        7373070639853668650581790286343199505413793790160702463077019294817051722180,
        4823864393442908763804841692709014014130031798360007432734996408628916373879
      ],
      [
        19196309854577132760746782449135315310664418272926255500908899397538686486585,
        18123132816088485879885148351452823314623055244145916622592591084094232513914,
        18436594886553181913092702411547018228276047601279727265790147051821171174455,
        15167500404313194506503404655898040457721633218143681920692711693000769735187,
        9437986152015460505719924283993842205604222075968464846270136901243896809793
      ],
      [
        21445376105821232747280055223032050399373725161014449207033808524504027971613,
        49684738714301073369749035791061182456037935161360748355432247732088942674,
        9826409059947591908303145327284336313371973037536805760095514429930589897515,
        8494798325496773219358794086647759478982958403252584257436898618394561204124,
        21251937175072447337747316555423152807036003235223125066270735279039060889959
      ],
      [
        5539100337780919206842837176908516952801756637410959104376645017856664270896,
        6297628909516159190915174165284309160976659474973668336571577778869958189934,
        12792263637464508665199868777503118105486490400267592501708855807938962470650,
        17254685306085558791725544672172906900581495686070720065168939143671412445514,
        3590396502942934679818900672232030233017710909687947858184099000783280809247
      ],
      [
        19055249881366445073616526879263250763682650596233071589085239500077496415637,
        7367697936402141224946246030743627391716576575953707640061577218995381577033,
        1322791522030759131093883057746095061798181102708855007233180025036972924046,
        20456741074925985565499300081580917471340328842103779922028754640077047587707,
        9059147312071680695674575245237100802111605600478121517359780850134328696420
      ]
    ],
    [
      [
        8266021233794274332054729525918686051968756165685671155584565440479247355160,
        7947823415909040438587565055355894256799314737783432792935458921778371169026,
        16508811191852041977017821887204137955816331040385276110261643892701458724933,
        1804800467126006102677564831888710635194614232739335985819349312754063580223,
        11189892034806587650995829160516587240879881493093022855087765921356611070470,
        20567450145123179140729389574352706949280207113956641415022972885523439610844
      ],
      [
        4666756311257455192796774305229624459258864488677689058174087310651786875914,
        11389253665835451896363091846189307652796786468610595637047377864063404843117,
        18793736599347263150867965517898541872137378991464725717839931503944801692688,
        4206344588923325482680116848820594823631536459347642329098796888497153867720,
        1739462481670645248707834504605096139894257554120906850613041004917967456145,
        18514227342636266640333254638454588508118462110178719555586534011641424431745
      ],
      [
        17887039315911403193186866703775654467672391491657957999455462537283842145802,
        2824959020572825365047639014537190268717891749361604043531643698340708119767,
        12521547103713919592301476538318318223836047611311454785951907894055964264287,
        8658146183671258251984364885894342376430874614261222570603159082682815800788,
        154390145585284450772861151318029820117470958184878116158462181541183085587,
        7593705166056392393963956710828665339496927193740869686529339432486182720653
      ],
      [
        5529559239163081088908568555890212324771345012509269613465629182165427812002,
        3729910453162885538930719732708124491456460687048972152311428493400220125686,
        11942815243552870715777415109008273807076911177089425348095503288499102855779,
        498938524453430895689241565973888863905147713935369405079343247530256066618,
        3976257517234324421403708035200810671331954932478384823208414346189926720724,
        723540703523219510043977323240437576248315561543814629392162302024056718473
      ],
      [
        13306548824219676333032339487546407241767961556934015003605485324283250885682,
        7970147269291664639740298762956131361316495463191268382513594527221399186752,
        20633313939958767604804835838065337107615699351647541991788258289962727735454,
        17162090859520817529294904484646695645841022315617926715432606252643123848792,
        9181379842957190051440498041153333325098774266789773971685141362947015398641,
        7051606617662816798224904133351061549832959857069896192072217769241273559278
      ],
      [
        16619522548478824222688310091434959542211899852679631815023615875678448806029,
        14965311177811968100298579672135357167599499478246106482433786066289128683961,
        9792733250919070275775594069208673385381167169182805600474820364274865306108,
        2069253833779081039049908513863485270550301879399727430830923273191877809560,
        15847298987712771667136245955631872888473964330474501593909263901393348546986,
        12244443532166430060291409356011430759892629145539185535677568234713942157668
      ],
    ],
    [
      [
        19332164824128329382868318451458022991369413618825711961282217322674570624669,
        12346323761995603285640868741615937712088302657627126374070962894016296466118,
        3913895681115272361294397190916803190924061797587910478563401817340941991811,
        7048322889096718105055545382948709082135086733564574465991576956878202831861,
        10375086910057323893637057154182902576957472442368661576421122036461645295833,
        12765622911241487148932810040772504127756393086809438933166282251044289864727,
        266900212758702307861826326591090138389415348463003233900705815890364224151
      ],
      [
        14435131616556129905356866638030823183270286404767286105643513738132789033353,
        5780976801287540146775934937953368730928109502001687434229528186520268917700,
        1618320442446662026869390273942730786145909339107736579759397243640902802126,
        3818399583522206096165108192531271582827953520684743806492664825009577810261,
        11764506724346386316602508039052965575734225646587104133777798242528580374987,
        2414215974836165993714858157462355581258152126063378817495129367240311967136,
        17609437036230923129211608175600293197801044251801590649435913902851695334081
      ],
      [
        363438080029711424794236047863047716381155074181485245036621530063262917196,
        535766679023716739184211613469394818313893958493710642899297971974381051070,
        5305068908469731303772738758164870877638068032868328180355958394150421214337,
        10807632568240507366657354568432178961148417327580695024415275247652313539292,
        15964415873358391713354948903242729080763777490509563223190335273158191600135,
        20700362719972015883260687302741075186857660623182772413609788566925949033885,
        10135127975676256977820296631533839366076919827597067890970660746228807376456
      ],
      [
        4251490167543116819728642817282216847143714366441358372252125244838181656331,
        7745587495915033527847242564710473705100826890903278244320948416581724663023,
        11741113129223221800185946819924457344647035336264986754437921049066977440806,
        11630296782890656599545188109639399768829653360050213193782325240600583381364,
        16861140446185941149398487176581839232380972247302922484807333229513905651035,
        365879246117123675211400356410703684399715291171114630107795112994207447819,
        21725607857580053522363567649763546934441685061337033780528788383243719579033
      ],
      [
        9222866548596464928765000608129177609426964853736257576074550520759533736918,
        10261578281201197531384003420612639018011405529775212563256392340336951230146,
        15644037447921591571869862919382888810859308861783088910843592577202362807673,
        12752004188139535619565478547449108772137477456363099481095747591698702436636,
        4205805109630387448825516813913983509046636797101589615147198457314360427718,
        21047095155106717901091873146599497621258071512562421967648909471775919992713,
        15624165295872926124160584750951090817255240214488120310950503163805737026315
      ],
      [
        15064589937731741958666763896598138037875460434244947486199623542160035749721,
        1801577872277160959016940766173040841160105238799805406938450020949902989173,
        2896766420608048344829901127120623317655260981420052771341833288256800199953,
        12828791469509204618898135640019714232831708508424682785876476343251730674999,
        21363471986981372923191391880511344708743312828234098289107697080824665183315,
        21372706354350795416381912271616633829725494570576895047490974943034914894898,
        16006531510217730955981102005088687858079561573088629102219485906666961331083
      ],
      [
        2389357602244845938251345005183369360523566673990464798041306722747500447645,
        15275955107196234672088664710679934029171843237458844492987233368659104714648,
        8038797517535218686870517662905230585331773059774130312418943649247287196930,
        17923922393436914864421862212181654800719733137689602673604754147078808030201,
        12890519745320143484176500044628647247549456778462652469313611980363507314914,
        8058516556024397257577081553178859094042894928866720408652077334516681924252,
        768425396034382182896247252731538808045254601036758108993106260984310129743
      ]
    ]
  ]

"""
def ark<N>(field[N] mut state, field[497] c, u32 it) -> field[N] {
    for u32 i in 0..N {
        state[i] = state[i] + c[it + i];
    }
    return state;
}
"""
def ark(state: list, c: list, it: int) -> list:
    global fieldsize
    N = len(state)

    for i in range(N):
        state[i] = (state[i] + c[it + i]) % fieldsize
    return state

"""
def sbox<N>(field[N] mut state, u32 f, u32 p, u32 r) -> field[N] {
    state[0] = state[0]**5;
    for u32 i in 1..N {
        state[i] = ((r < f/2) || (r >= f/2 + p)) ? state[i]**5 : state[i];
    }
    return state;
}
"""
def sbox(state: list, f: int, p: int, r: int) -> list:
    global fieldsize
    N = len(state)

    state[0] = pow(state[0], 5, fieldsize)
    for i in range(1, N):
        if (r < f//2) or (r >= f//2 + p):
          state[i] = pow(state[i], 5, fieldsize)
    return state

"""
def mix<N>(field[N] state, field[7][7] m) -> field[N] {
    field[N] mut out = [0; N];
    for u32 i in 0..N {
        field mut acc = 0;
        for u32 j in 0..N {
            acc = acc + (state[j] * m[i][j]);
        }
        out[i] = acc;
    }
    return out;
}
"""
def mix(state: list, m: int) -> list:
    global fieldsize
    N = len(state)
    
    out = [0 for _ in range(N)]
    for i in range(N):
        acc = 0
        for j in range(N):
            acc = (acc + (state[j] * m[i][j])) % fieldsize
        out[i] = acc
    return out


"""
def main<N>(field[N] inputs) -> field {
    assert(N > 0 && N <= 6); // max 6 inputs

    u32 t = N + 1;
    u32[8] rounds_p = [56, 57, 56, 60, 60, 63, 64, 63];

    u32 f = 8;
    u32 p = rounds_p[(t - 2)];

    field[497]  c = POSEIDON_C[t - 2];
    field[7][7] m = POSEIDON_M[t - 2];

    field[t] mut state = [0; t];
    for u32 i in 1..t {
        state[i] = inputs[i - 1];
    }

    for u32 r in 0..f+p {
        state = ark(state, c, r * t);
        state = sbox(state, f, p, r);
        state = mix(state, m);
    }

    return state[0];
}
"""

def poseidon(inputs: list) -> int:
    global fieldsize
    N = len(inputs)

    assert N > 0 and N <= 6, "min 0, max 6 inputs"

    t = N + 1
    rounds_p = [56, 57, 56, 60, 60, 63, 64, 63]

    f = 8
    p = rounds_p[t - 2]

    c = POSEIDON_C[t - 2]
    m = POSEIDON_M[t - 2]

    state = [0 for _ in range(t)]
    for i in range(1, t):
        state[i] = inputs[i - 1]
    
    for r in range(f + p):
        state = ark(state, c, r * t)
        state = sbox(state, f, p, r)
        state = mix(state, m)

    return state[0]


# Sanity tests
assert 7344690997738223295645154053021918994799603882408193002967283753145648589458 == poseidon([99])
assert 14744269619966411208579211824598458697587494354926760081771325075741142829156 == poseidon([0, 0])
assert 8599452571108419911675042369134657596129797276905188988960674134744449929238 == poseidon([0, 1, 2])
assert 18821383157269793795438455681495246036402687001665670618754263018637548127333 == poseidon([1, 2, 3, 4])
assert 6183221330272524995739186171720101788151706631170188140075976616310159254464 == poseidon([1, 2, 3, 4, 5])
assert 20400040500897583745843009878988256314335038853985262692600694741116813247201 == poseidon([1, 2, 3, 4, 5, 6])
assert not 7344690997738223295645154053021918994799603882408193002967283753145648589457 == poseidon([99])