結果

問題 No.313 π
ユーザー xuzijian629xuzijian629
提出日時 2018-11-02 02:18:27
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 51,484 bytes
コンパイル時間 2,319 ms
コンパイル使用メモリ 203,948 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-30 15:40:23
合計ジャッジ時間 3,545 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
6,816 KB
testcase_01 AC 6 ms
6,944 KB
testcase_02 AC 5 ms
6,940 KB
testcase_03 AC 5 ms
6,944 KB
testcase_04 AC 5 ms
6,940 KB
testcase_05 AC 5 ms
6,944 KB
testcase_06 AC 5 ms
6,944 KB
testcase_07 AC 6 ms
6,940 KB
testcase_08 AC 5 ms
6,944 KB
testcase_09 AC 5 ms
6,944 KB
testcase_10 AC 6 ms
6,944 KB
testcase_11 AC 5 ms
6,940 KB
testcase_12 AC 5 ms
6,944 KB
testcase_13 AC 6 ms
6,944 KB
testcase_14 AC 5 ms
6,940 KB
testcase_15 AC 6 ms
6,940 KB
testcase_16 AC 5 ms
6,944 KB
testcase_17 AC 6 ms
6,948 KB
testcase_18 AC 5 ms
6,940 KB
testcase_19 AC 6 ms
6,944 KB
testcase_20 AC 7 ms
6,940 KB
testcase_21 AC 6 ms
6,940 KB
testcase_22 AC 6 ms
6,944 KB
testcase_23 WA -
testcase_24 AC 6 ms
6,940 KB
testcase_25 WA -
testcase_26 AC 5 ms
6,940 KB
testcase_27 AC 6 ms
6,940 KB
testcase_28 AC 7 ms
6,940 KB
testcase_29 AC 6 ms
6,944 KB
testcase_30 AC 7 ms
6,940 KB
testcase_31 AC 7 ms
6,940 KB
testcase_32 AC 6 ms
6,940 KB
testcase_33 AC 6 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;
constexpr i64 MOD = 9997;

