1000th digit!

Algebra Level 2

What is the 100 0 th 1000^\text{th} digit to the right of the decimal point in the decimal representation of ( 1 + 2 ) 3000 (1+\sqrt{2})^{3000} ?


The answer is 9.

Ayush G Rai by Ayush G Rai , 20, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Thomas Hayes
Dec 31, 2017

Here's a rigorous solution to go along with Darryl Stein's nice observations.

Use the Binomial Theorem to write x = ( 1 + 2 ) 3000 = ∑ i = 0 3000 ( 3000 i ) 2 i x = (1 + \sqrt{2})^{3000} = \sum_{i=0}^{3000} {3000 \choose i} \sqrt{2}^i Notice that the even terms in this sum are integers. Notice that the binomial expansion of the "conjugate" expression, y = ( 1 − 2 ) 3000 y = (1 - \sqrt{2})^{3000} is the same thing, but with the odd terms negated: y = ( 1 − 2 ) 3000 = ∑ i = 0 3000 ( 3000 i ) ( − 2 ) i y = (1 - \sqrt{2})^{3000} = \sum_{i=0}^{3000} {3000 \choose i} (-\sqrt{2})^i Adding these formulae, the odd terms cancel, and we see that x + y x + y is a (fairly large) integer! x + y = 2 ∑ i = 0 1500 ( 3000 2 i ) 2 i x + y = 2 \sum_{i = 0}^{1500} {3000 \choose 2i} 2^i Put another way, x x and y y are additive inverses (mod 1). Interestingly, x x and y y are also multiplicative inverses (over the reals), since ( 1 + 2 ) ( 1 − 2 ) = 1 − 2 = − 1 (1 + \sqrt{2})(1 - \sqrt{2}) = 1 - 2 = -1 , and − 1 3000 = 1 -1^{3000} = 1 ; however, we will not need this fact.

Next we will show that 0 < y < 1 0 − 1000 0 < y < 10^{-1000} and hence y y 's 1000'th digit after the decimal place is 0. Equivalently, 0 < ( 2 − 1 ) 3 < 1 10 0 < (\sqrt{2} - 1)^3 < \frac{1}{10} which follows because 2 < 10 7 \sqrt{2} < \frac{10}{7} and ( 3 7 ) 3 = 27 343 < 1 10 \left( \frac{3}{7}\right) ^3 = \frac{27}{343} < \frac{1}{10} .

Finally, since x x and y y are additive inverses (mod 1), and y y has a 0 in its 1000'th decimal digit, and some nonzeros in later decimal digits, x x must have a 9 in its 1000'th decimal digit. Here we also used the fact that both x x and y y are positive.

4 Helpful 1 Interesting 6 Brilliant 1 Confused

Just finished posting this and realized there is a cute alternative way to see that y < 1 0 − 1000 y < 10^{-1000} As I pointed out, x x and y y are multiplicative inverses. So it suffices to prove that x > 1 0 1000 x > 10^{1000} But we know that x ≈ x + y = 2 ∑ i = 0 1500 ( 3000 2 i ) 2 i x \approx x + y = 2 \sum_{i=0}^{1500} {3000 \choose 2i} 2^i If we pair the first and last terms, second and second-last, and so on, we find that the middle pair has the smallest average, namely 2^{750}, so x + y > 2 ∑ i = 0 1500 ( 3000 2 i ) 2 750 . x + y > 2 \sum_{i=0}^{1500} {3000 \choose 2i} 2^{750}. Finally, since the even binomial coefficients have the same sum as the odd ones, namely \frac{1}{2} 2^[3000} we have = 2 3750 = 2^{3750} and it is easy to see 2 3.75 > 10 2^{3.75} > 10 . Using a calculator, I find ( 1 + 2 ) 3 ≈ 2 3.8146 (1 + \sqrt{2})^3 \approx 2^{3.8146} so this wasn't such a bad approximation.

Thomas Hayes - 3 years, 5 months ago

Funny that you can't add a solution if you didn't get the right answer...

Consider this recurrence relation:

a n = 2 ⋅ a n − 1 + a n − 2 a 0 = 2 a 1 = 2 a_{n} = 2 \cdot a_{n - 1} + a_{n - 2}\\ a_0 = 2\\ a_1 = 2

The solution is: a n = ( 1 + 2 ) n + ( 1 − 2 ) n a_n = (1 + \sqrt{2})^n + (1 - \sqrt{2})^n .

