0 1 1 3 2 9 3 25 4 61 5 132 6 259 7 470 8 801 9 1297 10 2013 11 3015 12 4381 13 6202 14 8583 15 11644 16 15521 17 20367 18 26353 19 33669 20 42525 21 53152 22 65803 23 80754 24 98305 25 118781 26 142533 27 169939 28 201405 29 237366 30 278287 31 324664 32 377025 33 435931 34 501977 35 575793 36 658045 37 749436 38 850707 39 962638 40 1086049 41 1221801 42 1370797 43 1533983 44 1712349 45 1906930 46 2118807 47 2349108 48 2599009 49 2869735 50 3162561 51 3478813 52 3819869 53 4187160 54 4582171 55 5006442 56 5461569 57 5949205 58 6471061 59 7028907 60 7624573 61 8259950 62 8936991 63 9657712 64 10424193 65 11238579 66 12103081 67 13019977 68 13991613 69 15020404 70 16108835 71 17259462 72 18474913 73 19757889 74 21111165 75 22537591 76 24040093 77 25621674 78 27285415 79 29034476 80 30872097 81 32801599 82 34826385 83 36949941 84 39175837 85 41507728 86 43949355 87 46504546 88 49177217 89 51971373 90 54891109 91 57940611 92 61124157 93 64446118 94 67910959 95 71523240 96 75287617 97 79208843 98 83291769 99 87541345 100 91962621 101 96560748 102 101340979 103 106308670 104 111469281 105 116828377 106 122391629 107 128164815 108 134153821 109 140364642 110 146803383 111 153476260 112 160389601 113 167549847 114 174963553 115 182637389 116 190578141 117 198792712 118 207288123 119 216071514 120 225150145 121 234531397 122 244222773 123 254231899 124 264566525 125 275234526 126 286243903 127 297602784 128 309319425 129 321402211 130 333859657 131 346700409 132 359933245 133 373567076 134 387610947 135 402074038 136 416965665 137 432295281 138 448072477 139 464306983 140 481008669 141 498187546 142 515853767 143 534017628 144 552689569 145 571880175 146 591600177 147 611860453 148 632672029 149 654046080 150 675993931 151 698527058 152 721657089 153 745395805 154 769755141 155 794747187 156 820384189 157 846678550 158 873642831 159 901289752 160 929632193 161 958683195 162 988455961 163 1018963857 164 1050220413 165 1082239324 166 1115034451 167 1148619822 168 1183009633 169 1218218249 170 1254260205 171 1291150207 172 1328903133 173 1367534034 174 1407058135 175 1447490836 176 1488847713 177 1531144519 178 1574397185 179 1618621821 180 1663834717 181 1710052344 182 1757291355 183 1805568586 184 1854901057 185 1905305973 186 1956800725 187 2009402891 188 2063130237 189 2118000718 190 2174032479 191 2231243856 192 2289653377 193 2349279763 194 2410141929 195 2472258985 196 2535650237 197 2600335188 198 2666333539 199 2733665190 200 2802350241 201 2872408993 202 2943861949 203 3016729815 204 3091033501 205 3166794122 206 3244032999 207 3322771660 208 3403031841 209 3484835487 210 3568204753 211 3653162005 212 3739729821 213 3827930992 214 3917788523 215 4009325634 216 4102565761 217 4197532557 218 4294249893 219 4392741859 220 4493032765 221 4595147142 222 4699109743 223 4804945544 224 4912679745 225 5022337771 226 5133945273 227 5247528129 228 5363112445 229 5480724556 230 5600391027 231 5722138654 232 5845994465 233 5971985721 234 6100139917 235 6230484783 236 6363048285 237 6497858626 238 6634944247 239 6774333828 240 6916056289 241 7060140791 242 7206616737 243 7355513773 244 7506861789 245 7660690920 246 7817031547 247 7975914298 248 8137370049 249 8301429925 250 8468125301 251 8637487803 252 8809549309 253 8984341950 254 9161898111 255 9342250432 256 9525431809 257 9711475395 258 9900414601 259 10092283097 260 10287114813 261 10484943940 262 10685804931 263 10889732502 264 11096761633 265 11306927569 266 11520265821 267 11736812167 268 11956602653 269 12179673594 270 12406061575 271 12635803452 272 12868936353 273 13105497679 274 13345525105 275 13589056581 276 13836130333 277 14086784864 278 14341058955 279 14598991666 280 14860622337 281 15125990589 282 15395136325 283 15668099731 284 15944921277 285 16225641718 286 16510302095 287 16798943736 288 17091608257 289 17388337563 290 17689173849 291 17994159601 292 18303337597 293 18616750908 294 18934442899 295 19256457230 296 19582837857 297 19913629033 298 20248875309 299 20588621535 300 20932912861 301 21281794738 302 21635312919 303 21993513460 304 22356442721 305 22724147367 306 23096674369 307 23474071005 308 23856384861 309 24243663832 310 24635956123 311 25033310250 312 25435775041 313 25843399637 314 26256233493 315 26674326379 316 27097728381 317 27526489902 318 27960661663 319 28400294704 320 28845440385 321 29296150387 322 29752476713 323 30214471689 324 30682187965 325 31155678516 326 31634996643 327 32120195974 328 32611330465 329 33108454401 330 33611622397 331 34120889399 332 34636310685 333 35157941866 334 35685838887 335 36220058028 336 36760655905 337 37307689471 338 37861216017 339 38421293173 340 38987978909 341 39561331536 342 40141409707 343 40728272418 344 41321979009 345 41922589165 346 42530162917 347 43144760643 348 43766443069 349 44395271270 350 45031306671 351 45674611048 352 46325246529 353 46983275595 354 47648761081 355 48321766177 356 49002354429 357 49690589740 358 50386536371 359 51090258942 360 51801822433 361 52521292185 362 53248733901 363 53984213647 364 54727797853 365 55479553314 366 56239547191 367 57007847012 368 57784520673 369 58569636439 370 59363262945 371 60165469197 372 60976324573 373 61795898824 374 62624262075 375 63461484826 376 64307637953 377 65162792709 378 66027020725 379 66900394011 380 67782984957 381 68674866334 382 69576111295 383 70486793376 384 71406986497 385 72336764963 386 73276203465 387 74225377081 388 75184361277 389 76153231908 390 77132065219 391 78120937846 392 79119926817 393 80129109553 394 81148563869 395 82178367975 396 83218600477 397 84269340378 398 85330667079 399 86402660380 400 87485400481 401 88578967983 402 89683443889 403 90798909605 404 91925446941 405 93063138112 406 94212065739 407 95372312850 408 96543962881 409 97727099677 410 98921807493 411 100128170995 412 101346275261 413 102576205782 414 103818048463 415 105071889624 416 106337816001 417 107615914747 418 108906273433 419 110208980049 420 111524123005 421 112851791132 422 114192073683 423 115545060334 424 116910841185 425 118289506761 426 119681148013 427 121085856319 428 122503723485 429 123934841746 430 125379303767 431 126837202644 432 128308631905 433 129793685511 434 131292457857 435 132805043773 436 134331538525 437 135872037816 438 137426637787 439 138995435018 440 140578526529 441 142176009781 442 143787982677 443 145414543563 444 147055791229 445 148711824910 446 150382744287 447 152068649488 448 153769641089 449 155485820115 450 157217288041 451 158964146793 452 160726498749 453 162504446740 454 164298094051 455 166107544422 456 167932902049 457 169774271585 458 171631758141 459 173505467287 460 175395505053 461 177301977930 462 179224992871 463 181164657292 464 183121079073 465 185094366559 466 187084628561 467 189091974357 468 191116513693 469 193158356784 470 195217614315 471 197294397442 472 199388817793 473 201500987469 474 203631019045 475 205779025571 476 207945120573 477 210129418054 478 212332032495 479 214553078856 480 216792672577 481 219050929579 482 221327966265 483 223623899521 484 225938846717 485 228272925708 486 230626254835 487 232998952926 488 235391139297 489 237802933753 490 240234456589 491 242685828591 492 245157171037 493 247648605698 494 250160254839 495 252692241220 496 255244688097 497 257817719223 498 260411458849 499 263026031725 500 265661563101 501 268318178728 502 270996004859 503 273695168250 504 276415796161 505 279158016357 506 281921957109 507 284707747195 508 287515515901 509 290345393022 510 293197508863 511 296071994240 512 298968980481 513 301888599427 514 304830983433 515 307796265369 516 310784578621 517 313796057092 518 316830835203 519 319889047894 520 322970830625 521 326076319377 522 329205650653 523 332358961479 524 335536389405 525 338738072506 526 341964149383 527 345214759164 528 348490041505 529 351790136591 530 355115185137 531 358465328389 532 361840708125 533 365241466656 534 368667746827 535 372119692018 536 375597446145 537 379101153661 538 382630959557 539 386187009363 540 389769449149 541 393378425526 542 397014085647 543 400676577208 544 404366048449 545 408082648155 546 411826525657 547 415597830833 548 419396714109 549 423223326460 550 427077819411 551 430960345038 552 434871055969 553 438810105385 554 442777647021 555 446773835167 556 450798824669 557 454852770930 558 458935829911 559 463048158132 560 467189912673 561 471361251175 562 475562331841 563 479793313437 564 484054355293 565 488345617304 566 492667259931 567 497019444202 568 501402331713 569 505816084629 570 510260865685 571 514736838187 572 519244166013 573 523783013614 574 528353546015 575 532955928816 576 537590328193 577 542256910899 578 546955844265 579 551687296201 580 556451435197 581 561248430324 582 566078451235 583 570941668166 584 575838251937 585 580768373953 586 585732206205 587 590729921271 588 595761692317 589 600827693098 590 605928097959 591 611063081836 592 616232820257 593 621437489343 594 626677265809 595 631952326965 596 637262850717 597 642609015568 598 647991000619 599 653408985570 600 658863150721 601 664353676973 602 669880745829 603 675444539395 604 681045240381 605 686683032102 606 692358098479 607 698070624040 608 703820793921 609 709608793867 610 715434810233 611 721299029985 612 727201640701 613 733142830572 614 739122788403 615 745141703614 616 751199766241 617 757297166937 618 763434096973 619 769610748239 620 775827313245 621 782083985122 622 788380957623 623 794718425124 624 801096582625 625 807515625751 626 813975750753 627 820477154509 628 827020034525 629 833604588936 630 840231016507 631 846899516634 632 853610289345 633 860363535301 634 867159455797 635 873998252763 636 880880128765 637 887805287006 638 894773931327 639 901786266208 640 908842496769 641 915942828771 642 923087468617 643 930276623353 644 937510500669 645 944789308900 646 952113257027 647 959482554678 648 966897412129 649 974358040305 650 981864650781 651 989417455783 652 997016668189 653 1004662501530 654 1012355169991 655 1020094888412 656 1027881872289 657 1035716337775 658 1043598501681 659 1051528581477 660 1059506795293 661 1067533361920 662 1075608500811 663 1083732432082 664 1091905376513 665 1100127555549 666 1108399191301 667 1116720506547 668 1125091724733 669 1133513069974 670 1141984767055 671 1150507041432 672 1159080119233 673 1167704227259 674 1176379592985 675 1185106444561 676 1193885010813 677 1202715521244 678 1211598206035 679 1220533296046 680 1229521022817 681 1238561618569 682 1247655316205 683 1256802349311 684 1266002952157 685 1275257359698 686 1284565807575 687 1293928532116 688 1303345770337 689 1312817759943 690 1322344739329 691 1331926947581 692 1341564624477 693 1351258010488 694 1361007346779 695 1370812875210 696 1380674838337 697 1390593479413 698 1400569042389 699 1410601771915 700 1420691913341 701 1430839712718 702 1441045416799 703 1451309273040 704 1461631529601 705 1472012435347 706 1482452239849 707 1492951193385 708 1503509546941 709 1514127552212 710 1524805461603 711 1535543528230 712 1546342005921 713 1557201149217 714 1568121213373 715 1579102454359 716 1590145128861 717 1601249494282 718 1612415808743 719 1623644331084 720 1634935320865 721 1646289038367 722 1657705744593 723 1669185701269 724 1680729170845 725 1692336416496 726 1704007702123 727 1715743292354 728 1727543452545 729 1739408448781 730 1751338547877 731 1763334017379 732 1775395125565 733 1787522141446 734 1799715334767 735 1811974976008 736 1824301336385 737 1836694687851 738 1849155303097 739 1861683455553 740 1874279419389 741 1886943469516 742 1899675881587 743 1912476931998 744 1925346897889 745 1938286057145 746 1951294688397 747 1964373071023 748 1977521485149 749 1990740211650 750 2004029532151 751 2017389729028 752 2030821085409 753 2044323885175 754 2057898412961 755 2071544954157 756 2085263794909 757 2099055222120 758 2112919523451 759 2126856987322 760 2140867902913 761 2154952560165 762 2169111249781 763 2183344263227 764 2197651892733 765 2212034431294 766 2226492172671 767 2241025411392 768 2255634442753 769 2270319562819 770 2285081068425 771 2299919257177 772 2314834427453 773 2329826878404 774 2344896909955 775 2360044822806 776 2375270918433 777 2390575499089 778 2405958867805 779 2421421328391 780 2436963185437 781 2452584744314 782 2468286311175 783 2484068192956 784 2499930697377 785 2515874132943 786 2531898808945 787 2548005035461 788 2564193123357 789 2580463384288 790 2596816130699 791 2613251675826 792 2629770333697 793 2646372419133 794 2663058247749 795 2679828135955 796 2696682400957 797 2713621360758 798 2730645334159 799 2747754640760 800 2764949600961 801 2782230535963 802 2799597767769 803 2817051619185 804 2834592413821 805 2852220476092 806 2869936131219 807 2887739705230 808 2905631524961 809 2923611918057 810 2941681212973 811 2959839738975 812 2978087826141 813 2996425805362 814 3014854008343 815 3033372767604 816 3051982416481 817 3070683289127 818 3089475720513 819 3108360046429 820 3127336603485 821 3146405729112 822 3165567761563 823 3184823039914 824 3204171904065 825 3223614694741 826 3243151753493 827 3262783422699 828 3282510045565 829 3302331966126 830 3322249529247 831 3342263080624 832 3362372966785 833 3382579535091 834 3402883133737 835 3423284111753 836 3443782819005 837 3464379606196 838 3485074824867 839 3505868827398 840 3526761967009 841 3547754597761 842 3568847074557 843 3590039753143 844 3611332990109 845 3632727142890 846 3654222569767 847 3675819629868 848 3697518683169 849 3719320090495 850 3741224213521 851 3763231414773 852 3785342057629 853 3807556506320 854 3829875125931 855 3852298282402 856 3874826342529 857 3897459673965 858 3920198645221 859 3943043625667 860 3965994985533 861 3989053095910 862 4012218328751 863 4035491056872 864 4058871653953 865 4082360494539 866 4105957954041 867 4129664408737 868 4153480235773 869 4177405813164 870 4201441519795 871 4225587735422 872 4249844840673 873 4274213217049 874 4298693246925 875 4323285313551 876 4347989801053 877 4372807094434 878 4397737579575 879 4422781643236 880 4447939673057 881 4473212057559 882 4498599186145 883 4524101449101 884 4549719237597 885 4575452943688 886 4601302960315 887 4627269681306 888 4653353501377 889 4679554816133 890 4705874022069 891 4732311516571 892 4758867697917 893 4785542965278 894 4812337718719 895 4839252359200 896 4866287288577 897 4893442909603 898 4920719625929 899 4948117842105 900 4975637963581 901 5003280396708 902 5031045548739 903 5058933827830 904 5086945643041 905 5115081404337 906 5143341522589 907 5171726409575 908 5200236477981 909 5228872141402 910 5257633814343 911 5286521912220 912 5315536851361 913 5344679049007 914 5373948923313 915 5403346893349 916 5432873379101 917 5462528801472 918 5492313582283 919 5522228144274 920 5552272911105 921 5582448307357 922 5612754758533 923 5643192691059 924 5673762532285 925 5704464710486 926 5735299654863 927 5766267795544 928 5797369563585 929 5828605390971 930 5859975710617 931 5891480956369 932 5923121563005 933 5954897966236 934 5986810602707 935 6018859909998 936 6051046326625 937 6083370292041 938 6115832246637 939 6148432631743 940 6181171889629 941 6214050463506 942 6247068797527 943 6280227336788 944 6313526527329 945 6346966816135 946 6380548651137 947 6414272481213 948 6448138756189 949 6482147926840 950 6516300444891 951 6550596763018 952 6585037334849 953 6619622614965 954 6654353058901 955 6689229123147 956 6724251265149 957 6759419943310 958 6794735616991 959 6830198746512 960 6865809793153 961 6901569219155 962 6937477487721 963 6973535063017 964 7009742410173 965 7046099995284 966 7082608285411 967 7119267748582 968 7156078853793 969 7193042071009 970 7230157871165 971 7267426726167 972 7304849108893 973 7342425493194 974 7380156353895 975 7418042166796 976 7456083408673 977 7494280557279 978 7532634091345 979 7571144490581 980 7609812235677 981 7648637808304 982 7687621691115 983 7726764367746 984 7766066322817 985 7805528041933 986 7845150011685 987 7884932719651 988 7924876654397 989 7964982305478 990 8005250163439 991 8045680719816 992 8086274467137 993 8127031898923 994 8167953509689 995 8209039794945 996 8250291251197 997 8291708375948 998 8333291667699 999 8375041625950 1000 8416958751201