string hoge = "87083019341285540821939937713326225045727691719339473251200184948061896065615555873143053470014810073075149693228580297652590971629330384158067021544579618277599565886807253424379716799506540753158775380660993510532029102415648640241526585917304388668931470375493690649810897453370523644601138306800841969036419930047546484760049570373217823279411652514511662527371337279599893999373312516045568645062658648829656482251766095946512591939013721446997166290952907987875472076543468716142656834331066167942943932265642064873583641461005930014994913633574503104152819186681308904563375715205676034403811685778947756966964777236099138938104868217347029544385031096818769465534448450221856405940974361687742725435494193054419136865893363337265251011308162752091309330782417283690026783925814211695110608720297659811259582165268282550785945096383306847621389011543318937072787026007272724956255316792691135693365405458754222326077899145432803756940120018725834138659821495382176532995263247853652989212840447664602569891057918625663482385533499824533723445795704417065108334323385060316477885106188443618022597254296078832792080054864593536800987677777721802089381858909373555947131624378238719610722884059042284003745595552268679370760265664923648260359579783322011007480674239371963370448971458084689239952393489902171826320236543689173796780890935917035231404878252381687640743788200297571323741060492025385406432759563457754094579328522720956945509273056248269177734985960148619092228067768782182001813977852469027652354976299550781041559708230689745705003084503578904461672926140997045525536506625700997033914435295206016361717309638465123005392820011495857208181274133128419067725088465081184817577459314620191794088627817015305413549587419297700905582655525235584122083028763398864514961370349049551545652143549115603360468861930020038576625009789065959641526252238085757604756997609583056454556034199963957483272725324708262738929676929257808485967365673732487549551565677050307118694473846159239166940333722130222592447243506621441328286650253507905888551497699299598560198987836496492631255245156396021316849711179378929633440867559772983869879615532191412798123368523521537805922109052457760490539192695202799446738631159033878299567228069327200338723054790231411516192748841021207636038282576843291010823009328339147100538553975146552041150326212216876142041215173171482296851211145457178647861997020910241388090173184875881434992929292872026025044253807670602429750918803493071371804687665751508423906614671299752350849619637746934975350155191506175982287653357708372525080368283191452313744335070617645985979622032754248728529404437378972067292227934821443176952365473252932263237101430072145760028426816197777296059594803919126879139820460747565433495245024356580067844592456005871745359182215407637849582076448124989690763137397473610141803293585303448159562850692926814577960506720398941372492411439105703421180157337481332291431651488693386716042326302866979358711212116080622421492294045610242570024916024605489109786016918737498624768528625817678105631437619799945959398479572735908670338439067601280271952630546118952752548945768284042867575762060758892133162072782760735711313635191638547310732793311716570302024733455041287622706098253393959146363737956410434408655470318369780091331148174704998934012846734081630742345822579845345556123721629964973700099003932333711708363739596749547217453266330565914555196185663021453457102308337973107784905848446894319616971212166084618560823053657779592085208789627457794581954100330959026727561499558410213730392750383801991025556443051442188458341421314914428279773758340267740789063283942817575614278264213009506954222679314740226709549401517607374599829691226961956322093673007472430774560621291007047058060877619765359247563749649289237350971761379779630302615567979861246558427819147899797759206677163136129201524412119434317301014663935686746638540983830064886928881850144404877626058052133998989136011714835442002701219455878902705607212474090970229511071751246989386698512318821002273220055056255597201772384285821519386924273618852928945001894552203897431255965544130026831481896992081629529657257017036922789732736377621053509756032483314355189292032167260609078647975337704033097510373785273556443384524215864236093812712632628217459452610860220224350945611425467100377044381022723357554481537772761045926059877163715006336177469770710708803286143765810070319715825818840236891813196148268567524325932734261717173853139151630454136413599313383145563007804771672875282386144611494072673488541851615773529621647073976299228332325797170387634515630497945507908154519717842901290931644242609426895469933899263734680183145042786456957967210297058822470830296963447156617794012612756067204642586046200326813726673472850972722812841458029484439898254332175707391474486662091051153896950774699073841316076627273728466587879424757021856101561778195969632421857975844634499476247456696796929776860590701517379161097390665985476338289834797769771815041440554144406636251661263926169704911245684753263554641079121132992489526015155442728497866748327870362529862690275301336042296944518799384315947525377416602439348078681105904645414289544370987885152882876998985693229311468790245547220974103817309648026735197042006884040325338411385817722279971871937433244456617870123837691673968555633661132697556268826658376997336737225453055242611079098286307268115866073350488348369773732992969095355840477307158420578680028992233256032970712708485907030072462542443868147679097385565056695731862861002047721476873582448805767623304933126095417281908810442176844210573783936430909642725839976593762443632018495793324244481735382033411199501049829962696962887643273896402373202664768183860387359208296011995079331289277751807736816941933300926226114810379376971320902442557100194148740436826004339840480313875229025563764927291249129890601181333824020521016855427376337485202883486848393092536168709768816090722202376026141962215398339359204915794782204054726224447149057405363287534312638010181343694320818559075025860671698902687265397483707502853290228458505973010276276110529568216040638696406249184037744931136755978589678912652625062394153178595879678387405174351922633624920838815425507998776063509318491073384396747236993638239424280984381838798993886524387653712998230154274025403566852726941144642387433619049282688518959808385384488097914943562877742562717930521389003342249994133653642256790640443220245498781749382792263740157378190359117065153572937659949340110897620147090454708593897588008139361726583008322738943952886894006945656556225685398240253601968570130575826213904008646187688291863231927410044197721139458993417804991378008442297611025472961545510271930304457911993563866665894783391276230599121592482336416557597874405799747614151053186952531620470417293340152614583650725915125100923710538803963285347854300695282435715203212453602354704894312450560460468293847810589207001540909009737751763581076988604005191181614717283297061968463753351732160385962336933674398522271796091643957189991761794064673533479896527598004878823116838566294076115281372198969463881297658416940549493599623585047377543412034829575749430911498044570074547163383653585691853544986335368633338800124535164660619323498765132922847420789606676797938820119196994758437403295556513100242757077568393871450766894096607227390990235853064120501519913454898590910149499014860765425977948892813447663667605144319784465915555835984127981143480874880632198373242837717001405689310113484259331179773651711513957512162061692350343368396266953892748577402884030448085648578602406073005263448499542565510040622617206260866296138716203587525751535387160716479663573054027032253554293524250400700467641399253094546450439124950673567656209169963985052688074968955218348315113871707222856335043055914596345848050410044610628168304780885927472510710895233539425605546533194627384773916404082766237140582078428183449352456629437348097430303495850779233415140927053913288506397218831677539364423633795419442000192650910217970902857006581498579175891509742227323737921480946700679515535264436896231732988201032702892568252220991482597140154012125009973571815517257357331874183703627726741175729925444898962592702676353785853689977993155782395814002989544651251155587890088696223747891250678698421382475605956093754654652644571182705850251730889387710012256128073409617107591369621695117932634245512036936969661511680496169351908586682210972663238857675379680856329506577119882828399704045726873221847267758463583597198426326282458638244117029381614100988085108552856876835687571050599814291381659771191108515554419389669320372005162343053011505898227566740017781747892754619480592928553993080012005071114401190467357231454996686576659256899904991376205864435440040023996839663314466786437328264613780719632729207677861360563073168417112111160395859661659325601731142844659713791943682790364117092343345299402207744432160335583065953471601202334831124050092623993994187292956463562552661660168724105446201527987385050937666035751692896257640472077054090848964184833138341791040215293776675145234344369057147869234373717361588385009671897485527641392176599039732234266632832992991507062993536438656144520561455871328037816147148742019244349845308340443160045389175021448913027757360283102963959872060665186461281804612974645558677521313338219626722260341209324890337279324046218474976172872890111875322882365739071438290918973957720923245603815740257247933852084551918744829937571624960523680969823326191050628562989633115857079467641839647255856242883637015274195342474644744152061504082157193392146616682779258239787009639263282908674445250863190501665636122339179755798813655180504241839566203684943897336374826224406436831046283854621158805278520519772601116646512311431881715178038172889614846340611712181304346593173318771747296375294697291049376672380863356193154650517218256832027450199470667196321595915239753687061375535991512926674728473378311072302617281708421338680572663771673802914092393695023400852773069928142445019172466368994032399092493642488656371656749789010459926330834495007062459603864684026950002067540872732784920805573330196224821083393908010675999366799242585720216778577794736711695466607268571843014725105459917150665127644660101248607537662554862860989017896012869418717008321160231417353494058827377882956936206809790149444934063692645036835113991243473751452848894136226156489989341331983094181952627832108633820917957638425963683355530143006625366774971406582708341736369642233602543683225790487880656865137641107341345927174112473556793593471250682196753778499640590011514195456690049334193706000659209749617539880221093103436972425883755670770348672513856280704063863672518664659136853001774317982259436987523721858945341193513526252651994017331128952205016424987080530466462073355704095004560187099471045733422780706470697744254048148387700958990680573874524684721522499927741597095790217349395252345501863917511427585036089351271945990697639402627678320028813682383126275780755759445249672701513079673983364191553786774819210106839410595837497682874088554629155561700714331602356321243437959880316077559914793070866206976197797860214660062357889195843301842172260898092156968764474698034336083232315050531105424195425282744368266281668149323489183692292640586622352799330616126426066976024780162648429184889064249390932920458981781317465279936828792071979485227762321976882348087371676205060851526151221492330013959633231983387620487828424976548477118701824441589883501168245324160739571506437747636600636627047421432924218727135204805668312118339448603006752106270932969339292340834010985566228250079277220426372902488465471985282994610711472134259975025982597406859348195081305623150019210199629723802430802036298853871405247296698176232739817738156741050229459271765044974549744774544717987445158710182157509024007069858639319396992719415201352985129399562834189883666940383177648165593974297236310730990726830124838813996937191776313716948090628661023869271389429310669400723360671642517809934339085241274287097590464086209259803182631521744450023224878749595087287495212838830149516807972599496451482556064322243224961491646997567092452693757712517628836808609472094755522097701005581715159925931618071209606252633384296511909549532103111644450489517558643101930537599136391538351692387530481978206578837654961377033873139404868580374385639605280986506062592492633619620591349145328535296805895264238225700550008043206492597624296082788091023563513944391535073069852080233141014948349658186924179018173924799048659245303813436991972933903942677302640948501703974255175606667223267760129022571513747382221984112007996153915672278966053869081349916271890872799532792089387821824310316737268933782545640859662265299932836184405844699964072290103460548620818152496286322698755282375645575121004553409976851547290069352847716576129834601498764387022141688090336287099343256227786322890320835450598545495436033251988622564078692839175081307993120174575794912139852776597941409751269684215767304839653932416167080075692159518197827359985295501200700535772054622351139687400400784520886535640185867938874131635596477291702602955246669158717625647124088763671360442935312891006972426653779024293218206887832825479574663023500875004485403201477786780672970337729104346162859634802217510437605983685858983701699161863797470735362966259465607295472286546709973555465991246316116844425948794695042516853676035846274342293687261062831072090718125554092126597956388547628109128192078230979951390232504096635925847127846542638813827911426295048465430074907151409574481741539155823890450014286576496796390083399861680281634537479876366984135090141219890928420556405114893387600786275814065216319567695116471938635490960035449011145317549601523269231636338898609879550951589248776899033425615564001163114233643471614593871879455146864648630038170595252453472687475993796393452402172729810974525192086356318872577282653625266175110326935997148277868166553336290640040254706620160715393773751843631343332154583592528727848523275663253732936677358730365658977512951765689467551664735063151226620949141161953936145941334083536684514502822182078327122736989744142750940215997468807917155484356768902326121945792139849418337464986425830201525655440841166370658200595526524932393994872479248989933836043241485329976918044386705479980149737147775798309949902524808740302804725772783816845504183654422117357337026602024635702208558722995132096408585638591667439746635318608311181466309709704545940611049419333666522790816386487062760683330799153538188791944710462620377333798356727337995894366694469083111668005849638194814056197495476362472125913239676748026774039610825330215425904032742013185661723005490550279471256920756530369750705708573915838493973812074960808559346930768217958598968342341035194706921293073528267142415964526645434041843044018058058677752963686171545023739482183650198276405183758465227201106339542621573086729604073598857135022382977122312011483875019200831364070724944581259224862425518363954291120423571253871112635642743178623065100829387353070342714596940127266284202161610927150326846756427131319084594370017674743103708957974422490333588539457068691741352469459036599972703705365381019602943549509719965841396633233873703442878302286997823409704320582515306765539358889369333280824702867799709830247181730305788475029223976122044591866041748510174298170633244587792605107405476124676334918080714671025681789302372234319817710354347411921056467808589292852411072600521249623276080458929408768884447946530243589178929471802748413984621007176743664725250476316036095602584142095008238209265525192868000863023507415279630983686005442035606294587766289503194030838421768567940483204437116837812901326128432702094241159880721137796068107778764359189631491067912449525455305920836232333118450595290377992729969998563895778427752287621065577743374029949167510443866465618590933711580879019060302291723899818736328789044833332626738400206968980684167388655734262896931523701470421253355432742802841561610274137455257898519064503921361336598169883416609185476245247426441915696353554972027928693613848312074923341359181403260161135958305412652456806660137220659052807886284508149477205460560949828079504580448178843299787611483309826419578131291412116911044018410659988413607972542707094417192685075816724345458811776408912598409193957118373738509018836319835622930925211648172608583681234999610521865901847692727119178770361939175667108273885426477732102251814420322544475511286916896305112925756366524620072625633198592213205143995943521975692361007694128451556011054835305703634758674006551456349671601833248279798881958284141761732266104109320340217110028420265555815589320981252108597106120696924511431277723359074314495757263658079610409575640097357388843357515193876737384342331657712761461055296920878211638687684136190127592612049253725170847103358023643846539360649361407949705462523628178441279555277393342921337096260379402210417328542451757226898258184238200542167852738782235218284069246394090825300099196323509721603267952555522585618251861377792593264817002903058879592579843160988392171005244758147816981016221990378345370992085770649450376327210204841149876140064040415601006267020779589574866812454260828387851782852622706306506906274111779087192255504349020345254499689058098785437937092331206998162288412168229112662821958900142497617974266193182537391372153055971517284999174878301125554224481404812256862165820462103281342525766980970802684725589820911044083623903392452695677270154448600583603375495231629641883385768151680324058027514593989985384766973238908416561580818848094913632153076401135130631069082818276097290410022737537127180457534272856834860915204361084188906190978706681715824691077854737352375568836132676773346684981566958974459200651035581420151638060031875095507251323798433814964603805358559101360926709705129571834617548139962934210095411003347729076966678070428158758938050045592043773443173994212958138837352380417077793441317944768134588200854716701746641276990785868892906682126509600709472962902824138798491152509803789621856343091617851907336658969163734877105549693123035155919848010333157350739090268741389726823317729423769819122758480453709713038784347932997073202004217858268693883187831975190257504715139225668613516548575654054824800348084287127609005068058590580796274665555204431621508878630795413726936594382270581635723093362173281294063239851360314452528021614371261912925410575219437122973698918354140428823976013297653878717365383540495855830231118757460906576425723938969304770323884719638257568982529859257135319655909104632314903388366887429082011050883479482393366436083947648908178722276681026871403893056359331964165244332648102518473815634504595904346513315436988483898250818797942154596351802464601237488627872131106566803634173252593217690222251074287954636774201985027247920825298517655472508034885099921217929631235841035893718362874941903618833491335481755579013241426804415335362156943569876953969693576429398008738244416526019495324399034958087039633044348522070695513803590142236168858348235397379152929168524575043268519379593731284328682351790306854360736145356618029590439546448543115341681811695426260398653294387190830910001325627731529603176358820649908520970731584537724338019697185005828089762529032010160353295251483091851038949710532287830004069187499856538176811988162219290398121980562914177973524237468809654398787217799899741937522423313596351085592813375398972235085794354293270612170784014669320580723400171176500277241670844475534050850253910978607913349588635250722245449164047637609654296790005828800805943267651106756809895835602857777781550036549257412726978258839307996896322353701448129876843607977821158930304868710893235704667527455252402084027869962121756763450494824582655789536113126175332553943759858020691775108385182966567496310687025352840244107534141469547458570390016664634884011080666437083085040362349324013862347148685526435850191697764761201752966894741645702489257747127037551765469564724869258417928916311924790562821926523690573519049726198494607930418874389564520984871303922980524870057865837893450165508459629705539044241835768526969120489102398490510337771920384333110587476431714528402519211938802339707248849583460506888767875904399314914572996548401668071957568785684863734601402165443641856840322641150445480138910293986583406827149116992597440639019965726864728462003542970188918648246694804208641051038722588173485437713329718285525210463551452821912348347577223077608273303930088806112908255638774057237605980973833422539116697919338798813127664693996922703699942107293169053212875441531250251334156463935944219712236512288963206114396991857929118774840101672501391488044113004567320910517870503381486432382798079085227304886042410989167468359515890778893784893282687238770703751149091288784755069257888223739934984601822491000868928255972330875385030166534500215412889756458616146693334568526801424967088805859107388563109634613299606859438912470386925940723460187922450338954461432007470326285621294585144755614362545104445932005033736946331999481614164303746061413733256984495007570906472943696300155485634197502771260529682446932786069621293825225131513734445601835767755269994624853747445756321400641756228358567263733425483931246746802946729788123856446722886067039034094646664862894281020525273181533532387332274063550430958432959755799382284726779398867854398860975775401945771581212881362846712418614866991855896272396779187327760530819597017086427059031674867277812211631279246973726945401684126762598998005509817228665987931391458849419369387109703092915415048819926004942834724160096098148147078311271253549756528270220136711454467766142362459538455161355797582867759898941586349348151713518831244771296227471042544819476694037201743547108706821689237161139232654176368021744009765151366845306123165238270274204889398927417243065260229590209662580182504020311558411231271566980475390517068537858981460174080348579419829348436156285589658838313377837212165065931984255575899536700613422408947384320055017652956755106690503706449164902656034026245060524535695177780213946607538585401885205140543693962158493251923393549480923405233033237283196093816757430653670037667270352556264621129543206495138806961779870224560191294253800807367126714032411465018148384258493620772945738903028794963269638496873367656994128624730573157786832052226618414634357178307618805734701903402106354674976839806773008837645415659850580673079894646185714478839192426048945090251439314922475530177529475512051030321866577324479770224373094885715510321550536709882150131283835208748633658668131853001556272793075187605887269341238712157579136724467876802240539490548901124514157037126921708127075365272389365385375158385097142115832462638955276507738294632427291291411671881010467771008266058299802441871801978138965446762492661640053911054227182143661941311347647968549464498771871611381740114863810569801776546322253569739131748749428865830086103607829217973212938965592384706718975000859858720025548721447474297523896676854278024987537370634472611739497518437734260136431587564216097267456731729423929279999702986772492236079265553487873449001808661277203392030551539892637852463809696802399272589231826960404802363448881852349214040696093366441069812116541258314211349943116700772547118823208169312247397806981135940043564460807051293463241956836426595881127163597942671211739632798237402153828208100318757402969890187003319626630273500384732977218547616919554130090279640965755828456384756651768048787283634777986257117529338125334265456752240406916569885098241055251222264153654223476158064022269166558974601254708636687527793064817979774839353727014510433717809562619652557601873305872326890020958633456072827323017284276079383877320231851097053214842235036143976825121468820183287020747468908017129064702981726210744442018292853005296554868505566723215384223568772375278867436965756423009657618301009043044879839619881622925634084941847114362471634179536402608693731015893693655870805028922952129654829511334539454014793103542205627975247981479145564285027054941934781178649441867454148348258977084192759717803023862320794988420253488356871700773840561414249228452814975460065314354430283262977942597463687920676292345603805451179156251399917162251712008960945776545184833230593300020805062185714915048318084338490701785931894107173561216593819570772049224128566619867767626409558600500780962083706574941931508691271182498980122650035872723936143169718146858291615093650175292783736090480782499781432156020758386042063852606150669661280193770125250944999260748495751718405867209957470555809140810225198547606276693885409327916916356101797223028859158857375625356603157789391640289921240533938195095381599053906685840298531729971779307811167503712780284903864920730451611637500074100217125549281002016040839115881046471265377785322112606875140355764724195238121364523709260787458329649734693777644089344281587344277090743148831282288897562251440661646374957507771085390081203777128351424097436221014454359001956862482634119350009061161925583348548937928506181935470171711021310911291057674144527409610254279368106692540497181871366545620625326183501972835329951648061774243733365412700087515935685968781281653135171025050102531623156862146110195183609114932205861979935218311414930272922327447827391703772584569763084086605370779127376639695226668606302626182250680305876591911314990645842060718971308666093999681925292268116880521004432227145724819956376263674997128933609573722309854442909473016197221529156563391000873992049189321127669088607353629310987192329269137158160930079325555336514579688611335979280004527315842379319715832176746029468279304606772437333666157457722253867288823704587212041338685770714434898148986659598945079486024100950682279371688109489939961615597879544812003609809743415102149433060162655038190607704924248081218985966599777921430170571396096759575549414192791275460225118236786557800116422573216082080845164754616987518185205927179319748888703612257622110090567180763874803895502305024561906201782469934168816030256965134313408368956628638373304482602285540709741581824438249182927439009836572491486505234401733753398729999474618852128283884817568031664967376659444474843541766374797869620441971841293234381626076409018280109155113954365245491518906489741303916105032544488974475457715888034707525956001640859458942436071243919198039074908731400035967715435534067742873031125711743039232598584120479960194337023757886385547667470719198084466462641692696239088070444233557333035291568671785378461199805044754065795792045881079086373227963508822607440730924686849183259344179631560557909774354437821932641001635407187136080058484393191425541377480877236100520699386298592859449207457311841147272458244993928058046949147609470266787052395635921431899064659668339036631036947500511039782674778379045649095379937401967166930486008915351794630821248004481306582970074758728802963316817508076554228153099720706337268094506525413365472538520782274401644903313894193176563681992974224825762013085713181271737056576840250030940214898094150149752553413437411221296491894939035441778012021001042633642259469950281930692668353155270050724169836408361447590137255353654063266922294939269813479433978121570200052324232839786235853866494472286105033856826964926659546790753951522318587765979006947940759966452657192363991778996408658952050115678638281676445588419050363421846221329836590453704855621576723581547451554196595520956979648253700698913487645403327546414657241316214758157409255423922267322081383511370608030726342676455342340106654969883807843451701736728024779745945794949494222028741136223038675805369545291139304333034929564849003370689079627889816032515696373590166912883846412201276311478393751916786577490934561179909964206906714529411668559209162265538652908802669517211694692612536307202743679447504995832193314017284165050114545615680284941522827549209499731699189795170487447066508656155589933408810459900296696511136564863260053779596509046397508706483576524632434247141749850181196133487611267778856041859652565601914537694405254638883879018671098042548612512822534487627845828146315257495580251013758258427182394978109548147098232178279720252759666726670085967363302550816770055056906147277683752142694127503326067802117919258547841322636545365942182171240090138347481897671596507225934862069021646380571847361455465765100490078789171442519691345327694162478782858964081248438081682366933410156823908550362551022988254681710181935054955262875409796575722070434111804496747386198142922726889781634729151411545655627478320618248403289389704388549211801853013268205035259046812561975930993470608458650343908933696457162635948133238127575554878551565906483775605655697790618846609421121820670096541710671217121369554161250994639436279259241373038418198256516227779193975481425930341958807961053658934183763924368600147456635134316882356664498619999356726974223733544649728594203389386942726757526292901997853385656778376724214657213446912855436060057995330700996959607813075115550493927888455965204807782554758058146945579198792581246029114477845200103196065570818034722425073648101839808801317115261652777247031506399069050844341620406180126153918380377389464448708569808289839041377061931286179704971437311874075731086313348414062223774943938018591796004555678124103217640370149510223427673490363425214047064123204036616510946606859866918796849736856576822058497333860136933028257771191293414849780724367787627186062572615835747276568102062677263411453662415384388212596190203281058091594815363700184403349529445983229701941420627985898307275726145772750526560794045248245714632820537008759715988518272574271257046415182309637794519123785768867172366784876431899283831722937531201471154593171986170206569716297520955621967718420236914810213333795429027025288152714379205086365274443022935233532877940999042021078356945342013553716752766626752305194348611230408659201654250079713081675219982880068289339012695972241166736311501523733384385118410812819135461200231203711040794761037020938312099924084974366947411083578383599564806080320539374128933082972757447776976145507989297252224561736993305157834868280925681388650042883118454945285560528368696571949336997074427674363016709800527929624158802926059128161887723572743160334419234390577053494142459649151190331098039514417853858691265370085999567719895645000233643911762507500367280252871909580042718640295503649398078981305097862404946837249255482363577376869244818542409116778904735526428636149278776215475220029201774579798209062335839340635113508114887342346828391256198903231842278797646102661740073904841941594370304032116435374388606759586907975519103325555337303754196776464030891201951537528950749187085030174508968351260097500216825100260614372010772153967060160551417533919912790240641583981780905178206185982491211847218017239044570695798663175146392619388942278047411681956838355196908453220474996341721695716571478597661302190810956226903520626487901712980148584513626945707618890000943627805126219713237525180025072118719705876469087923086444250014841645081458606992054669097134959525938849566365262484148923681927248366537256376655407481641425404991937618497817026585429607443878241811435591959530873960037934274291680069975939690955330240933637727396717613429338039072631306084706494370205179638339991981027798516416044650310234767045631090928186040380150495992537052109323050948977863326522697990537700923146562435902150784944940121746601320400744185455183888980058254662421289137710194432420837397814666044997630589346681920743278756646103510475245508886749657208000944388934550716034000422982757161397039166416761410197177441677630823636689898955743478416980692858430673418723952596432467942587530322652669898283766097211736779272238203733033109757240355123537072616798544417720650957179079626898774991757261787697510678919377510623632675856988794320572309938946250370099719383564673773406781878029476980729568825062331112242595468515568345338537153536447670320961928448831989851583967330292501189142278751552531053429964851286721803167519809801766112838402154384503968319845246037575305796273458480688259623430577075376466837834719169469845651033673160152943044051405762175055512845196269487699156941471289980186263305408620696822023482145474796743100585328517926782407432623722499398777851861884443334890621783759240120521217085263570822447359677253692101238830428684055367690786421213138564262232619028433818024687509801911170342725262483964529618603887318988152050997399620350989634406212129060705695644662931388124553437581996641077438179406888603605693114550076337025546289046232980000076200588345102324474764626457899237580846614284082178989367535277388478510626641056488031157323111418312351772555489888616732084666382567452730203727252370443188115481781590876384672345046382185105730667976939387697894211312648263725340776873266994094011177871841987448424299549493588365714915143297424153398676250679056964861796997705226025673966225215724868374204828226556716466748227339436466469003456898296055725485243608391885086156080675290696251009152763442930613517044312637620491022952244186448481462357949240691709148524257355806071320013657508828079620014029306055351818560227046840282360847806758812994242119277259881672442644709390920370526397837283649851001103362259933027658911613092853125169381782240273655626680084556308451699290892249045518701766429747342397218333782393732082101601197993392765325124542505124912133482860604505881832861470600278466353674852766455964766702176534945617512716543902453197842309358477918403903606898594396039376270882375055939556004908340141438626680681152894395832277864742879848368937721668057270758184722810177149414515946999581429344229684163112137916239459474872488917862122405906679936837865328762536833054405841500660887032948436861469860596290659587224811324428117477907740817825450577844511647490647112847036076894215114303848375086634396943426913896566027112056910341443826376244390939265613937528009151134477532726514169127238496854727389043226618482941893394990208310860663227523166941306467134397562309244284140861458477130670349535641632679862391032287907740806881537747807212378046709951264350970000754196258518161995630497891541484916843937451055149303931460380985234865761952879762619467499894115198284512750482003223277920950396069870001468121300346761894384687187249815309980719932181331505429025618838863635711594939855147751149461166425369008606437644156744638226042550679939757644238955185972623966776804739904251897973606382977917140082307017218423445608708204481552103219068554916876695903061634824569783184841241166392426745584990349623052920636171705169204621313480774229889395210799398192316637094497830612996401643715465023222726927141943410362888901225328330208710462176532597358081248326955137424042488111541308361528599289152487906057603156118059657861545794252502711710154616733295712559953097565764195652401127951711893662279745502722050249153921561681909577256242970911411626776667806275463494302255589161264761082763285956923776551279469094543069452941657065904342202434458094334238625896761664993047286254888397867575226542075538032921621199842334961179526802194669295374667043330981916413426194743290877065532317560657348789902027412811234369942945357942511165149141530358558492423764235031026270204380141084522705119092383357815705296680186054087449004755280000863163820311029817910461677580958487847790750542515018364828141916221695316738860639652771882462859785829376242955089235501772233141278127816514403507464631210985640031405733114161378953337395036891861389258382742445819336558923021428135764937838223267857433639025929918621770966242666415806702238472612577558352538716223529960565610052809822366404807555693113579267119176777756984997425713642199442317233153869343142353231489957138954130286827022571002482866877534048168198948747198020353081308847749221785718659119092245174733106541833883453672988479700070671755268500942402042362202464624755524194633785883078886409190638678098881345175624336142188662781220617501101330081489306983277349667934159363653672438466165195273894317598326494977579958230782066578828491739178466720305726914794009559713308384220287812609191197034078047322028287397802115912822976559138144638627071487766616387001145573659348400651718015675775171438708090694237511718237797532793965235156660650478742947797650986356093596191201870634248983780137500692223377651562169507983071313478726127461217256685244905571812480040377890032157729437672897888049668035162320794590059365515553338090244615108113533366147146429937440905991402769531390146647957453381863895640414176700638082603533788182199418150906703428006251655978149430959771659109822675666073527495089415383516373871903355592006916442393793126051668614226269646692290528855790851101996617397635760011481704320530462125447759817059063256030207080932654536180594306131251796349124091245085422384286334613426124640542072197665725432125704350314090539835831622498885765397671007078095546057035938545695477639540037028536314497807175090696991718990950285851703631378056649482545686210983179010257607466198012841125211452858887864906888287499066529039360214951595143015413080241681723180527108528588567786483881075032404536402216190838186555351847452632961716659194073773728575664305563176849499687036630239518992944951670149262562642893759284191908895056534706915823930945218490757038643646354013760726393464450268718744004232764159693542279615541301383844258436345958829026616109667456653519602805948232167732088140507702700206195972425814137460999544664534537420764571206833159969699080405300930358209995074877595163611796502920182847905646790346316878165072912949472491191423042269022152679183215629781023740840710164232545080476910468390484973292252688206521957866097659123784404985211700324585907215075557015899486200906929052727234918861657084300093171759196451020930271245938089724448942367363401599201072838487654272652064232442134617396618820064515519233337318715422003730060719790791239613044988244882354162439825019497749371627740955399148320469714827080704912366018585958606798661760374122680424283229952261790268222202252815966515770416836676145764377026314937118445522270887276243061538072379644286250407669172097762509583527220569927630659324255894828861196371314420471449245547734485732971720008393293883463820068113847864011380996128502765378615357664266424834828127298499238541218902662522081366146975526865266413588908701339414185100779122165528560818139038989376583260188668785780755284267315079748568992029756223096043735864560449514715912508511375660424066605930129188829905601510301739060646508579096429449956246084105889281468100435120853181707014777451978162418792960566248277798075999192834684127311545569442076483110098007337801481362677838171525546440496809284954487316469158862200989214565672430413941637219257854703971814841879053111469915524859445641373670966577562391590800621511095436346285810774279559357792109551301894619612454390109978938404091955102686330013458163972823262827125987241563140924149257913472973626704000466412105310749067948811417571891521908987522637157700377228894660470302054487866018002531593403736721056405768342547506137479490831477472312345880233262372477039294668878250770575932732914048005970212292599423832051724088692130494868618826842359891004291731785715249053674283240503976333831614526989192564023648967158333301409982837996072210354473675984594589376856195266628983776190026178165723139451061197019953795391381577731095511237538075808622351432404242589699836525667260179870647017051088040785426940569630345175834527142083209148350959008594484595644098344226093747131622086808509406121054638637604167315516454703813430293581267040987245335783590391880890001823010145146558866513974648757835244767031602720485741926075730489981549744539702779052725521858190159212751781076039524229838972942274562027694001260601393503297588995795907852244174817109418324033187330680113452937684735990368130648968855612847503290563390643910473950180711763740209275173355149031125944179642679656114921279837031705944036988667166334444346399080224885811221568295595565310986102146722257516990934643480769622912381831869092750619642981437621577309237077623860682184037785111765849423240648551561588706238403363118004257185613311527346602995519424848244773165144692613119021835887228158038824089849566805495663823459899245710975403784475207330237060061194134758259849845205566229790191609441666800625529663555651233199741388811301194173166105046080471633230399226287109166682984452988543003778030401518362715082635372894946734492314367577405948179086508704755316562021416924746268536972802941528563886303879917093275122935783575692172429301605333740200598260012467686621242166624418939159926212120196582293581909255097819185017213402146747321224319813562282928671775822954499692594841899529096215625406663931961855873727891689400283792161822659142868811890401646073185255186981731015928590180064955832090061091745772589231749573339934945797338174426831436506303306281518394650793204190502258646865717785827089160156316136139101889944804944328898764411347386276359185594048116123063701091457420866737427538058463291523195715417315536242183699953756924904116874938916916362023320151689525154790427811161929005732222906118394172392179659967906746269941203842998554075352168504933017804363219256065324544039756522457182486317695212450459843677471581466595604528203877135909950172344507260390622035361719425545062686855146114142064462904594797207886641157788193506503124597731906064361071005785398382391080185686960535939350723194103544080734501931896882248304749811787249497049293813178073852249456095408628326876415169983741988913715181915016102388621999284944359164333735840055191939558320173427403035377225468634328102800715455648332720821601778844852565673151569162641124587163301228529669370749461706359413996236556487456488980228697486672551865115015799381250637801015376072923674976057276853046342219262632840993989559054995490840621713720590504178250991788349926685549732398516353934012779820399086156231287841546084219886651412960074332972799327733334933280840072492665811247566703870803065764851653751696230171625098284797957298899659532290421381971983242623719876487917751447018475692375467852231515844313351177910448418304022902912650793384993139704443509521816897869579003482359425737195216510272982661327366488172994758270355704586442945624529102299541220544260293046061712285672692373874094724054533282710275815823642942908856641900959155398782559972888700306379962643607013382328104235096584756069757945786669790215842625978186619403420570411525610732104585399078364147178234957982560502280338610747534690893008262919991369878975768318354163166225490030804776920358860176760786733838811239684061863677437219215817580486749798364213734221658491001475586794544455308236018533108646520581714797033948147969818057386377097781546463019237197271042671372752261408174662330824163498352011559590827450897831174715238440978517461525315992503127309961868450863528366453443504131594043403066316100319899012403292452195927131948124239760643298689207407506437803870261696753097247993345340214062775625169338768924292240817814667606229490114279845030016745452531866737859875941221850878293193761261228180363663277951858959977871809096416825998178478722598492065264719810650337707198776874996595468650803674166128005446797354564255331448319973573585577560085023982427316217688410515319706253999659727267562885355477204557114295334647693609602856083299124089997128187480447295836563269219549580285397099095461409713991585649242318119890224843295636663996609082145851833418398414006350832552292888204939602770536443258826871109070005004004191795443488385746768048721017420316620065109139536478720460944405760283859304070160553631207832364117979686272606009133500797149129504332278466815152149658009594657941157316605129914371698509854185316897646798837030275835656253077592364069570328389525860325030524547450723098963565695299177298258283199644101577562321151989551419948545547250177676757643124824922962626675939440436314292019088270871647511096034235748159036004440454796289163833885316235377082914601016655918986024525302503025634569893325093628462611198680030619638176850505507982074666979885570847383188127625634018734771399951862787027705703485334841882637396881110368130243537869475518886506429215033508668619788529956987251914818286434320439067625426252343820920708223660174030244037910487914292136763344060128371653977569811512101268046441520120974656271618883089684249134116151232938034764468086411346878792625574696466899949319053233550740321019919245055802123064755166573995171218037299295977921574892550785519227503287931354422192559917604620859589386752154631727325190748068574914745113753942117506343662907369859622768096802046602152739206382065887352409518439050127270187287483105294273595372104044450986349881374200577946114850984794256030720261510815538660083336663197055263809576832915535405687224233670114906865299515202093266869048129508602359245049446354576927594601692943666976801011783862437647133509768702401405733598159863803204641085568552352164945854704915528229450319364391420679896809775708739456956284822590043165009286888062267854539969036250150900323035777383604048283656568867054123174508687422150135918056501391683650019347740489612255019241239418630173079299349803579225299024753575534051687727753390382130075166009600814853779222351232344161650724624425349960152430800464503789624527775640314281491460547887243873204730525247697098599668537266594636276505801841875973357915681331036230010445863416222348333234117291037283974403497127175652383165889029488869922304642726571036984365892344111836575661860880122520543867209882225893866678397244637755212260558393863730867306255229831134087700024615286800348181863065145585062237770761486007720486186590760015526114513043753579953797918900003338153358406246149672653661747431427587092084742413535841110233968599274454143769660408745787429549938914082445861151148595767872682441197157222017062267232583190765812609621491578038588966737294798736835841850235881239815199188766833831050632777319582241054361211806181679688237821412063880509215070888542953912269920068154715939059150316474375759988679236337330800141187900618748035377133750746257682027682946241284678822343739597817974484680585997534202715262468669200688755322027982276889135259351169597954133424747117519283956500413460854113318816594262342230769523790220546350763269425509627397395572067710539329919911695966819981094614850623465950567774465753102439226396306776385203967981700370354932305707624773082338807243614500053669538137757412608983254657974817742114763309103462384682409326228667889091303004387756159349621156791525254919149848845036561218976636541374032618455525048056890341438202413149024904367707269848691047602157982947223747763991455645251149437679578998892242948502463540900093676572894052193350845961852638183246827935411534342690381178264297175448159267028129196789510172575569411959344401465554420729677381420808605090334400427524892541104023451917420091920603908041084494625879989326389476931572991504355848199513951858839230211149561982903534824880387218569488526097069409935935635328587839811174849753423326659804303959802835195203484488963335222062655393367841957131921287262236817519676168550764963349052895295881457715475296888037195221443110455541950576348918113113518345218573574507814466099115952238020491629102225457142971711670256973096048456705951897424425499135803785090988645872435686722788222853505192647628273084860556144126724681431449763740881900144467912472179256228694571498213676806766420402451647585976628266208379121390048449619423658793918018999462266528831673245824619273366434438709304798818922321555759542487356886640385866983448528245775931615559723509852775158015255800907136194029683269834003117591779146758777331135151825139658956857037532237447274995507005015158928330235205673400412410146835038819624401372356128795667806985313389784673484250970198322406436806392688621575494516275078364049391001939246141224838051922657632090168799695079093092480230092935820629467159298902136357259037789933118853279296136315369462684960482422632920162413462949473499299312114737294833213871813140014892371631337293485119279944866226626472381737882969411748366419010842888255218610161087973002961428164547852698847824775566122559313023446434843677762207700910185391701668830642984683180422818495135423252549733945503294299157737655803658639488875372537375724539710674062034450692161410496653015325485968542150511725018146802434742429369785325407208286600140733749309634947405714942052638690510511632120425103074620549524246067356751254385266048791680290035507606219235072038258538831425588363827118991785968967588319528021528471326286829731922756297887027849008605838993376712198923569475558178137792229077190534549267327457061301480567024014745938314252110408113770038726426487088788996743664213179491016619651113062930455690638502842540504366138460298581364425680883847842333856878187316662451355033561968088903796237437620534120945679771577724606713438635990839418192701503725672349449680382729171741714941983428551074190538142892724688419576432974131352847230953144133385648267792230532030827631715825301477500562677932320628784171681522915715623951990268960628988907488150214451247188931218526752251466791348523263468984255118332986927154697380859280678798985243908593891114581968574567971083455251244181079603731087926010073749054978996226707317965592421732603017155283305572251994187011297340686829639658268411881824618613599407257640571804800925596795106321329943707451971942971320472039910383704032779735880812909127972937612832179472344356283164768266493425589032462865344765921081866876644261646618693542490650943529451123772999234574341081070752549614962569922138528327939222954533934124447455759044457255411640294009179320474719953623721578100237211577739489546749936056575963482836991666984444505475";