(I didn't know about Pisot–Vijayaraghavan numbers, but the characteristic polynomial of the recurrence relation above and the minimal polynomial of 1 + 2 1 + \sqrt{2} are the same and that's the link between Pisot–Vijayaraghavan numbers and recurrence relations).

We are interested in a 3000 a_{3000} . By definition, this is an integer, and it equals a n = ( 1 + 2 ) 3000 + ( 1 − 2 ) 3000 a_n = (1 + \sqrt{2})^{3000} + (1 - \sqrt{2})^{3000} .

To estimate the second term: ( 1 − 2 ) 3000 = ( 2 − 1 ) 3000 = 1 0 l o g 10 ( ( 2 − 1 ) 3000 ) = 1 0 3000 ⋅ l o g 10 ( 2 − 1 ) ≈ 1 0 − 1148.327056013589 ≈ 1 0 − 1149 ⋅ 1 0 0.672943986411 ≈ 4.7091658552 ⋅ 1 0 − 1149 (1 - \sqrt{2})^{3000} = (\sqrt{2} - 1)^{3000} = 10^{log_{10}((\sqrt{2} - 1)^{3000})} = 10^{3000 \cdot log_{10}(\sqrt{2} - 1)} \approx 10^{-1148.327056013589} \approx 10^{-1149} \cdot 10^{0.672943986411} \approx 4.7091658552 \cdot 10^{-1149} .

With the recurrence relation, we can calculate with a computer that:

a 3000 = 212351832735661211850036721375886776541419741846830798047797649326633830265800348754922726611482329696978386941712386628313233722329396831729262976271935913028968686217854171694479750950007138598702047874928937006048825941728804726445558472950595484372408258805255973963893612565744659452588885634672251124694961267804898152795815102383284947073021158623268979166708897371716288813328574125896002105522342531264500667666010593004805641201407485523369661123270309321721319990425609586215891216379523104027105154328230715943028688427964504737016740719705648004760033477439060120822056401856842664843498264757732196936579380206418720952006865612562210412207828131451616365295898234402537336762320382508754921202825754807404557820007055121102645156842126064526301550033503710326243580686202343689290385612858013208292479048892324242891437926936379579771661271219677064396120739803309230502981355688484907132471136023854101013706580243115362738647939748123348684831357244274136458378908357255958491925980356588743876497779219636407873285945202016359307298985412901504489975280743182186498490579824057349140600741150807126892554341838245583515532450000002 a_{3000} = 212351832735661211850036721375886776541419741846830798047797649326633830265800348754922726611482329696978386941712386628313233722329396831729262976271935913028968686217854171694479750950007138598702047874928937006048825941728804726445558472950595484372408258805255973963893612565744659452588885634672251124694961267804898152795815102383284947073021158623268979166708897371716288813328574125896002105522342531264500667666010593004805641201407485523369661123270309321721319990425609586215891216379523104027105154328230715943028688427964504737016740719705648004760033477439060120822056401856842664843498264757732196936579380206418720952006865612562210412207828131451616365295898234402537336762320382508754921202825754807404557820007055121102645156842126064526301550033503710326243580686202343689290385612858013208292479048892324242891437926936379579771661271219677064396120739803309230502981355688484907132471136023854101013706580243115362738647939748123348684831357244274136458378908357255958491925980356588743876497779219636407873285945202016359307298985412901504489975280743182186498490579824057349140600741150807126892554341838245583515532450000002 .

So:

