8 8 9 0 10 9 11 9 12 19 13 19 14 40 15 40 16 81 17 93 18 140 19 173 20 267 21 315 22 461 23 572 24 779 25 970 26 1314 27 1619 28 2152 29 2662 30 3442 31 4265 32 5468 33 6706 34 8502 35 10434 36 13065 37 15969 38 19853 39 24130 40 29769 41 36093 42 44166 43 53357 44 64957 45 78120 46 94585 47 113406 48 136564 49 163163 50 195657 51 232927 52 278157 53 330156 54 392625 55 464625 56 550655 57 649601 58 767291 59 902740 60 1062811 61 1247074 62 1463957 63 1713231 64 2005579 65 2341397 66 2733521 67 3183716 68 3707750 69 4308394 70 5005592 71 5804027 72 6727762 73 7784568 74 9004157 75 10397390 76 12001513 77 13831907 78 15934045 79 18330046 80 21076039 81 24201411 82 27776346 83 31840463 84 36479593 85 41747336 86 47749761 87 54556555 88 62299697 89 71070087 90 81029805 91 92297976 92 105074456 93 119511560 94 135857160 95 154306496 96 175163844 97 198679436 98 225228183 99 255126374 100 288837027 101 326759840 102 369462794 103 417451218 104 471422878 105 532010113 106 600071730 107 676398772 108 762042527 109 857991812 110 965534805 111 1085899329 112 1220664423 113 1371353080 114 1539893722 115 1728173996 116 1938548973 117 2173346201 118 2435442333 119 2727704512 120 3053635444 121 3416762842 122 3821350644 123 4271723549 124 4773069918 125 5330684746 126 5950866419 127 6640090672 128 7405998550 129 8256486322 130 9200818872 131 10248613391 132 11411080434 133 12699918991 134 14128684416 135 15711574982 136 17464968641 137 19406075524 138 21554650506 139 23931530989 140 26560524458 141 29466809972 142 32679055692 143 36227652163 144 40147068205 145 44473942455 146 49249682244 147 54518385152 148 60329749608 149 66736790559 150 73799078576 151 81580280743 152 90151735202 153 99589788713 154 109979796514 155 121413212765 156 133992039334 157 147825711795 158 163036016109 159 179753734950 160 198124145397 161 218303380319 162 240464547020 163 264793857165 164 291497394851 165 320796982664 166 352937749702 167 388183682224 168 426826049950 169 469178716502 170 515587476997 171 566425095371 172 622101745956 173 683059732944 174 749785128122 175 822802271788 176 902686688251 177 990059348978 178 1085601126909 179 1190046781207 180 1304201085169 181 1428932678456 182 1565192002897 183 1714005021808 184 1876493305618 185 2053867606141 186 2247450301736 187 2458669028408 188 2689081689818 189 2940370190532 190 3214368479825 191 3513056414650 192 3838591144186 193 4193301405562 194 4579722571436 195 5000591490902 196 5458885833411 197 5957819588932 198 6500887177271 199 7091860042925 200 7734836015540 201 8434237240541 202 9194865671876 203 10021902582818 204 10920970879967 205 11898136850300 206 12959980043104 207 14113597682007 208 15366683335534 209 16727534466443 210 18205140927228 211 19809196614056 212 21550198901511 213 23439465152709 214 25489244815765 215 27712741605538 216 30124239791003 217 32739133502682 218 35574068897157 219 38646981814404 220 41977258246063 221 45585781718496 222 49495114341364 223 53729556077626 224 58315348874036 225 63280749799403 226 68656261725106 227 74474722538485 228 80771565728093 229 87584928908240 230 94955948044735 231 102928888391552 232 111551477300167 233 120875061074935 234 130954981325731 235 141850762544528 236 153626537518957 237 166351270448352 238 180099238531664 239 194950296044410 240 210990419380395 241 228312019241308 242 247014557292554 243 267204913815968 244 288998086189948 245 312517620329250 246 337896401690835 247 365277161066630 248 394813370100546 249 426669832574919 250 461023699169787 251 498065156826411 252 537998578384526 253 581043325644512 254 627435051468894 255 677426633231730 256 731289648597169 257 789315458258628 258 851816878244118 259 919129434887095 260 991613259330997 261 1069654539605645 262 1153667667930535 263 1244096918012866 264 1341418878373744 265 1446144388519996 266 1558821295714012 267 1680036686773390 268 1810420012341309 269 1950645655908226 270 2101436473838362 271 2263566750723220 272 2437866209464060 273 2625223407035719 274 2826590278051661 275 3042986032028902 276 3275502300249458 277 3525307606020391 278 3793653193473921 279 4081878149870891 280 4391416007449851 281 4723800607103318 282 5080673574079136 283 5463791026666988 284 5875032039203496 285 6316406310867193 286 6790063746733447 287 7298303216552670 288 7843583398915744 289 8428532779819446 290 9055961923240929 291 9728874876225899 292 10450483053030872 293 11224218234832947 294 12053748275694494 295 12942991912610117 296 13896136527548402 297 14917655008489145 298 16012325835025943 299 17185252261541551 300 18441885024426954 301 19788044157132194 302 21229944654199034 303 22774221264072404 304 24427957491247105 305 26198713756335166 306 28094560161866187 307 30124108462795954 308 32296549074135292 309 34621687347343777 310 37109985362250237 311 39772603066636632 312 42621445458212025 313 45669209219723255 314 48929435971367598 315 52416565108514334 316 56145993894346594 317 60134137295008760 318 64398495772660555 319 68957723017368487 320 73831702405913590 321 79041623636417011 322 84610068942853496 323 90561099762082048 324 96920353922115418 325 103715143617042906 326 110974564935230795 327 118729608568703221 328 127013283220701868 329 135860740650265285 330 145309414679693748 331 155399162377977943 332 166172420596361300 333 177674365307737372 334 189953087839541588 335 203059774630372583 336 217048905584142610 337 231978456787597494 338 247910123700401847 339 264909549677187927 340 283046577042794446 341 302395504604188017 342 323035370017374572 343 345050239866632830 344 368529527135175323 345 393568317849588580 346 420267727930517559 347 448735270876654066 348 479085258770842489 349 511439216021973673 350 545926329866688588 351 582683915774433905 352 621857923427523980 353 663603460057759159 354 708085358583224149 355 755478765897844707 356 805969780627363113 357 859756114210454413 358 917047806625008364 359 978067969019468723 360 1043053586726638331 361 1112256353244930332 362 1185943570943364499 363 1264399087326516282 364 1347924305060686384 365 1436839232730334576 366 1531483617154157442 367 1632218122276731634 368 1739425598244581120 369 1853512403646913963 370 1974909827511669684 371 2104075571868510490 372 2241495344674462208 373 2387684521650094549 374 2543189930215045125 375 2708591711715806783 376 2884505318775278794 377 3071583601455131032 378 3270519042973469952 379 3482046096062847324 380 3706943684858941040 381 3946037820700792680 382 4200204401183915524 383 4470372137982463145 384 4757525687566397671 385 5062708927354652159 386 5387028456507820611 387 5731657260822929543 388 6097838626384546032 389 6486890238184866811 390 6900208554227174529 391 7339273387961201717 392 7805652795792048688 393 8301008199043742116 394 8827099843806004972 395 9385792524398953608 396 9979061681076037580 397 10608999793942076313 398 11277823191358696306 399 11987879190958509582 400 12741653699761654057 401 13541779187481588801 402 14391043168358729113 403 15292397101473607657 404 16248965854302362032 405 17264057635250308597 406 18341174550056968924 407 19484023683423161559 408 20696528871658460123 409 21982843063238315982 410 23347361444704047561 411 24794735224283945258 412 26329886263184256359 413 27958022442274629623 414 29684653967595984116 415 31515610497728497299 416 33457059310850249609 417 35515524389841412579 418 37697906658767808211 419 40011505244321906133 420 42464040012263517086 421 45063675247699494407 422 47819044747122881846 423 50739278186399951478 424 53834029051885595298 425 57113503994193797441 426 60588493912574735173 427 64270406624910368876 428 68171301453538507490 429 72303925577618491162 430 76681752506246530985 431 81319022518852955926 432 86230785452990513272 433 91432945682175968333 434 96942309691689360885 435 102776636091526851758 436 108954688504405668445 437 115496291164863941614 438 122422387699751588068 439 129755102923549651305 440 137517808153632032539 441 145735189876977116587 442 154433322311047892377 443 163639743689015492555 444 173383536852696690774 445 183695413982936054252 446 194607806094552457776 447 206154957126195612456 448 218373023299526587024 449 231300177579689179902 450 244976719962654342520 451 259445193424391655975 452 274750506312592894536 453 290940061020487473654 454 308063889783137865234 455 326174797441922149763 456 345328512082196152231 457 365583843398042866387 458 387002849758814609056 459 409651013841920155046 460 433597427882057021236 461 458914988414271154325 462 485680601642856313667 463 513975399329357056119 464 543884966420080104463 465 575499580325630881363 466 608914463168682921202 467 644230046935242406620 468 681552252949517797711 469 720992785634613424680 470 762669442091546941466 471 806706437490536483682 472 853234747928968955438 473 902392470786733176992 474 954325204365644209114 475 1009186446886302466514 476 1067138016772394985008 477 1128350494345113409844 478 1193003687013232086126 479 1261287118137923845777 480 1333400541826785177668 481 1409554483900789674897 482 1489970811471752560497 483 1574883331447899707020 484 1664538420604037500181 485 1759195687617653030026 486 1859128669923619532195 487 1964625565883925187549 488 2075990005359644607308 489 2193541859289337321850 490 2317618091616039990944 491 2448573654288412337128 492 2586782428955444071216 493 2732638216217187802254 494 2886555776351964388141 495 3048971922536693292673 496 3220346670808211561521 497 3401164447955052955895 498 3591935361943784043699 499 3793196536263288582071 500 4005513513178194240867 501 4229481727492176981718 502 4465728056233566249292 503 4714912446106656241043 504 4977729624579662502891 505 5254910896723916367674 506 5547226034173794863446 507 5855485258624746026249 508 6180541326781669315369 509 6523291719512006100290 510 6884680942706842229667 511 7265702942979721233704 512 7667403646349485232393 513 8090883623454574585687 514 8537300890145393163715 515 9007873847465921315182 516 9503884370634026952455 517 10026681051546762742896 518 10577682605250409485782 519 11158381445473322910111 520 11770347440565899739875 521 12415231855579091163797 522 13094771492811407316929 523 13810793037257718319847 524 14565217620363011778316 525 15360065609291769989901 526 16197461636285605073825 527 17079639876179305531571 528 18008949587922511575662 529 18987860929127744470847 530 20018971060880286621987 531 21105010552881424238697 532 22248850107673651480712 533 23453507615179264830938 534 24722155557950301907005 535 26058128779641888271732 536 27464932638903878386579 537 28946251562616161080296 538 30505958022621290383385 539 32148121951437658149441 540 33877020623242279203356 541 35697149017323807668944 542 37613230692621751867052 543 39630229192445072446922 544 41753360010522840830057 545 43988103139563609062358 546 46340216236241812830072 547 48815748426081666373316 548 51421054785170895332285 549 54162811524699275299436 550 57048031918540266509595 551 60084083002646689033921 552 63278703090061316190074 553 66640020133365949640838 554 70176570982274465170461 555 73897321571549158415882 556 77811688091202780496998 557 81929559177851826442022 558 86261319183824588420609 559 90817872566938803423122 560 95610669462610828967812 561 100651732485657946034389 562 105953684828970343874338 563 111529779711294472642068 564 117393931247316374049232 565 123560746797642198328930 566 130045560878417015485537 567 136864470694054832813814 568 144034373379963885276050 569 151573005025182829816614 570 159498981569598525356857 571 167831841652725180079882 572 176592091517201656990464 573 185801252051730328982753 574 195481908085864162579085 575 205657760029849559055674 576 216353677982013898672230 577 227595758406200253072514 578 239411383512725210899326 579 251829283455543145264374 580 264879601491067222893796 581 278593962222476744076598 582 293005543088011197845672 583 308149149229282929095871 584 324061291912328250699374 585 340780270650784419261858 586 358346259219407250392964 587 376801395721928700610581 588 396189876918353417110521 589 416558056991678740370373 590 437954550977531640400020 591 460430343054190966143401 592 484038899936529513198688 593 508836289590460633414236 594 534881305533257826354673 595 562235596957231325758576 596 590963804965913068748641 597 621133705183078184164407 598 652816357049661254417145 599 686086260093857397604932 600 721021517517685354546241 601 757704007412575986153381 602 796219561977995499876154 603 836658155085460187384229 604 879114098595421690969740 605 923686247801916342468001 606 970478216448906471389384 607 1019598601728736316331179 608 1071161219746317375514389 609 1125285351898255676233005 610 1182096002693748385237627 611 1241724169508800830605422 612 1304307124847639640028237 613 1369988711649080143705162 614 1438919652262940481473140 615 1511257871684681160085188 616 1587168835729116103587042 617 1666825904786378852078443 618 1750410703901677912897783 619 1838113509882024388568982 620 1930133656237515455285852 621 2026679956725793885705504 622 2127971148379149959141167 623 2234236354854237317646225 624 2345715571062094258608130 625 2462660169996233593871228 626 2585333432801608015125640 627 2714011103087014094908915 628 2848981966616350867339697 629 2990548457473716608778452 630 3139027291938513960819768 631 3294750131266261499862755 632 3458064274720883235524284 633 3629333384163910648320872 634 3808938241665588270812695 635 3997277541562860777923206 636 4194768718558903558460335 637 4401848813419386669929071 638 4618975378001154829103353 639 4846627421310325605527827 640 5085306398478843632656976 641 5335537244510910763060556 642 5597869454855084146658725 643 5872878214821586890318101 644 6161165580081924783227624 645 6463361710453376733053123 646 6780126159402557932234806 647 7112149221669830431257346 648 7460153341663028508888490 649 7824894585239071236801081 650 8207164177754827320231753 651 8607790111241714524672686 652 9027638823838528223006304 653 9467616954593646416178381 654 9928673177046199833119343 655 10411800114976569252815118 656 10918036344034728303723233 657 11448468482940499784471995 658 12004233378289050578424338 659 12586520386985987127923908 660 13196573760698268513199852 661 13835695136704468564400153 662 14505246139913965775048013 663 15206651100829112036614829 664 15941399894636389432929047 665 16711050906625149343656051 666 17517234129572253171087998 667 18361654398752688849015816 668 19246094770705708515001461 669 20172420051918129360818472 670 21142580484087790880385439 671 22158615592673871369841493 672 23222658205976301777369794 673 24336938652043239860334077 674 25503789141277747276361591 675 26725648342686101015248226 676 28005066162321647314571487 677 29344708732565638640107223 678 30747363621540131915116065 679 32215945272053649638884326 680 33753500680179165807312310 681 35363215323689726901850381 682 37048419351324402256767576 683 38812594044005336991167131 684 40659378559926151994076964 685 42592576975604764544410985 686 44616165635849075497666962 687 46734300825784205191097717 688 48951326779005345666958205 689 51271784036150820783316125 690 53700418169169782605646971 691 56242188886822937711436888 692 58902279538003739721206526 693 61686107029768345724477200 694 64599332178086009112726275 695 67647870509663083556616430 696 70837903534397052299047199 697 74175890508403232088030934 698 77668580708845836382036413 699 81323026242240524894255988 700 85146595409276792965133021 701 89146986649698052340824117 702 93332243092257573476566114 703 97710767735317302905992015 704 102291339285243383661155671 705 107083128680366169618234124 706 112095716329973817736041216 707 117339110098493879325956140 708 122823764066841696386694047 709 128560598103677935205481565 710 134561018281274312272733120 711 140836938171535710634109424 712 147400801059825914626960696 713 154265603115186994535152658 714 161444917557794464422885607 715 168952919865535553471380434 716 176804414064014636127285081 717 185014860145447025143271222 718 193600402664496103720566790 719 202577900560388187948357202 720 211964958257423784170906781 721 221779958097416789120026931 722 232042094160582390538519902 723 242771407532952968550416486 724 253988823081611006669379323 725 265716187800745415770197102 726 277976310794984666772751374 727 290793004968350700769526955 728 304191130490879903884218340 729 318196640117036747487828859 730 332836626434022788874253485 731 348139371120368615565045780 732 364134396299469162194988785 733 380852518075231557314723862 734 398325902341595807673551246 735 416588122960441018408324557 736 435674222407323612948829840 737 455620774987511505517581316 738 476465952730080773607919922 739 498249594071147204897520320 740 521013275443004709300305693 741 544800385889561951339292564 742 569656204834595582849205576 743 595627983133298599283240084 744 622765027544189537668374064 745 651118788762778669174802914 746 680742953165469944641695607 747 711693538416910155348056444 748 744028993101612767081380483 749 777810300545853415431007527 750 813101087004024377984506140 751 849967734389279108680730014 752 888479497737106625595322850 753 928708627596634062959763326 754 970730497553930246934456097 755 1014623737098300187654567633 756 1060470370052751929907186342 757 1108355958797140104105500606 758 1158369754523454113354173759 759 1210604853770698897638412962 760 1265158361498611162333819753 761 1322131560968146405795582224 762 1381630090709362292436049278 763 1443764128866788648931124872 764 1508648585226028609539204366 765 1576403301235637167045406344 766 1647153258353015760540204869 767 1721028795054270128382147658 768 1798165832863788986536426407 769 1878706111771492072139858137 770 1962797435422710281873295455 771 2050593926478915619910919374 772 2142256292565829249231329080 773 2237952103239843023526039622 774 2337856078423396530323177718 775 2442150388775606026197250812 776 2551024968485651637656642106 777 2664677840993433631838047530 778 2783315458164837421021566664 779 2907153053467412404178438555 780 3036415009716841914549483805 781 3171335241984627773907463091 782 3312157596283862323245848337 783 3459136264671717169277878285 784 3612536217435748648702605831 785 3772633653054726031893309132 786 3939716466655335928769304717 787 4114084737711722614074337729 788 4296051237767815189727759058 789 4485941958990161524791304196 790 4684096664394503769245420882 791 4890869460619437285508972581 792 5106629394158727056970870996 793 5331761071996489794744569995 794 5566665307630607943478725776 795 5811759793505107072299360319 796 6067479800916536233763330916 797 6334278908497707196376388979 798 6612629760429848200911729869 799 6903024855575732431478285674 800 7205977368777692623740852811 801 7522022005609381786074913672 802 7851715891925422403726348639 803 8195639499601754719986909094 804 8554397609919009280990644866 805 8928620316093914017554652530 806 9318964066527816750378611406 807 9726112750398426351399391537 808 10150778827289850911535256139 809 10593704502617716050679846994 810 11055662950680401157324250576 811 11537459587234190584929354654 812 12039933393570074389893986238 813 12563958294142147809157960983 814 13110444589883613155779327268 815 13680340449424489608751652773 816 14274633460517774766625862678 817 14894352244065256043373840044 818 15540568133233894511925710430 819 16214396920245011623510943525 820 16917000673525860169739335948 821 17649589628011861966723801015 822 18413424151503353306990589577 823 19209816790087354877946972746 824 20040134395759274020165408878 825 20905800339494723389076032496 826 21808296813155536084040822216 827 22749167223738607906288595869 828 23730018683620321249638249012 829 24752524600583855691206825601 830 25818427371571819381239125693 831 26929541184251967029563245679 832 28087754930650740455114901828 833 29295035237266321188531724902 834 30553429616252594870406638678 835 31865069742434907441167275547 836 33232174861111909809006051522 837 34657055331780768633796818981 838 36142116313131183002001035482 839 37689861594851176327942761058 840 39302897582011657497494821270 841 40983937438009951067435191149 842 42735805392293584233056552581 843 44561441219315713648217343513 844 46463904895433017004735960487 845 48446381440705164347953148315 846 50512185952834167292916727269 847 52664768840749793089148885044 848 54907721265647646040373286310 849 57244780797575516590314858200 850 59679837295986848816573398184 851 62216939022991908057649546648 852 64860298998385037975862764439 853 67614301605862607267918733294 854 70483509460220461483565299493 855 73472670545682264721794745867 856 76586725635912727420285890566 857 79830816006660663747583577041 858 83210291452409966487265498085 859 86730718618838084029976786873 860 90397889663347556861703757792 861 94217831256390551678860761430 862 98196813936807598596664205241 863 102341361834891511030190231291 864 106658262777426679192366880525 865 111154578789481792988978280992 866 115837657008314051266765651349 867 120715141025311769177009741756 868 125794982672526143239477659918 869 131085454270955894025762949216 870 136595161358419484241602709894 871 142333055915510023978407616421 872 148308450108849608862517457778 873 154531030571571302305789343011 874 161010873241733049953936995506 875 167758458780134196748964340510 876 174784688589839863556030899610 877 182100901460543892353032923982 878 189718890861798531644904257157 879 197650922910028017042923855183 880 205909755035208229263506880726 881 214508655374051918470190068874 882 223461422917576609899081426965 883 232782408441963083154026922520 884 242486536252727946446329708141 885 252589326773343603857106039228 886 263106920010638347076915028208 887 274056099930504016222794777747 888 285454319778728140169187838063 889 297319728383053491887475326274 890 309671197473954177240391806151 891 322528350063001558755172916107 892 335911589919183390862792657354 893 349842132185029234391872745517 894 364342035175996885764147820484 895 379434233408177647230033900922 896 395142571901099788683919146663 897 411491841804134513897316027697 898 428507817396858992955071441836 899 446217294515586950010296636743 900 464648130460265785407713872448 901 483829285437935864522401433744 902 503790865601084546888946450455 903 524564167741375384986163855038 904 546181725701529269480276568611 905 568677358570444599054319374948 906 592086220729111059775525825641 907 616444853817356411204686862103 908 641791240694116950735525610344 909 668164861466594597876849042616 910 695606751666512106897127598597 911 724159562654551535797549340425 912 753867624337121466426315648168 913 784777010282688343555266400600 914 816935605328195027830346939949 915 850393175769411773705952885492 916 885201442232596619304775949160 917 921414155328413686868725267073 918 959087174192851614742650761719 919 998278548023723647993414232404 920 1039048600725405775948148120612 921 1081460018778596140334927935544 922 1125577942456255518160751248800 923 1171470060511324213401792004278 924 1219206708466511058675233071654 925 1268860970641217151250730215141 926 1320508786055704760906378778652 927 1374229058357744505203683858175 928 1430103769922394512510689601080 929 1488218100281069786744798395865 930 1548660549041880617334119632843 931 1611523063469133192917155835412 932 1676901170896135361234664256274 933 1744894116151804619206725581937 934 1815605004188285601351342288474 935 1889140948103610469690417307475 936 1965613222760639683488939755625 937 2045137424210853238676341739668 938 2127833635139296326813884710238 939 2213826596554859415086116589575 940 2303245885958374861378658090621 941 2396226102229471288991846184135 942 2492907057482038534602973532435 943 2593433976147240615257311220953 944 2697957701552579399349120476478 945 2806634910275267328518425657455 946 2919628334558433759252587150560 947 3037106993089164952097382690930 948 3159246430448395655356437728005 949 3286228965553917744058136484462 950 3418243949429595324370816927865 951 3555488032645951276504162051489 952 3698165442789978396970731074956 953 3846488272334991905506112971789 954 4000676777294954863583304908415 955 4160959687061623970977858521857 956 4327574525837471375057676044015 957 4500767946092275217687304205838 958 4680796074486944742264182296152 959 4867924870724177802414057518334 960 5062430499802363267117409625154 961 5264599718166346770643013976605 962 5474730274266716528835684279481 963 5693131324057730453090494965258 964 5920123861983355570781791728896 965 6156041168020704456057502762286 966 6401229271370908768237118899459 967 6656047431408729933961565010150 968 6920868636524468790946243757549 969 7196080121514546131166538385761 970 7482083904201002151066615661307 971 7779297341984634412409125410656 972 8088153709062099799424896249346 973 8409102795063558197423382480842 974 8742611525894894990728640598016 975 9089164607596719949669820908102 976 9449265194061785341416048789907 977 9823435579482671398769773620676 978 10212217916433160170481594629288 979 10616174960519115132885214237455 980 11035890842568536165451867510553 981 11471971869365203439800513915318 982 11925047353966617708030908097648 983 12395770476684203565760393210848 984 12884819177842651707030485205948 985 13392897083475229756421350210806 986 13920734465153602203577940185581 987 14469089235193539949654168469644 988 15038747978522611452978680909913 989 15630527022541879271257125340316 990 16245273546361550803366042496674 991 16883866730839775485145292543233 992 17547218950905147129588027780710 993 18236277011696260412420309441916 994 18952023430106722216556229589473 995 19695477763380607400536120698093 996 20467697986462346435649788974259 997 21269781919865689032755086705014 998 22102868709889611034135226158038 999 22968140363074044446113354679798 1000 23866823336856057498541056073481