Long Long Encrypt
This is the first challenge from the Crypto section of CTF SG 2021. The challenge introduced a different variation of RSA that uses \(n = p^{q}\)
Statement
My encryption algorithm can encrypt paragraphs of text!
An encryption code and encrypted text is provided.
Observation
Recall that in textbook RSA, we encrypt with
\[c \equiv m^{e} \text{ (mod } N)\]and decrypt with
\[m \equiv c^{d} \text{ (mod } N)\]where
\[e \cdot d \equiv 1 \text{ (mod } phi(N))\]The security of RSA depends on the hardness to find \(phi(N)\) from \(N\).
Solution
By knowing that this RSA uses modulus \(N = p^{q}\) to encrypt, we can easily factorize \(N\) using sage math and get \(p,q\) in less than a minute.
Then from the formula of \(phi\) function,
\[phi(N) = p^{q-1} \cdot (p-1)\]And find our d using,
\[e \cdot d \equiv 1 \text{ (mod } phi(N))\]Then we can decrypt the text by,
\[m \equiv c^{d} \text{ (mod } N)\]Here’s the python code for the complete solution.
from sage.all import *
from Crypto.Util.number import *
from gmpy2 import *
n = 121360368116861606771833968655964769506728397093212974761176901482618556577197621519522746566096888369901569313195058449400564426488114803593988517412879318912859488725896866856635825279447605648797976543233445953944403716335663709048585650625402362721502809763411570415327611273558280909844963284874435721848926925656003634648988841063369190392199769405018076028629927919150798624171871045268602493719571010724488889673698355228546945032036577356325539367700926677764233725180866939541421082811060148289778168100419126459272454878775226203203704576720113356397147357623307294460174345272047073714387063415325932338351570579330910874355990208466331138761219393569159697579706597093082937000506642533581470837732572600896901951878006067992645313842064774247477361417213869446802047567429858786565768987146320410108111248891812486410707869616296902513312035809666401262349054356687953933842923911154016645997404681983695847297765657374159543313164183226079734327840912505752410157696858550015206405749903566301288680001663762427671389067902791761243436609652165072415035352959934637686930118852672564163105167621582639278885934945642774424518306968823629844633411664880939182500844138243877427097676433191948378822786385487204065667397020758615345164306898814172820005430789832253865586019035578713593888346520054594276371741227835209691717788600537149824861707744156303819035435037427467307536364185486380311847691359176532110545156274057114287323458764451047089987027577599824043745296598360758079518292973287070918932333228215286165065684906245291205980598298304099853073715368130803501879767137891270138646526884613457338623614714661103162013740496962275217908648264416374067855743741460092528405953569177862516568298350408757484699771363557927283332090769520240194167667550102651319840131465927349009097559236853367936962977995218182013289812127347922858667110469788496581840633630326560418576448316508397549099983376998999611669026540709739817929057390172200247366824745428953939834370762577890910052748439173462588698784952214701243884202098577620143878278030311183468948991959471844493102660285155508369516523540776194583371393026705345189287177969612626787656711163096634136966730680432634318061969983960127453367452815019078052501116670402828557540356902217690049283375304975964402434920547616496083016478875149852953863730419170570973742388790088488499671964044448519731330582518503413209280610112098721675205596814182118575743897509613480655517378643509957083004739741396527411315537738544685238520792474858908315825141259256955929157503101024920222731774478493465003291331625383421251800193066608951349813626028446341199227663220494338086099856443585771816713109795097768183109132488325947763515756946264532113700155692243448243032383462377841714740615197415219672337539129750713230904646548027204881075819955999481406556997939832557641539152342253444438803056781929243756262409090584754846326750144285835332252808861583912930893176651092075684704611547552079973982865357236391702673160266755072121586515639716567843945475304054813641358409523865234620243172699583528770850475331000302820959237178159884911588280587313622684398913903239018602862495472602580851435668019282718425385181421843781455710801152635114592446203988640845770565074267542549076274881042497462513589153120363252027927576014012176232493607568049456013386832706085032154422040182638473152499143602113799632528089455726857420969622054016243134553846761588592600921074719766813249645039014687167079256843134976388055277934268971916118145808988420314904341811416458758524322958499516358200849974589788201086951309836048832805276742056409441218564310270527884770159849585323526788414629909690158876235612229113309413504266636846247682620307917249980828109334296437981419888222948945048675288037035567499304532244079480153138485831794259372431003149956278085858761586170454697161604394298200356194230719970937996305154034475184350089760984514046902255825015507267400831773698390549059978510117075581606868740022912546837039941201755952260514867712896929768198259175340519078053653340454981202938671867218040334574717381813532098167552479981389890369568517303366381428912384747226564651422992303139088680452807519708576981802322223035724043369374955104912377510127987147007263500055748401903898453691583697811005485035372403687617145516484989836746321164813840271709429527533572098224440153541195962256364422193549592255585746471303844002665237105255536366836044870855016126687836856770380187401565959321794614476330298824572177157023782479183553168175749612996713222696931688614762166672198808900489316929396138265601016170160314459462282452200747961866160388984020597312765939917486834545923073936874583521252790160129561852000239813033335334285625881947295781034259814643462577942461408031629596246727904453737314442633380410510316523286380033261489749463539081656811210701800204801151227199497727911556859348563185704137334796089022745195188318749768164258426040592495385603089081456313793484040884442487812408863814200732153261592078921303891484875707612926845674277958256847601252861954506384002000478383750529956611909671086106573072131401899321941525274851215780740666358143640597155163534417299806106059697372606768206501472084695564503006953376827484853920957930295757959042046475917800565182657377620735860703437667929871862145239214835818716715340388376021869040399849491530519831247352372419549727994664590132538367003868921290949047741416575455935652827556080146277349502969741503465531677805386293098855300918287656951432294755070383998687034560761954966567871572489270864479667733977931475887606193702364106199069247626126052077847220057384983931137960015407167585742811312097632342370227418558242814767360583094877216237730883123855767644321742644944546624854988486019648478969860224924412690841746463231707862498386722053370634271703185890834399083640040533303348218064756177368252548916340346435992061901447971646185836942685204629226292585725221634340462181057539724792233856219500575457842328161429550829701811990862705243309320818458644965673684321731538183633965186493561606730626634513547404687986702079791596055453562495666797866162242270146801218610170053930892106494439107508897713968680188071979554194487248899375708340625795758084440468616390885339467911850171918457904907606471187709462656885277630199594731110336329391174290662242309461962980169008556666594452453128487428709231226705316520542062509315082983790957512320833291173623481205434884826876897168910800875662841074446321341466783483135080623222015807292942833223828743337377849907808153861934038489154364944025947866651009641148112394670466296177047385101980874042047153089991764235116525562241220138547944287537467231661120859365291217022094500165069532126325028656569027117703500877369153904291745422838321266921665028823810915709191972350517550122684153039389259935952484881233712882301057370236404758436078169024051445963667370106359306258828041200201057838775549762968554123763222564900871701649643229376790473806450758741046501142414665398587476221808258625680530877216688853096114550959245836326615669907278012488225461559611945961937957181119524675885080868424258265210448109936126113800232703173251479012834892292438493923787145736542465566839286917391220318657419294328281292328810280239918473649351339414546701821815245220972629019765567355344147397381647375594648613597908772176910215422127604011903368237711586273436337688942414707994393011944279656782705876051701617803218260247531599255074613930029701747941171296477459468996116287713101119341016306041049986309328449550893126248475224248820328862815532785417584271466578137424564304205318424487420283199443501727978413990494393427676196339812478070223530272581325110899206655024086045067152615012469602993554322498130692201995662359980876232395843280367174276159756515065288328134919124666276181378513540072699477150409992436535396882726964504895480367617485076894850187952165787324234164871564397678780334998828394093490964314595946854975626403034377566377654604929024792771179874546867596967328405243941251112747040312857805441475717485994102306528971181660843749830075053800115116479278610312363342701319897785083829902287085670227205515208715841027603588900581600589242430198304785678085788298596716169096145229949535750956609794187218803855715384834464723275259898598374780737359386777087203711144662723304935906656723058559052706190633891329031741786420430989025877340372944653337342543646908607002166353641543545199678128347017153094121569625634778445816856131827123485514561372785496688093614791099720876309266106250037328827534940750718094865772714828702354448805501409018497242168354387896378127039951870806879398239431182379612538382654158380183551797888468010513216040439493559379146643162831596956477606851860938479482509326729678403948106274796992493546874114628141369667666703980468190884131075212832714451379471894904357164682926173460368604474873385189331316543401671913921492263646040582608944113980436004067347728986524326217727737193572486851569611950370880907357130238352667991780994119288115462186502978539447652311222482005439231997879929905364512026188585364803223743034862216297078366171225884685460617508578599284687750491503268307104938733894991258138397329240456080149272018095079544551732608571989321784532138776716914747496360281580349644803424245030687593214545541507126205596161033173361178139354967020296824273241258479361237195356587648289083205279004678347628442706869909822510110655343144256565868943383800419288899752966144974256790627114451410547198202941029947607937361588613061572379365062861029999970631392756076123908662440906178757651851580461411537153682925535362603656758746421243163627190287408461923787566119509020494850939287618347186101964608653522877821868592247950063883298898579595530758047735568898153207774994465074841440019710566082877217161257461158513280807426415081953843209255325186499651062608702175967913057807622811414709100693597091702072676180621555362530353019314911004047504012673276739227505478763016278096492420785711172009145868623163270888730666460210726280441658616266503047570929281205840725559170034431555374503268933271726659752598527300736868600221057736773813733972647130308784271657171750486408893725820064383764001604614802083263740822042518881410710825245678161064790522537740947317559562820522412433319570561557073037581055332133312294131663634224817467354470250946479418972139347333401377517619359555243287569761158581139549542749006580231727360584516282019705886082202522587391532104495035404079345315066494184253329210577316840247328753368500803341870340625530630279179213400615807179494244898708051393465961958705200130123229378573021813754576950635422975220115106211585214427521039224693639318914793952410480966633916498350282709099948513618531856415907841717787541824736779670073268903862886824980070142621500343154664644946698687784169365713545467373040986005772616039171042599220912448921551381269876337589404185462682095920298660284280595965945165879247725035503867767417708899203906290346630676479983322248842684827074989399944538735848743112641431906637682737745517087411663567146482835729255498884685319209187799705507768111363263801825859425676023547656955319284091252663809692275624550830267768332998118625649286532313509675202344122949126519437751918283641702818956717897689084277308547178831094266202092065519954734561377081358966603245364132902228575675732905931560313472046320039913022992068172123626058661077367846103268767597303930006569788112834754539817773328785222096754641803038617872936356290064018428385009981507205560396860198101878793907142068847539780956817086576369687947163768704374530712405204015249263768894188263897552616509162535740758828756899538277651991937972223082806876733032870986492098744715433091794128058457460583245599355482422654748436878768008907457578195781362084533396095866713014154191401406637114822510587253034061167197269234496958307410311565864770172685546333224299515822886692492007377634723728459297876311018205251423689663527006983877349505901774564737535208744479726180004188737943711644047311924500503515571814696117826146402315089100333108921324633466254012837431502341548883756570486881300084354411964786955032157326157279310067629969394587427137965855011211681359303623836163672495329995061113553914378776307586348416424477669689865019392477214879823031844510144051527602300657005683193415136642487965098233125759462786490429457977867639789121846988966520673698746985603462346502624582673127117583308721398871147468591210551938135516282245917272110831481192434656561828886419704915598653727869884896474939458131800106687443950781051359343472367733796109655283142761372138426149285409973867759504771735653456373623961210160484352036304350127610928591680168203003266863339742908173661612876415552190571134913562536661695526732964733706984669856241040086305171098307498436613849021033115569732137635062941148070273971783416882667366461687253757090991831047077078184200291297379032631384315956363377631614411766146461428032534962665602090433420384156176997310796522855416239141038728886744147561494318519345910285012706039742115248611761552361450559781145848936682414722411931636515307783125634261868842535901547953424881759963325627759476188795792281058223090362167202615426532434817741059491763346346580008842055082577859793360760629876934225971219142764409216221766479872792527049193614281794704912180816124489148233960161109684890371233799595216871312917976364072719330936693507542569833565633358885851794746772469912395069269353224264977710603649433047615560272239006897246837031509115034153969523320199210464655752373656435262390776542171921487858833380382456228115047625297746804030442417741693217594368505653709018632328071382758441557170605518773219313258890361516444413614831953241086425328632419502196520152842632293667102356065375060571798916859134453958515082116850847564225332893628159155707615857182060388588996375121081517983403871348947879535674723754608890428872902445017584040897448278957245359071452680048626403715078079206091976534257688917799388568362340164982193810223019006329605180296613988081883714061986933299096250866335137090619073943256662709698040767489022492083606023601825696880771841670583335636728506841522068675208629731768795071883020708629050155421708204695423291775054931297167485698382337477050194068452976264001173712986403688923514335278618392117851838652021051843326309479577253476423414480860643488304793122323111356452654594097976545173145876956848578531885737899572934436895229336447963920902990055753562128051271291876999950758943996365735879105185687530183437615080515783320623295699267764511561085763864211466340323440580804600177980263738166437977031948288434736502873274592422495527606395779125513330028878331996787392355534496354698721341615420939349858839348454735789302660535641842992725527157953614515233997629631707017278327911627980353337176757333713494885635700453976262303427713624308968677711750694189390373409820803353587273934666562188694602266315017976194808160259753036767628640901164084705737486890843100482576271532937505773029182762693397234446606487938037023961652858806276456827329135114858659468425277970386587017862344359371526808205049229104077661022913968417473839129864185518017661936563601233487870756267196950606287583055439666731472793951470768907102740743393885905933471715029017567735347331255003927109490429407170251903551417373689710743130077142323568542472075294532453031268443652971335946434719141542027493367851916548495201027118736294565961849756403217666254751092465443967802782035750386962106550259199249491889346885732826359062910094785486176404566852076741378550364175096894394477972125217275221037659582575034405269888898784280236477661128493875268956536553565881350165001564532276028224998730644373149076562596624861022964733606863074427950614755853728579690602828166419364296410333825227084297557565794251524294887950707607156855077040119597055815699504315787534595356678748772520649642061445012051520974542834633144822785795737077141972236120153285009649542015163767080724152000940968936632164902476135155943315426061241580610016625286980211136649333958439400678530982437961319281671725531972134115490073542018695748439873936080943288752569213928679721627496348080362798613424427735176800542919195693989917688322680625694121278514049877148903372228967458353752981327647075429965215419720020369618793372548932621702277958860767037433460472205330779928515642396754030023546127114494302348643541325151548516547674383788816462630413216911679602275632444502793641823799648848416914609525279493490010522179651585931709927591093192411120391622894969162715005312382896119992501636231353786522610225710434051743336603021229068984187624769037474790050789550033989683360395384212337267536733585046970074888094719476245733910043946000403260457593543024542262575241692668569427351674286795333634684802712114635761593933752611052603226463227243151860193568584964570512935727997765281596007453796373044166851162055535967846573597150982249244256148756750686422100209327684422722108122328860745849422559713661296966160228175882747375879385353108734458742217497306968821743499160734321798833707823041307500959872630786910235136001976943059835401396375385339718980099926676014375105024256843630192644228242042571992641153987356704716654072037913395080615595410161427103693765201451406506621308638126897672663935384453975340782376476131402985225389428839833224907303857635745969717790838408414447636544122967146135753038782712754651664912884315373261461830157390422062017669940709558835936854252674648580056959370333858832235763752660048207541893961365783611489911855913253909036249438251015783386826771488632675374415930070781586238995371683664460130875147205380645235713304157113975253861930628145236425026110530327192263969222060756442746984213818834785159420964863785576272502077838537728975448269245751826763479806642856567966440871708293377780824709905423264079885287217146336956655302614006560061367245404298619085564856768051769342771334298698438855791077932045009460251806162786138131397473385886032987641345621079384806240131832810331152723492899149067947698517970026683216980813955290891135185232576918486747758660304964337589623402531315413104404029313587711926748105599175642946133072068589333939984774246441077833151667285361776246228981362594044767753770689305601993517040646990596867199621486337359277188031150829999505892656801973588710435647918052333008457888309075297196074865374785163332355731715328426625352143148065105029542639339461510948091273142685603805693324728109794491208549677859960813280299773950112206047432516068620435111823506855404747571015561323137256706577578844480325570196981911133261856550983498506912327912363722355692565163109509551121325229176327879721811134272808271440445055538918693092321966352563969917313033562173694181447616325925647933558847629585789411747377806149045547085987191324407350534675583472152320728374525649522458600421781794990362119043506056090628779140209191148755593589181926365069772867806087512937180123097027014456652374526560421570674863319751180752061351579515245255669155445597696372543989935538801640649753476777884397291336015183247560668391235071392921072765213939024895223242265817480488924237911241176629648823297409299098675756563883171180243580251247728191923133776372292691652079115118286248921868078261343237047978794069004544823641104386953123013597791198051816293740279899441382702670022184340558557746293449699857041892058349558046558473848142534816563554802347605658634750081424018431518263192691200769731020023955323097679689527119481419214607332998361348871088496004996824961251113477333547322529072123489841830346145328333791689454871717947281093125520279262566994830045578944046830995616899627906928964856768848967046547499133901243817512774437113873572130123147232383954030673122488399771987198912347131304135963637482035167785660179022760450826362326692800985423951417131236077507359306284534613512269370567795795143413823726478811764794208479347422656947327969990634359310700418477056748791048513017877382168025842576406954539052423572433560374340708717278647322668726363642446534399169176365751706019442969235483529375350608227920616747012992978483825899582194171734310614421368499722881770306928974484203589791167824529436613908996658138412140559859018819757619609518554599992631867004221124881293943470578943126525616563560911669681570589685101771894970528040201516370833793192180851926924065091016522732460176657935506687018632491974546707765809920967489220354246680006939108558431565472730983335057563667125960795646614532544172357229096514688557098054520713786750898933065437923182562160309734966963484580655936323539749606843015634943067405631629022528135724169430750240430660180448138723233440505969637516314058816385501939347667274556652696256292359222065458566052315685631349752383013361063021460099568312049720253262838360104951771065442839117321370524017740643307859417181598278556175531033439309097038181286625493147223888668390478213718328625726077378726921531201015906952207942239356391656612345255905926532058708098405127045623003015512205144318743421633844940429817074341112804735824730608182760957652187158733835153251241636390611123421556046258291737351607137609811472115251295485721218455488210098034944102557695105199307520953809730681494447241322929928239635013285752479478210906826465357630063252395933168462046418989893812776322163564914935788184965995466524337477322985559180462468210813766710905520897905170234026895315264695818589937762766833258421100757213352640484955305881208947926934336583528806938132074640355653691835269358580441456205264533053073749164866880766703946366148383138166549697281058587420768544945231546977034636320634735201573014036942072489586782490389397501625408650859311974521964466986343762580331905042954425309560383804370992206452531632248435128977900947854612382000308638985801394088633531807810664552067537770712796222704904508263986256842250684041171250355720610359220418268389856259076049783183117653582942015678503638162578021007415108158041637718163774165719477635233741196632943566299321842241060607715359971626197830749680279628270853125091820750494623264378101165056824316665213296704487651060527368145647432632040066662427849481591210688915561855531597796581677945302759607163301009226426179921848780182479228069199359948152887145072928661410369978243206066873240763693051615532383334058718967502706954033620305573899170143196203313603841925380517542196123209523656786328685165319531644139236867084354725754687975494211508519727517468680589139112011488508992055776993292955175366864451434550114516096681720329474392879830722257408538607283169759157107908195662589448614528047693787545103665051139211820630198887524632259906453027740835600975789173213528426012468393073615909576321025741505026421645533393838732591056511844737706960112660019921378179918404266875005169348291504075028293455797398913354354358236187611280377035637963187204689345464665312622547076621739755319886470779891064007934137197391592675358028254318219282617597098481410023159770376228744228473221174273631739105780931675401256051057183400250598539456405778199328403194391681769660990160207431528515175797344886350377910977714590648261267426445333554695610678138461073349223637272166994878459663622248957457084623607679958307418053770134181525933900288497736934167311916265412748871228530615277532783562436165254996714738847863569008389652355903338078269712162639607881431473700601658646654574308448562491653371585072382615808128519155444314676085975221192138466525477318294656295910473022840628140789509440296942919775006557254476949007944884844625421845764823386445390270409342734177011985422826618847969164198903274568390376711065194795168321317775914250574922037937764808578635795192793362669557321409552690295409077256726124528995375237467690822687318865125172484156221786557935677293836121246022791300069670233653725244782908762517902327121928789777222948445646958298292896318284985954325238186742516560382856627259740747714130173272763250170258022841045044905598918825927537945198178386636070605295457601549428516988680961998545213082998544719515350068725871245286712983970868282313445287044566449833926654609161546194997905676509585604840214492660099149889571849685135241083971578272159693976637164212085308616681196681119586340924365752469755835258570906131650228750519229270182179469831356597800752896515512424880394306391279836894888917209800968586468936369275923765386930151661169459049243923756584155949923766013721088380031144561852068881172188036239023974500881911098589212631089097003200078602419304387229819764063129957817111421526505142155402988966144660534183428747974658907694791435166877112219748126483958448442935500604325230982806987561127894583293317143991939910547591346357530419516397022892196192207896194317175937725269072841541481985909390127796012790957202625569642569269477174570583632690408715797143290725543243553310361899461971027930738839857154480353700735969791740050242869530358496124420818277377664145706305942187271083897631814122875614445168985087738582815740119693669995464675227054131855817684684389834813161403883520072846618238477726084340657722926413551146122958022608611350724016646624748507881496621096877348678922947285439315201309247377374414594511796149063693320420489118681103128699173041281466715318316240024995099174045294289942877456923284085513658678645043142229384914461588628634677926062720631844100941101094184060071473708524989688857077330566790297569369915230294387936064653193292225972306881466303831614285440923124614860771733414557216506115409666623173259916935960593327407880956823841628009732195485836145157161308861926395200459959777812239144727651866528841620625899537590535578661007591713116236266332312482719011831936533901674182519077954560243931246859471628119389522329854658160699441951457698648381625707638046289394042121447089961284810647096390642744271276898921474371239967795609387197816152426706389959710922411349604956304472289097558890833233470756504312127761072899618276930876986652653205066730165614908404570531747139573812599270897587441655621418075423516361149291610302826561206244405381091934142623376477573519178889676739223927157970775686599987682816564222736675622602717025651502685885788628465377775096899270162383671992059208632832017156129200540818096982008665101648488404593001381210909041493469867635810044639022468978353034593066838369625804231811680672358735170207913703070857926506698030269029905787279940148195698781635157003741165282763918616302406272734688034119312339744788854360143705387425700328465241609275686070012077450548245762097528265075680197763922907390992230398898204163013654294092151303466984883199203344310406597741852670897970073910505262238186972979923029573512718276799092514990380888205898043330833618813475891528142162567043864551628866171663511684257108598207911683871612077931452073907646036957003821680731882053162828678626624005653162231969912343153674486647921040284210766859659755522105136019562444026973964745020422474264840712198373627856728129328979266070783024021715802991160034408778122044336685439718829488117901570259269542040790522627902501980801562988920566307827062326032660985224258118131067350814501763500222823290076851169190465828330373341917593976839769139014999584387989946881889816680154846072781099268183561805000412743812273552009641918846744169763527587221990937054600154556937791004344548582553684955093756826844218384293765290266217512555010149851096012964158362710291660359141464564889627732556176247900323953615103910013359387027639587439711420523177380619024786018039997845600236890127898422711825089702102711088835743011790375748612286190481021727729006880019878076417267324175424642922397765868469516776613146680011524689768043387144951743407351583463724390592861797185953113829660269476956864793251342225322561105025947499092886504274206617394145280749657693244995065176282340809110688125151595867520556732869758279975185492117402345680057086948582723336247785677479973393224488227549714816113720300983398126988796486693737399562411286223559007892560461164634343711643657634665735243135100709906113407614378694095092657676442160133143079680969036459618363746337204971479998985420166897516406880088341129792258926526107249589196944832984562238734662716561738927112365702006011603541522238046315406951389850354469428289320186530712153087623921705237070256859620813121769568832163643683903191382618773534221030719190925042388378577306345456107284144182986629167224302563263357687518320803729493724373102214351355886156543484206946035162768767886675539037508727291407456442425953152853840229739132728337764328689829594461748341956113120950362977608170308852673426315862149250390255729634276360037390970567345343504593476814545501005214924400017355458083385988809309028080979579145478868030946941943061379690839871674168009002333857725397257895889747737211789372494567049513678475507323735759575217999827200977719863543895399054352402367252879029639823037997977597210294529975182948207022144216626460116432908925050024731492413269886721634953955717127982286272158256717204234546211696727426274990013771464199938045152242901861472214923197819063060792546811438551046650228187359693304053920145663247211123925472240497427964799378925679603896987667881196904264096488834848400317720188115983223263972957086734751959302268451277081578714618227519778588654226867809231313506679398354685000765275591965538215453309037545750911058263966646752262743421795453467082621031150177783679550747965635590033809152815100915127507064768536909806294341016282491532660313182778102367528181542531512274248295015650939630191544464621802179541081118054227189125449054145686411174609813917574942349217681143467683795369695729950926118303817554515227848937102084082220857739454277205159413404033767028782682442955674865677341155162171829298001460371753648884123496303843736107022187336720257849802293587902096019203397559470937182764528004222076523174995349218145175080819181238368594068788739418485701074069424475502698137043760136862047588636980783177325739386702803684717124147616063764595209828303740863455236326120275934024870399619395119965295250758972129785944781415970624356290685224018265354066944988046551704417857404128223323954489851738763028822121811954298029472558584056095916247498026124548397626240444636595492818034212468421584380221647493948293638546392431054667927886261043914159140445321207542331504545207909063358929575155140460502451696997412612652012777879504010637489637645119238416726682260759598279918164745412169515122228561967729394395062471866563517503371664882945809398284842465969132656176678442000423705627202109071350004199402164447244694145057511658192190767866849898892362529835576750234327751315582032033081615533858186184606684483856562543625122293474955056012654287601859197289026041153331341734696247002253671813583260286022124016448274231609369921538647898706332873871995797329009155109894444423764875631343187336763556910852125055635029543077375008757899991917804738239593224008083567818661963997110687900071295386531915750909531529599097110883681183532270364397662677523309101810189868750629380416073599009688625958151254812555119745312012304609947639863226943237789467009965585725673677601220706093525683414325381009799813192450915176707999106024693462344317288295322183173622689532161481545785164863092121863158166869870127730683708832501461473703560512741121185796349299036570723300833978687702699800956871135467478750260509411230354605862406072485061927654675787531032443138813720405109212228241835699967284612114082664241341631823640216621852596404716728447594686506381731290919759060844453262358686084364481718118770031693755544760223967586121261322256798616937744935367750001141505397799560186103968495188918347337516334119630542595915659409622867770896379807418990977602000193106323880342340854236143027935076611054902151440240481545029346463582016454212476497995432572194968824575680699316769385006293577980971274526192684822419520299339657220883772445734370720517868487852595430347307759603526442764822767777078785632160037888444423551343097399764440851189046583560511077364751943463971526932329932732809183119094258289732819113180746226874781251781061371224191146291187374548837027802496591521546639858531093599297958479686764394119041386879063454774193822979280021161916927769590444271395605314185717137704755375608397741377929081425604151331741550216779479875316826587705997969661224598446742319540735685406846382138951745985237223650134997872132128724247919204436628471848112878191972593627780443153032789889135622132753688312725263899045354128926633130235112694160936992870452715717812162042859118584324575025493880298167142388524380087256416927702969954642237649939726694108040913489370960980096778958518536822301520162278079124755692731745928278962580825151051843025475671520934935307374837848745263283451419877719392017994743635017710377896875666525674073147338739641311540355353992252196831059395098886510698833235098213316081090998677132781323046021526548929658234882190617763768003184699503519684094229857417341945028818634298295546830646487758698075597784291740353696804335603823774906967230675848010734409014935533167483581844864089284536505178730573402005991795958055116727501036532168573
e = 1000000000000000003
c = 45324607213868303658887091279141787549819829345754618933335354441423437476589465344851354756322769667266338983213350175503703911317359688842814922995769751457641729899990831131988893015916512215731819482613774593958354664832407005431300364109365958465391880333045223269518811880311835900113260455940796802830841195747001799448745163931988812689709553521782670871068728519612998407861336027589519697206893555126128661283187660457826377584514040917892119598486133189145207477822638296970511353168507066592180602842786124528189958862269078227090008445367249590684266002358258862133394507521208556981777906625127620989365498380882574829784644442948867577383265993941724421220000430618613882658235302520126973444584427702628347212944694036118005520727474609871875909887194563754779198231690843020537112817467330892106207606452571126326908274956585631546732310081384257079668209000915015572596108103371602320877845658418286811660695099255201904949781545026450198019517929584194302218191955876251831056383736695382955612517319192557639305844950368005218817669001961832970149986214379810554916920294438030717574631567405501764299433720144721269108730891778203472499420491429143872762390722608414101342599191273382768263046221658556334414147093401425421941627369425252345115687681780995204048774193784044172073149808650945098738586358295362928180423910405531802645782237318807978469932205990058009464488724209527047497558919047701509868407487554531670491417609547352634682512600031828562849475520039267512154455399277730515203638131780465930239495913630990859086154020698205089642369078017585541331473610605657921038006313756564721825683167780615233903703706781145545126854686176255100141694952362588843875411868718551249453433650974962245168191094192879033968496759215766131795216061613645976995265241474907354687896254294860616113466402141620214362036014838676320367893372236591266919365918370195481900963657437373078325842040915865512186882336059548084279060390296349150744481258926820266482131847789387557610745337237630065706725313740917796185465455166273336660366016826051938068705675762499424541741451728627381226914464412267334496314938387819455429004435660998530747251126241277397041817656979495359195410662855532527694428808056257333995215466530196496986027815900690185731262033441832899284954556000826518322127786128596900410703670802371980317497263627711607706578694702353797397924727040188973089778328474155290777842067715284280995096519980379826992043225095926438443281068576678822926707882154042154775662102264617928420008274864514573736830328156252540409768172946621192003062434143814456179762799772810448041846086609689493482724955763301634198718025645434976840698434821336193125379954999605684198982772428706583024835424713579611184032246171210971180466253004838864023406517294776851422423335908050892822041464742811505790666525182863262748857000627142696381479818165204284657022708339872728745873321078031875089460766312436489547539793011671411917200930856141166568475031624596558200806615535112714580744598879293003934035085544375357095625192552657070994653543832969321106575129754881528559956844119940188623818551964658334644866589128229220848506247206422256477509509882488551312873221783195215706858853604314043842870112181890993032840920804922712361260921878027415465408808768283878642654754705313207207280903630427995976377265883822532042271140627730644532417161066127141096371638800493820797147368191348696496093069027577088051156067682024185786524942892022119290543093645346223044205405000105824194315945388097625413398206891776312999801022774115880275342648738873051365694745656314884708649381408665075838045639152391476581908919652986765278351805569359315129991505821644478699624178362931653589269236680907069366195111097923725514715755078689947864822244887335457130029361535360691400121343729449505840570169365054849771783059148673672894170215588378096955968511528023883004927049849838907488614810196812208353018455861534857479860802966545964825329570628481585490884599949048162277580598746276695825939734580347163280622987820466809995842140307991197162054150128100339598656644707086710639512182695973553649135487179271700193233086857818286218452538396029300290729999883849939377996745002832651666445607901975449092880850499245352961220617637678732275053199602804782027760706863699036975523999522929925012967205000640104660638548244203444891752973063151791822525051505767062347101866582590146095471804187037501962128103896380115031526858509584089725161949355749440604556151485144296334827757291496310122281390234735695459009677929939985362307870118801023167252925237715972180517913635891453975317410565481338139270032884687220489662858933147655519133215934736325761950433749057860085947745639901317756753155930621321284416861148309389411587385314028946608688560338080484200744527598878071700100711162010434593177790667680276150715818807290973379189926159263338066010811823068415649802791148598620823170049414777284410213859780737170753109694091113347570639630861313420016682745987624631908597294112010823071406379746990586677792285787184000822625851198885986681035798507093085845968628968353145510479037641958008603924665035770038668071694238473885986004193547176239933037453864250731426777043631170439205106615748051061036879910778462168281628300244050482693271595688283972469307966048707090633158204558569050305467674297779239813668398408103715043523401707698709565952737954090678296795444060211699680113120173809187317676069670491087720566777164689909174408721879740862765833924363442724937752349596211819817707984826212310499140034461254417956119146575194308746238839022950629266722881240007540758664834464759840915592366601566391625246208753556260240398281651284301524152785999927693875562412016370290679160777679448560961705665419472435679740547357452242178361786662213189287574280405782862021642830528851676168570356778347006132931295069895099176974181980121997543207299095760285597154880051708894274199869524567142243438973181100437964763812718536885394329601294760351773898808768029664445850606602095541431883562418151566847630598610909545048619595375260734868915294073634123386456131992422572479074825343178577556876960457167480673200566539800166463851790971659461761617392614999272183417975219074653679189293954519840800518485822124846776424724057105201543936927761999787727543737824983666510138747648679117234408409556635181431951042569950961337683959591787315843210812450637999652245550213454378173376520354948374063924905917282455276928675201987381015088862281853330221172310660389445649223723070200445354351999543421504673395982782626439615371520066182090831657332950118533277600052744761036765602478183354317630136601521257549840951585899597397357772191914413993048144621262471483149238502435396970058570175785520153761522561300715651143079999615839498509453517052537882134602514694091708971201370285605948996423232530062665419348618883210655907548636770562443793154930202300751964718365508026348310209848502390758431591036773583589592645689438381001967316104437732805974240278580464572978535057831876388630622914198577775828884019814212671598506586431957341700493807583941472999686554470685398591827322072565437068350058426127201339472693871877899924509178466766367161980955602787867328039295585699943049508057479394624966866935481733065768303678565386026800139081214595535890660151907979118108775139777056805284757977158653318895887786696603105606490612689475767158238839591773523100635794768984807307252180876235343012391683844864222997852537959612885794781335310771239228954307257298630491062792242695355295254416602489828663301138246686950048193226307090217612898203498621936412045956660228472937064719375235449316445460458994497344118273754104310656756885073890598898123760214446349921311578853288589130940335638490688531280832428803093191202297980791678647378948898349091280964848588181567038455427190073366823983906599097978906852051417602015405036473482710284604021894877888199171003727196499848014492297155305593262253169624814130901606463519820087292030509493722775327743807601978793570732011153340690772854175386832603451624930535699882268963181033278863378726390772054080544424077011126230273366652452739754940469888555252574118065151168502601122595231882483548687572630021874207633923309668780669649572073732714638196971246121209515370193344191810704720507039997479926101464470778441977852918618861463726329621066164658122253689300819912178062105905729505088329754004018115303787779488900542297862778704660383728392356921533574117635277657907732372204703885101851863087917182930537412779677521330257246581171409097290128389659162846816090988896612624763864626711461711441874843728615853531167125374926974707642115388054075591141511255032514753410343581463878929889781216825160575683610025199208827269120327455880441546632290908456180260227278384161056102082552975829685015966873502002752465885285974693230897831991144107511346761057852791382760968714234676840392710497536194661288008941577359669386083025109981587769797591250370323242216279533082580750530745166491512280906105788863599062770899633090204881699816491688460319232526233311347376998263332917792041507031392429124481651145401743769098916586353499673351002716152807092193333668992886832070007213352630680887639291873610058217966832588800403123198058243873294055713497877335500799895860110946427535417021565782660463908517502743693861205480920273502551323689765822200153423939973963029891891865584361332122949346784583218987607405956333069688379529341881737514917774040674011986625295033307356433422798603313115316044700609301641840853337032006776837756436099893760471148131474150131220115545469680816054144640259886852541665439789858606408173196624214591898574266661199780003873081876448915319953767555019005368400943035709772313117473275600225607154872079829199854295984002774449932764041168000535342430046798245686516166218438309654672031304478871849335535891162344481459959370297643202031899385364731772237825786771336545886834683993773200762403737484568968168142470011949344735132247173052372915800974130424304062603603962382812845954526410833019897061284115251236641530079324035208156709870725765966692090446157396420977453600261223003596095366898031769905479543507787990668048262714877600885727526747824848587053404058750440924094567978090892789819540239584955090064245335846393140892230853169179497435523710927844940216598027432047649715109825924022303495250008105213672642057542550204011980827626281151022351514049546135646774258102694427282468407464445200529741853724562140976029045264974320669082239848779858981844924832633207394243955908914631376899512051533434040593650788172509051306101854628545556189752299008621807407902882439688975294379265066484952606977616172765688709006308238860434685299221725121394192126956304856984441209998601179220215752019617752891685764862193962945932661876939389968678267571681793612483227915488035615075582310264754790335901069268374380335284936828635704777163175916050844851287139452794904373068833069622033608354085699493216104177046288571192668881738277434987287806822800326570374110304765276653802388169259175186897961429527819281643500628794507076136842677595720351050374974875331733312833103065686961031390782249402902716639981305734481685868064369349796221175461890259578338118064793297819478779969316632481155754454884816498832893361167732738767529707663601578946028408753294070117558779889881651724167171448576452094857753037547693953785570682171350982625619072104715056438685614573997356620996608090418070121703593782388147734815283121131791064659773525670402995338828174071216287577817645684864662632557316557881572766715234449465721165051616583839578681748635903608330811895790112547484415497417469556466300450779130829717795802237592992767440268618004721160399747283350064925212494455797304081448284619918932831381403317386945769276152694565336824434254581676822229583153688545426405167824538091481181421938114139183541834097714803605587393511416513109288274889877761343035195183914593987637900251094393029712127564369928544667311068117898702236034791279463820903510176042774004253192903158311457896629309837963813818413279712865398324862742995404945678036467563211951562049730802191186293745523086785675641053878152933567739328956084217997751556000052940761152707718184601555418117265272379727698403983881814853489515335949061309573056755573813019946429341758488455831854846444838301814078787922236289430798194882498741112546816349961097534481901226619913903552356842168048683912058023509318747608466260076808689349170245291071589980886689659843785463720579696538739725242775781031656374651826112890134005757507680894117140838003234955409010706800864980860733840894955836531466975423650600166732486449744025115803195603814726436306572831227575195646812949945999777843654721127912289419617596161081163979974536879506690461641361044162770081579085951428938887044827928000132808753756967683408088845327244130372340812464751336498887027176913457897382264637765939827024270686780255012184502286357440319532060283009570707669381076827686433910649020256430235412532396329641699541894289812295718706444688014279776067576200970238733604255206417870128566752422354838291119467323173781367026579466584998412123191972675342997357978170626272679341176976324401158019588121291033485210215474869899696964467743181163453713580168579438199654419933681393982512940934419100693839874866800846717967575226403458074997801046907967140061091008056281379725810954149363411591518907224633334239376413765420467203359911365881449573680012335008024840216783040891973405757466244761954951379311964037375529016908027485465014353078941470756048478004173829906822911018395439772031587299271158813583853726241167358599400889819306498746165221555478975295214772950609316970659926291484964575995922403340802490451054379483123228374769232776992261614534356943021760206546554106805694212326235525596895747174215144361471052403392487182701776267666821181834308957807128324093393973565837372028230964297193170258618273897254639951499412144731232340385817152360126696878699637479429896552914568747416488285086985444765664256728116847821511140292939853438748816527823454835323407685456595309585626138162615899056199781983517144436286961749398296318025168867351967375296462118444457838930048251689576036772271503576566419891998744557946075475658684583876543469094385664627428477823015289614766637033282347375476810272640055129846174671296516342278287310366594684931063091780806334566111299191581299452908570380933320523133523063967247511114451132198789867835396068837714721354145650515026928926039878389574217917526863803178069746184018941795631386458213377908650054226569261549705558936090204938834488570415494923580202733745322200597258902867248161462753202288086416520335837275783886706950989886411272102519959661763937389008303269690275417516464340651080082438776630908600890216363699282343048789426455610982118866952677202755766362605779533689369975685288284609968203956431732554844909161759540200352664833676295480954987778639509609624395715022033847685870104151594000110128521390734000879608004802855276340324930813371903661692668786567804462747992862183735563075225464467327319780134255659144489074546918180108970040654574081597555451079567429299912744714084798986878422601188126774619464010368166702825801476321689216497415290866452328985100027480606968119775684000527604190012730705965566081380627291055623337362435997256808010993799865941030589765312200468325045342644205371445116753539351425056259546467848350747577271120474432870109085249484301580618425913575175790149799445604881366760533736470522893843057482145318772389064658240274976794338212882773685176628263464528907582249054807859143221080774398566197631814246489480834639674951496099653835600702422140559760767294627132313927856896174075854615263354868192249447751710622319216155142186764014310510117812577936775462960462203698383862785250932291749842001936693114954160690665170851248624482237417039411457075621456094956819066437057776690919692469227544849148770079074373553737659241727223669448658040172175406532521773948017506221576932200586935167943706239236995863606200701510944943405768478415963768020504960728963432780953372770569202249003810606382450600643622454425306999883005069261561868077549685628173503216071299545495012412085136535268995735237809904683304247889121269831285242358571246359920776564954317463520588588713415937095361664908608175260631835055901651512789518693933664286104440183132561572685479714029347794455899423922485582840990160878576004512700680583368524263721453221512258265044541529561175474819919630438015018211635138503901764086885067165899208260033382912257106500559699339840753500711101225554255742454451854539488155034203032724785513364972218296711401173819645818056672700954540263529144956802736408793681958514720679451932559214742736843088905950706898558294561675099300039267556561641405757071234950253959542927084337127707201269301525544872784604371897773342149435172813635804362109840460784917396060084877697464791725034564735273115780423315413730338871777205802108398616774657255176771352534648734227903977860146065201413966637384780783294566667709245325118007071990516760510354414354503220585173893192661788277279907043103535247343023355771413027988477556276660344739418956698942120625153425720617700220711820003006048254209416181509415374373618029633448299348937261890320331841731298825116941762978895788607475278858604199478290098485237038738625775366367771098258985927116078395753660978376760642013300407670340653962203898090033385810081102817665481138545935393777107369021751269516850314009998282480514220280501366449801311494747089749924635131479024890687450614490350707142100354583937891114630067105391109127516979897510154627590765452967386110987067435671250861669044725582020494475276654763330321487639253997333729709638921816351481007663149941721711772751113994178106208929179127234970317974316375498877958845246668857976680813941821212727018097865308789083039273864744189955944355942162400836766006358753039401193010076207823432944935947549371544121696893297205096014139246553799776937482564838220273307535440345645580847825870371254148143531758189126546426793447076607150222898227427399366218588211827277230328654643398924934644483806741437840099050074354439556010269513786905728131911358765145074561319289664039614545200965189274418275282358553203122764496154486706475410317544806027088944475117374986845878281308378044146237194411189037636906125299369324138562113407870756288681082283375457965240325363136749211766035742366691556226861127021526119569287081304954186933502102627177227253719618005576862624867311581661768807069235216268531999945692328074301234123603127189048711453766072708327305154810169944218085827746356625640644111363079303498906772937989606697914144163921109813871409686445871682819102682308744426938009357746469068327129486208569013510121783543806670239242155165216683255524642299152572848311587162677012038609255266740245321758232060062489477166097049456742022891484435099945837220004748876495806406858989814820015612558382309717398217965850533965874434381845538733338447877380957139945789647387299917692984540722162956385606141860441780158947785756164834269456803514049182187287047562668322651218651621298596895736938099340107554019973829902163699632088874547096401419100410418718968802667658476196029697546227382281938670816136089726136569554274222460357578944873394329923286088641897503839034158966034026574607733488123584192405698062757151646352910813491444273292672638711906221101579045877104559821881038329981367084902526475930137748546077356047589728421117114092411406219534714905086739248959912966010816675524389464861213096578589854715885858411153524549166228515227267688942129765171096464894740230762370977923676604367497950023447445464729020455331454285548620170388645715308975704517900870964840422492693375247640182404960448384014946463047422110283195472380960955323366943176794863102620905760632078082331956656142303006419612121507462995042193028419338919511896401917870954115635500971969802335450970918371479433075802722783150137614775877498625519316286484144612862940820415802691565518931544134408255414966834892387769735305022631948358390271338950791618710490048327242236120016292401256085168617801586231538401890162721058316721607436380929015403059542128475832992966990836851878220464563616855755563745308292026205438677221100092054895635661189281232308856785426703400442695569371185973858517819194134921443165314964010646624011744278202475985408475039453509908721071642429843271155798136535338586247314077935068674697546276724808390486634894403938427187016780645560081112662354223385222188281781751526410202039416643060918784987925414807829623900793083824669411196086953323461167472344015721789425987034106300496153535245958030825245816350644861324569986387724915458492127578378085371923873619536244138881015641635729322203334703735457098623898808838830687194677730871303021303708218629361025193957311667164050831478820174427792137597083101041235651537538775683810586603350819545362190025347627483284411173105594742378524079611147525390303746264752986753349438405038356550666968415307379341375638014200624624814601245610373049155853005706998591087910772753173465273365749491720825029247784472051177801093087890009125369672356641960922005318553747050113571973648301516520995252516082423687907452462857729290003394593407276085555974094000650647218986709628905187873167939141111725568180793634558532614032798571990357415616897678605168597962346190032874433627354279001451451846296140024771203293291460752724499342815660349276143297482528836172111313846958200762532145042132499803462025443969010852820047364380435431967123148768232200205864487928115587768129664131677974389920128117061854831922980069275070713081259312873714934797305935539225101821295792306087131688905227640606924104477822099598254999176263490293839520509720450259071422743605906488451960771871715504635377212175684405685014564934680740187611113750905043983826426148017232265343788361878728493266882429380042944771690106567530064911773272257406536258155276717646537146419060128991776093804196193720017100604224303302979718705473339424968650587694164565425619915156845908712598956807443299078245847276033558873810364934818960896810421384859900426421392813064041767546160572656704077668912368730451367607441306101247153750882280332576403644502258914334413776513104937838156888008318744088849194859567287581042177947477060138482452195718335628155384117734797506891277961219147793082842258184618839741476519507246681072453581898205362043821984517058818878478397126357619844941495923303591396241463185925450370996925439334947294472303512789306175767581217193257823431329109791411867815496575435633199703275084613922246441165837588850833510793511130225889426981436824962584205443561346448900103095940786749523452521646148094947881146000460776814010767755891084581828249101042852976039978709299647595363355176785446150608442854887698787383510407502381373940964478618382286916865153980107548517588932835992063998037687486482470455690349950096650908305803030993151249362974342054521159195328731023776055351627878647783235747022115290633623906562639645867457625476771239104980901515283152046342916550070849682263446745591323512613939737386702325554836984215026575010407863776154330543308326717550541340182603519894958120781156925603219376624657729202146854434172466178697142563916096334138432068897347574267326372971454162386713302340859730887975066470973185744739521596999815876418037879191460474833950131991533970112405639917130585649663661008456422312314850748708861157998480883072315921223538342701228221958283621386068353073850142385379747935686296104993952233915693785331110228399897326406828454144468514181302292663848702069857594499966154518305043676348491221126950175868238898933554473049595130033370576075980170674485761555803093098859953137855704659130904172481175392532192327698075485943118422513913507033016503045096027653479981165000473049082033263204085594500096705554591126564576238270356070663022179886585634647243948070010870798392352789548289916343518186721735220854711629123582058109793435704923466688688826249909598009968856846574286691972647305839146910332796024897449372835515588753910683326203573945859042621272634094507475552748089328973383999592466821377846255245357756368836166054636027621011249907229644105062608310408220348228464517516573843182085597909981731207677838472812592982770523010716137246633676338785677787701125033218709597497993304570887024972245481917483474895607911011374882546662076088903553025933871770579807364334507352474973775718366289102038526917991033926475768330481838289474558880688531150121460979254318601804187432984184875717983520110713828597691570926981803952582297008456203133477033603243702419555023383562449883609332254585673357735491001513445685258672556499047996707262644133656580526619072464780479340306942812381917076914782780522381413692838469358299754485746234211617835217036924841689944680966938845564419693492947026409008988313864746938114556015166861857996974924634272826032223141074611805769467633912577151427883483936526964862657177326251170267606220045052151925099547796609177140513960754446728796301847479130723847518167838922252493336323380342425890922866093392021084401151974088252513832046100477386203862876501930402750383108899816748872321237931730848356825650052174721292024995615684933090345146589365287715232523946652445846478129115467867379632299872998989446007120321258930099697115279057215382416095812223993361703578755948140795947943637906252532400152258122673485295725475251653038530662177152738494912118118998598137537763089380506979634319399061186232914346775072295327527873434099298877508700719278443098025418222855622882853340509034325528507658875583553303796922707302968657635532940149879164057508182803365632775539746306335525827875601405536215624930934940881831841479973139107320998784361369752606349475814203369080108247863539595927192111735226163050752431830374306691068937101953113083909971207275713115097049215090202544781618012417402492863070126149555152383822612695551223569656009170497976215324967263987936821481345522853579228551934997561778699843966425917454130582801583110323840813773698635128449780867634611595898559373142524934021419637882411089113108771475803593725739288528425192138107771646783697330484787176941504646532358743771734121456986177310795999783858158971145503212611845433494448119094821486588911873545453265628890638880707606461074043340900945912196285437030972786920605855830705377550615846860695685889746202847845279342727185230229241845145305881819611493473956354497761452170674539198783039777513807141168644241192734723864894842021175427103323477858852452755611529072073215343462218247337918111476989836578150939865170522178034280979287822157107559809305499771415506507669453222734929068700162652858899713039733639200589471005481938283719882283202647819167036029619468482424271789995400866433190764638722986171611637134212570186046088186286682310769294492706753552333510838542651030548050890568212369698268470777688613689546231131392344977899780883655128427946262345672467916176675894565420141941079634096730168470990576094694813850335799728928353332613901427091661947510769152815184592872282184318115112899171765324532634791120156322942805728869276730811091677837294362595154578601351721656441825706886251168641059582340307388643148420198769525738358114636319824259894237961550495994495977397721810910949699717992151512979761677519560050299778569086702835484595124199318014542216443145308835676120467480427578823510815330909662897228753833347268713911258523129583058556349828926002418272088358299519413465390963757413814798967143142944567191656357535800019609492338695750679692431023790169682093706905320443416336721570833110482751678125495499286458844526976208986029402418088661284838029631576394389194020175886014909856442662159574562297499097787148913654335850971714564130212892745055722535728293924315809004161033588818228571863336579736687248167707586247735668851282399010442627596313407331253655495129790049539080050889280083699572958394539908971379321136890063090238668303024932337970371214846607690302432433901704216446323990310514701306019530236860913821809431877740122083707407168792748364622398903127862418413770021666354467142527097884513332813169996010478590337452390657540272674255724585089702068751570363520276984235790039114007985060253154084203530017023454465697658696130731057409553524502091497095638700875084267443455363707041915949516710357201590911166524065540309427335229253421050942135159091293390819333487058190617345663060720977481091873376588723353942359595949923364175887828091601311346484940408444845221967527571349058726597078354863304061938564730023199023442183802964372619712765469181204515710565497569032059516420778047369063039443860133381187697268475432781564437589372920682960293828731488594989857731500929343246970142626757813017940854219240012420756329078254669066935146457555544408780428181135301717827685348917420387687908801862560624152740871492925557372832737526685900915944147810509822318519534681489874000758891190424238023944818518839521396465349565994508017659357192900467513097466388311402287510625640437336095967069846710694651757589666643020480964314533076471897510280337933655253298475814214742686472971491435498840936239829313562511678246249284583322665153812745929815113000929995452200424460642458879139197985040821662031080903066662762305742240804133695843055015971557614888156587995761252487785922889732682043250189949153113725941161706347095415297752034102415851062536820036007305576699784264553937673493051794999050553021746353199923725754260657170207524069309449797830671112240865593629632756769451907056247298590622958889500567815444553515379260494468570719110648529413847100763193739845710187056528431694152708886058954555052788603962022932228845610869974635380173704184706827184335973762360441437458019277985463340161848858306660707912219324564269477454506185706784538113612633836342360303695957598545629756587389970558272433597687009362215222270991406450401738557111123762517209388229174096464095609318638211110920564061493746371944049324150043635029334394029256821957625152060168341341432420172932499775170208923289173649830803180131127135988820874536407938813466789318670412919996230982657601854742202864247722814355196533526495526938348517831673928990447727226827073042131701074248226136145989748878890269089076661306179086224649580407992574970976748030394765916812731624685920874536458240702787107049511623039688037323494700770407648544979304489682154256238014145665028402076811770640608276613947243589710892587311152058430231324053601915326154094028325148648562827965479180415676620403987157491946722482675259040613200460527285767070540303564430546362365395847280601578684882340131067024344007203825154601037717723558841715041300168852840623437909861358066562408381233195662944802124401387778808917301517136051776282028192498099819468154280085675747749316839881443535199881924482778916944376763274086828619107520462881377466736769517033795145369932882868991274823785124636810867433043584559998748420587333255423618958389888582622952768650752982051316618781561715810195066904729635302076613282498523282589238972626274256592824835186571425509607002329465476209420245056214193581456686154130338033633462610906217772987862597469659943251706890583588009318672432241534840174000786316311520625656053754039162690747199345897242485426934920143858126438282984709185128249930341077693596065481707541263621457781940464982204378179213770819557207059381838915667596546435981065679159237782091114932448529249932249582464262152743121387597869990060732301116213513393088105801880718225910486619373630269428440666102340313011437815305413415927669151411840780975875205583956593974071028469229486788584917784134150290392329541586035383330544922614321910441742067229699589932224640993310414336278413373853486911656209939576843846628962696185490891225687329974095769786674611457666495622234926233237451893898753614563238564052859354163992184000075464781612780937025019696940843591339439006052227931841023334026388346202228175214802984166113099062555555052085937412790931231334428047451726132935095039362874091317404279233710496853707667634035002188700230516220732768859270594544365009493599599436173234656099411670043697388386076943374407111330765239860727308572236797800804427927928958292710356139066892013516698782110342454000773638630504719911986813982735146138369991321497485494933449938199206165892831095421752607787462426071678355694223197739611332224299725301232710398490389920820145121529105010713410364567055955732670617806412203387722706711769563661090390481880578937626690871472969650283114362481847113584424454283218939306843355174918937410056560636383999275850204909610262906897405770314368114936884452786230158369145768200838904337003391438006961826748769055796419362765796851362816562544207131092587758084634550439899649917509898496992807940742766496509692563598472863156271266120127112172303878627511502196383193966166727264884849301995712654903007957843217870022674035564480430862584535394591069160600748424079714481097687064882813131370321173177376218410113765501356018731059406014854930748436797768169887371115353323895139355483818325985026669752283801483019901399882072851667105122052332988431459152813129089
p,k = list(factor(n))[0]
d = inverse(e,p**(k-1)*(p-1))
print (long_to_bytes(pow(c,d,n)))
flag : CTFSG{mY_fEll0W_s1Ngap0r3aNs}