( 1 + 2 ) 3000 ≈ a 3000 − 4.7091658552 ⋅ 1 0 1149 = 212351832735661211850036721375886776541419741846830798047797649326633830265800348754922726611482329696978386941712386628313233722329396831729262976271935913028968686217854171694479750950007138598702047874928937006048825941728804726445558472950595484372408258805255973963893612565744659452588885634672251124694961267804898152795815102383284947073021158623268979166708897371716288813328574125896002105522342531264500667666010593004805641201407485523369661123270309321721319990425609586215891216379523104027105154328230715943028688427964504737016740719705648004760033477439060120822056401856842664843498264757732196936579380206418720952006865612562210412207828131451616365295898234402537336762320382508754921202825754807404557820007055121102645156842126064526301550033503710326243580686202343689290385612858013208292479048892324242891437926936379579771661271219677064396120739803309230502981355688484907132471136023854101013706580243115362738647939748123348684831357244274136458378908357255958491925980356588743876497779219636407873285945202016359307298985412901504489975280743182186498490579824057349140600741150807126892554341838245583515532450000001.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999952908341448... (1 + \sqrt{2})^{3000} \approx a_{3000} - 4.7091658552 \cdot 10^{1149} = 212351832735661211850036721375886776541419741846830798047797649326633830265800348754922726611482329696978386941712386628313233722329396831729262976271935913028968686217854171694479750950007138598702047874928937006048825941728804726445558472950595484372408258805255973963893612565744659452588885634672251124694961267804898152795815102383284947073021158623268979166708897371716288813328574125896002105522342531264500667666010593004805641201407485523369661123270309321721319990425609586215891216379523104027105154328230715943028688427964504737016740719705648004760033477439060120822056401856842664843498264757732196936579380206418720952006865612562210412207828131451616365295898234402537336762320382508754921202825754807404557820007055121102645156842126064526301550033503710326243580686202343689290385612858013208292479048892324242891437926936379579771661271219677064396120739803309230502981355688484907132471136023854101013706580243115362738647939748123348684831357244274136458378908357255958491925980356588743876497779219636407873285945202016359307298985412901504489975280743182186498490579824057349140600741150807126892554341838245583515532450000001.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999952908341448... .

To get more digits, we can remark that

( 1 + 2 ) ( 1 − 2 ) = − 1 ⇒ ( 1 + 2 ) 3000 ( 1 − 2 ) 3000 = 1 ⇒ ( 1 − 2 ) 3000 = 1 / ( 1 + 2 ) 3000 ≈ 1 / a 3000 (1 + \sqrt{2}) (1 - \sqrt{2}) = -1 \Rightarrow (1 + \sqrt{2})^{3000} (1 - \sqrt{2})^{3000} = 1 \Rightarrow (1 - \sqrt{2})^{3000} = 1 / (1 + \sqrt{2})^{3000} \approx 1 / a_{3000} .

The fractional part is then 1 − 1 / a 3000 1 - 1 / a_{3000} (the 1 is borrowed from a 3000 a_{3000} ). If we want to use only arbitrary precision integer arithmetic to calculate the digits, instead calculate 1 0 k − 1 0 k / a 3000 10^k - 10^k / a_{3000} . Because we know the first digit after the decimal point is not 0 (it is 9), the number we calculated can be put right after the decimal point. The last digit we find is likely wrong though, so we leave it off. These are the first 10000 digits after the decimal point:

