ks = [1462227062794249126369859823370329795444295554631867449122519463903085153603985900680740216206168716423777588580245877886440288748604020630699018542826979566965387039050150069523167528973701117587082189067128448763762233651697690088165126309640643249893980922783446939093480513501423929380273397400708296781344423099729594996935151205635124630966978346265570102760841188859706856157965455490428917432012469015925570881840242441646984344205989934223312311722527845, 17436088264981004997841810232705191434707487036117316568031039310756229463817709762330626096875057666532776781413031682988478368320631200639484646124749334955850093397553177978996330881043557698983399584498223222105144624884205328876488334329130830465297477669138121963831402080876078357077714205039964108868193841782271495425644463200232523492344001660692840819160127541347575190224749912289543698786833926857916729347030739521501971908837887266088602825603179428932500122868635833564921115729380769315969449959847532694279060981180556955413680421245680949817931938812637093078177255366095925596232172597647804659446, 169559415577702492912881115171844374594897133030580223300760597578879930554761809414648409965790290108683744070236827542547112767931390381215817208191241194452401715396697138137182840759511035487717013487364495797652031544286820278750675326239062595892448739046788242584477837603604028584783800711126256213550041835365566067529075264741159242623075137208552904103323636912832758118607742414554050834861661347524996361121876885982545956793412777613516967651789645670837406737788560923095674100190720996844931263803247711890541497769408802573382496173181275896304033554412089516486158308042512557770316390458745235174270820619821158359708588836275104941171089532593072639298996037834372691067497283819036389853616602440038642702961597540965107104661813887585271108258467582, 353291124480685802122760873619558181197925748758526501461956322344713145481696018545548833112663130052221102526199589136442461136617134139228771440873303781403752812631064169836368616974931324935659661616432397250323791027357698736360780111349622044193849460721756463896782586060025792712427344165223388631274105033257953386232975622550466772244070538660725769821337872161112606157590652531598571409049763994992112562965984307203582687185746063109802744989804265169651236595150092278455325980064053498109201539606445526852506504951020231421164201055246981085535835484260199043182412639045612970769228962343363308833437852540654614315024696428638587640053405690902605225272716392141318356689485996722112797193445203157167283359129296847476836010747322296658815494204920904679373943240361056289263055689989853602794079068762252790541020355479732830748629340531275553956346072236216251442369981439899969148055895199797337493316, 15179303239962972288090709923258186951958171456436855682777477692171617505348532247047242658368307257431505429176030938743052282481669819891838891541215477308429612423006023438195430836574000543742809228546430000091179899316856488547218901706415026288318088205302049807334703045024896255849147262301854988225565498235577522563864689394270282449494777293613090615435735306391538191861818216934248371120219493426168505800995544058108910908179783162033445093246274431640068273309491502382851514221655427718436104350319852529981208352415296770552441024164515192550794244703092453886081781025084452892498434750021938722777929757172650087934502975720197724550995892550276217204632074271485875928952811717435969392225184804651569530492559664256153442664382496786312755369567453642365570522203867667064702855064117777248996452839510530112258447365219153330364325480082364302480271013963043808407808026617207478317657335771085499907980998058580300198585325142615450209133083897393551483195987009899057506802305527262738968147264513649676062280043385168050292062437784343481003416836360329, 104314025112423274137233712089887942843544143270638359212971052274128269239471444157192816218808079846611202214084249469627150795706839411653429768726632207799788014550224322493762432406192490957609286668132611092680358220234900446241372261756133560546933898911405464919838498505955386741631220042481687693247513434548162014035705016381807652211578605534090062861927303094187322830394428003720849259122728764020582018050036758593860110512593538102856625101436236685192028585785277359733026956010177985114124809725271266235518425292300207754430093643901348424098723963444965623388363705031341005891153453971749807676104809873756494951980451522602316873491452723525098105304097227244362803315664527459814806074055296007282695273078439762481309737546526713550861490435485841202437290236273820499123268038887900937637888673263245804550050225236201356152470642062093953920448272200600863673489805148880500648543349624355627609552339313652249538084845763001317045938369921466480729660920730443079784782692236767617383867121962635468379178835807692901877341892412552450901873955386866840632105626000662355131829735238309392134598804443268332424263236647235664725585301289855948091012922650578186399459695913486992557308313400835129903295472, 4343840077241661846268935044680587301922553038527003445558194299629246437770144538620877381238906692028249854972040151877119476048349008469539245051594012783879085195059417005760769680951795800991838280644405366143799108863486512837967757384337716585187068737628553329955797218927948991807398217726158890043209786493155396314350961622153611660511283644242391666275370968989005241503828383899735010790229677725184129352599961733027673035747501574385230757945287667652891580150423322079486963198642876365246595747082980621374167798723795545482544349625906607527172146616536749758514128592808962495027958181278487153055495228539745094046329616245517171769643273537017191271548980274132500153620316208900769372928143878394476769232210760910446165114726727346459588121745157883051053172477968719246421056145184230282266693069367823549866560055702512612897427682313787206166585448900167833527105055197710187205451619052189815465364328045147326853372540758120163941655690535948810941959546749120505801600233689886118090477238999842117697450804442045413189286597419777550661497797676126492038567180797469427287581550651480006192621101368344597554817693129617367587265330631435038864934907358392135820575836786357021588185619258824320681971817694708190104082162236078675439624893099574428154391060852816948575281188326664739692492957173855447270784701674993602965772572705572236661284175838750276, 33232188464261655563179500532261332740673268011927651630320348613939386668276216461522230721806580297413734568274970935459682942632905228878109266134442095157849521426423087852309281434787500339731212538950209119002423508188676963099974651225610558899243654721531277558550493327350452829753190227897808568073543678269898207509403265336445740620238191925668387207191570780928973245140015529624527394339504110166219539275461482559378890285009329265175900569903390034280071197123026951890243045598372762777194271518734277493717862068019851753397533687634966545727487904367806612431117675184708993348444665119927999157611733751268566184403876833185469516137451908620375918418813671459671015165252098516843945558856771686910403711604755349007547521956309000907909321344073563215005461926587582952949359614987174889724241132421264477252674765866525922832869625858802619129860030857164098812287559445509108640318149480136605636205337149260208047286736509632239281682602528730811378780178290081953095940304361016309200367801327179710042344212586894803008913891990437132132154254944818304511848018157641226316486358816741537666493766664969385708412966038685156129617636758707978377511764106375364810771789547724915964400747168477073598611228354770053945278770974453529085850122110633659583211141893829685722257824029598188511772787791704436267726687275674340238387313917520001746093685584958790950657401396602667943161883455431709467342749040393470692558305012064228847045344065542300917341497880086951027085764240682050347639183710265265174608568581, 444779920211605528457399163778798302264962864500581879449061229089239557061028178632115126869104894859226622560444516783454331855728643653865605416497057611218192216553619406318123596530221714071025603907837449777716507496519968322248412164964314856154515711925650355367893348523307966596574094376371033024957143232394835676102505384939927310874548633276763683911796494980021115548783946752097475837673376331732397502955289357489918575906500096508563791334858578196054364575510262549227364768636710590870090347574179185730720326430135005745433229085504757196383182089273767249820043995239845148428050144582143617569531992315827635029452027206779513658792594533984308575410806115812027902735755703109725290139038156207495514857551309765646867686889984088386887429907974093388131425361751082756577755914020028802552784669428525627343682049455098817841762010840270014859394810253384211716918791183946657609375093285440242734069437770190190813413589772304378568548089845839766313942144795085022405996403115650259032402819679689834193687730312737088900035185810701229565183457677574983602078058685068344436316207621825755389502057132478973466812474466361405511892936227130460055637816125221120263639554189413490859455156262013094121152711225170530206766029467454109467305401401846460468093777715624211347060013862325763649394914935407437210178038317290293919361423759769343159231891689139655490453425886071219512994202371899835337440763173124439640514220811318874946924703189200447691715469272243497270647235873464259786562267062001636730421451659510209634262617060501219332722128011149714434675517928550498574212874429311999930642838137400894349532393752915440919307741932816838690395606129263401130, 7602657349299010857087412189053904610014835470031847851883656349200899897074907434799227128793882909815738193292999732731888978083302895341590290406257165745016960805038897127665671830799203429105439046544232550057709873279272509500788880966204623301536523568757142788616714342396835348896652095993273120352216558215593487864297089604696564960677302089801831232789103069985778444311388865194583877243016764859298874263207514989622286824950955134805871171552294553075628653085978727480483509447782713038101591216015129434695340034230885326874585545666722007375755217543974918948104058213162198622707539613172458718150254646150294432030411829433714905174414616923009739539225989262351006787760054622647363592552091025438151580366414103445836645659713990402360169403016672502089016488614454624878982485618028646781661937237681350359808210590576468884385972827124881157769458685969004277110291444619196405001534224888721294643753150729204059438079951844348808565383170513314781032113884141668626087014977362543472261224194658720773278314480331562064521903562028929772245246023044918780612944818960063465178711539798601604042918647125400052489298307932451350609822767956789584605169244797260390089496546479886501231620453426723358141585623383732719446553408376039010770786422589076208046136110959032740167791347231308499822725649244370210435390174503003095419480360405606956944343844737311175070859345840892142099028930344584283138344997292575870767828146422997758547138227712103360348602516685557024226449188853398358276132193649977284120887692434143592539192811494203655959855535383027295793357853938962196086241223840647731695273486642076372427955673144634441281545597498351950046381851656586528708237353884336502685431879297832928729212632646314921058694911651155140211366665485536218812420299903213130769617228499207211355651173115373832276702819917, 84264285782731568162877315100957489042921709978064128681351268312087746569277269486245900009777400169887830271723552358655565447593550146955011831050100818215000508691318113595184405583164046098487595114378660143656870174865126611342542042359190092909153954755450866325242940723529598062222899187359928557844177883049590925651498994463750219753412624841866695746278533280094878847475236701017015819139013181859456526369446971330754812310385508018904191327621492159168820784532796330689921699298448074204812463376397381282323119448865011664447416851175564248969000702694318145335362835482058897168517488161967391334177372697703315388808719141005307789457461912851355132825731054246686755461163054191160703614564317990818604434605413936738139726767800963911739280012496306857434637923374480459728565199969705867209254398601345461449150134011614149873500167983320745189254670021733091744167981087834156449345560645456017335407633688885028006913440590401180339340613693275890333649989994343631183579024732181147263210054753733928915807504572214832934722959416211618552311628264441740006263506928574652072303741962304773970001278403931114817733924209744938397932123215729579525983133592585604481836441256004482294972680139829929612014077833332681473454850703790455910234390018139844986977475904490461864701830158535403553678623812164036013559496102371103327886019446045373299153105962515417300141416878319759519389540938146354852993808369804508844242989928184577744636058484630309125804687764207122455205953467056765480238519667329086954915863584834116160428194118255018588109352554311335461224660821734294806261011545470878130619510996578906865491369421849868743287382195889612248362671647411387033198694140556943015854769888065336118318462104334038850907108272666824691321243254155599118711741561988645703051401242347980726593263524750481061186510425684386819376145632247818469939222055128225225680599982324030716227856712465076900465158037591919290264095582887285060549164180202017670962738795868581166749, 86875322477430958180737121081750310417552562568937472111462285494068077044224883282734365519155742412567742579384640688864318774506290688726649362821127869025823526558190891391368772700819437828837459806248988365684079824273784568628472269256575474035185709547347651993828702097549741334374364807937523943589572886556418546138161477442285095981598112603569341799645993286627117775387075506854483018231019196901947857611575841702330988975450215180893407629689116208362182111134678579611569697431926172879405158644545853375597102146456828749129737059398592090470207221930164907529449914731078780527501106015075222892079609819142004929517650214077829963858911041047626149998836986070729125260139028680402532903187215589441565748744974914634384575746331436503499349361029226889115930910170650991829637232214683931349631413139076186550993209917767820494311457665926894684877305970805039969582722809409057884485422798810134923124618610122219627418825157655548696504402394251875250216209088386596839289090205455355830326463145513637140192806838161127837601889645337809125003492037067870634529636104813436961659217629590299188696646907180990318511335172435862882285594729483438730028804396906143686407113299921602779063868388165847291926366314379673487291861917979020712234162374569910970226596823115360201748087179946804305525598669650976080327154187180758461602309422875784085236535569730334773176739598656049048170461638432200220436248431274572686422522379720157015816524948018313551155878299198696729645812418550240418562460968434597425565276688472550697127256796390159826046074365566403255645195972270118195562599397495009632518911353576570958767630794735474661250425256764192128158589944999335063602995713281667673220224066976800182326927451684095263096450327503087613798593569273550869670074927576509772147487168451681956168877773772760560498198909642263656809675890678191288443016329637625633073593034921242604872479828009991046383160941673220022936977188891725330716968754725864852252393788824966035242075304806536640145214252474418277831012513594308952183851343958969850677298051187040013011759593833806518361877966381266531975488250988830914527197364101, 12512746540434506671622137154487272479684301796741804852784466276118318939301642459078381853231258719083628458347218300308117654564963998239910113998177176145693597297093613404613373790353962391872079537076763899617842035568892498763955045462691124784114867824842208398619557012590225397311703746359043524766454656517843775988786861851276648768563329960194176509861369794873055457605566481169738163028805838726245153501259733517437071411250664053003146288253452678594410757071147688309902950173685554263072263315677468119998237322488014934897657616287531839226555887811741614460852594517274931125186552830901907056814814364537922270306184144816527619368461860735029130410855453249885989873125086119053183377748071520492963343904276809950936122217011456932719335145019854799217844683275916251254411759723367406995497382110560047670724344385060716483035502136838796674166618447372318994376720742190789098253575402714952812659933854943786548064525033834188130429821475033759906784746466100360319090217901641302494652036828536156345999295944207311903908579168517843644212223034389569172093947663228241575508427027088548956357607118349234005954956185598117597472201788146015733232957686350215358611056864787006128071212201859644019363381882103578216957110324101802774053325622415064181605199128828290427210592657379567354577480538732546950307498243047731412124485919082022649710227773753299708907420377570860905912772090222116049362619789689065827376289781835174416236170541192824551498867290178284835242340226614885213085297034699023207334693204443834177633980478287732765627349487390651101805889417613406850491982522373652059294595205056982377527663490663856624298132703619405155068989422975395069609806200717991260670611916599446743505075260280455301127997860556855773088502432536965641419712974469765402344889497455850368646912720700712406187148014080534412935202873400913358906387215078903911309526903672652336133008199048483053203616435313691633319058270312626100467991257715266040851461069620411861732977165671779365665772314236597023035647614424138241559672376552675319414807273488451981119673616629216737966281726964723616994609707694019677386869057732381647985259361201436431774138127924914503212637589804812882400769493547225221791707699401249315407469433861394473469478007958068015775562155959407640271035, 8708772086314275150137563047822324600135662221530061604490923488781196834561031216119766508710300439592586098337033648172158478037428422016638015261006654452028325941079516640378163094114359263904509663697697446450829644183714138570138053299079111099978730162273301464139950471846002885912898793623780911069208262571511170830772519224286142285588233365329150597172851602037056835267890472296625561911616145092230018104567552026345101742597268103327522556484095066615892886223565058357363680363535631942614863586767642475310674520180258183502370763782154430809207907408245635540513317210636762204031484268471851140728225200408406477879491421034411771595550287534644492458168126531514396470443302572852034873709549055869547530655956369042654261333529517571359153739442787262860093740661118519451621018435524810049086927689546375333874177211297659402716374232772574921960004351227056283357373573456626553641214672035447396850649297539465342595024155246359918811294045883925114447310675847751632815638598802360958589640694941216735143869543493813631906641446867757344570346832228628926669569641235390679032157550781745139542693343976899951858605641387961226781860479580622706408871423958897669045935376111333791269969907893321496309204776813332733513920276388085041994007557204267637656364577970814757016037506402807507663275686948184629913418881333357288030576799576733495401166943446587740185387874828772125373722620767643073868513719861621143440955960613060364895903611801265463530162601221089578458698304546551933625165213065587195349408747310822367615685148092899114446129224352042234315865770543693346677200293484242331181710417082363209828386909100998998888639900536186820795298321286714108461675397032864388542110213210827364423163325349547591341479159200210127489502278231430650721377665744894470461939053982524090875574789651853588962397719426413835176058841208314719781852021952695059793831541054574871680705012400864629090745303863048197498118155019461006670125137061405464976922277176269488571398394629261276128473896794210626729855368774199524936087915252643083350806653978162434973122894687105799198912067140963567030871513363285565713597188757003358857092315759659368775879258759880919191003344516366609757523241375325301693755640462733509474415702644254270875174073203609818099246161951619877073996976627155333499346477458629618081495288947853190429723736471113704267980053978389993182103772852202476116179106939188158462552458652108321980165243577989, 600670032931697501164308145888014197492570434182237560158362504047400318743985557099146474331125213856150404793770533457208418057346330441677143608228832189090853249915025345091440471977572520377721353552421230209210878714408072035504562082229497678931477951277415656323261513473676851714174232119110952631892409156281805902829840067360861715042158260954202580085062540987292060373485291126788640037325353253582263912429148264582730931166497761524857603024286533377786733733569503217095911870554634981195459051734711257551318783862993538532061516918229242512785148483203666879172553287417202171558010581931339490420944579378230441427075256586289381172933294401587550551868745979621899498946185449116142910195187754784531077545817750030440559239594200572501795505647816820925940699189807911408560014741609936565474163109147615538288077368434085501495660339791023107653834631734799739401195331082524762689829404043854362928974818455326969933539941993127168162613893714556812406931262398133232164550840686759286879519200522303631666340760585955445333243578595829239195345013932609791828394260147075352440178009791316103080071026057431465935054583990885807722362958473601534263884483797804520563080119843829936517581710475224995487406412704094626227661853966476374689727423649602092208013642493973696165953898208578723428386172214500367650457610332358123936218429284291631085293746168516063238704669713654100448973473107547290896972051178145687724778934856166935295480879225802399479077346027327314330339492654814903821691676533513420126315351413897998334933276481425781316933061160336396245725800475529909180155168951048807842776329370733724945778641650510054608686950632422179126803289332576361096595524712081770649946303450447653874189205658344800236157548893404541684986435295108661952487239009695950009496079506381196591935645314690427759872790821975631216132209928929354223296595481820239561580620161078572691513920025180731146443551810374070796784563832569069540610771634802811283644303060748631402280436293606074124845116433560780371614622560694771710506136314406382632695962443912413902134325317328060708301892967007571381754948796760722223816096248930178117187568894324829422197591098693433015570587292619159140504205675563120383480457405492676888099039922054652604691220210221980510833810667665873272200431377635693722100801416566512889633584494029920362450447581541351127279435858414431885445382278645820452301854483001535497815948240428726604118517960146521827602352741617814422650606656703172306618878677224079000419335204662784233051630328692085443396990051814696765167700904476881356841198817297213897315038, 16802200282185468546709956092597774740677661549186109526956115242473121883967931163131646187704424819015848998645400207990914089013740921040117435052153841770979793783160919446710908856026577921822303736856837341534046856200378566367573847587481842033197417244157615430123019293064402352517730950287717412467467865654183120580805017956735624709774788608215096623799957840473617022005811932787883583498153009349216019520591315741115282954188920266939008472763372248700697866120997747281838993436471646694877967037584713292557154069090849429661358360669249141411401563354311865086301325223201338603660585063135197133579821848197298915130533944228373462645556131332664180638837298172981687095294316288287474397100963640912775346092923086826604630609655904543259441330900502644107449819662176812660489691326329405408557397950478553867742426469439899689820127149948041436799921133103166748621889384866646157787616184868217116001323368301878471584588973680319019047080248726830275150507574175166679909676797693790108124055103246880427997452475987304179562314626608037471679968401792562140826537740199515244895441348559877458197387323837253170889409923432265627983693113613925422770696270052261532295092167140744798998616784973950454662490861686686088097664631333759768155114942862532519746034900590201459240562835926241941887144381202153705241903628166984657567323072355632922438685555213721062141830979317585407175747781177680148572415131107678588710821046069788978524572240303124373546329950302755883009871688891897763945611072996185025629828607383345003927868697847599452468428107980542821610672736393669832455756995387290606284835293616942665638848969022879828703775592928644725559259945529304050112289143946763124018433851771902626785481385869955110673938215223622863613678412315324306153440766902206001688838913230436350171971289551619865068519200736270652193304810653015371888594169504114520468603987418351580463962583790787745908309177358777801427510313483309516938585851407176405272323275406264541269998648558076115710572739949113174179063104037408892800012305672645293826133157192205750448664938758484140537975600112928783731131731160554472918720908169457539285420601699964488745103603485765360051670848460168635009550254451173622724686795853530317243637913985666214527422655976232855531815124677038149005239212580323707459514903671850604938595975480625971419288321333482646971954799306704972896590507695031753549266109898497496991269990475759448688581247659517684220339086012734812415537965920455360852739093844076811759759173303373454199660054006117215442176739570999154607921395801738324345694513716171731402600767074759488172948500119306978382635362273371756452203795420879806823382694171689272398990752964743539328906992588078386684970091097095002524822271111900103]
c1 = 363788646363430038957594782766177313516930410013028761096125449525352900311987342432332707389678725464245570305442656091083147693929633253905472222223119105496597576680892700795690978029583841539541374381306488238546636925041645743837795052980068923686651284191050257037214462852085566417008362992641640639862428112228493556483476170926590723955399664612288121797929235261679990399185352352544286959163976884867676390120340127790862048627561021372508575978346406322179713972665443056495181281314029605259955375166316993493231524529034376084736285226932730392410446057610167031627686895389188357267336304140707750661551754532703726810046229782522509583068679068266026330534604220136448779670239303044844594369863033342562614954908580980797071779438702134548396966154384817728024762723793272143181635940946334888845065820620182286804643281323447179363272699368386379953273502775010659085362938622805062632668642982294663858335244396163857338508227323801751681995976156487970781553331051080424612021398707159108830544940316009623664909356175231889874464365926612039289520439021685692867423908585449824825323639525381296026274686349117857285659369998795553471936274903352010099265109629071229881541531543477669574187083631324785284254322
c2 = 408184822131518156560324293475775283916865330287271026174896526350123511666895281956297307670862799857291692050125369779347444868678108319280695068081984027607535529170555137883873801205238074937937942433229726545428621408643537931796698659949811571615439710035675674461716185346635792745790874541046465708604310892716226150611709100803537856333225160587696062166931121471905405372834167788843039506170303362597157739646424300148724721973787617390725217064863182798206515059995025139870581046657455818390197378360718268577414540468313327849155326977072599665355467818781585456624519602844435476444300792593181233725708809256956289242348798772583396011536497809799519543692707372931861510836406771810916160714625641110048105945905698555148489134800297890071585166636593108936219686471652288476546797128397632673886639590166634763861905600305344338904568157848336645918449260801970498973364463883003344546391045331665345600454985730993059182020185438557159428617482719829271986950641093353253897984198499501965120625507862855814501340943227107501804839977088104677785444986972836309787440401273632064782837200999263612507784233705263545942160822597103292282242714942650302979883274746718391358487897324158260429570732440514025523470979