0 1 1 1 2 4 3 12 4 30 5 65 6 127 7 225 8 374 9 588 10 884 11 1281 12 1801 13 2465 14 3300 15 4332 16 5590 17 7105 18 8911 19 11041 20 13534 21 16428 22 19764 23 23585 24 27937 25 32865 26 38420 27 44652 28 51614 29 59361 30 67951 31 77441 32 87894 33 99372 34 111940 35 125665 36 140617 37 156865 38 174484 39 193548 40 214134 41 236321 42 260191 43 285825 44 313310 45 342732 46 374180 47 407745 48 443521 49 481601 50 522084 51 565068 52 610654 53 658945 54 710047 55 764065 56 821110 57 881292 58 944724 59 1011521 60 1081801 61 1155681 62 1233284 63 1314732 64 1400150 65 1489665 66 1583407 67 1681505 68 1784094 69 1891308 70 2003284 71 2120161 72 2242081 73 2369185 74 2501620 75 2639532 76 2783070 77 2932385 78 3087631 79 3248961 80 3416534 81 3590508 82 3771044 83 3958305 84 4152457 85 4353665 86 4562100 87 4777932 88 5001334 89 5232481 90 5471551 91 5718721 92 5974174 93 6238092 94 6510660 95 6792065 96 7082497 97 7382145 98 7691204 99 8009868 100 8338334 101 8676801 102 9025471 103 9384545 104 9754230 105 10134732 106 10526260 107 10929025 108 11343241 109 11769121 110 12206884 111 12656748 112 13118934 113 13593665 114 14081167 115 14581665 116 15095390 117 15622572 118 16163444 119 16718241 120 17287201 121 17870561 122 18468564 123 19081452 124 19709470 125 20352865 126 21011887 127 21686785 128 22377814 129 23085228 130 23809284 131 24550241 132 25308361 133 26083905 134 26877140 135 27688332 136 28517750 137 29365665 138 30232351 139 31118081 140 32023134 141 32947788 142 33892324 143 34857025 144 35842177 145 36848065 146 37874980 147 38923212 148 39993054 149 41084801 150 42198751 151 43335201 152 44494454 153 45676812 154 46882580 155 48112065 156 49365577 157 50643425 158 51945924 159 53273388 160 54626134 161 56004481 162 57408751 163 58839265 164 60296350 165 61780332 166 63291540 167 64830305 168 66396961 169 67991841 170 69615284 171 71267628 172 72949214 173 74660385 174 76401487 175 78172865 176 79974870 177 81807852 178 83672164 179 85568161 180 87496201 181 89456641 182 91449844 183 93476172 184 95535990 185 97629665 186 99757567 187 101920065 188 104117534 189 106350348 190 108618884 191 110923521 192 113264641 193 115642625 194 118057860 195 120510732 196 123001630 197 125530945 198 128099071 199 130706401 200 133353334 201 136040268 202 138767604 203 141535745 204 144345097 205 147196065 206 150089060 207 153024492 208 156002774 209 159024321 210 162089551 211 165198881 212 168352734 213 171551532 214 174795700 215 178085665 216 181421857 217 184804705 218 188234644 219 191712108 220 195237534 221 198811361 222 202434031 223 206105985 224 209827670 225 213599532 226 217422020 227 221295585 228 225220681 229 229197761 230 233227284 231 237309708 232 241445494 233 245635105 234 249879007 235 254177665 236 258531550 237 262941132 238 267406884 239 271929281 240 276508801 241 281145921 242 285841124 243 290594892 244 295407710 245 300280065 246 305212447 247 310205345 248 315259254 249 320374668 250 325552084 251 330792001 252 336094921 253 341461345 254 346891780 255 352386732 256 357946710 257 363572225 258 369263791 259 375021921 260 380847134 261 386739948 262 392700884 263 398730465 264 404829217 265 410997665 266 417236340 267 423545772 268 429926494 269 436379041 270 442903951 271 449501761 272 456173014 273 462918252 274 469738020 275 476632865 276 483603337 277 490649985 278 497773364 279 504974028 280 512252534 281 519609441 282 527045311 283 534560705 284 542156190 285 549832332 286 557589700 287 565428865 288 573350401 289 581354881 290 589442884 291 597614988 292 605871774 293 614213825 294 622641727 295 631156065 296 639757430 297 648446412 298 657223604 299 666089601 300 675045001 301 684090401 302 693226404 303 702453612 304 711772630 305 721184065 306 730688527 307 740286625 308 749978974 309 759766188 310 769648884 311 779627681 312 789703201 313 799876065 314 810146900 315 820516332 316 830984990 317 841553505 318 852222511 319 862992641 320 873864534 321 884838828 322 895916164 323 907097185 324 918382537 325 929772865 326 941268820 327 952871052 328 964580214 329 976396961 330 988321951 331 1000355841 332 1012499294 333 1024752972 334 1037117540 335 1049593665 336 1062182017 337 1074883265 338 1087698084 339 1100627148 340 1113671134 341 1126830721 342 1140106591 343 1153499425 344 1167009910 345 1180638732 346 1194386580 347 1208254145 348 1222242121 349 1236351201 350 1250582084 351 1264935468 352 1279412054 353 1294012545 354 1308737647 355 1323588065 356 1338564510 357 1353667692 358 1368898324 359 1384257121 360 1399744801 361 1415362081 362 1431109684 363 1446988332 364 1462998750 365 1479141665 366 1495417807 367 1511827905 368 1528372694 369 1545052908 370 1561869284 371 1578822561 372 1595913481 373 1613142785 374 1630511220 375 1648019532 376 1665668470 377 1683458785 378 1701391231 379 1719466561 380 1737685534 381 1756048908 382 1774557444 383 1793211905 384 1812013057 385 1830961665 386 1850058500 387 1869304332 388 1888699934 389 1908246081 390 1927943551 391 1947793121 392 1967795574 393 1987951692 394 2008262260 395 2028728065 396 2049349897 397 2070128545 398 2091064804 399 2112159468 400 2133413334 401 2154827201 402 2176401871 403 2198138145 404 2220036830 405 2242098732 406 2264324660 407 2286715425 408 2309271841 409 2331994721 410 2354884884 411 2377943148 412 2401170334 413 2424567265 414 2448134767 415 2471873665 416 2495784790 417 2519868972 418 2544127044 419 2568559841 420 2593168201 421 2617952961 422 2642914964 423 2668055052 424 2693374070 425 2718872865 426 2744552287 427 2770413185 428 2796456414 429 2822682828 430 2849093284 431 2875688641 432 2902469761 433 2929437505 434 2956592740 435 2983936332 436 3011469150 437 3039192065 438 3067105951 439 3095211681 440 3123510134 441 3152002188 442 3180688724 443 3209570625 444 3238648777 445 3267924065 446 3297397380 447 3327069612 448 3356941654 449 3387014401 450 3417288751 451 3447765601 452 3478445854 453 3509330412 454 3540420180 455 3571716065 456 3603218977 457 3634929825 458 3666849524 459 3698978988 460 3731319134 461 3763870881 462 3796635151 463 3829612865 464 3862804950 465 3896212332 466 3929835940 467 3963676705 468 3997735561 469 4032013441 470 4066511284 471 4101230028 472 4136170614 473 4171333985 474 4206721087 475 4242332865 476 4278170270 477 4314234252 478 4350525764 479 4387045761 480 4423795201 481 4460775041 482 4497986244 483 4535429772 484 4573106590 485 4611017665 486 4649163967 487 4687546465 488 4726166134 489 4765023948 490 4804120884 491 4843457921 492 4883036041 493 4922856225 494 4962919460 495 5003226732 496 5043779030 497 5084577345 498 5125622671 499 5166916001 500 5208458334 501 5250250668 502 5292294004 503 5334589345 504 5377137697 505 5419940065 506 5462997460 507 5506310892 508 5549881374 509 5593709921 510 5637797551 511 5682145281 512 5726754134 513 5771625132 514 5816759300 515 5862157665 516 5907821257 517 5953751105 518 5999948244 519 6046413708 520 6093148534 521 6140153761 522 6187430431 523 6234979585 524 6282802270 525 6330899532 526 6379272420 527 6427921985 528 6476849281 529 6526055361 530 6575541284 531 6625308108 532 6675356894 533 6725688705 534 6776304607 535 6827205665 536 6878392950 537 6929867532 538 6981630484 539 7033682881 540 7086025801 541 7138660321 542 7191587524 543 7244808492 544 7298324310 545 7352136065 546 7406244847 547 7460651745 548 7515357854 549 7570364268 550 7625672084 551 7681282401 552 7737196321 553 7793414945 554 7849939380 555 7906770732 556 7963910110 557 8021358625 558 8079117391 559 8137187521 560 8195570134 561 8254266348 562 8313277284 563 8372604065 564 8432247817 565 8492209665 566 8552490740 567 8613092172 568 8674015094 569 8735260641 570 8796829951 571 8858724161 572 8920944414 573 8983491852 574 9046367620 575 9109572865 576 9173108737 577 9236976385 578 9301176964 579 9365711628 580 9430581534 581 9495787841 582 9561331711 583 9627214305 584 9693436790 585 9760000332 586 9826906100 587 9894155265 588 9961749001 589 10029688481 590 10097974884 591 10166609388 592 10235593174 593 10304927425 594 10374613327 595 10444652065 596 10515044830 597 10585792812 598 10656897204 599 10728359201 600 10800180001 601 10872360801 602 10944902804 603 11017807212 604 11091075230 605 11164708065 606 11238706927 607 11313073025 608 11387807574 609 11462911788 610 11538386884 611 11614234081 612 11690454601 613 11767049665 614 11844020500 615 11921368332 616 11999094390 617 12077199905 618 12155686111 619 12234554241 620 12313805534 621 12393441228 622 12473462564 623 12553870785 624 12634667137 625 12715852865 626 12797429220 627 12879397452 628 12961758814 629 13044514561 630 13127665951 631 13211214241 632 13295160694 633 13379506572 634 13464253140 635 13549401665 636 13634953417 637 13720909665 638 13807271684 639 13894040748 640 13981218134 641 14068805121 642 14156802991 643 14245213025 644 14334036510 645 14423274732 646 14512928980 647 14603000545 648 14693490721 649 14784400801 650 14875732084 651 14967485868 652 15059663454 653 15152266145 654 15245295247 655 15338752065 656 15432637910 657 15526954092 658 15621701924 659 15716882721 660 15812497801 661 15908548481 662 16005036084 663 16101961932 664 16199327350 665 16297133665 666 16395382207 667 16494074305 668 16593211294 669 16692794508 670 16792825284 671 16893304961 672 16994234881 673 17095616385 674 17197450820 675 17299739532 676 17402483870 677 17505685185 678 17609344831 679 17713464161 680 17818044534 681 17923087308 682 18028593844 683 18134565505 684 18241003657 685 18347909665 686 18455284900 687 18563130732 688 18671448534 689 18780239681 690 18889505551 691 18999247521 692 19109466974 693 19220165292 694 19331343860 695 19443004065 696 19555147297 697 19667774945 698 19780888404 699 19894489068 700 20008578334 701 20123157601 702 20238228271 703 20353791745 704 20469849430 705 20586402732 706 20703453060 707 20821001825 708 20939050441 709 21057600321 710 21176652884 711 21296209548 712 21416271734 713 21536840865 714 21657918367 715 21779505665 716 21901604190 717 22024215372 718 22147340644 719 22270981441 720 22395139201 721 22519815361 722 22645011364 723 22770728652 724 22896968670 725 23023732865 726 23151022687 727 23278839585 728 23407185014 729 23536060428 730 23665467284 731 23795407041 732 23925881161 733 24056891105 734 24188438340 735 24320524332 736 24453150550 737 24586318465 738 24720029551 739 24854285281 740 24989087134 741 25124436588 742 25260335124 743 25396784225 744 25533785377 745 25671340065 746 25809449780 747 25948116012 748 26087340254 749 26227124001 750 26367468751 751 26508376001 752 26649847254 753 26791884012 754 26934487780 755 27077660065 756 27221402377 757 27365716225 758 27510603124 759 27656064588 760 27802102134 761 27948717281 762 28095911551 763 28243686465 764 28392043550 765 28540984332 766 28690510340 767 28840623105 768 28991324161 769 29142615041 770 29294497284 771 29446972428 772 29600042014 773 29753707585 774 29907970687 775 30062832865 776 30218295670 777 30374360652 778 30531029364 779 30688303361 780 30846184201 781 31004673441 782 31163772644 783 31323483372 784 31483807190 785 31644745665 786 31806300367 787 31968472865 788 32131264734 789 32294677548 790 32458712884 791 32623372321 792 32788657441 793 32954569825 794 33121111060 795 33288282732 796 33456086430 797 33624523745 798 33793596271 799 33963305601 800 34133653334 801 34304641068 802 34476270404 803 34648542945 804 34821460297 805 34995024065 806 35169235860 807 35344097292 808 35519609974 809 35695775521 810 35872595551 811 36050071681 812 36228205534 813 36406998732 814 36586452900 815 36766569665 816 36947350657 817 37128797505 818 37310911844 819 37493695308 820 37677149534 821 37861276161 822 38046076831 823 38231553185 824 38417706870 825 38604539532 826 38792052820 827 38980248385 828 39169127881 829 39358692961 830 39548945284 831 39739886508 832 39931518294 833 40123842305 834 40316860207 835 40510573665 836 40704984350 837 40900093932 838 41095904084 839 41292416481 840 41489632801 841 41687554721 842 41886183924 843 42085522092 844 42285570910 845 42486332065 846 42687807247 847 42889998145 848 43092906454 849 43296533868 850 43500882084 851 43705952801 852 43911747721 853 44118268545 854 44325516980 855 44533494732 856 44742203510 857 44951645025 858 45161820991 859 45372733121 860 45584383134 861 45796772748 862 46009903684 863 46223777665 864 46438396417 865 46653761665 866 46869875140 867 47086738572 868 47304353694 869 47522722241 870 47741845951 871 47961726561 872 48182365814 873 48403765452 874 48625927220 875 48848852865 876 49072544137 877 49297002785 878 49522230564 879 49748229228 880 49975000534 881 50202546241 882 50430868111 883 50659967905 884 50889847390 885 51120508332 886 51351952500 887 51584181665 888 51817197601 889 52051002081 890 52285596884 891 52520983788 892 52757164574 893 52994141025 894 53231914927 895 53470488065 896 53709862230 897 53950039212 898 54191020804 899 54432808801 900 54675405001 901 54918811201 902 55163029204 903 55408060812 904 55653907830 905 55900572065 906 56148055327 907 56396359425 908 56645486174 909 56895437388 910 57146214884 911 57397820481 912 57650256001 913 57903523265 914 58157624100 915 58412560332 916 58668333790 917 58924946305 918 59182399711 919 59440695841 920 59699836534 921 59959823628 922 60220658964 923 60482344385 924 60744881737 925 61008272865 926 61272519620 927 61537623852 928 61803587414 929 62070412161 930 62338099951 931 62606652641 932 62876072094 933 63146360172 934 63417518740 935 63689549665 936 63962454817 937 64236236065 938 64510895284 939 64786434348 940 65062855134 941 65340159521 942 65618349391 943 65897426625 944 66177393110 945 66458250732 946 66740001380 947 67022646945 948 67306189321 949 67590630401 950 67875972084 951 68162216268 952 68449364854 953 68737419745 954 69026382847 955 69316256065 956 69607041310 957 69898740492 958 70191355524 959 70484888321 960 70779340801 961 71074714881 962 71371012484 963 71668235532 964 71966385950 965 72265465665 966 72565476607 967 72866420705 968 73168299894 969 73471116108 970 73774871284 971 74079567361 972 74385206281 973 74691789985 974 74999320420 975 75307799532 976 75617229270 977 75927611585 978 76238948431 979 76551241761 980 76864493534 981 77178705708 982 77493880244 983 77810019105 984 78127124257 985 78445197665 986 78764241300 987 79084257132 988 79405247134 989 79727213281 990 80050157551 991 80374081921 992 80698988374 993 81024878892 994 81351755460 995 81679620065 996 82008474697 997 82338321345 998 82669162004 999 83000998668 1000 83333833334