lista = [85256327, 49276985, 87432183, 892789, 472769, 29694747, 456185876587, 638365854763, 6523274369, 6747634781, 258745832923, 41694381, 236969278565, 8721454761, 6981854149, 492541, 616521, 476385236283, 814129832389, 858147474523, 8527674383, 85496767, 258565, 496929436965, 638149, 692149, 49656943, 634161, 67456161, 49692741, 436923638985, 214325, 632329, 27634365, 678983894925, 258949272947, 294985218941, 67236541, 636181274347, 27694143, 4963476329, 2543616763, 694927, 2981858165, 67858999, 21678525, 498747, 238123454583, 472963672185, 694943436587, 418383818921, 838567, 492366614723, 296347, 254149, 6189434981, 47476749, 254965816725, 4167814781, 232587294927, 61854783, 89254987, 2127854763, 23236367, 696385, 2549818525, 67618941, 2781256349, 6529472385, 812745, 61474523, 85654523, 678141632361, 698725, 89496547, 87494723, 2367494921, 218581538585, 416323694365, 4941874747, 432785234145, 83878989, 676545438941, 4789272587, 29858321, 87418947, 83416365, 216745658765, 872581, 2961434165, 2163832127, 8729612967, 69418583, 8749616361, 418547, 81492769, 878169, 636323, 892969494389, 636143816345, 414747218787, 29432943, 2583294329, 4141276329, 23678143, 83412125, 61278961, 874727, 4341874783, 2327288529, 858729, 838749, 838785, 8787612965, 256343, 438389658561, 6565898169, 896789432969, 896563418767, 4181832361, 6367296523, 29614349, 65654165, 496763, 272163456367, 65894745, 258747674927, 2589854769, 814785, 658329, 256145234545, 816387, 694382856583, 696161, 6341618129, 894763498785, 476343, 874587652921, 2165852125, 89472987, 41634367, 85632167, 4727872969, 89636125, 6965276945, 69434585, 676741414965, 832765834949, 47469, 6729854783, 4121876765, 632527252929, 898127672921, 2367218927, 83456789, 898963, 27612541, 254127, 814545212323, 832547, 69238365, 63212963, 6165678565, 65256941, 414345258565, 81636965, 69414921, 836345, 438381, 872749238969, 85855, 2127858545, 4123414147, 276549, 812923, 478769854969, 2181894787, 2181258983, 252563, 696145892921, 29234367, 27612581, 2327832929, 652769432383, 2945436383, 414521418381, 2543816761, 698565, 4187819987, 8949498561, 232723, 6543636783, 256383, 836143296365, 6981692985, 618743, 632947, 6561872965, 49836387, 6185814789, 89414941, 41858981, 892569, 43872389, 836941, 832721, 292769432941, 894547278189, 29818347, 2949852381, 87216365, 424927472165, 45252365, 63616549, 856587854985, 4325696329, 478783, 2321856789, 856563, 8565836167, 892725, 2187612389, 2541638925, 656547418147, 298149, 256167, 412129292361, 2347638369, 476781, 6381852563, 6185892569, 27656365, 498621632781, 8789638165, 494569, 21638143, 456587, 292189232141, 27612183, 4147414125, 292345, 6529856529, 274923632985, 8747232981, 418947, 2723418581, 61258965, 2747656943, 2325454387, 45274143, 85436929, 43256749, 4141256167, 214583678767, 8137852165, 8547678341, 498969616729, 67676781, 432749, 872521, 25258161, 4923878329, 412567296383, 69214365, 212147, 614145436767, 676521614569, 4521692521, 21652927, 414341, 23238967, 896945, 4747496343, 63476949, 8949478723, 616747262589, 418725438121, 492585498943, 674767836521, 2525854383, 2761814963, 6725812781, 69276765, 43696529, 476145634123, 258983, 896569478945, 294143412121, 4721434189, 6149218783, 818521, 65458325, 8589612749, 2585876125, 854187, 236349, 678185412527, 458547, 838169, 8529212165, 47876561, 23492783, 61616547, 83298183, 2589952187, 4929876729, 898723832787, 41898523, 854187212727, 874767474169, 618949, 4563474529, 61872987, 2521616143, 4329696967, 256367, 85292381, 25872947, 67474389, 412585, 2945858927, 47818143, 61456925, 25894169, 652767272163, 874149, 898363432123, 63418989, 896361836723, 454963, 23696345, 816149, 8145834963, 436743678381, 4785254929, 674521, 4787234183, 21632363, 292329418981, 63817969, 292381, 8961432189, 494349, 696529, 85498169, 8927676145, 898763292321, 2585218787, 8147294721, 8383698745, 832763216761, 658389, 23216761, 636149454743, 436949454325, 812987, 276125, 412747, 41294387, 25438943, 6529636769, 69854167, 4985654721, 4967163, 4549896967, 6549238725, 674949, 23234189, 834761838547, 29618389, 23894381, 696963878383, 434349, 816325, 836545, 4121274527, 836569232941, 894923, 8183292325, 61892967, 212965438723, 27232349, 47472347, 612565856561, 4925232783, 4181221, 25638729, 412987278725, 496163, 69412763, 4367294989, 878941292785, 498749, 672543838321, 4943298589, 476161876787, 476341, 256947, 476983676563, 832145, 4749858787, 8143614521, 87454923, 69632581, 694161, 432565652585, 87812327, 4327832547, 832327618741, 67673872521, 65672729, 2749416389, 49492161, 892789, 4381616161, 21832167, 492389434589, 676343, 8763232743, 69232783, 454527, 23838741, 838121, 2329658987, 27456323, 212189, 258561, 8521678161, 61252127, 6169652527, 61496781, 698543238169, 294561816589, 4581212767, 254781498761, 87656563, 63898987, 89267, 478749478729, 8749834785, 83692589, 896521272387, 432321, 416565878781, 854121, 414383816985, 454581, 678527696923, 89672981, 292983814125, 2521276163, 896587698383, 874965, 452967, 6921856941, 4389454529, 47698969, 63432561, 61818769, 694525838121, 8989436947, 852565278789, 81432325, 636389, 234323, 676961638167, 8181632125, 47414983, 676725618785, 2325816525, 278943612965, 852163432323, 8189236541, 872127, 2947272743, 838581, 854521694187, 636561, 4983278365, 29474147, 434323858541, 81616963, 672165, 494923698567, 238147, 478989, 496121452945, 4787418121, 8527636125, 61654929, 658763434341, 254327438125, 6385436169, 23432181, 2383658523, 4783298341, 45816327, 2783876387, 496521234565, 238147, 8343256149, 272547456967, 852745432547, 2181296769, 658543, 47234565, 812347, 672587, 8381436381, 45652163, 2749436967, 4981214341, 412365654527, 25634161, 67472125, 63634765, 876723234789, 236147, 2325876163, 876167, 836321, 8923634361, 656781, 6523414789, 63472789, 832361494563, 232947612185, 4961216361, 2927894547, 638585, 25234329, 832767696169, 6349274163, 69212963, 854563692989, 694343, 6721654929, 476725, 43858181, 67492529, 4767298769, 4783836983, 612183, 2121852523, 6545896167, 6127496761, 836567296527, 278521, 814547694121, 218965672945, 8541632361, 89836745, 2367852961, 2323212761, 2567616743, 6969838387, 852145, 2389612567, 41236187, 89672963, 2543674543, 87478381, 658585658541, 25658767, 47492965, 432941, 838981, 8989432541, 21434183, 232927658967, 854349, 218963874567, 83478527, 876721, 832985, 4581814147, 4749852727, 43494165, 834747874523, 25672943, 27438145, 474761834345, 45218963, 65274545, 65478947, 6921812765, 63898549, 432785, 476743, 452165, 69472763, 43212327, 27414923, 292729, 496965492521, 674725, 292389674363, 4743436187, 654725456981, 698343, 45278125, 21692969, 234989, 2349654165, 45496165, 476549, 452947, 45452325, 89474789, 476581412743, 876983418361, 498167638149, 25232323, 496945, 4965418747, 856747, 69254581, 27218525, 812381, 6523416181, 81854121, 2563612741, 634547494165, 27816141, 416323, 612183, 63698345, 69678563, 638149452123, 2367612367, 8185892543, 45612381, 618561296921, 678583458561, 43216767, 832745, 6383894749, 2323298921, 234989496947, 696389, 454323, 6565616361, 2527274947, 4525696169, 49454947, 4381654169, 494989, 294383, 43498161, 6163456389, 474929292743, 85494965, 2723498963, 4547278989, 634927, 672963, 25812763, 6387676943, 25294167, 45454925, 432767296187, 65854725, 8567276983, 418123, 67438545, 2743438363, 2125856343, 254529852349, 23274987, 656587614945, 836169, 2363872127, 218961674123, 2987292369, 61614565, 41618943, 23652765, 876189, 874389, 892181, 4721298961, 894149496361, 4521472527, 618923292565, 45452325, 898725, 6149898125, 856529672923, 692329696189, 852923, 41618185, 67494965, 65254147, 65678947, 4949618387, 81872969, 8521294781, 676723, 21496125, 4749698149, 6947478785, 81678387, 616147, 696161, 232741416969, 214723856143, 4729692787, 4361238341, 216525674341, 2945474929, 67274741, 47698345, 852165, 69274963, 898325292547, 65896327, 434549676341, 452163816187, 876963812747, 83238785, 814327494143, 65696183, 2389896523, 8585694143, 8929632783, 65658163, 2943656129, 658547478589, 41498985, 87496185, 234147, 29676585, 296945, 892389, 694381, 4347276345, 816943, 2947218969, 45498945, 4587854945, 8923454561, 47458987, 276345, 4785874327, 274381218387, 698967494569, 692361216785, 49636341, 656741, 67418383, 874787616965, 85214925, 638323272545, 8349436769, 656547698187, 8963256321, 2323492327, 272727, 69434787, 472789892167, 8965416187, 6381292767, 8943436327, 698329276925, 454329676523, 8525296169, 692969232789, 476343478947, 216747214145, 274729478143, 816923, 2523696989, 61638943, 498129492525, 654183, 41632383, 47854149, 616723, 876567834341, 8589476543, 6347874781, 69676725, 612789, 4543892985, 496367632347, 8169412567, 61678583, 2781638747, 2367816727, 296325, 454327814129, 8767258325, 412361, 21258327, 658367258549, 41672763, 672761, 61634169, 438723, 87818125, 216325836167, 6327814541, 292369816741, 254143, 654543, 652383856967, 21818963, 236541, 698529656529, 498525672325, 8321476365, 612565, 474987, 61698123, 49638945, 6149898727, 452363, 63632761, 43474583, 892789872387, 618947634783, 61216987, 89896941, 89238165, 6167436989, 476541692183, 896565, 678547, 8945454569, 21212147, 238947, 858767476345, 6929872529, 476941, 2389454527, 278989492925, 676565, 6161654389, 29816789, 876721612161, 45452581, 272385, 6363894545, 81296563, 418989, 812341278181, 236365, 2949658583, 816189674741, 658781, 2989298745, 49678529, 636183, 876361872367, 292727, 694985, 834525858981, 258781, 874549, 894969, 618141, 87238581, 8985214167, 258389498561, 418789638381, 612141274585, 6987694581, 2923674169, 27898561, 612325832949, 874529, 212389, 49614721, 474923654521, 452727496581, 858589, 8381834561, 4941832729, 456767, 8387614383, 21292983, 416761834783, 476963498563, 8741498145, 47816141, 2963634921, 698743232347, 49632181, 41678747, 816189292327, 8585852763, 694789, 4963698147, 872329256789, 674981, 65234789, 812369, 452147, 492345438581, 674529652527, 6383296385, 85234381, 496167, 89658589, 856363432363, 614569276941, 23634127, 2767652983, 856123814383, 672387, 698983, 418327258547, 654587636969, 29414729, 2387896741, 432541, 436149, 818565238147, 632763, 676325, 2965616963, 872927, 672127, 256587418527, 65492167, 63858167, 29256963, 456741418387, 454347636567, 678587852789, 434921, 2781612923, 816961, 6749494529, 652163636783, 436947, 894781, 872989412789, 87472383, 294563, 2565698741, 47458381, 6961832583, 8165274789, 81252387, 27434921, 8745654521, 2783636783, 252543298929, 832349418529, 87298743, 45254141, 478323414163, 694325612963, 494149, 436349878325, 254589, 87696965, 41494781, 25296525, 4761838325, 436167232125, 496527, 638563254183, 874561, 274925894767, 63236143, 2523278565, 61894563, 8381218167, 2169218161, 29656967, 674383698345, 812523672567, 4567894585, 29294147, 458927, 83214745, 69614561, 492567256543, 672349674761, 29296781, 616541674989, 63812369, 63256161, 83416165, 8563618521, 816149674143, 232927, 456783, 6385836927, 87418349, 47696963, 614121, 29834925, 894567892727, 898929, 6725874525, 212927, 452965]