0 1 1 1 2 4 3 15 4 24 5 44 6 81 7 115 8 168 9 247 10 322 11 424 12 561 13 693 14 860 15 1071 16 1276 17 1524 18 1825 19 2119 20 2464 21 2871 22 3270 23 3728 24 4257 25 4777 26 5364 27 6031 28 6688 29 7420 30 8241 31 9051 32 9944 33 10935 34 11914 35 12984 36 14161 37 15325 38 16588 39 17967 40 19332 41 20804 42 22401 43 23983 44 25680 45 27511 46 29326 47 31264 48 33345 49 35409 50 37604 51 39951 52 42280 53 44748 54 47377 55 49987 56 52744 57 55671 58 58578 59 61640 60 64881 61 68101 62 71484 63 75055 64 78604 65 82324 66 86241 67 90135 68 94208 69 98487 70 102742 71 107184 72 111841 73 116473 74 121300 75 126351 76 131376 77 136604 78 142065 79 147499 80 153144 81 159031 82 164890 83 170968 84 177297 85 183597 86 190124 87 196911 88 203668 89 210660 90 217921 91 225151 92 232624 93 240375 94 248094 95 256064 96 264321 97 272545 98 281028 99 289807 100 298552 101 307564 102 316881 103 326163 104 335720 105 345591 106 355426 107 365544 108 375985 109 386389 110 397084 111 408111 112 419100 113 430388 114 442017 115 453607 116 465504 117 477751 118 489958 119 502480 120 515361 121 528201 122 541364 123 554895 124 568384 125 582204 126 596401 127 610555 128 625048 129 639927 130 654762 131 669944 132 685521 133 701053 134 716940 135 733231 136 749476 137 766084 138 783105 139 800079 140 817424 141 835191 142 852910 143 871008 144 889537 145 908017 146 926884 147 946191 148 965448 149 985100 150 1005201 151 1025251 152 1045704 153 1066615 154 1087474 155 1108744 156 1130481 157 1152165 158 1174268 159 1196847 160 1219372 161 1242324 162 1265761 163 1289143 164 1312960 165 1337271 166 1361526 167 1386224 168 1411425 169 1436569 170 1462164 171 1488271 172 1514320 173 1540828 174 1567857 175 1594827 176 1622264 177 1650231 178 1678138 179 1706520 180 1735441 181 1764301 182 1793644 183 1823535 184 1853364 185 1883684 186 1914561 187 1945375 188 1976688 189 2008567 190 2040382 191 2072704 192 2105601 193 2138433 194 2171780 195 2205711 196 2239576 197 2273964 198 2308945 199 2343859 200 2379304 201 2415351 202 2451330 203 2487848 204 2524977 205 2562037 206 2599644 207 2637871 208 2676028 209 2714740 210 2754081 211 2793351 212 2833184 213 2873655 214 2914054 215 2955024 216 2996641 217 3038185 218 3080308 219 3123087 220 3165792 221 3209084 222 3253041 223 3296923 224 3341400 225 3386551 226 3431626 227 3477304 228 3523665 229 3569949 230 3616844 231 3664431 232 3711940 233 3760068 234 3808897 235 3857647 236 3907024 237 3957111 238 4007118 239 4057760 240 4109121 241 4160401 242 4212324 243 4264975 244 4317544 245 4370764 246 4424721 247 4478595 248 4533128 249 4588407 250 4643602 251 4699464 252 4756081 253 4812613 254 4869820 255 4927791 256 4985676 257 5044244 258 5103585 259 5162839 260 5222784 261 5283511 262 5344150 263 5405488 264 5467617 265 5529657 266 5592404 267 5655951 268 5719408 269 5783580 270 5848561 271 5913451 272 5979064 273 6045495 274 6111834 275 6178904 276 6246801 277 6314605 278 6383148 279 6452527 280 6521812 281 6591844 282 6662721 283 6733503 284 6805040 285 6877431 286 6949726 287 7022784 288 7096705 289 7170529 290 7245124 291 7320591 292 7395960 293 7472108 294 7549137 295 7626067 296 7703784 297 7782391 298 7860898 299 7940200 300 8020401 301 8100501 302 8181404 303 8263215 304 8344924 305 8427444 306 8510881 307 8594215 308 8678368 309 8763447 310 8848422 311 8934224 312 9020961 313 9107593 314 9195060 315 9283471 316 9371776 317 9460924 318 9551025 319 9641019 320 9731864 321 9823671 322 9915370 323 10007928 324 10101457 325 10194877 326 10289164 327 10384431 328 10479588 329 10575620 330 10672641 331 10769551 332 10867344 333 10966135 334 11064814 335 11164384 336 11264961 337 11365425 338 11466788 339 11569167 340 11671432 341 11774604 342 11878801 343 11982883 344 12087880 345 12193911 346 12299826 347 12406664 348 12514545 349 12622309 350 12731004 351 12840751 352 12950380 353 13060948 354 13172577 355 13284087 356 13396544 357 13510071 358 13623478 359 13737840 360 13853281 361 13968601 362 14084884 363 14202255 364 14319504 365 14437724 366 14557041 367 14676235 368 14796408 369 14917687 370 15038842 371 15160984 372 15284241 373 15407373 374 15531500 375 15656751 376 15781876 377 15908004 378 16035265 379 16162399 380 16290544 381 16419831 382 16548990 383 16679168 384 16810497 385 16941697 386 17073924 387 17207311 388 17340568 389 17474860 390 17610321 391 17745651 392 17882024 393 18019575 394 18156994 395 18295464 396 18435121 397 18574645 398 18715228 399 18857007 400 18998652 401 19141364 402 19285281 403 19429063 404 19573920 405 19719991 406 19865926 407 20012944 408 20161185 409 20309289 410 20458484 411 20608911 412 20759200 413 20910588 414 21063217 415 21215707 416 21369304 417 21524151 418 21678858 419 21834680 420 21991761 421 22148701 422 22306764 423 22466095 424 22625284 425 22785604 426 22947201 427 23108655 428 23271248 429 23435127 430 23598862 431 23763744 432 23929921 433 24095953 434 24263140 435 24431631 436 24599976 437 24769484 438 24940305 439 25110979 440 25282824 441 25455991 442 25629010 443 25803208 444 25978737 445 26154117 446 26330684 447 26508591 448 26686348 449 26865300 450 27045601 451 27225751 452 27407104 453 27589815 454 27772374 455 27956144 456 28141281 457 28326265 458 28512468 459 28700047 460 28887472 461 29076124 462 29266161 463 29456043 464 29647160 465 29839671 466 30032026 467 30225624 468 30420625 469 30615469 470 30811564 471 31009071 472 31206420 473 31405028 474 31605057 475 31804927 476 32006064 477 32208631 478 32411038 479 32614720 480 32819841 481 33024801 482 33231044 483 33438735 484 33646264 485 33855084 486 34065361 487 34275475 488 34486888 489 34699767 490 34912482 491 35126504 492 35342001 493 35557333 494 35773980 495 35992111 496 36210076 497 36429364 498 36650145 499 36870759 500 37092704 501 37316151 502 37539430 503 37764048 504 37990177 505 38216137 506 38443444 507 38672271 508 38900928 509 39130940 510 39362481 511 39593851 512 39826584 513 40060855 514 40294954 515 40530424 516 40767441 517 41004285 518 41242508 519 41482287 520 41721892 521 41962884 522 42205441 523 42447823 524 42691600 525 42936951 526 43182126 527 43428704 528 43676865 529 43924849 530 44174244 531 44425231 532 44676040 533 44928268 534 45182097 535 45435747 536 45690824 537 45947511 538 46204018 539 46461960 540 46721521 541 46980901 542 47241724 543 47504175 544 47766444 545 48030164 546 48295521 547 48560695 548 48827328 549 49095607 550 49363702 551 49633264 552 49904481 553 50175513 554 50448020 555 50722191 556 50996176 557 51271644 558 51548785 559 51825739 560 52104184 561 52384311 562 52664250 563 52945688 564 53228817 565 53511757 566 53796204 567 54082351 568 54368308 569 54655780 570 54944961 571 55233951 572 55524464 573 55816695 574 56108734 575 56402304 576 56697601 577 56992705 578 57289348 579 57587727 580 57885912 581 58185644 582 58487121 583 58788403 584 59091240 585 59395831 586 59700226 587 60006184 588 60313905 589 60621429 590 60930524 591 61241391 592 61552060 593 61864308 594 62178337 595 62492167 596 62807584 597 63124791 598 63441798 599 63760400 600 64080801 601 64401001 602 64722804 603 65046415 604 65369824 605 65694844 606 66021681 607 66348315 608 66676568 609 67006647 610 67336522 611 67668024 612 68001361 613 68334493 614 68669260 615 69005871 616 69342276 617 69680324 618 70020225 619 70359919 620 70701264 621 71044471 622 71387470 623 71732128 624 72078657 625 72424977 626 72772964 627 73122831 628 73472488 629 73823820 630 74177041 631 74530051 632 74884744 633 75241335 634 75597714 635 75955784 636 76315761 637 76675525 638 77036988 639 77400367 640 77763532 641 78128404 642 78495201 643 78861783 644 79230080 645 79600311 646 79970326 647 80342064 648 80715745 649 81089209 650 81464404 651 81841551 652 82218480 653 82597148 654 82977777 655 83358187 656 83740344 657 84124471 658 84508378 659 84894040 660 85281681 661 85669101 662 86058284 663 86449455 664 86840404 665 87233124 666 87627841 667 88022335 668 88418608 669 88816887 670 89214942 671 89614784 672 90016641 673 90418273 674 90821700 675 91227151 676 91632376 677 92039404 678 92448465 679 92857299 680 93267944 681 93680631 682 94093090 683 94507368 684 94923697 685 95339797 686 95757724 687 96177711 688 96597468 689 97019060 690 97442721 691 97866151 692 98291424 693 98718775 694 99145894 695 99574864 696 100005921 697 100436745 698 100869428 699 101304207 700 101738752 701 102175164 702 102613681 703 103051963 704 103492120 705 103934391 706 104376426 707 104820344 708 105266385 709 105712189 710 106159884 711 106609711 712 107059300 713 107510788 714 107964417 715 108417807 716 108873104 717 109330551 718 109787758 719 110246880 720 110708161 721 111169201 722 111632164 723 112097295 724 112562184 725 113029004 726 113498001 727 113966755 728 114437448 729 114910327 730 115382962 731 115857544 732 116334321 733 116810853 734 117289340 735 117770031 736 118250476 737 118732884 738 119217505 739 119701879 740 120188224 741 120676791 742 121165110 743 121655408 744 122147937 745 122640217 746 123134484 747 123630991 748 124127248 749 124625500 750 125126001 751 125626251 752 126128504 753 126633015 754 127137274 755 127643544 756 128152081 757 128660365 758 129170668 759 129683247 760 130195572 761 130709924 762 131226561 763 131742943 764 132261360 765 132782071 766 133302526 767 133825024 768 134349825 769 134874369 770 135400964 771 135929871 772 136458520 773 136989228 774 137522257 775 138055027 776 138589864 777 139127031 778 139663938 779 140202920 780 140744241 781 141285301 782 141828444 783 142373935 784 142919164 785 143466484 786 144016161 787 144565575 788 145117088 789 145670967 790 146224582 791 146780304 792 147338401 793 147896233 794 148456180 795 149018511 796 149580576 797 150144764 798 150711345 799 151277659 800 151846104 801 152416951 802 152987530 803 153560248 804 154135377 805 154710237 806 155287244 807 155866671 808 156445828 809 157027140 810 157610881 811 158194351 812 158779984 813 159368055 814 159955854 815 160545824 816 161138241 817 161730385 818 162324708 819 162921487 820 163517992 821 164116684 822 164717841 823 165318723 824 165921800 825 166527351 826 167132626 827 167740104 828 168350065 829 168959749 830 169571644 831 170186031 832 170800140 833 171416468 834 172035297 835 172653847 836 173274624 837 173897911 838 174520918 839 175146160 840 175773921 841 176401401 842 177031124 843 177663375 844 178295344 845 178929564 846 179566321 847 180202795 848 180841528 849 181482807 850 182123802 851 182767064 852 183412881 853 184058413 854 184706220 855 185356591 856 186006676 857 186659044 858 187313985 859 187968639 860 188625584 861 189285111 862 189944350 863 190605888 864 191270017 865 191933857 866 192600004 867 193268751 868 193937208 869 194607980 870 195281361 871 195954451 872 196629864 873 197307895 874 197985634 875 198665704 876 199348401 877 200030805 878 200715548 879 201402927 880 202090012 881 202779444 882 203471521 883 204163303 884 204857440 885 205554231 886 206250726 887 206949584 888 207651105 889 208352329 890 209055924 891 209762191 892 210468160 893 211176508 894 211887537 895 212598267 896 213311384 897 214027191 898 214742698 899 215460600 900 216181201 901 216901501 902 217624204 903 218349615 904 219074724 905 219802244 906 220532481 907 221262415 908 221994768 909 222729847 910 223464622 911 224201824 912 224941761 913 225681393 914 226423460 915 227168271 916 227912776 917 228659724 918 229409425 919 230158819 920 230910664 921 231665271 922 232419570 923 233176328 924 233935857 925 234695077 926 235456764 927 236221231 928 236985388 929 237752020 930 238521441 931 239290551 932 240062144 933 240836535 934 241610614 935 242387184 936 243166561 937 243945625 938 244727188 939 245511567 940 246295632 941 247082204 942 247871601 943 248660683 944 249452280 945 250246711 946 251040826 947 251837464 948 252636945 949 253436109 950 254237804 951 255042351 952 255846580 953 256653348 954 257462977 955 258272287 956 259084144 957 259898871 958 260713278 959 261530240 960 262350081 961 263169601 962 263991684 963 264816655 964 265641304 965 266468524 966 267298641 967 268128435 968 268960808 969 269796087 970 270631042 971 271468584 972 272309041 973 273149173 974 273991900 975 274837551 976 275682876 977 276530804 978 277381665 979 278232199 980 279085344 981 279941431 982 280797190 983 281655568 984 282516897 985 283377897 986 284241524 987 285108111 988 285974368 989 286843260 990 287715121 991 288586651 992 289460824 993 290337975 994 291214794 995 292094264 996 292976721 997 293858845 998 294743628 999 295631407 1000 296518852