0 1 1 1 2 2 3 6 4 21 5 71 6 212 7 554 8 1289 9 2725 10 5326 11 9758 12 16941 13 28107 14 44864 15 69266 16 103889 17 151913 18 217210 19 304438 20 419141 21 567855 22 758220 23 999098 24 1300697 25 1674701 26 2134406 27 2694862 28 3373021 29 4187891 30 5160696 31 6315042 32 7677089 33 9275729 34 11142770 35 13313126 36 15825013 37 18720151 38 22043972 39 25845834 40 30179241 41 35102069 42 40676798 43 46970750 44 54056333 45 62011291 46 70918960 47 80868530 48 91955313 49 104281017 50 117954026 51 133089686 52 149810597 53 168246911 54 188536636 55 210825946 56 235269497 57 262030749 58 291282294 59 323206190 60 357994301 61 395848643 62 436981736 63 481616962 64 529988929 65 582343841 66 638939874 67 700047558 68 765950165 69 836944103 70 913339316 71 995459690 72 1083643465 73 1178243653 74 1279628462 75 1388181726 76 1504303341 77 1628409707 78 1760934176 79 1902327506 80 2053058321 81 2213613577 82 2384499034 83 2566239734 84 2759380485 85 2964486351 86 3182143148 87 3412957946 88 3657559577 89 3916599149 90 4190750566 91 4480711054 92 4787201693 93 5110967955 94 5452780248 95 5813434466 96 6193752545 97 6594583025 98 7016801618 99 7461311782 100 7929045301 101 8420962871 102 8938054692 103 9481341066 104 10051873001 105 10650732821 106 11279034782 107 11937925694 108 12628585549 109 13352228155 110 14110101776 111 14903489778 112 15733711281 113 16602121817 114 17510113994 115 18459118166 116 19450603109 117 20486076703 118 21567086620 119 22695221018 120 23872109241 121 25099422525 122 26378874710 123 27712222958 124 29101268477 125 30547857251 126 32053880776 127 33621276802 128 35252030081 129 36948173121 130 38711786946 131 40545001862 132 42449998229 133 44429007239 134 46484311700 135 48618246826 136 50833201033 137 53131616741 138 55515991182 139 57988877214 140 60552884141 141 63210678539 142 65964985088 143 68818587410 144 71774328913 145 74835113641 146 78003907130 147 81283737270 148 84677695173 149 88188936047 150 91820680076 151 95576213306 152 99458888537 153 103472126221 154 107619415366 155 111904314446 156 116330452317 157 120901529139 158 125621317304 159 130493662370 160 135522484001 161 140711776913 162 146065611826 163 151588136422 164 157283576309 165 163156235991 166 169210499844 167 175450833098 168 181881782825 169 188507978933 170 195334135166 171 202365050110 172 209605608205 173 217060780763 174 224735626992 175 232635295026 176 240765022961 177 249130139897 178 257736066986 179 266588318486 180 275692502821 181 285054323647 182 294679580924 183 304574171994 184 314744092665 185 325195438301 186 335934404918 187 346967290286 188 358300495037 189 369940523779 190 381893986216 191 394167598274 192 406768183233 193 419702672865 194 432978108578 195 446601642566 196 460580538965 197 474922175015 198 489634042228 199 504723747562 200 520199014601 201 536067684741 202 552337718382 203 569017196126 204 586114319981 205 603637414571 206 621594928352 207 639995434834 208 658847633809 209 678160352585 210 697942547226 211 718203303798 212 738951839621 213 760197504527 214 781949782124 215 804218291066 216 827012786329 217 850343160493 218 874219445030 219 898651811598 220 923650573341 221 949226186195 222 975389250200 223 1002150510818 224 1029520860257 225 1057511338801 226 1086133136146 227 1115397592742 228 1145316201141 229 1175900607351 230 1207162612196 231 1239114172682 232 1271767403369 233 1305134577749 234 1339228129630 235 1374060654526 236 1409644911053 237 1445993822331 238 1483120477392 239 1521038132594 240 1559760213041 241 1599300314009 242 1639672202378 243 1680889818070 244 1722967275493 245 1765918864991 246 1809759054300 247 1854502490010 248 1900163999033 249 1946758590077 250 1994301455126 251 2042807970926 252 2092293700477 253 2142774394531 254 2194265993096 255 2246784626946 256 2300346619137 257 2354968486529 258 2410666941314 259 2467458892550 260 2525361447701 261 2584391914183 262 2644567800916 263 2705906819882 264 2768426887689 265 2832146127141 266 2897082868814 267 2963255652638 268 3030683229485 269 3099384562763 270 3169378830016 271 3240685424530 272 3313323956945 273 3387314256873 274 3462676374522 275 3539430582326 276 3617597376581 277 3697197479087 278 3778251838796 279 3860781633466 280 3944808271321 281 4030353392717 282 4117438871814 283 4206086818254 284 4296319578845 285 4388159739251 286 4481630125688 287 4576753806626 288 4673554094497 289 4772054547409 290 4872278970866 291 4974251419494 292 5077996198773 293 5183537866775 294 5290901235908 295 5400111374666 296 5511193609385 297 5624173526005 298 5739076971838 299 5855930057342 300 5974759157901 301 6095590915611 302 6218452241072 303 6343370315186 304 6470372590961 305 6599486795321 306 6730740930922 307 6864163277974 308 6999782396069 309 7137627126015 310 7277726591676 311 7420110201818 312 7564807651961 313 7711848926237 314 7861264299254 315 8013084337966 316 8167339903549 317 8324062153283 318 8483282542440 319 8645032826178 320 8809345061441 321 8976251608865 322 9145785134690 323 9317978612678 324 9492865326037 325 9670478869351 326 9850853150516 327 10034022392682 328 10220021136201 329 10408884240581 330 10600646886446 331 10795344577502 332 10993013142509 333 11193688737259 334 11397407846560 335 11604207286226 336 11814124205073 337 12027196086921 338 12243460752602 339 12462956361974 340 12685721415941 341 12911794758479 342 13141215578668 343 13374023412730 344 13610258146073 345 13849960015341 346 14093169610470 347 14339927876750 348 14590276116893 349 14844255993107 350 15101909529176 351 15363279112546 352 15628407496417 353 15897337801841 354 16170113519826 355 16446778513446 356 16727377019957 357 17011953652919 358 17300553404324 359 17593221646730 360 17890004135401 361 18190947010453 362 18496096799006 363 18805500417342 364 19119205173069 365 19437258767291 366 19759709296784 367 20086605256178 368 20417995540145 369 20753929445593 370 21094456673866 371 21439627332950 372 21789491939685 373 22144101421983 374 22503507121052 375 22867760793626 376 23236914614201 377 23611021177277 378 23990133499606 379 24374305022446 380 24763589613821 381 25158041570787 382 25557715621704 383 25962666928514 384 26372951089025 385 26788624139201 386 27209742555458 387 27636363256966 388 28068543607957 389 28506341420039 390 28949814954516 391 29399022924714 392 29854024498313 393 30314879299685 394 30781647412238 395 31254389380766 396 31733166213805 397 32218039385995 398 32709070840448 399 33206322991122 400 33709858725201 401 34219741405481 402 34736034872762 403 35258803448246 404 35788111935941 405 36324025625071 406 36866610292492 407 37415932205114 408 37972058122329 409 38535055298445 410 39104991485126 411 39681934933838 412 40265954398301 413 40857119136947 414 41455498915384 415 42061164008866 416 42674185204769 417 43294633805073 418 43922581628850 419 44558101014758 420 45201264823541 421 45852146440535 422 46510819778180 423 47177359278538 424 47851839915817 425 48534337198901 426 49224927173886 427 49923686426622 428 50630692085261 429 51346021822811 430 52069753859696 431 52801966966322 432 53542740465649 433 54292154235769 434 55050288712490 435 55817224891926 436 56593044333093 437 57377829160511 438 58171662066812 439 58974626315354 440 59786805742841 441 60608284761949 442 61439148363958 443 62279482121390 444 63129372190653 445 63988905314691 446 64858168825640 447 65737250647490 448 66626239298753 449 67525223895137 450 68434294152226 451 69353540388166 452 70283053526357 453 71222925098151 454 72173247245556 455 73134112723946 456 74105614904777 457 75087847778309 458 76080905956334 459 77084884674910 460 78099879797101 461 79125987815723 462 80163305856096 463 81211931678802 464 82271963682449 465 83343500906441 466 84426643033754 467 85521490393718 468 86628143964805 469 87746705377423 470 88877276916716 471 90019961525370 472 91174862806425 473 92342085026093 474 93521733116582 475 94713912678926 476 95918729985821 477 97136291984467 478 98366706299416 479 99610081235426 480 100866525780321 481 102136149607857 482 103419063080594 483 104715377252774 484 106025203873205 485 107348655388151 486 108685844944228 487 110036886391306 488 111401894285417 489 112780983891669 490 114174271187166 491 115581872863934 492 117003906331853 493 118440489721595 494 119891741887568 495 121357782410866 496 122838731602225 497 124334710504985 498 125845840898058 499 127372245298902 500 128914046966501 501 130471369904351 502 132044338863452 503 133633079345306 504 135237717604921 505 136858380653821 506 138495196263062 507 140148292966254 508 141817800062589 509 143503847619875 510 145206566477576 511 146926088249858 512 148662545328641 513 150416070886657 514 152186798880514 515 153974864053766 516 155780401939989 517 157603548865863 518 159444441954260 519 161303219127338 520 163180019109641 521 165074981431205 522 166988246430670 523 168919955258398 524 170870249879597 525 172839273077451 526 174827168456256 527 176834080444562 528 178860154298321 529 180905536104041 530 182970372781946 531 185054812089142 532 187159002622789 533 189283093823279 534 191427235977420 535 193591580221626 536 195776278545113 537 197981483793101 538 200207349670022 539 202454030742734 540 204721682443741 541 207010461074419 542 209320523808248 543 211652028694050 544 214005134659233 545 216380001513041 546 218776789949810 547 221195661552230 548 223636778794613 549 226100305046167 550 228586404574276 551 231095242547786 552 233626985040297 553 236181799033461 554 238759852420286 555 241361314008446 556 243986353523597 557 246635141612699 558 249307849847344 559 252004650727090 560 254725717682801 561 257471225079993 562 260241348222186 563 263036263354262 564 265856147665829 565 268701179294591 566 271571537329724 567 274467401815258 568 277388953753465 569 280336375108253 570 283309848808566 571 286309558751790 572 289335689807165 573 292388427819203 574 295467959611112 575 298574472988226 576 301708156741441 577 304869200650657 578 308057795488226 579 311274133022406 580 314518406020821 581 317790808253927 582 321091534498484 583 324420780541034 584 327778743181385 585 331165620236101 586 334581610541998 587 338026913959646 588 341501731376877 589 345006264712299 590 348540716918816 591 352105291987154 592 355700194949393 593 359325631882505 594 362981809911898 595 366668937214966 596 370387223024645 597 374136877632975 598 377918112394668 599 381731139730682 600 385576173131801 601 389453427162221 602 393363117463142 603 397305460756366 604 401280674847901 605 405288978631571 606 409330592092632 607 413405736311394 608 417514633466849 609 421657506840305 610 425834580819026 611 430046080899878 612 434292233692981 613 438573266925367 614 442889409444644 615 447240891222666 616 451627943359209 617 456050798085653 618 460509688768670 619 465004849913918 620 469536517169741 621 474104927330875 622 478710318342160 623 483352929302258 624 488033000467377 625 492750773255001 626 497506490247626 627 502300395196502 628 507132733025381 629 512003749834271 630 516913692903196 631 521862810695962 632 526851352863929 633 531879570249789 634 536947714891350 635 542056040025326 636 547204800091133 637 552394250734691 638 557624648812232 639 562896252394114 640 568209320768641 641 573564114445889 642 578960895161538 643 584399925880710 644 589881470801813 645 595405795360391 646 600973166232980 647 606583851340970 648 612238119854473 649 617936242196197 650 623678490045326 651 629465136341406 652 635296455288237 653 641172722357771 654 647094214294016 655 653061209116946 656 659073986126417 657 665132825906089 658 671238010327354 659 677389822553270 660 683588547042501 661 689834469553263 662 696127877147276 663 702469058193722 664 708858302373209 665 715295900681741 666 721782145434694 667 728317330270798 668 734901750156125 669 741535701388083 670 748219481599416 671 754953389762210 672 761737726191905 673 768572792551313 674 775458891854642 675 782396328471526 676 789385408131061 677 796426437925847 678 803519726316036 679 810665583133386 680 817864319585321 681 825116248258997 682 832421683125374 683 839780939543294 684 847194334263565 685 854662185433051 686 862184812598768 687 869762536711986 688 877395680132337 689 885084566631929 690 892829521399466 691 900630871044374 692 908488943600933 693 916404068532415 694 924376576735228 695 932406800543066 696 940495073731065 697 948641731519965 698 956847110580278 699 965111549036462 700 973435386471101 701 981818963929091 702 990262623921832 703 998766710431426 704 1007331568914881 705 1015957546308321 706 1024644991031202 707 1033394252990534 708 1042205683585109 709 1051079635709735 710 1060016463759476 711 1069016523633898 712 1078080172741321 713 1087207770003077 714 1096399675857774 715 1105656252265566 716 1114977862712429 717 1124364872214443 718 1133817647322080 719 1143336556124498 720 1152921968253841 721 1162574254889545 722 1172293788762650 723 1182080944160118 724 1191936096929157 725 1201859624481551 726 1211851905797996 727 1221913321432442 728 1232044253516441 729 1242245085763501 730 1252516203473446 731 1262857993536782 732 1273270844439069 733 1283755146265299 734 1294311290704280 735 1304939671053026 736 1315640682221153 737 1326414720735281 738 1337262184743442 739 1348183474019494 740 1359178989967541 741 1370249135626359 742 1381394315673828 743 1392614936431370 744 1403911405868393 745 1415284133606741 746 1426733530925150 747 1438260010763710 748 1449863987728333 749 1461545878095227 750 1473306099815376 751 1485145072519026 752 1497063217520177 753 1509060957821081 754 1521138718116746 755 1533296924799446 756 1545536005963237 757 1557856391408479 758 1570258512646364 759 1582742802903450 760 1595309697126201 761 1607959631985533 762 1620693045881366 763 1633510378947182 764 1646412073054589 765 1659398571817891 766 1672470320598664 767 1685627766510338 768 1698871358422785 769 1712201546966913 770 1725618784539266 771 1739123525306630 772 1752716225210645 773 1766397341972423 774 1780167335097172 775 1794026665878826 776 1807975797404681 777 1822015194560037 778 1836145324032846 779 1850366654318366 780 1864679655723821 781 1879084800373067 782 1893582562211264 783 1908173417009554 784 1922857842369745 785 1937636317729001 786 1952509324364538 787 1967477345398326 788 1982540865801797 789 1997700372400559 790 2012956353879116 791 2028309300785594 792 2043759705536473 793 2059308062421325 794 2074954867607558 795 2090700619145166 796 2106545816971485 797 2122490962915955 798 2138536560704888 799 2154683115966242 800 2170931136234401 801 2187281130954961 802 2203733611489522 803 2220289091120486 804 2236948085055861 805 2253711110434071 806 2270578686328772 807 2287551333753674 808 2304629575667369 809 2321813936978165 810 2339104944548926 811 2356503127201918 812 2374009015723661 813 2391623142869787 814 2409346043369904 815 2427178253932466 816 2445120313249649 817 2463172762002233 818 2481336142864490 819 2499611000509078 820 2517997881611941 821 2536497334857215 822 2555109910942140 823 2573836162581978 824 2592676644514937 825 2611631913507101 826 2630702528357366 827 2649889049902382 828 2669192041021501 829 2688612066641731 830 2708149693742696 831 2727805491361602 832 2747580030598209 833 2767473884619809 834 2787487628666210 835 2807621840054726 836 2827877098185173 837 2848253984544871 838 2868753082713652 839 2889374978368874 840 2910120259290441 841 2930989515365829 842 2951983338595118 843 2973102323096030 844 2994347065108973 845 3015718163002091 846 3037216217276320 847 3058841830570450 848 3080595607666193 849 3102478155493257 850 3124490083134426 851 3146632001830646 852 3168904524986117 853 3191308268173391 854 3213843849138476 855 3236511887805946 856 3259313006284057 857 3282247828869869 858 3305316982054374 859 3328521094527630 860 3351860797183901 861 3375336723126803 862 3398949507674456 863 3422699788364642 864 3446588204959969 865 3470615399453041 866 3494782016071634 867 3519088701283878 868 3543536103803445 869 3568124874594743 870 3592855666878116 871 3617729136135050 872 3642745940113385 873 3667906738832533 874 3693212194588702 875 3718662971960126 876 3744259737812301 877 3770003161303227 878 3795893913888656 879 3821932669327346 880 3848120103686321 881 3874456895346137 882 3900943725006154 883 3927581275689814 884 3954370232749925 885 3981311283873951 886 4008405119089308 887 4035652430768666 888 4063053913635257 889 4090610264768189 890 4118322183607766 891 4146190371960814 892 4174215534006013 893 4202398376299235 894 4230739607778888 895 4259239939771266 896 4287900085995905 897 4316720762570945 898 4345702688018498 899 4374846583270022 900 4404153171671701 901 4433623178989831 902 4463257333416212 903 4493056365573546 904 4523021008520841 905 4553151997758821 906 4583450071235342 907 4613915969350814 908 4644550434963629 909 4675354213395595 910 4706328052437376 911 4737472702353938 912 4768788915890001 913 4800277448275497 914 4831939057231034 915 4863774502973366 916 4895784548220869 917 4927969958199023 918 4960331500645900 919 4992869945817658 920 5025586066494041 921 5058480637983885 922 5091554438130630 923 5124808247317838 924 5158242848474717 925 5191859027081651 926 5225657571175736 927 5259639271356322 928 5293804920790561 929 5328155315218961 930 5362691252960946 931 5397413534920422 932 5432322964591349 933 5467420348063319 934 5502706494027140 935 5538182213780426 936 5573848321233193 937 5609705632913461 938 5645754967972862 939 5681997148192254 940 5718432997987341 941 5755063344414299 942 5791889017175408 943 5828910848624690 944 5866129673773553 945 5903546330296441 946 5941161658536490 947 5978976501511190 948 6016991704918053 949 6055208117140287 950 6093626589252476 951 6132247975026266 952 6171073130936057 953 6210102916164701 954 6249338192609206 955 6288779824886446 956 6328428680338877 957 6368285629040259 958 6408351543801384 959 6448627300175810 960 6489113776465601 961 6529811853727073 962 6570722415776546 963 6611846349196102 964 6653184543339349 965 6694737890337191 966 6736507285103604 967 6778493625341418 968 6820697811548105 969 6863120747021573 970 6905763337865966 971 6948626492997470 972 6991711124150125 973 7035018145881643 974 7078548475579232 975 7122303033465426 976 7166282742603921 977 7210488528905417 978 7254921321133466 979 7299582050910326 980 7344471652722821 981 7389591063928207 982 7434941224760044 983 7480523078334074 984 7526337570654105 985 7572385650617901 986 7618668270023078 987 7665186383573006 988 7711940948882717 989 7758932926484819 990 7806163279835416 991 7853632975320034 992 7901342982259553 993 7949294272916145 994 7997487822499218 995 8045924609171366 996 8094605614054325 997 8143531821234935 998 8192704217771108 999 8242123793697802 1000 8291791542033001