1000
929625682748791 43281562136 6279398152597652 89748168363995 28614896999 57167695788 543892786181 959616894 4481983113389195 742996847326 595256882 4779485872 67515416653248222 841956984651722 8913849133 864713597247549 264129344 4633661732848 113423557691676 128394478 9219992544 64779954913 232831453227 9347617645 1145633566 1185473632756 93453526279 78196211171273921 941686287985 4659731516 457587113187 36218854152 7517459324 9457891682 868295733 69965487184395 839673153 5125743531126 9745312976848 964331542 35354129846294427 99213433942 1556438496761 613219937 1496123814973 1566518493492749 16541661992479252 5444333917983 34778722161514 193314898217378 932322542433 3567199764 22825996237893 4171646625 1833593198 26347533971193872 6459139342 963436765 9471621199251 7689178278459621 3596662367352 88293354969778341 6396486563695766 9961247329 73172744976549 82651823638 4117982531 3947188672 192279861669679 14217891552814 6498413882 426265488 668739545 99396961123 6192792911298 96825413813863948 211742489 6717259864 948261676669349 54197576962839 89358954145833 188553961 72175223812958 781246836 6888957348413 4617381641339 54593944438 66979169432266882 7425471425549 87724723342 776599334994 2535476647216284 13842217351142537 79666372631 841157412185 266553927939 74896629178 866789187 34711689315 76965214611515165 15178999625999 855217928627 972848986226 8998269972871 26882393597 173225376966138 79235953222 84889586265427 38255785873925 8992694856356 4715166575 7854856444 992378955 198224223 625158271588179 63683668269265 7862376875 359259131761 57979319111 87111731572 6536574764921 628625417587544 49159286155386981 34644748374 267541659257119 6128269338338 819611467192 33685419162285793 94663325495 19797682671194776 89721515287486431 31272781927 19316546415934658 65721154132427 26269628249465662 472725752 92155243286394 19632113397887792 46181125311123798 411662937 617155538 981565154586221 7945625391479 475763397687 774325745 7272221968385 686139272358356 5624642233 2654116759 37695484391184654 32341524781331414 4448545191694371 98195364894752267 88221982374988 61171141648563 41963562315239348 2492838493296372 318352717549 73836834617422 14396431412678613 81537749533964876 95449349675 1116891352934788 2554738622456 9723624526329 29829521329 39725492195678588 28287835392627945 553362798944583 699781846785 63672763533 815718493558876 46183528752754 2198284419547 7132938922 421558683876516 575639875183 351926396768672 98235978624433746 82465967485 762695536 149538876 394691788583 5729126144 98188742974493479 57351578387323 9776444348957 95412873612389614 63357494437533 49192354372 94488663436 39971412398293551 3917346146574 716447333 215245269916 562834322 92253299566127 32735411967867562 4559141667167 84957443754334999 798692156614298 566311638736452 6479392678 2167985616 98826999185917 25765254118935778 95999191765645455 543941555 688134473942498 318935158386 7786381598 86218913833638 164235368618637 897197287 53179851575 7397379952293 82172798157681774 674982866617255 717889167582 59648217925 82977461767881 7195547164 523558243 82143333841 52478434711316173 315232968485797 97166995196166479 38796634289 692646147637291 7284978235849641 361986563196115 7111943387 7427479893813729 9886839815 492254121566184 3917475733 6115661565644717 818151692599294 725591518278 8917127867949 31791837829 555922623 171196883937 5684256265552 841662264 97675327843465368 642715216536978 5937591698715 13869479861897 12287412386 4874353395 27371157854584 76674632821 65669791295 7335488989183399 46774271844 71899267979955634 7749295536656418 2897315945 363163259 6313327196 6371925775717 26785873812236 724586363357752 864925737782 8135936794 1267473962 9152282512 996648659196715 58524961696853791 39697418798858862 41893562771 668982844647966 723251964598 3936512683 235647544 3734651773 28255358493766566 389237117 1377727241949 466367188772 97326183786339786 6424572159 5791165215539592 96757539541785 9676977121321529 163169598 591215714 149895858496 237823918 495939874 7298246762 3219678771121344 39331542123 68145995751996448 142515458364 227324321328884 22854978557352 127276437826 64329721162397 646196958978 441693138352 3197568322398394 6857268276182 2628158192865999 1862939274 76924116336712 57214356718 65429645425 2261973148815 7167462192 6764451544766 9328258187 97191276666754523 452486818524 81185642618253365 69155821551 654125693 795857836597449 2187261334746 33471896535 33356959853 253357764655167 1874526252 6131422663553 52365154163471219 8659455547758152 964353792 26196463993682 1731621522994364 5747857482894617 39413295745295554 8236631837821 148752598842 66586139289687 2777817514249 76961932165679 268852191 5329765297377849 537115942442752 6478354799727539 284463555395 18111597724 3526844141 863799167293498 34471259543 329532631591544 315818486283 69283497169243 977526933 2266616231665697 5287632428286365 9145792826 59434688588689135 416971514767 5485851785441 4686574511 95114188121618 41472771982798 27261762136955 254787838898938 27272724233233 652596538861684 52425386379936 2179128331798 1673294382374 284273619 38349287574786441 649575135 4464586791182276 2954748858371663 94684921198858123 445895167479 232849357786 12777516859687578 21655957755921 7619664254432 22164335492 2757613667 4936492231659263 442324931941788 5817362419 22194784539173782 75239315497333 8368986399 938438417 187716694 5618544755 7945199891887832 929681564 888483119 2398818279938319 55853386736 9739675176118 192645795792211 26222331417755 257127359811 842769113 283326599243676 796776139 578483664998 9629443164 6343459246479 26253341169 649591378575984 9899893929748 2231211234171 7714158997979153 89983323778821 8844114741786371 836861793778 12214719587 99881129523336382 6966562619868953 397864564876 16668731695693887 838963473 22798553136 16221229583 75587525945161563 86455199422394786 95955541859158869 1425757419789 266871458 5491348618672687 324974229 835963621561333 18965873197478 633211473 694939424 9954956157 86527466839449983 7959545527 5777367956344416 556181834418257 18662328449938 51229823599229 45489131337 4466286139 15881418347318675 2564965321596 667379619968 19797926555877653 4931553774868828 96949344258245349 4668484164635 48569495486 8237859293193168 232814737892 3543926663321 279189675 91475387168867813 85238796877649911 64776164461242 171232128597348 943137692927551 475563366848 27166611761 267486163 18893262256578 5816911798157378 239877475278637 52785387216243 7897872138 8226576935351391 612155934 39541884856 31197299282182179 54755474772 8963599276332446 8283462364852615 565338512552 292177852276251 46418654599912533 672383222795824 1277551121 73392581261 5852941269 3296825589465123 79258748638719523 3191653156 1893655913631 599355654 8534942999 5689921611693 22646942167626156 554952931821865 631764929459245 922442797985755 433858454741126 228454171676389 13771512193697 7292542191543 2846663253 73549456829411 75988417813628 33863745822117895 6863228667 87923113343653 817355882347881 6673762535466866 4535267376618874 3288553718356343 31132978766822 3686598711 22854736833826318 71488957114928654 94537352366648234 519124529 277963912151773 19836761714548226 2114745485833455 75897972442 295429549294 6713656812813925 9455651626 76124964622 3961161299865 99924943584565539 95136319556398165 1356191332591783 684785297 3215649855286 9239621492 5851621852 9337121155772 14285972227832763 3521999545681 464152672258771 2922552158335 6551625846326 438286442336 72995369827747 45574597128128 2992791136584881 4593439551216193 15353967562288 312787987342612 783587257 36872577778 93281375189711961 8587565226 2398813616847 62167116661728 48663365574 155729296731349 84379582123217124 216446167746119 94677869783 25831876886178357 419576981972 12336662934532987 3741823286 13913929587 3286845949658 45364614848664943 542852443949698 28868477355139435 677855562979 79186991697 376669512356946 52576813743814 188519316 82664473313198454 9229953289 22158399448232 668175281 44381816556144439 597637775 72554595973 899449386647 25687516594599 4249394963741 123368747913 7856981333165 1263695389224 794237862 768168431945854 178662987914757 5241968851958145 55959687493224 9915546836 516154952 57855738592212261 6313558972237436 9838788396 59613786661 67846546879335986 89162656696283 63332592118899785 91741221877 397168638173 6871473114488 1288773233899835 19797998514177171 432112132284792 939899894 895758731959 4696114335262974 64295434364613449 2698994663848759 316776976763 4299562338 2311967248118 9537217525577141 3322262112297 5975462918116 715769374 637683358559 138399728188 932911384888 46517692923878819 899154975574 458165496617781 714834839 99368986383 3379451393257287 3719354874912 2914263718588 71491394232 443629561 322946394766 316757229 4533461222344524 66916712955 775955612 87578695861 57772168775394823 297476159 8544321858891 1294864936 617385884 745926722811 97685464453157594 6144687475782 9438391637248247 3283492376189 713382197126 3997368352 42548616883 5695256332332427 2727283989883 87874525596 31267162728972 8917727414 81612188141159 1154756864 1445871285845767 4151796145 31986885886 434956282975415 5636828242367825 7965661326166622 33962577934296179 4382963826 8481851344 51951362359233 4595217443 89439276199 73681414486253 427795111815 93555364482 93572799745 3874625724424951 17359487737925679 2351912588629765 61239169679 4241571877727869 829316856 6248895257841 1287381366328455 59254759231 49371649828 47587475463 4992251261371 28639936469162 2973534692518 5774555495689 121743614 51563253553 662241316252 625478176155 64677533523589 59653335356 98174336474331 627812944795638 758597396521456 15512855196563 35281624658118425 818684254325 45766667219179781 8528239667445 154467629 1264761751884137 9162258454692456 817653412752 176336114296747 293926819 9956829185182 6228167286 27586493893 22386579132 5383139614487 985969164679 326112792346628 734672721253755 8794582248 88231234237 224638545 1324184469915 75995418632174 5133934431 211778769 1232676428927478 9395948193 287326948585989 4141751219 58959613619 25123121779676958 7145935757 692959355125 61197595127542 466879336873 81623792778 81763664947 142727773 1711732983 665667394853 55282377156437344 5746532386215 6393895469 15232766974 64482898661 77265398142688 58897814796931973 58696169425 85517691956 846699215 282251926 9374762149 76395318287717 5294682577 5336368542 763221837858762 717577529173669 1723313695236 136354951 37982814656635 5929477436559 9797629981744817 24776499338198988 45337592197966561 2823647667485 4587511737 25933534784 68391478221 798168974968315 178961957395 87963561251724 68635643487235 767946226 6148255562652 486573938869117 1326229555928 738197139 49768721719887281 51955274929952 9615181871 744656516 651163375747 19348166512145229 451893868899273 183989747247 783349111751169 1365689163146 9485328794 82719273674 1646296982436 69783974661 69159966179797 58486923251337161 31174348742514833 33412834285532 5461745591 7188767164779285 2971284695 2857619887175 527166682894 7647718675189727 1283922599737937 5751589713 578279179873681 6863532461876338 3198126889518 968776838 515398138 94249374431886555 149345554 5465671919995987 7539811452 5675271958199962 889616589761287 629397462546378 3611366589 241665129689 7999433457344759 48761766141955 426576876 9114537237216 659923522922343 82656199625425123 337446174756416 437193155392893 214179936 34366884492734 532919433573 4494753364 169832163782145 975984344 4677932378387515 37597439447 92478818944162 1927538598 719649367883594 163559626 758476956 4286473344268 7953289276867 69362915338 1578936575615678 386855124229 839231764591448 2891245725782538 164678855394 81751833536727636 517648187996385 44989726335554972 6293538782828858 7659129452 7939231259 28929236254263279 65422683745528 874392531 9861115769 4394459678469 33594773518316 876214134 69341224716438638 37945717253813 273692394 83829428439325132 6536914365 8461411711 6889473289 122887622574 98463591891734 9619154584444141 33187425143234564 81193484597739 576114562332246 426565385327293 168658386912227 275475234777 86793367574974193 526549712 268545156518983 555171673926 6114897321 113521181642977 887933112369 14936823425512925 752727426 656494282696 26272423145112756 85643951464561 391729187272 1313468478251512 79867749117628679 79159452336 649397582261914 586332917 6411691883383 3962821691 175295614 57624738474 4643189683551 68295194445785714 5268261294 674756356 275137111781119 13979751671319529 53578673268756296 286638636 9718851728515263 2242289155987329 94446584587575 661517465365 8496299852937858 7552837245 6268598848 22235953297 8316696735223717 95393288621782 79962899862268 9848279726829712 55899952699987151 5615151164 125696751398 1117437819876 688719266 98479397293 5566258121475 11481362736669 7735241153 71224831482612746 674535249943 399567724332 7627789455 241745247288 6622349619 7966834449 39545933146183716 431484375988 86638642187859 26832257127169355 881338541459853 98938269675 7914594396667 61628494689527176 98424711284236831 8314528698921192 9729163211696939 954593786688 45626242883148946 41825519871241 97696616897229127 688174931352 89711483632815628 945679447271379 2374216996 6759636568469 36143877969 4533928825 376326669531269 548728719 86715299112617 49567634369243 9319546278391 17933574362 8913953381 5266461714398732 6995282246799176 533342452232 39873712898413 39141516122 7877433897193 334445252974299 1661456194729 439481566513794 18321694173991231 616769483465512 49334312997244 9264892145353245 133469848679213 547962113 5347521535 13769385934 8178456996337592 86828619875 49423954715725145 881263781311785 75461513795645897 82686149129372171 1126918797 2625354396572 3637958116653365 4115467167439 72235413823231945 997746445299 912987449 3821676196755324 311848237166 336444392146 29457427953 17468331948319 822715648 9659148222842356 6145157627858 497742886525 956237486992475 919833113898 844498616 9591816872983 458875967 617599969 8416225993638 618479825679 525189397266 3126518234 197847286526929 