1000
594136968952621427 215827317698746073 357501764395421 332341789307170369 662580716951798033 494127627192978131 141631869400493 168275561604961 46642007413523 919052778680571949 880661201486794657 914955101102009153 176560166563159 979659690265568209 95244115301161 830443625656368257 383296927289009 428415479673860797 136814864638279 309758004879456109 333832756983541 665163387901659641 503502967663667599 276794010492667 8606018413846823 151007361502146599 67671891971718841 200891853357294329 38857220677469 241971871719889 600455071609062529 147538443504619 231245112883661 889552881011766551 13999661678812009 318880568463959413 64431842570569 528994528027146343 247795672929446339 402548229889921 181780222592659 419555882438529731 214471681337407709 414749907376581971 275634283526821 258098970201037111 486122733041448731 793859967773310253 307361150978712253 253933346255511749 156738613679997631 232665440000034037 250341926481457 101375549258414933 302918467286251 932284587353386271 43117787799731 32327595961163 626089375598229167 779677256161837457 410884118437957 564886980346760861 347644098471026411 13309983132434141 113321294013139 141099138121819 364394668281041753 125759940623197 17910609068750687 154564049281971587 324942747105433 79210118882051 107904528697386991 129299627831276783 229796275954098551 225965945705545057 853220713939750963 405026453303659009 275882644611547933 294542487584197 387978181811782249 827206184857160551 989548064654047057 111832969495308377 930734686887618541 113362076078917 129888859505617 63340089407237 157467417933383557 183109458115693 818252210914919801 654242192035750937 73394738750939 71815534717541 53692819720408333 460673226528513653 164874764146665383 671475171693347191 3432945674126719 206258415756233 122954605686092767 351905214328771 459155766259435681 269903859466289 186605763557031121 135630316603462337 551312375578211407 251650278156279539 536810401234417 419344679957499139 912200529684936097 571662718886402701 939340223099296099 269160747022247863 806693836749579173 79870631992927 425249886588436753 62080035678971 952943562293036387 115058173294067 320142202724987 58755162169946771 214956465285827 102396415996631 60109427673513011 591845771907143849 185582030224363 721336519763093957 322810668288991943 257262614413458431 293633294950815191 123736987131661 227651433930623 86356159050887819 187639470955771 717835221229019423 87177088629173 270494486783268263 238887800238617303 97533629379894727 171083266695053 939824417007407153 968929674098308249 84552659706486977 533559003746438603 95760336426397 872018318678660441 106833041265437 611753906889406189 301454348818485781 896506719404200651 969583596361169789 12397887311545927 336985201430677039 128866062659743 961965837506280239 865768387145024417 77732591390051671 26572305612861329 173366438291040679 19519482259510523 79251100247381 697427193396545581 977259346095745631 236253136556007071 338290649926221809 338422752995641 478394593536546151 126066575857213 291669679981051 262558231925909 163331535235340861 128800852495412771 691299620018936561 67325957760157 297825081872109263 923893497072159737 397883316737249873 853720716777977137 749756642356216667 257728753651786801 48221226475136861 986221168575454379 128678914674229 10733205868021163 496466381779439971 183304948232233 688356961336759003 221696949818479 319049448485701 256098835174508849 483010941452042363 645812255610161603 190256708670940157 219416932873123 34475400937343 448480071671897 879478062241996747 123983501623649 504521305528553897 509636584050233267 307935422452331977 125872168311555733 141477310773076561 206464539005873 55617645018899 112489506810203 425497694096609399 410408707612572997 292903679359944767 10165408615924027 51990026381617 233799168727584773 195280301814989 135131012588499461 314187580015614751 278609247777729263 423937043161309 348703956344190971 478629691683306239 651661625309362817 548128109262505753 70843862375081 395563812269254243 97823694436607 563082232070537 182090690246283293 253925884309308647 572343430497269107 900753591813002549 102754102977059 662675812729341163 79468488119099 306804604587628033 675638822781734263 10451324164163747 196055153155557799 253162368934651027 317202194142679 872152094389369337 124848601865851 897873118564207477 34921125723207343 38225226246060181 778026961706317417 51939743379751 116917193414869 105693227752456321 94386386953057 121169030819021 229437833805461 881382479432106403 462586478444963681 136138630023329 295781626462737179 337335033404587 326093235597179 311805914425254943 777940318446363749 533869066308301 583997664618149129 773359734636654103 62688040038443 529554841187511647 333571004662049611 62470743714377 462125770523593087 228432489131791579 894948133480771549 326626914940979 220968849576205343 84698837035541 539892549231661 97219025342591461 651481513891388987 105142966111979 60602179220744023 283570914188218933 577189283710422731 642038619544316791 618082277315221 769960194254634863 846562269028560047 327015981581563 121545092859913 973941708433652269 111721129529089 46948848180039301 299748692585311 197562409602401 541710462923579101 709485493418139617 494130658835453 2874518842310743 3683165936271487 6735351876218281 248234773789183003 849364630361713211 134085896589049 415716754703355139 179168682200279 696192681354630311 3000229281272357 221557584808663 261726105884317 38935257002740621 96931485759971 149474829049386847 458332051912975711 2120709255411283 251151834744611 186979707291661 164555478569683 370325183905708463 304207420994776031 148550580729443 775839589624855201 192316580813247763 51994109114790107 253970861658813251 800008960035488303 630888525516026353 127434610814104049 259962745233866183 231294929722823963 344898645005377 765981872266025131 386110071549373 435599491360172521 774645876909867233 179305553109169 198682396929840389 648447196000190201 990600741041808283 149001462204368729 412951437245959 291122191837271 93899288308171 207491223607344319 518596324013913157 284565328949519 372004170084761857 68587027289587733 114077909071126769 705173527009214533 37913890482277 235602498135639763 184483041364898641 718016980833542683 112820127133983323 166167700714969673 426922324431354413 445442262391474769 110766952360724917 440268101171273 152154829807609 567036459422810441 120808999958327 365356024316909 344220870505051 441109081499773 377272323565352771 901195217369393899 21479924979281779 801628798825486909 68509471686641 122317723002271 678117548009848333 342056583086839 178258320943227757 106852918899410659 269225105288747 145187212009479287 905601121327931393 801363140196635183 452291671558029931 93409174218391 37626378224994347 113928552478437019 680266461607843261 403021251475459 419815731166143401 116236745732953589 75367859613592439 34461459016206407 199015150720318117 240578554453721963 137880527380010137 51395177074999 856172621962447123 592677207198335099 205713564541663 158998407360858103 898517641831106951 364127421305565721 566333108521741961 785102686486422517 535893410936968351 568854416782297511 712022258712009299 738067125651692537 121579346431393 599117418969699797 342090049801259 261944712865439 137071937162353 19847875168553 216600924061316099 170125880361121 210290532984288083 389843733689527367 981510673604909807 244742143226677879 121897483884643 495817442902277729 286425801971131 242490444352361791 298572478567689829 212341218960213839 166283650691747 378414039096677 152582777442457 543173478461263267 631028553757717561 335280683402516821 489659517220534333 138654536025373 2667065525989237 38407123731711479 992686946224773109 356043984669673 372050190869941 249080567047350761 17542359478667063 830114688785755157 479036810201699 163655228195853599 661162794682759 95799404995409341 371397518580501377 123837268423933 320215298438149 941903048302846727 113317306899749 402629820782587 31815787003172233 104073197468741443 690304087980684041 230425032199687999 970621904182011317 252383183268089 124151995695029 459111424244518847 96750499814233663 569147906137143013 579483642156671713 218407192839899237 135656035578487 242899899397954537 732199232379747053 712295898461402141 272302757530216297 842635437921649979 277682935714291 441069780361974541 83628190734589 623566585173322337 87928653498558659 112743218794537 599851133446098827 154835434129729 820414653288691127 311572918962803 162399465784849 459554440238864731 117752372511973583 88840639897147 288757967490043 896484947506048379 81631860754008457 953983622310833557 376327713053387983 689509887056617271 551634869682557653 206632587080033 326681929935091051 78760463586923 57495964611022271 390580412539775771 111555949051823 140044331880029 247337348217761231 455716203550402937 739711463764937087 153684619887233 896263866350458247 39379411918694759 182092419581164129 626672787138975257 298748507367241 832090194703540027 509867465159501 337630821529255993 497449824323479997 228874132073295883 261315131521151 747612944222399897 601991559037600939 253383666608218319 279003761320306111 312964691520270401 240880120578515063 103710806718877 379725224554667 439824178215767 747292474638065159 477912700184221 460570913938062341 726080088599673751 910648473383193773 122493685374744683 279625923234869 169487961448963 604927611212848277 19655294594788729 857448671080211543 134612910901776821 257287492778001487 34628243274651331 29898644004510409 737922756435970229 285115998566548309 744010384506532379 237395721828071 749898526088592271 357436798222267 844953598472991019 12388011382498991 754422801000718093 259424395461227 531239360400809 17782014731014997 181603545809123 70418978835016093 841040293163782559 64407261086801 261809317191379 123906451092186271 672697764622857383 85388044832641 82480233866746139 26988211455211 279833807107759 514803432235383919 653827032756769 163545264987827 358970584975690829 82939231529447 271844138051951 607594383610139 165769193506079 130684056540307 539095846381399117 921072559569541541 172535821620751 178485432777461 367495427071979 392601180179891 5047629410216719 189091883403192769 789736979153616973 398979908082857 593626517514635071 144636788561557 858719787080591441 54830746135429141 280883100700399 30880863752988499 180539900454671 123373129176318881 714709286501489 862744397305567057 420304329989068367 211259397547970789 438431259231467 733292002036105639 88308598687951 474691124706593 469109399140782553 308192629191533 1704061659965419 227544871662032299 962078616472768523 150742936801883 602640146448759781 85396663240001273 207509215065448991 70291363888019 395689370406321391 514719277697267 411327164025344899 314761786705002037 223191846631695181 36784776832927087 981098666588777131 844437279876226679 264995330717833 150257129389316431 526052767000847 59088661361658737 461998206327342161 189719871312596837 9458838973177849 726704897130171871 48827210081838301 465380943820754237 761843167920458969 220057526471606137 415029596554193 85197698471371 404185064073166601 737465187882529343 65442536204600491 915895992915533789 492352391947693 946726547513312081 120930120096871 694334708576344837 241533178353773 906212018946294457 30867871326576073 146841990735607627 215638689574955363 288716082614264953 611838349583349617 878103242461514149 117480575128183 442713886696393019 245959738972826843 37615062154215737 17441025209012681 40393103392748969 63325614914762891 308097200568847397 910264772868332389 796504550486361131 208691512037187401 485423474663015219 205016721381006149 41486158784251 571986047347773343 631773036162452141 96121603100309489 185667846605597 44305703265987313 224125650508709 476535828271288921 299082901683623 310452586970256749 368995500141110783 361736153974109 740948629241981 956509090533200441 144375992340575279 486394018720615331 313059692288929669 25501781088478963 181024068421213 456549731135185697 719447555478776699 323000526912313111 959717146213827919 986700905128492991 238059228827238817 147134010202676303 18127581531056357 282081314017589 310977526230289 150458660891188861 218445194748445789 300798315506677 271089316712953 127268573594436103 471151843223263 103507232080061 456265871048231 111243560364389 299660414828813 623255678884199533 558744630819493 430204409512771 275405580378823 504185066368583 510002416133789209 98532200697871 124825720708357 718748390163524827 544295151078491 461382108218071 48845338096125997 481648072937539 120137616995269747 334597824278112533 607032100254319 200390808181175483 244215433795008041 471954490351358897 269632950588965819 420566013562623671 730222556362475993 417453489328067 477355135877602421 356395082560249 272081363855909 163236690076003 596331100753112033 581401464867279139 467106976249768991 732863193191374673 512548727556739 130647177142393 39282161687063 431100169387150517 840131414619446371 122860711158083 137331118261087 916194523182488027 195917540193901 997996730833224809 538259948323423567 383541326627017553 370593037144651883 483834205100502917 135879295649554181 54489861772637 19509857377748251 851870326634806033 110683827375983 2720996807675723 936531003481959943 326178382326130721 516279566845943 246856721835553 469361210745739093 992737930465954061 186977659292861 343893223662613 401037764162043563 207429500266398197 144150932994287353 450539595237379 950604389237472787 281247362366143 301086727431434963 30238353691003027 686317179813701 325036026397473709 515390118295566127 194027688714809 60002609906653 187831642253309 49434539181884963 61144817747161 997358582067461827 47233397957981 568796138530666171 210359559622504129 178273319525215141 168224153687297 912411093894766493 914571442499683901 508824917780940799 62435199663768391 286804402578038453 334120274292971 825128478973189841 326244434966696621 623878449506059213 213402033548563 346258304948965489 211463459027283263 252177979544633 792313843576815277 407256411677873 219440280330580367 749878011483257483 179743476655187 155054700424303 144142341336799249 696512250404928781 619232053333471 266701317026659 741987129203935217 173789043650171 390046880398651171 208725045480704147 175722398346671399 49717396948103 967799403533906731 121483160361317 290478713538839611 609675246916528979 777810603371755729 326602482719633 894476100049289867 831211486778823317 459525587825393407 317006758823767 184778349360287 84124278674175473 981678463582796923 336232283136794393 820479899292665897 962643495471320983 798489854098259881 39876411662681747 5221983548241331 244247878384361 278555738239417 246570199689887 588246597030239437 835249998041026301 589628386239457837 806036859771712687 934602868792473193 145692225640699 375296000226859 364268381589929437 420237736665626777 802744879502327 637399724795002361 558388197681563 390377969018077199 567336160749643 496811598981683981 224777736425293 906013366930951007 205640422760611 334146477531287521 84239649154165429 741730371842095417 166619575234283 299323319095739 479975249117479 675578396674897621 263731831789926613 234342584622601997 576279704018197097 549511073864521 208914751799774051 81972366304008307 214789489869888103 256992757088933 176105533721238727 73572286603897 223547663014883 205593572196043 428180207754253 161334988986908459 128140113070665247 69765592816320497 121636172513693 100855842478573661 387534479356942207 466686754984840619 589467584981262329 183742538158037 706287863688462527 467723594320765949 388955537129842621 444404569769873 78942802431461461 246779241079883359 81621366210570257 291832349977017071 690730537643637229 62436235914017711 960461118148301333 285367996166971 302185337815283737 472078280667897227 308868882750227 53895474247619 85335241384093 770296882222225537 763620805495338139 172354747787239 446278588240581293 285799124494991 385456729207679 583175913379059809 774918673700322311 280009276912354163 144160230461691287 877782167616717017 705337047227115547 454215886732921 45893917644397 437335366984998827 449537171287280911 117810805810769 121410350637529 209298490472177 721249309751443171 78944449564489 211402440680828921 842625729111242827 363269849443317337 130420804096601 798822203569255637 312843046899211957 354281605316227 613097746705475159 273107055485010679 22328929526748731 245210837913731 228263055827044439 158702648013444443 505975027296733 1174060690550219 259649170542071 315357433898652713 633580707270226579 319661531602507813 607587650414104523 322934266585097 452292862780523 564914667897886291 528896048784279667 132150533969957 172726147756445807 243579523399181 527699016334885289 462329783998718653 674225516738849051 644424685075144231 245821079116801 56649864973297 412008087054637 140906801860241 409850383748719013 14727344740409893 497467743824477 210417750141463 784311808024819829 635351424308306479 40623104843071637 492161513556277 225439273721279 146126002896631 435214855991430587 353785833490764523 286840832448708113 748830353066165789 309740134664927 527907204428021983 670550244291072947 725870625257819147 807318773492808529 323403705360173 139243527877057 70496229226267927 94535729003293 386166806627513 599598648185317237 220743795487247729 30558497337157091 844555991247108559 972802840810259161 293255328859469 50285890255478401 809647789822351639 139763366151693073 100490538356509381 880835223931272683 663605045544008431 96346155359304197 108087079390167347 255437935830329761 39538145118079 466236349356632443 522121531252411 491217445781649661 539257525713214883 201721206840767 242300838083897 62137210928614553 259329970012609 559345033811792369 614764346256831943 801536403262615739 296029415897515481 183119752372013 511693015328799529 127931663074711 449921458676660221 456541123928023 107184516503284729 239402308779629 943955131587488837