0 0 1 3 2 17 3 52 4 121 5 240 6 428 7 707 8 1102 9 1641 10 2355 11 3278 12 4447 13 5902 14 7686 15 9845 16 12428 17 15487 18 19077 19 23256 20 28085 21 33628 22 39952 23 47127 24 55226 25 64325 26 74503 27 85842 28 98427 29 112346 30 127690 31 144553 32 163032 33 183227 34 205241 35 229180 36 255153 37 283272 38 313652 39 346411 40 381670 41 419553 42 460187 43 503702 44 550231 45 599910 46 652878 47 709277 48 769252 49 832951 50 900525 51 972128 52 1047917 53 1128052 54 1212696 55 1302015 56 1396178 57 1495357 58 1599727 59 1709466 60 1824755 61 1945778 62 2072722 63 2205777 64 2345136 65 2490995 66 2643553 67 2803012 68 2969577 69 3143456 70 3324860 71 3514003 72 3711102 73 3916377 74 4130051 75 4352350 76 4583503 77 4823742 78 5073302 79 5332421 80 5601340 81 5880303 82 6169557 83 6469352 84 6779941 85 7101580 86 7434528 87 7779047 88 8135402 89 8503861 90 8884695 91 9278178 92 9684587 93 10104202 94 10537306 95 10984185 96 11445128 97 11920427 98 12410377 99 12915276 100 13435425 101 13971128 102 14522692 103 15090427 104 15674646 105 16275665 106 16893803 107 17529382 108 18182727 109 18854166 110 19544030 111 20252653 112 20980372 113 21727527 114 22494461 115 23281520 116 24089053 117 24917412 118 25766952 119 26638031 120 27531010 121 28446253 122 29384127 123 30345002 124 31329251 125 32337250 126 33369378 127 34426017 128 35507552 129 36614371 130 37746865 131 38905428 132 40090457 133 41302352 134 42541516 135 43808355 136 45103278 137 46426697 138 47779027 139 49160686 140 50572095 141 52013678 142 53485862 143 54989077 144 56523756 145 58090335 146 59689253 147 61320952 148 62985877 149 64684476 150 66417200 151 68184503 152 69986842 153 71824677 154 73698471 155 75608690 156 77555803 157 79540282 158 81562602 159 83623241 160 85722680 161 87861403 162 90039897 163 92258652 164 94518161 165 96818920 166 99161428 167 101546187 168 103973702 169 106444481 170 108959035 171 111517878 172 114121527 173 116770502 174 119465326 175 122206525 176 124994628 177 127830167 178 130713677 179 133645696 180 136626765 181 139657428 182 142738232 183 145869727 184 149052466 185 152287005 186 155573903 187 158913722 188 162307027 189 165754386 190 169256370 191 172813553 192 176426512 193 180095827 194 183822081 195 187605860 196 191447753 197 195348352 198 199308252 199 203328051 200 207408350 201 211549753 202 215752867 203 220018302 204 224346671 205 228738590 206 233194678 207 237715557 208 242301852 209 246954191 210 251673205 211 256459528 212 261313797 213 266236652 214 271228736 215 276290695 216 281423178 217 286626837 218 291902327 219 297250306 220 302671435 221 308166378 222 313735802 223 319380377 224 325100776 225 330897675 226 336771753 227 342723692 228 348754177 229 354863896 230 361053540 231 367323803 232 373675382 233 380108977 234 386625291 235 393225030 236 399908903 237 406677622 238 413531902 239 420472461 240 427500020 241 434615303 242 441819037 243 449111952 244 456494781 245 463968260 246 471533128 247 479190127 248 486940002 249 494783501 250 502721375 251 510754378 252 518883267 253 527108802 254 535431746 255 543852865 256 552372928 257 560992707 258 569712977 259 578534516 260 587458105 261 596484528 262 605614572 263 614849027 264 624188686 265 633634345 266 643186803 267 652846862 268 662615327 269 672493006 270 682480710 271 692579253 272 702789452 273 713112127 274 723548101 275 734098200 276 744763253 277 755544092 278 766441552 279 777456471 280 788589690 281 799842053 282 811214407 283 822707602 284 834322491 285 846059930 286 857920778 287 869905897 288 882016152 289 894252411 290 906615545 291 919106428 292 931725937 293 944474952 294 957354356 295 970365035 296 983507878 297 996783777 298 1010193627 299 1023738326 300 1037418775 301 1051235878 302 1065190542 303 1079283677 304 1093516196 305 1107889015 306 1122403053 307 1137059232 308 1151858477 309 1166801716 310 1181889880 311 1197123903 312 1212504722 313 1228033277 314 1243710511 315 1259537370 316 1275514803 317 1291643762 318 1307925202 319 1324360081 320 1340949360 321 1357694003 322 1374594977 323 1391653252 324 1408869801 325 1426245600 326 1443781628 327 1461478867 328 1479338302 329 1497360921 330 1515547715 331 1533899678 332 1552417807 333 1571103102 334 1589956566 335 1608979205 336 1628172028 337 1647536047 338 1667072277 339 1686781736 340 1706665445 341 1726724428 342 1746959712 343 1767372327 344 1787963306 345 1808733685 346 1829684503 347 1850816802 348 1872131627 349 1893630026 350 1915313050 351 1937181753 352 1959237192 353 1981480427 354 2003912521 355 2026534540 356 2049347553 357 2072352632 358 2095550852 359 2118943291 360 2142531030 361 2166315153 362 2190296747 363 2214476902 364 2238856711 365 2263437270 366 2288219678 367 2313205037 368 2338394452 369 2363789031 370 2389389885 371 2415198128 372 2441214877 373 2467441252 374 2493878376 375 2520527375 376 2547389378 377 2574465517 378 2601756927 379 2629264746 380 2656990115 381 2684934178 382 2713098082 383 2741482977 384 2770090016 385 2798920355 386 2827975153 387 2857255572 388 2886762777 389 2916497936 390 2946462220 391 2976656803 392 3007082862 393 3037741577 394 3068634131 395 3099761710 396 3131125503 397 3162726702 398 3194566502 399 3226646101 400 3258966700 401 3291529503 402 3324335717 403 3357386552 404 3390683221 405 3424226940 406 3458018928 407 3492060407 408 3526352602 409 3560896741 410 3595694055 411 3630745778 412 3666053147 413 3701617402 414 3737439786 415 3773521545 416 3809863928 417 3846468187 418 3883335577 419 3920467356 420 3957864785 421 3995529128 422 4033461652 423 4071663627 424 4110136326 425 4148881025 426 4187899003 427 4227191542 428 4266759927 429 4306605446 430 4346729390 431 4387133053 432 4427817732 433 4468784727 434 4510035341 435 4551570880 436 4593392653 437 4635501972 438 4677900152 439 4720588511 440 4763568370 441 4806841053 442 4850407887 443 4894270202 444 4938429331 445 4982886610 446 5027643378 447 5072700977 448 5118060752 449 5163724051 450 5209692225 451 5255966628 452 5302548617 453 5349439552 454 5396640796 455 5444153715 456 5491979678 457 5540120057 458 5588576227 459 5637349566 460 5686441455 461 5735853278 462 5785586422 463 5835642277 464 5886022236 465 5936727695 466 5987760053 467 6039120712 468 6090811077 469 6142832556 470 6195186560 471 6247874503 472 6300897802 473 6354257877 474 6407956151 475 6461994050 476 6516373003 477 6571094442 478 6626159802 479 6681570521 480 6737328040 481 6793433803 482 6849889257 483 6906695852 484 6963855041 485 7021368280 486 7079237028 487 7137462747 488 7196046902 489 7254990961 490 7314296395 491 7373964678 492 7433997287 493 7494395702 494 7555161406 495 7616295885 496 7677800628 497 7739677127 498 7801926877 499 7864551376 500 7927552125 501 7990930628 502 8054688392 503 8118826927 504 8183347746 505 8248252365 506 8313542303 507 8379219082 508 8445284227 509 8511739266 510 8578585730 511 8645825153 512 8713459072 513 8781489027 514 8849916561 515 8918743220 516 8987970553 517 9057600112 518 9127633452 519 9198072131 520 9268917710 521 9340171753 522 9411835827 523 9483911502 524 9556400351 525 9629303950 526 9702623878 527 9776361717 528 9850519052 529 9925097471 530 10000098565 531 10075523928 532 10151375157 533 10227653852 534 10304361616 535 10381500055 536 10459070778 537 10537075397 538 10615515527 539 10694392786 540 10773708795 541 10853465178 542 10933663562 543 11014305577 544 11095392856 545 11176927035 546 11258909753 547 11341342652 548 11424227377 549 11507565576 550 11591358900 551 11675609003 552 11760317542 553 11845486177 554 11931116571 555 12017210390 556 12103769303 557 12190794982 558 12278289102 559 12366253341 560 12454689380 561 12543598903 562 12632983597 563 12722845152 564 12813185261 565 12904005620 566 12995307928 567 13087093887 568 13179365202 569 13272123581 570 13365370735 571 13459108378 572 13553338227 573 13648062002 574 13743281426 575 13838998225 576 13935214128 577 14031930867 578 14129150177 579 14226873796 580 14325103465 581 14423840928 582 14523087932 583 14622846227 584 14723117566 585 14823903705 586 14925206403 587 15027027422 588 15129368527 589 15232231486 590 15335618070 591 15439530053 592 15543969212 593 15648937327 594 15754436181 595 15860467560 596 15967033253 597 16074135052 598 16181774752 599 16289954151 600 16398675050 601 16507939253 602 16617748567 603 16728104802 604 16839009771 605 16950465290 606 17062473178 607 17175035257 608 17288153352 609 17401829291 610 17516064905 611 17630862028 612 17746222497 613 17862148152 614 17978640836 615 18095702395 616 18213334678 617 18331539537 618 18450318827 619 18569674406 620 18689608135 621 18810121878 622 18931217502 623 19052896877 624 19175161876 625 19298014375 626 19421456253 627 19545489392 628 19670115677 629 19795336996 630 19921155240 631 20047572303 632 20174590082 633 20302210477 634 20430435391 635 20559266730 636 20688706403 637 20818756322 638 20949418402 639 21080694561 640 21212586720 641 21345096803 642 21478226737 643 21611978452 644 21746353881 645 21881354960 646 22016983628 647 22153241827 648 22290131502 649 22427654601 650 22565813075 651 22704608878 652 22844043967 653 22984120302 654 23124839846 655 23266204565 656 23408216428 657 23550877407 658 23694189477 659 23838154616 660 23982774805 661 24128052028 662 24273988272 663 24420585527 664 24567845786 665 24715771045 666 24864363303 667 25013624562 668 25163556827 669 25314162106 670 25465442410 671 25617399753 672 25770036152 673 25923353627 674 26077354201 675 26232039900 676 26387412753 677 26543474792 678 26700228052 679 26857674571 680 27015816390 681 27174655553 682 27334194107 683 27494434102 684 27655377591 685 27817026630 686 27979383278 687 28142449597 688 28306227652 689 28470719511 690 28635927245 691 28801852928 692 28968498637 693 29135866452 694 29303958456 695 29472776735 696 29642323378 697 29812600477 698 29983610127 699 30155354426 700 30327835475 701 30501055378 702 30675016242 703 30849720177 704 31025169296 705 31201365715 706 31378311553 707 31556008932 708 31734459977 709 31913666816 710 32093631580 711 32274356403 712 32455843422 713 32638094777 714 32821112611 715 33004899070 716 33189456303 717 33374786462 718 33560891702 719 33747774181 720 33935436060 721 34123879503 722 34313106677 723 34503119752 724 34693920901 725 34885512300 726 35077896128 727 35271074567 728 35465049802 729 35659824021 730 35855399415 731 36051778178 732 36248962507 733 36446954602 734 36645756666 735 36845370905 736 37045799528 737 37247044747 738 37449108777 739 37651993836 740 37855702145 741 38060235928 742 38265597412 743 38471788827 744 38678812406 745 38886670385 746 39095365003 747 39304898502 748 39515273127 749 39726491126 750 39938554750 751 40151466253 752 40365227892 753 40579841927 754 40795310621 755 41011636240 756 41228821053 757 41446867332 758 41665777352 759 41885553391 760 42106197730 761 42327712653 762 42550100447 763 42773363402 764 42997503811 765 43222523970 766 43448426178 767 43675212737 768 43902885952 769 44131448131 770 44360901585 771 44591248628 772 44822491577 773 45054632752 774 45287674476 775 45521619075 776 45756468878 777 45992226217 778 46228893427 779 46466472846 780 46704966815 781 46944377678 782 47184707782 783 47425959477 784 47668135116 785 47911237055 786 48155267653 787 48400229272 788 48646124277 789 48892955036 790 49140723920 791 49389433303 792 49639085562 793 49889683077 794 50141228231 795 50393723410 796 50647171003 797 50901573402 798 51156933002 799 51413252201 800 51670533400 801 51928779003 802 52187991417 803 52448173052 804 52709326321 805 52971453640 806 53234557428 807 53498640107 808 53763704102 809 54029751841 810 54296785755 811 54564808278 812 54833821847 813 55103828902 814 55374831886 815 55646833245 816 55919835428 817 56193840887 818 56468852077 819 56744871456 820 57021901485 821 57299944628 822 57579003352 823 57859080127 824 58140177426 825 58422297725 826 58705443503 827 58989617242 828 59274821427 829 59561058546 830 59848331090 831 60136641553 832 60425992432 833 60716386227 834 61007825441 835 61300312580 836 61593850153 837 61888440672 838 62184086652 839 62480790611 840 62778555070 841 63077382553 842 63377275587 843 63678236702 844 63980268431 845 64283373310 846 64587553878 847 64892812677 848 65199152252 849 65506575151 850 65815083925 851 66124681128 852 66435369317 853 66747151052 854 67060028896 855 67374005415 856 67689083178 857 68005264757 858 68322552727 859 68640949666 860 68960458155 861 69281080778 862 69602820122 863 69925678777 864 70249659336 865 70574764395 866 70900996553 867 71228358412 868 71556852577 869 71886481656 870 72217248260 871 72549155003 872 72882204502 873 73216399377 874 73551742251 875 73888235750 876 74225882503 877 74564685142 878 74904646302 879 75245768621 880 75588054740 881 75931507303 882 76276128957 883 76621922352 884 76968890141 885 77317034980 886 77666359528 887 78016866447 888 78368558402 889 78721438061 890 79075508095 891 79430771178 892 79787229987 893 80144887202 894 80503745506 895 80863807585 896 81225076128 897 81587553827 898 81951243377 899 82316147476 900 82682268825 901 83049610128 902 83418174092 903 83787963427 904 84158980846 905 84531229065 906 84904710803 907 85279428782 908 85655385727 909 86032584366 910 86411027430 911 86790717653 912 87171657772 913 87553850527 914 87937298661 915 88322004920 916 88707972053 917 89095202812 918 89483699952 919 89873466231 920 90264504410 921 90656817253 922 91050407527 923 91445278002 924 91841431451 925 92238870650 926 92637598378 927 93037617417 928 93438930552 929 93841540571 930 94245450265 931 94650662428 932 95057179857 933 95465005352 934 95874141716 935 96284591755 936 96696358278 937 97109444097 938 97523852027 939 97939584886 940 98356645495 941 98775036678 942 99194761262 943 99615822077 944 100038221956 945 100461963735 946 100887050253 947 101313484352 948 101741268877 949 102170406676 950 102600900600 951 103032753503 952 103465968242 953 103900547677 954 104336494671 955 104773812090 956 105212502803 957 105652569682 958 106094015602 959 106536843441 960 106981056080 961 107426656403 962 107873647297 963 108322031652 964 108771812361 965 109222992320 966 109675574428 967 110129561587 968 110584956702 969 111041762681 970 111499982435 971 111959618878 972 112420674927 973 112883153502 974 113347057526 975 113812389925 976 114279153628 977 114747351567 978 115216986677 979 115688061896 980 116160580165 981 116634544428 982 117109957632 983 117586822727 984 118065142666 985 118544920405 986 119026158903 987 119508861122 988 119993030027 989 120478668586 990 120965779770 991 121454366553 992 121944431912 993 122435978827 994 122929010281 995 123423529260 996 123919538753 997 124417041752 998 124916041252 999 125416540251 1000 125918541750