0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999952908341448372842849399950028571600702976824604622364294277954740573328982841254604611608381805302531989889631310800921145954922295992301756007360554085488955696731711226954906852951911837048468536144596050749191051184688697336359583501287063290676216645166351157543266626388116876585719731331197052231868754023064119426006936034298149574551377664879649871821901260149681645684975759327368314651223621254500537951208965100792431466409979782139882182850247059017844450940655035979481781350720211162465477055680061333845502921589067125593497420796424166819501844592466295996556219629673384496173838167848692542543207227695068210003219784022886926045769609902674991344982708104741437143326386829839595679745526172546953728450596519400061309003146391558813701166223803854555254274174228993218714471892905155238777331758593764890401805747824444254542022506782114300989372298134926934977229380162471645845385559019785041304740668775735462581715960402953493331892878893185953939500493999714590897918214282017116573109943277311990922615411872725506226333087804749236018011597965657768525747865247188123254861589432583005082590584591213919886984341767477483762493042232189898553737650916095742112660492766407033674287015535332423767991242444689438079845362744608193939657370523825177523098026590791544066523741569850850147219096490013130679099923154092416542948268310551316010822246154320526197303016217709821685624717635220739795823924123187182156932661182198188458636326758234547981397686352078217855017370992556781307064909684147168437134776989924009199679451751049463902071325078734830913298092919300478922039915049981436775069764631294555244427773656775976033874151651825477172977355365272140816744612776555341087399480285411816039582955340392622428186544329059791044752703188305422093450163231755612499214835127941203374299609377082285319815967876786649484439753101069672031397428599020725117506952109586811753877365473738437413681941890377760268424324761755950394943183758788668028735377092034491552870881119825181837185102966184009018702288882707564563624506934179688750974857511926101243807641478411329085587568621774527068273061264554966411686308946662247874324443665343317848182648308304843633193092457741108759147340711898447111036284688705080156462824851498096167926419387503557144433132173873965959354397565965382458076760556983413838201526008434832062319276538938893726842337789116984355938224191551697494675067898108346693416985859017247239403210556816922488594094854855235413932961712100433607544744618659749839591376100268945269482193820559932577925216939102214967574912760520116247535582113269186094192090009992027293712833250162322698275639475408937528460726068330611250381830311054608130670957837619324189573923941463129066382742400193855319637200435503498300303863082814894795081105312283781767284889805646109216584262530754772918203257074898493219991463964534496698626812142665289181467387527084504478506221572294904756977921950079221244331037255356955994752356210633010447751070424141892512432253150533618312646687947734200094028904480553155206558881651850671046870772695195511129294430398298176986017257231004431360315016868401457330826177562901661596039051008306069149741584072138510184452637483875635725201959739092559132355780162511282547183024382079845372374626877980481029863261318245625461967196525950352080381998580675972712557149212891915976897930298565718840383151071881817753584736889063288346624700469104490596867063066751415708178393268602390005875448727439495701222422922865959953508776318828518401759572467862944992382912810364002743883004903289473298349225103502230630608441393582302113749973137710656811132771098491917811173713302429661262067353181294928268163220479517468951464746925449073140886499590048423943777743514716180734485824952528680400365637871170306752156323794875955432132631429028315051496586039510824109138337167250176880329209616977516607002103360342868180142143694279512350011957831682002894359153024550940363127136353091677514941482837573784465143817723177673912291852321400764119194381679914684184578860049811274303916058757801810498818713950466399430129938096979494707219922710215593627353437068561876285937547747503834732475569990369400226406155321939720137590155121172062347215908103908356693771933397728105336924160958865893582636421148940801166285466771436500817660369817891640514157352261788550824848393879288398029954939513286940010362258467957581022425480757097205235068130635690719849875017511869361423591239084145627036445128287544940463760413913680119691499760638225764712448045793336523208163752566486859676565710140298564984538752426234224889174862687634141862794506946003671477726253829630835632732481935822647500488063917201208895704472740975731675550308940743056133935299513477020489728050813933338552437733223355308602001427800629813582469878762334009520932220432434198052609021402802746920342205063071808035716554704734117871818412924476957214006490392324254973495066381876398994817977801528358124840992648813247761827146777926376951675661060123650181106399502232996057705929103249168965572309264471446913860365024825841372807029554541211113026962199034781825255622088353311595413110371001235576924391191449479464407085273896295856953130127434143434025433245783191752755533037975193009853278639157303966470944721014617015027004023595112875458010661460596332071567411150879378428671647869005996164094419400618791412626843588400429707215070790307351264142391210098187492872349872552009732342540668808846364955079196060379452066886406688203789150039789454630136474715839424647849103279235224792868592357240695680606037149653321891944297444750960123244477632407320669804287152515784295263456845383811711654436431025686385563115615748967166136066194565572100293540544232112834486048337779791803529425757887187298078639555588404128537032073262289009902431617284851989187622137775250180562198080521907339837570508329902463689858213163728010527979024622115972759446572478052047213501338250617184854189870702484708726555563602482469222769732785212070409643380188354524288470075885642291439778007589734970913513849752819972914277419567202712141853260483080739741758934141338699083477716312287901497539572118118987688527622138119498093524966136895551072703125381775890125162053244834324260748164698463450376785760102678213171813486115047848456250338382111506459450381179340951125111584217923071931006047812803297981427180696103530798313003794013210826753439593604166371373632384470559132750475283791022381516202107974388712666697297756144842264263819634719011097723349703208504296025788058369579990407592868409369145594627954903840539823441630188523961808525238714372820256176793437965941676573051954945589856631713206240607663805047492671305089826826303915500258396860156665300829550517431431072699043416239186508895546515359182208915952583073488845552550549128066960031129667868475175457462745692544456357167694708419967020328450200777422866619468615411655627898507249827125618735746979304605038873442826444508192156287408366225856142745149084627588920575580692876437798574596618831697570317989288481334942536254188644969668106271478257960294324420400712064538896491255990242413034139584695789827221317256631816561749330759683691616703885861908735975421417758269088493909489743445179163102209192752902398244075553412785326038761253470975647776572306897373746782724385344731463672205636888829752783205338204941271326382371103620109336817825673492843693473494966199652600736604629478174912802016694768195857231792891873685685201008777889082942145833403783931162667541228828789032566059182231300988081495455830248649348347205311022998256408737628749942582057656391108193520065133121194916724992417707720646573739088306556703199549146184367251319871048984433873926719920847038163997498344580681356622358629837049626311216379277677696928175630230256500432490344875403335975480835144105743556344435211559931363901113816531804772400894225081370334340494300600597208484808311070387747146950205692411949140497485739042940199255749104794698548737386146555397569131530554975189326071378772516228806751550740534920454485012373363142032940361720559608903129807102930494146796819678553824814816784566071160144072532031466798983346344168737180199039480585556255614350579144464509777316647791265203156311667624151994287370647229242609698055590154797748241492189676005053527307414619599614112862226425696909434636589714132372953535202922567154566184141716615144861249512635795059616348504838242467749731697615407964563853461564526381436692356886832166805012171140412283301991815111577054870812264139727905355385457876573181639048726555231126669154472944727702039255043750733569353842229201457084633070975570998521796314500246528284974464072399913966159738362463340828748726969651619902171607718257865323390933626881277774572099590614962573077104528956624104235766475317933639127540787924027633209179917958605 0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999952908341448372842849399950028571600702976824604622364294277954740573328982841254604611608381805302531989889631310800921145954922295992301756007360554085488955696731711226954906852951911837048468536144596050749191051184688697336359583501287063290676216645166351157543266626388116876585719731331197052231868754023064119426006936034298149574551377664879649871821901260149681645684975759327368314651223621254500537951208965100792431466409979782139882182850247059017844450940655035979481781350720211162465477055680061333845502921589067125593497420796424166819501844592466295996556219629673384496173838167848692542543207227695068210003219784022886926045769609902674991344982708104741437143326386829839595679745526172546953728450596519400061309003146391558813701166223803854555254274174228993218714471892905155238777331758593764890401805747824444254542022506782114300989372298134926934977229380162471645845385559019785041304740668775735462581715960402953493331892878893185953939500493999714590897918214282017116573109943277311990922615411872725506226333087804749236018011597965657768525747865247188123254861589432583005082590584591213919886984341767477483762493042232189898553737650916095742112660492766407033674287015535332423767991242444689438079845362744608193939657370523825177523098026590791544066523741569850850147219096490013130679099923154092416542948268310551316010822246154320526197303016217709821685624717635220739795823924123187182156932661182198188458636326758234547981397686352078217855017370992556781307064909684147168437134776989924009199679451751049463902071325078734830913298092919300478922039915049981436775069764631294555244427773656775976033874151651825477172977355365272140816744612776555341087399480285411816039582955340392622428186544329059791044752703188305422093450163231755612499214835127941203374299609377082285319815967876786649484439753101069672031397428599020725117506952109586811753877365473738437413681941890377760268424324761755950394943183758788668028735377092034491552870881119825181837185102966184009018702288882707564563624506934179688750974857511926101243807641478411329085587568621774527068273061264554966411686308946662247874324443665343317848182648308304843633193092457741108759147340711898447111036284688705080156462824851498096167926419387503557144433132173873965959354397565965382458076760556983413838201526008434832062319276538938893726842337789116984355938224191551697494675067898108346693416985859017247239403210556816922488594094854855235413932961712100433607544744618659749839591376100268945269482193820559932577925216939102214967574912760520116247535582113269186094192090009992027293712833250162322698275639475408937528460726068330611250381830311054608130670957837619324189573923941463129066382742400193855319637200435503498300303863082814894795081105312283781767284889805646109216584262530754772918203257074898493219991463964534496698626812142665289181467387527084504478506221572294904756977921950079221244331037255356955994752356210633010447751070424141892512432253150533618312646687947734200094028904480553155206558881651850671046870772695195511129294430398298176986017257231004431360315016868401457330826177562901661596039051008306069149741584072138510184452637483875635725201959739092559132355780162511282547183024382079845372374626877980481029863261318245625461967196525950352080381998580675972712557149212891915976897930298565718840383151071881817753584736889063288346624700469104490596867063066751415708178393268602390005875448727439495701222422922865959953508776318828518401759572467862944992382912810364002743883004903289473298349225103502230630608441393582302113749973137710656811132771098491917811173713302429661262067353181294928268163220479517468951464746925449073140886499590048423943777743514716180734485824952528680400365637871170306752156323794875955432132631429028315051496586039510824109138337167250176880329209616977516607002103360342868180142143694279512350011957831682002894359153024550940363127136353091677514941482837573784465143817723177673912291852321400764119194381679914684184578860049811274303916058757801810498818713950466399430129938096979494707219922710215593627353437068561876285937547747503834732475569990369400226406155321939720137590155121172062347215908103908356693771933397728105336924160958865893582636421148940801166285466771436500817660369817891640514157352261788550824848393879288398029954939513286940010362258467957581022425480757097205235068130635690719849875017511869361423591239084145627036445128287544940463760413913680119691499760638225764712448045793336523208163752566486859676565710140298564984538752426234224889174862687634141862794506946003671477726253829630835632732481935822647500488063917201208895704472740975731675550308940743056133935299513477020489728050813933338552437733223355308602001427800629813582469878762334009520932220432434198052609021402802746920342205063071808035716554704734117871818412924476957214006490392324254973495066381876398994817977801528358124840992648813247761827146777926376951675661060123650181106399502232996057705929103249168965572309264471446913860365024825841372807029554541211113026962199034781825255622088353311595413110371001235576924391191449479464407085273896295856953130127434143434025433245783191752755533037975193009853278639157303966470944721014617015027004023595112875458010661460596332071567411150879378428671647869005996164094419400618791412626843588400429707215070790307351264142391210098187492872349872552009732342540668808846364955079196060379452066886406688203789150039789454630136474715839424647849103279235224792868592357240695680606037149653321891944297444750960123244477632407320669804287152515784295263456845383811711654436431025686385563115615748967166136066194565572100293540544232112834486048337779791803529425757887187298078639555588404128537032073262289009902431617284851989187622137775250180562198080521907339837570508329902463689858213163728010527979024622115972759446572478052047213501338250617184854189870702484708726555563602482469222769732785212070409643380188354524288470075885642291439778007589734970913513849752819972914277419567202712141853260483080739741758934141338699083477716312287901497539572118118987688527622138119498093524966136895551072703125381775890125162053244834324260748164698463450376785760102678213171813486115047848456250338382111506459450381179340951125111584217923071931006047812803297981427180696103530798313003794013210826753439593604166371373632384470559132750475283791022381516202107974388712666697297756144842264263819634719011097723349703208504296025788058369579990407592868409369145594627954903840539823441630188523961808525238714372820256176793437965941676573051954945589856631713206240607663805047492671305089826826303915500258396860156665300829550517431431072699043416239186508895546515359182208915952583073488845552550549128066960031129667868475175457462745692544456357167694708419967020328450200777422866619468615411655627898507249827125618735746979304605038873442826444508192156287408366225856142745149084627588920575580692876437798574596618831697570317989288481334942536254188644969668106271478257960294324420400712064538896491255990242413034139584695789827221317256631816561749330759683691616703885861908735975421417758269088493909489743445179163102209192752902398244075553412785326038761253470975647776572306897373746782724385344731463672205636888829752783205338204941271326382371103620109336817825673492843693473494966199652600736604629478174912802016694768195857231792891873685685201008777889082942145833403783931162667541228828789032566059182231300988081495455830248649348347205311022998256408737628749942582057656391108193520065133121194916724992417707720646573739088306556703199549146184367251319871048984433873926719920847038163997498344580681356622358629837049626311216379277677696928175630230256500432490344875403335975480835144105743556344435211559931363901113816531804772400894225081370334340494300600597208484808311070387747146950205692411949140497485739042940199255749104794698548737386146555397569131530554975189326071378772516228806751550740534920454485012373363142032940361720559608903129807102930494146796819678553824814816784566071160144072532031466798983346344168737180199039480585556255614350579144464509777316647791265203156311667624151994287370647229242609698055590154797748241492189676005053527307414619599614112862226425696909434636589714132372953535202922567154566184141716615144861249512635795059616348504838242467749731697615407964563853461564526381436692356886832166805012171140412283301991815111577054870812264139727905355385457876573181639048726555231126669154472944727702039255043750733569353842229201457084633070975570998521796314500246528284974464072399913966159738362463340828748726969651619902171607718257865323390933626881277774572099590614962573077104528956624104235766475317933639127540787924027633209179917958605