1 1 2 4 3 16 4 43 5 91 6 166 7 275 8 422 9 614 10 857 11 1158 12 1521 13 1953 14 2460 15 3049 16 3724 17 4492 18 5359 19 6332 20 7415 21 8615 22 9938 23 11391 24 12978 25 14706 26 16581 27 18610 28 20797 29 23149 30 25672 31 28373 32 31256 33 34328 34 37595 35 41064 36 44739 37 48627 38 52734 39 57067 40 61630 41 66430 42 71473 43 76766 44 82313 45 88121 46 94196 47 100545 48 107172 49 114084 50 121287 51 128788 52 136591 53 144703 54 153130 55 161879 56 170954 57 180362 58 190109 59 200202 60 210645 61 221445 62 232608 63 244141 64 256048 65 268336 66 281011 67 294080 68 307547 69 321419 70 335702 71 350403 72 365526 73 381078 74 397065 75 413494 76 430369 77 447697 78 465484 79 483737 80 502460 81 521660 82 541343 83 561516 84 582183 85 603351 86 625026 87 647215 88 669922 89 693154 90 716917 91 741218 92 766061 93 791453 94 817400 95 843909 96 870984 97 898632 98 926859 99 955672 100 985075 101 1015075 102 1045678 103 1076891 104 1108718 105 1141166 106 1174241 107 1207950 108 1242297 109 1277289 110 1312932 111 1349233 112 1386196 113 1423828 114 1462135 115 1501124 116 1540799 117 1581167 118 1622234 119 1664007 120 1706490 121 1749690 122 1793613 123 1838266 124 1883653 125 1929781 126 1976656 127 2024285 128 2072672 129 2121824 130 2171747 131 2222448 132 2273931 133 2326203 134 2379270 135 2433139 136 2487814 137 2543302 138 2599609 139 2656742 140 2714705 141 2773505 142 2833148 143 2893641 144 2954988 145 3017196 146 3080271 147 3144220 148 3209047 149 3274759 150 3341362 151 3408863 152 3477266 153 3546578 154 3616805 155 3687954 156 3760029 157 3833037 158 3906984 159 3981877 160 4057720 161 4134520 162 4212283 163 4291016 164 4370723 165 4451411 166 4533086 167 4615755 168 4699422 169 4784094 170 4869777 171 4956478 172 5044201 173 5132953 174 5222740 175 5313569 176 5405444 177 5498372 178 5592359 179 5687412 180 5783535 181 5880735 182 5979018 183 6078391 184 6178858 185 6280426 186 6383101 187 6486890 188 6591797 189 6697829 190 6804992 191 6913293 192 7022736 193 7133328 194 7245075 195 7357984 196 7472059 197 7587307 198 7703734 199 7821347 200 7940150 201 8060150 202 8181353 203 8303766 204 8427393 205 8552241 206 8678316 207 8805625 208 8934172 209 9063964 210 9195007 211 9327308 212 9460871 213 9595703 214 9731810 215 9869199 216 10007874 217 10147842 218 10289109 219 10431682 220 10575565 221 10720765 222 10867288 223 11015141 224 11164328 225 11314856 226 11466731 227 11619960 228 11774547 229 11930499 230 12087822 231 12246523 232 12406606 233 12568078 234 12730945 235 12895214 236 13060889 237 13227977 238 13396484 239 13566417 240 13737780 241 13910580 242 14084823 243 14260516 244 14437663 245 14616271 246 14796346 247 14977895 248 15160922 249 15345434 250 15531437 251 15718938 252 15907941 253 16098453 254 16290480 255 16484029 256 16679104 257 16875712 258 17073859 259 17273552 260 17474795 261 17677595 262 17881958 263 18087891 264 18295398 265 18504486 266 18715161 267 18927430 268 19141297 269 19356769 270 19573852 271 19792553 272 20012876 273 20234828 274 20458415 275 20683644 276 20910519 277 21139047 278 21369234 279 21601087 280 21834610 281 22069810 282 22306693 283 22545266 284 22785533 285 23027501 286 23271176 287 23516565 288 23763672 289 24012504 290 24263067 291 24515368 292 24769411 293 25025203 294 25282750 295 25542059 296 25803134 297 26065982 298 26330609 299 26597022 300 26865225 301 27135225 302 27407028 303 27680641 304 27956068 305 28233316 306 28512391 307 28793300 308 29076047 309 29360639 310 29647082 311 29935383 312 30225546 313 30517578 314 30811485 315 31107274 316 31404949 317 31704517 318 32005984 319 32309357 320 32614640 321 32921840 322 33230963 323 33542016 324 33855003 325 34169931 326 34486806 327 34805635 328 35126422 329 35449174 330 35773897 331 36100598 332 36429281 333 36759953 334 37092620 335 37427289 336 37763964 337 38102652 338 38443359 339 38786092 340 39130855 341 39477655 342 39826498 343 40177391 344 40530338 345 40885346 346 41242421 347 41601570 348 41962797 349 42326109 350 42691512 351 43059013 352 43428616 353 43800328 354 44174155 355 44550104 356 44928179 357 45308387 358 45690734 359 46075227 360 46461870 361 46850670 362 47241633 363 47634766 364 48030073 365 48427561 366 48827236 367 49229105 368 49633172 369 50039444 370 50447927 371 50858628 372 51271551 373 51686703 374 52104090 375 52523719 376 52945594 377 53369722 378 53796109 379 54224762 380 54655685 381 55088885 382 55524368 383 55962141 384 56402208 385 56844576 386 57289251 387 57736240 388 58185547 389 58637179 390 59091142 391 59547443 392 60006086 393 60467078 394 60930425 395 61396134 396 61864209 397 62334657 398 62807484 399 63282697 400 63760300 401 64240300 402 64722703 403 65207516 404 65694743 405 66184391 406 66676466 407 67170975 408 67667922 409 68167314 410 68669157 411 69173458 412 69680221 413 70189453 414 70701160 415 71215349 416 71732024 417 72251192 418 72772859 419 73297032 420 73823715 421 74352915 422 74884638 423 75418891 424 75955678 425 76495006 426 77036881 427 77581310 428 78128297 429 78677849 430 79229972 431 79784673 432 80341956 433 80901828 434 81464295 435 82029364 436 82597039 437 83167327 438 83740234 439 84315767 440 84893930 441 85474730 442 86058173 443 86644266 444 87233013 445 87824421 446 88418496 447 89015245 448 89614672 449 90216784 450 90821587 451 91429088 452 92039291 453 92652203 454 93267830 455 93886179 456 94507254 457 95131062 458 95757609 459 96386902 460 97018945 461 97653745 462 98291308 463 98931641 464 99574748 465 100220636 466 100869311 467 101520780 468 102175047 469 102832119 470 103492002 471 104154703 472 104820226 473 105488578 474 106159765 475 106833794 476 107510669 477 108190397 478 108872984 479 109558437 480 110246760 481 110937960 482 111632043 483 112329016 484 113028883 485 113731651 486 114437326 487 115145915 488 115857422 489 116571854 490 117289217 491 118009518 492 118732761 493 119458953 494 120188100 495 120920209 496 121655284 497 122393332 498 123134359 499 123878372 500 124625375 501 125375375 502 126128378 503 126884391 504 127643418 505 128405466 506 129170541 507 129938650 508 130709797 509 131483989 510 132261232 511 133041533 512 133824896 513 134611328 514 135400835 515 136193424 516 136989099 517 137787867 518 138589734 519 139394707 520 140202790 521 141013990 522 141828313 523 142645766 524 143466353 525 144290081 526 145116956 527 145946985 528 146780172 529 147616524 530 148456047 531 149298748 532 150144631 533 150993703 534 151845970 535 152701439 536 153560114 537 154422002 538 155287109 539 156155442 540 157027005 541 157901805 542 158779848 543 159661141 544 160545688 545 161433496 546 162324571 547 163218920 548 164116547 549 165017459 550 165921662 551 166829163 552 167739966 553 168654078 554 169571505 555 170492254 556 171416329 557 172343737 558 173274484 559 174208577 560 175146020 561 176086820 562 177030983 563 177978516 564 178929423 565 179883711 566 180841386 567 181802455 568 182766922 569 183734794 570 184706077 571 185680778 572 186658901 573 187640453 574 188625440 575 189613869 576 190605744 577 191601072 578 192599859 579 193602112 580 194607835 581 195617035 582 196629718 583 197645891 584 198665558 585 199688726 586 200715401 587 201745590 588 202779297 589 203816529 590 204857292 591 205901593 592 206949436 593 208000828 594 209055775 595 210114284 596 211176359 597 212242007 598 213311234 599 214384047 600 215460450 601 216540450 602 217624053 603 218711266 604 219802093 605 220896541 606 221994616 607 223096325 608 224201672 609 225310664 610 226423307 611 227539608 612 228659571 613 229783203 614 230910510 615 232041499 616 233176174 617 234314542 618 235456609 619 236602382 620 237751865 621 238905065 622 240061988 623 241222641 624 242387028 625 243555156 626 244727031 627 245902660 628 247082047 629 248265199 630 249452122 631 250642823 632 251837306 633 253035578 634 254237645 635 255443514 636 256653189 637 257866677 638 259083984 639 260305117 640 261530080 641 262758880 642 263991523 643 265228016 644 266468363 645 267712571 646 268960646 647 270212595 648 271468422 649 272728134 650 273991737 651 275259238 652 276530641 653 277805953 654 279085180 655 280368329 656 281655404 657 282946412 658 284241359 659 285540252 660 286843095 661 288149895 662 289460658 663 290775391 664 292094098 665 293416786 666 294743461 667 296074130 668 297408797 669 298747469 670 300090152 671 301436853 672 302787576 673 304142328 674 305501115 675 306863944 676 308230819 677 309601747 678 310976734 679 312355787 680 313738910 681 315126110 682 316517393 683 317912766 684 319312233 685 320715801 686 322123476 687 323535265 688 324951172 689 326371204 690 327795367 691 329223668 692 330656111 693 332092703 694 333533450 695 334978359 696 336427434 697 337880682 698 339338109 699 340799722 700 342265525 701 343735525 702 345209728 703 346688141 704 348170768 705 349657616 706 351148691 707 352644000 708 354143547 709 355647339 710 357155382 711 358667683 712 360184246 713 361705078 714 363230185 715 364759574 716 366293249 717 367831217 718 369373484 719 370920057 720 372470940 721 374026140 722 375585663 723 377149516 724 378717703 725 380290231 726 381867106 727 383448335 728 385033922 729 386623874 730 388218197 731 389816898 732 391419981 733 393027453 734 394639320 735 396255589 736 397876264 737 399501352 738 401130859 739 402764792 740 404403155 741 406045955 742 407693198 743 409344891 744 411001038 745 412661646 746 414326721 747 415996270 748 417670297 749 419348809 750 421031812 751 422719313 752 424411316 753 426107828 754 427808855 755 429514404 756 431224479 757 432939087 758 434658234 759 436381927 760 438110170 761 439842970 762 441580333 763 443322266 764 445068773 765 446819861 766 448575536 767 450335805 768 452100672 769 453870144 770 455644227 771 457422928 772 459206251 773 460994203 774 462786790 775 464584019 776 466385894 777 468192422 778 470003609 779 471819462 780 473639985 781 475465185 782 477295068 783 479129641 784 480968908 785 482812876 786 484661551 787 486514940 788 488373047 789 490235879 790 492103442 791 493975743 792 495852786 793 497734578 794 499621125 795 501512434 796 503408509 797 505309357 798 507214984 799 509125397 800 511040600 801 512960600 802 514885403 803 516815016 804 518749443 805 520688691 806 522632766 807 524581675 808 526535422 809 528494014 810 530457457 811 532425758 812 534398921 813 536376953 814 538359860 815 540347649 816 542340324 817 544337892 818 546340359 819 548347732 820 550360015 821 552377215 822 554399338 823 556426391 824 558458378 825 560495306 826 562537181 827 564584010 828 566635797 829 568692549 830 570754272 831 572820973 832 574892656 833 576969328 834 579050995 835 581137664 836 583229339 837 585326027 838 587427734 839 589534467 840 591646230 841 593763030 842 595884873 843 598011766 844 600143713 845 602280721 846 604422796 847 606569945 848 608722172 849 610879484 850 613041887 851 615209388 852 617381991 853 619559703 854 621742530 855 623930479 856 626123554 857 628321762 858 630525109 859 632733602 860 634947245 861 637166045 862 639390008 863 641619141 864 643853448 865 646092936 866 648337611 867 650587480 868 652842547 869 655102819 870 657368302 871 659639003 872 661914926 873 664196078 874 666482465 875 668774094 876 671070969 877 673373097 878 675680484 879 677993137 880 680311060 881 682634260 882 684962743 883 687296516 884 689635583 885 691979951 886 694329626 887 696684615 888 699044922 889 701410554 890 703781517 891 706157818 892 708539461 893 710926453 894 713318800 895 715716509 896 718119584 897 720528032 898 722941859 899 725361072 900 727785675 901 730215675 902 732651078 903 735091891 904 737538118 905 739989766 906 742446841 907 744909350 908 747377297 909 749850689 910 752329532 911 754813833 912 757303596 913 759798828 914 762299535 915 764805724 916 767317399 917 769834567 918 772357234 919 774885407 920 777419090 921 779958290 922 782503013 923 785053266 924 787609053 925 790170381 926 792737256 927 795309685 928 797887672 929 800471224 930 803060347 931 805655048 932 808255331 933 810861203 934 813472670 935 816089739 936 818712414 937 821340702 938 823974609 939 826614142 940 829259305 941 831910105 942 834566548 943 837228641 944 839896388 945 842569796 946 845248871 947 847933620 948 850624047 949 853320159 950 856021962 951 858729463 952 861442666 953 864161578 954 866886205 955 869616554 956 872352629 957 875094437 958 877841984 959 880595277 960 883354320 961 886119120 962 888889683 963 891666016 964 894448123 965 897236011 966 900029686 967 902829155 968 905634422 969 908445494 970 911262377 971 914085078 972 916913601 973 919747953 974 922588140 975 925434169 976 928286044 977 931143772 978 934007359 979 936876812 980 939752135 981 942633335 982 945520418 983 948413391 984 951312258 985 954217026 986 957127701 987 960044290 988 962966797 989 965895229 990 968829592 991 971769893 992 974716136 993 977668328 994 980626475 995 983590584 996 986560659 997 989536707 998 992518734 999 995506747 1000 998500750