int main() {
    // assert(freopen("/Users/xuzijian/yukicoder/input6", "r", stdin));
    // string s;
    // cin >> s;
    // reverse(s.begin(), s.end());
    // s.pop_back();
    // s.pop_back();
    // stringstream ss;
    // for (int i = 0; i < s.size(); i += 16) {
    //     ss << setw(4) << setfill('0') << stol(s.substr(i, 16)) % MOD;
    // }
    // cout << ss.str() << endl;

    // assert(freopen("/Users/xuzijian/yukicoder/input6", "r", stdin));
    string s;
    cin >> s;
    if (s[0] != '3') {
        cout << s[0] << " " << 3 << endl;
        return 0;
    }
    reverse(s.begin(), s.end());
    s.pop_back();
    s.pop_back();
    for (int i = 0; i < s.size(); i += 16) {
        int hash = stol(s.substr(i, 16)) % MOD;
        // cout << hash << " " << stol(hoge.substr(i / 4, 4)) << endl;
        if (hash != stol(hoge.substr(i / 4, 4))) {
            string sub = s.substr(i, 16);
            for (int j = 0; j < 16; j++) {
                for (int k = 0; k < 10; k++) {
                    string t(sub);
                    t[j] = '0' + k;
                    if (stol(t) % MOD == stol(hoge.substr(i / 4, 4))) {
                        cout << sub[j] << " " << k << endl;
                        return 0;
                    }
                }
            }
            // return 0;
        }
    }
}
0