1000
622687932754 62331981634 7226827357181 971893584833 5721254986 499141473552 2527148274633581 8456161424244 29273848252844 61542755357741421 542373888397581 1498228699 647456418221 657297235 74195761214918863 7768174578832324 143674744229315 269421175867763 77764953653699891 379951773275 4688733952758 6581359125396195 42138151986311926 7484323311628 35152457413 317888671544 26687528936 4917337584979888 668959226 34887138642172993 26991746937376811 1792888426 9998221221926 9671519117148141 115494152218996 135914774 712451915941 22686462435 6198657291836 695476258468 6747771384388 87142387443998499 5685427461953561 846764331733 366618541435 9186399364 928171798 598924826137988 937292978223735 59136436947 89977786989 25543758658169 795476498251 319922885763 6837613299468 246344651134 981558482 45966549158138999 64336941338827644 8854471515227983 9723392472928 1373459314145742 8644792411 947118995 83135324138 5655743957263 33458334136 997477118 2526471655272931 681557683816 82135376296297 3946917436939962 78151388356712 528944842932 64168256496319928 1793559436 973534577747393 78887115993286255 4156483386 48583955948527819 16412214731 7238853411499731 7418212216241499 9375488323 8627993574876684 57647284757471 923814745 37534576217 18473956496729 855873926962 82341648479336287 197429296131 82114751482624166 885417612 681263799 4375935686956 349492191666743 256686125878 2798214842 64853144726 23824726454496 8937377389763 394841631847614 81271674895 7852698154 64659337654457482 64171727391 61426829941169859 5249242281323 537237291 897245335995 1536679199213363 52765612574 9244296196893 1166613891973 8357544786528 84242822528752 2294838982 4813535932464 2476435698488568 88439997112731 166816628224 731245341 12457433314 466524774777 86242853361666 21654768729671 14669159554262146 7176878153497621 862512572831192 476133144195 88781611214642523 334441355773 29646127677196 58624626187869723 17459485279835 179981997655 949263964382 38126761936 72517494926833 911961855612584 846527963 2866263838 24553989146 839292844141591 383541582599 546894996191 366351664377 29675926445681323 877239738517292 34298435967 29789211479218 14736926621 5248133436 918134599666 75262268628793 863145611413 7588436547819 281193193 2319241831 22852649759399279 548416682 893568817 54719918418988252 7423245837592288 9916659243163244 66893783829 6824911345514 2238565244 39758739682 796751389564 4668372799234516 2829829715 8386623189 1997535563 9634628747612 8513272154237 54292233149354 863279955353785 888915891937531 467885856183 8162344111285 552531914198196 33552348737333 853536186553434 8511836486 932642947 389857789691 1919181957365 373842858666 655159738 179898848632245 753892735 7434921792 658592318572 87765676927 7253456473691 944563455117133 378645145 221113267218231 6869959881743 4572814925698122 917624644578 54214983684395 68327584471689729 4934715337649 39236759742 265738881538466 678631335761 6931291726864453 32154376752398579 598479921641 8146819336 4736759327971979 86824926742 37971791427 5259264234527726 4167129116737929 9637165335 1378118592874325 55536421124 943187586196911 485538574 77548851238 259836756618845 494373746591 86118963739431989 8728284681 436157675 868618896 645131178489 39814169577 238847492 314556272 448746269617 79226889864431 9624187338644 734335542 69127986518 522442192 944462375 72946128425 5321949128511 45193171696834253 8567219151227 621594345285 7265974678371143 6122124257959852 896974314 335996258 576849751883 364828931175349 134194129697 151762318423464 798867911198482 53556429184616 45732422153937246 8567423785185 6297817189863 7525591224749 313934933269898 8873969378187997 39945821683 969211485921938 67988916335995 933754156755233 679953657 2767925876782311 2812841224541 67968996741 7823791843595 168318282223914 178816727 56539569344545 9568339637 849651312889821 121267473161 2763479477 79959233712 34994373796776548 475442429141 59834395783 994413964512 339367578849428 544345478174716 3424537593276 98942942146 524635814548 126224164421693 7819951725284361 4969696774934 27575988744714 9322232139148819 55155741895567 33559965186622273 522879371 21714623187287143 5497558966513 8893544521677593 489641997 919133429451 93944241242443 322744156436712 225934933 164997257656348 2936669867154 64645912769967834 7278791345 261565922 525584643417 118417631519 661629498753 49982142443 5551113388197682 277149574521424 175986698396 23416226484648148 193731345122969 919143869711 5873658843962 325798241 9356845943252639 53625139778 441473373319319 23813135317718 74777584863993 66783672714537 4235226984 8388817471578 8314146175226285 97253569873454277 293597177456 53435519358639865 282134571288 1255294654783671 5733337941 7582986738234245 2975443446 53676316457328 75584144154563 944779964 3838712492573 8155161786367875 719829419256 9211791614 767592676565281 9698841152689 1233943164972 4762134783215542 363288974 8928595383725794 1141821274378 812143673644335 829867882 99517938285551 3916869585992421 5157261534 7856815226 6768454791 444427412 457624664935544 525285475187196 238393963 98914736412339 676477667 746983225251 5837323792 53631554854978 21785833245 59361178239974495 442126968632 9768538178749616 23317431161643 435485626521 6229784495677 4959327995545 14949638413955 3354874394527 119949568135382 3895848576954331 44594132786497 87773671936897543 455696531852 448816275729 3566764738313 793634218479964 2963899728222292 9411685178471 7916939296859 12922441545 8385531795594116 14458118724222 8996146378536672 16246843286 34734636565345 79448535219797397 936918746872 44799395413919 33624537589834 4481899911619 58254894564833 51653984679 96135192667388 7838317264327768 2488655899 3944491799 8363535676 843597728 3791692291671334 544335939 11147824224327 28569222342527981 185249469 1676117583219 931659887 2978427596 97388915943 33443518746141635 4814159794315 34491979817951 97263682994491 121379643524 4292488416541918 9355637257953363 21922754452 75255584758476759 61535156511778 7666294399 3283511656837743 999275725153 826223437571754 686543157618 33854857268487 855384319 26937347636294653 96251121439222 9461528724188 25959147968 97985364192 25946799282773888 517475882 262438373236626 473792893557683 238541147 33763175234 5615276887917 284653323689 7535973814474 596885186 644297491719 696668249 8371143277232865 2479191419 442938348268 2647271934353329 2924938766147613 57327644694 938223621133571 111585677 7184145545327 9819955216944 4561786631 247689573491757 68623733454295 7939674741995 47149334387766858 1742923571336519 9372338192984 495851678 51328594181666582 99662922259154123 58816561976 854299183171 346276657866 6389675849717 5554543143127 2598773957811211 73528615233939328 26656112469 223265966883 35876671154692177 847327692292346 2167473747 14782898446 72553855919 6116134483 55434556696 6494748536873 52321877351146 1361581998751 565645939 914135987 85269652296 81658116949791672 918981198953717 992898881833837 2257113361 78649781316872598 715673175 64586372335 354676874873 83845672594111 2698197839252638 66668194199632213 4474789735263625 379874744312 23699149186666 8362529387918 96211149527654 838378478 6764535332736 85465713765178952 78613187946871633 11752273833 818889829971735 989118981927 6197949611 856186922 56962587895 3141993954 65651578991851 631641153778 123253786358474 94669665543455384 43161169195 583552764489828 74174737476 12643292296723748 771296451176 678533886 695623229642116 566282393933 25168253711211 8759337895 272134134545 5571794857 69836668756 672643171 38199245867916561 885321451952229 26699285666181495 82315876158 594489291833273 9915633175329547 18586677834 339417459914 7476939759245433 7326867571943 7598674213668 716544496125599 189723545541 481777658511117 53311263228394964 467237531674 166583942929233 53439172746 286284383 924491419 197425682327723 41173894282669691 71947924466815886 9547441837 95357986323356482 71978867251654 3257136723 7411458323 867553982973746 266323738 3426228857471588 837728299 76495229146358 97986974195 9528814278251 64922293412115 269356492636743 73962913483 55878486275 845833816751345 686457175734322 62835152757 2999347738656115 382399349 26667877115651535 169576748574 85552572544 57229123633597527 36553981914561 4884292422 5346973121194 4992863627915 971897919443513 497951418453 61416478153443 3349519883796957 248792788956139 9123857116761 9649425811 897252432229 75827234224 2874191939533445 4331761922961973 827795348676535 363899719444939 98556884286772346 2713838788376 62965316997648935 615338465498 452859161199 4818444389 85735426339 193145939974427 8647819639793797 9125358449754 35156364374 36823486426 127663587364 16998222427811 85441611495597 13558385451442292 19586929396197174 8715861149292222 8279983692 469974812 43639731383746 7665392757261 8844258135696 5543457986391763 7778794687 2314954413341967 58485983283531865 9499117254934 48453355931483 6949415455 99723959477659448 792261256265845 34346161134713326 169478718358 679236869621244 59447993287116395 5423385875 287945845513635 2973237385 15251238964 27667746769332146 374198936939383 2691781574582 525445539466426 75421472444419745 48676622518 658743516275151 242995859 686193155 58283971599288768 92853344637 6341218873472128 141149752738 3595829847988 236324551 23874312674279 461349332198625 1148896918256567 6295767416 1971129652914 928917578763687 161551837529 42178383469977 44936545144148557 82375461367635644 34457925424 32857689285714 973333751763874 564925521882175 43128256893685391 5534356547 71795392772454378 96535279582622571 64141388751747 1888384896225324 73541727638766399 368485777478 177135313 1832913913373374 14487793152635 936252349548 65391428975232693 488563785117 96834191997922154 3137391841 84648462261432693 896689571424125 47594177228679188 33111555344241 289943578949 26166915136714 8117143464855252 29565162543 1978727438769967 2195464645176 896663928 43656752799 46133943952 22176546514472 23344242942 4493915492 433191979914698 4395776125445398 831566985579453 4178278132641 7121739782253 722266815 69955337655981 4755155918841931 232223941 7447889575 72439477696969416 348252715991 8739612446142 2621845418 53642564124924989 6723957354243617 4718745434458249 48875763933215469 314499387583438 95141924244 5748456776973734 994321733 29599777497436721 6137476262112898 821315494 873693386595454 439659356 57276188714193222 828138615953 481977287147699 86976145422148218 211328767852976 7275635997633 255765145733 9599533619889 7683912958 4112969386 12854993799781 8739693788898 96233943931394 7422195525736898 1718792658258732 476586427393512 2423754616481 924655352848 91119768897468324 81326715179692149 1431943571139828 4633881579486 7585269953341 347969825895975 2421221634117387 647956275825 43495126722151912 76583524386961 7139154115821 949123552 4821649275732644 49291244225815 689721962 45533437446833 781426913446898 8622977169626478 44272653413294 74883277596 141893284871 1315466988168 68576751634186 4828278989134 937369811681956 4737349454881665 76389528321 5884577475835 58411969168578 13494211246355552 347829581 187315335 61736992973761192 1761462772543246 295257241 971797324 76294286897 9179723957637 4633918641814612 9974895975 8932576734512 335446862719213 961675331368766 64835188837 562247957632 9394673351 743949279861744 85723865934863 894124587 544642671922 189652941 82754347188 9599686132 822762311122541 546873331711 5543654491963 746543527729676 5677827581329585 6297129434753729 83575422368 4889897183 7951557666858248 37356375918191 911969877589 837492462 3968463811 584343556816 353583337378 432553369189141 9135255582 1114432618381 6585887641 35739198519888 587353559972 368453941332292 4573245127231582 16747826436 9365535799198112 6683851792 892826154329 9727386644 659831576 9728693785793 442565832 241554311942869 283873986 644236134295 66199882295738 5423247252889 8148199174571886 53882866148459729 9395794625 822138142913239 139118291 87456348857 314116541368 3978268622625766 699543181 96343318425 1266296374181 29741129879 2769534892432 927158379327 78323186544 6295769277 3466153663191 69949864599 5285145383195 1414482929 3854198935542838 3626682369725 648485216558 169119338 62949471527639167 6218328346936294 955679978 9971532972584 954713279687816 2642685691776721 64622377553144 433325246412 1161878859 14413316742911382 75215268126794351 8786717641262 4559519664117 692786745612666 1633582426877747 74256644133347542 1143542137 42282661866113 72117999348886588 44965346742464239 53531812898384922 25782522824248825 68744575383 7919831666113 9869169244294752 165672536331 2991976635 15995335427 9819273273 5323182242 9425958961 14992862416193 72717146284754 456733956464518 964587598476 17218416748136 1484933679837 7373986944 5462742832627441 358462484 1289728785216866 523476661912 9494365968653957 3499736218621 671458866242 6284157411281 3169292479178 2633974846143 28269629378 5589276946593 7481712675435735 474183291747574 827467548667 847539972 68323884573999414 26122128147 13799411435883 27137412214619187 25849559385846833 8465145526823 99511788873 93747775435379634 955397182 9913694652861 46239248449 8252176538831 5187269939 63471964937 9269267353128 6183867551861 3927255617 4625281177479963 1433854333627 5934755658314235 31385998117 49114297446824 7541413954 3731829274293327 93897225151744588 446728833149633 46999831851 94566954284855 1894311564436 428649923 1673863675882299 1315289467459 7961856857345529 896877799874 9634631955373 3287929273 9889731628 429894893 17182946399 3681953414581666 333713346764816 535916472 45865994899344783 241788834831 477476864852674 59663819275 689165342646862 2149519154 21747741953 169981225149 45711418417 11915176962912 21228999624888297 11186737396471996 23972712468 3178843622959866 88897948573371946 39825786624 45176888713314754 25153826113323484 762911368915 1831245916935219 5318568572593 3788645723771 599731989963563 594677736776857 112396251392 2447476341423238 875471867736881 941216759147 532792756 12281465474699 682289411 85793888373245 12414775355 72451644825284837 292442424161654 818533647 28417252255 3741419946894 521275338 48539817918175372 86227436189133264 57239786226 