0 0 1 1 2 4 3 9 4 19 5 30 6 52 7 70 8 107 9 136 10 191 11 226 12 314 13 352 14 463 15 523 16 664 17 717 18 919 19 964 20 1205 21 1282 22 1546 23 1603 24 1992 25 2009 26 2414 27 2504 28 2958 29 2974 30 3606 31 3553 32 4223 33 4273 34 4936 35 4912 36 5885 37 5685 38 6634 39 6654 40 7664 41 7454 42 8822 43 8454 44 9845 45 9746 46 11015 47 10684 48 12637 49 11939 50 13761 51 13523 52 15321 53 14660 54 17152 55 16203 56 18640 57 18122 58 20306 59 19417 60 22843 61 21205 62 24193 63 23563 64 26473 65 25098 66 29104 67 27092 68 31023 69 29877 70 33370 71 31499 72 36818 73 33882 74 38463 75 37240 76 41521 77 38938 78 45080 79 41590 80 47614 81 45393 82 50289 83 47265 84 55110 85 50461 86 56926 87 54619 88 60872 89 56637 90 65691 91 60055 92 68317 93 64938 94 71727 95 67247 96 78029 97 70774 98 79964 99 76339 100 85088 101 78533 102 90670 103 82594 104 93915 105 89219 106 97930 107 91095 108 105918 109 95565 110 108104 111 102522 112 113877 113 104823 114 120936 115 110036 116 124519 117 117436 118 129148 119 119773 120 139605 121 124991 122 140751 123 133485 124 147869 125 136258 126 156755 127 141428 128 160541 129 150846 130 166301 131 153060 132 177895 133 159301 134 179128 135 170117 136 187652 137 171653 138 197898 139 178105 140 202902 141 189429 142 207881 143 191459 144 222664 145 199164 146 223220 147 210887 148 232978 149 212606 150 246010 151 219967 152 249554 153 233404 154 256108 155 235971 156 273290 157 242930 158 273161 159 257313 160 285602 161 259182 162 298688 163 267178 164 302924 165 283939 166 309894 167 284059 168 330810 169 292888 170 330540 171 309814 172 342125 173 310706 174 358370 175 321531 176 362993 177 338095 178 370192 179 338684 180 395629 181 348480 182 392174 183 367864 184 406472 185 369739 186 424868 187 378445 188 429052 189 399799 190 438742 191 399160 192 464818 193 409889 194 460723 195 433885 196 477531 197 431621 198 498358 199 442766 200 504433 201 466616 202 510547 203 466022 204 542053 205 479303 206 536515 207 502740 208 555022 209 501099 210 581392 211 513295 212 582177 213 540217 214 590858 215 540298 216 627390 217 551501 218 619231 219 579396 220 642137 221 576728 222 666024 223 589871 224 670358 225 623267 226 678390 227 616836 228 718932 229 630661 230 712008 231 663697 232 731839 233 658690 234 761338 235 675996 236 763644 237 707062 238 773834 239 701977 240 822630 241 717055 242 806359 243 753223 244 830720 245 751454 246 863652 247 762670 248 866018 249 800571 250 878833 251 793821 252 927655 253 810100 254 910775 255 853726 256 938342 257 842322 258 973938 259 859910 260 979316 261 901515 262 984758 263 892328 264 1042518 265 913857 266 1024242 267 953927 268 1052339 269 944180 270 1097478 271 961929 272 1093121 273 1009965 274 1102127 275 1002650 276 1165405 277 1016170 278 1142904 279 1065439 280 1182411 281 1053219 282 1218784 283 1071973 284 1217507 285 1128564 286 1227666 287 1111541 288 1298690 289 1129796 290 1276769 291 1183520 292 1305644 293 1168974 294 1354986 295 1194783 296 1351906 297 1246375 298 1360665 299 1229657 300 1444051 301 1252178 302 1406939 303 1309303 304 1445457 305 1298427 306 1497200 307 1313409 308 1494702 309 1375120 310 1509208 311 1356323 312 1587866 313 1378347 314 1551124 315 1452281 316 1591752 317 1422575 318 1648110 319 1445257 320 1651452 321 1512397 322 1654122 323 1490477 324 1745063 325 1521446 326 1703790 327 1583770 328 1748593 329 1562499 330 1817402 331 1584219 332 1801202 333 1658119 334 1810105 335 1640130 336 1914765 337 1656644 338 1865005 339 1732613 340 1920867 341 1706084 342 1978806 343 1733172 344 1969902 345 1819260 346 1977118 347 1781158 348 2086403 349 1806882 350 2047145 351 1890669 352 2087008 353 1858804 354 2156074 355 1894699 356 2144467 357 1973779 358 2152476 359 1937901 360 2284911 361 1965343 362 2213095 363 2054752 364 2270129 365 2029973 366 2343516 367 2047116 368 2331258 369 2140933 370 2348568 371 2105852 372 2465544 373 2131221 374 2400874 375 2238626 376 2459722 377 2188390 378 2544712 379 2217091 380 2536185 381 2317048 382 2530403 383 2275172 384 2671078 385 2321305 386 2596910 387 2409922 388 2657966 389 2364691 390 2759810 391 2395114 392 2732788 393 2502443 394 2732779 395 2468941 396 2884314 397 2487134 398 2802247 399 2601917 400 2884396 401 2549539 402 2961664 403 2581308 404 2939190 405 2711808 406 2948706 407 2645408 408 3107588 409 2677365 410 3032549 411 2796321 412 3086286 413 2746401 414 3188239 415 2790284 416 3164376 417 2898630 418 3166118 419 2841534 420 3359237 421 2875762 422 3241322 423 3004537 424 3317397 425 2959513 426 3421702 427 2982465 428 3392770 429 3110673 430 3413438 431 3046942 432 3585253 433 3082395 434 3479884 435 3235646 436 3552744 437 3152970 438 3666238 439 3188451 440 3656752 441 3336520 442 3636497 443 3260786 444 3833028 445 3315721 446 3717859 447 3442259 448 3809143 449 3370823 450 3943688 451 3409137 452 3885195 453 3557798 454 3885312 455 3508179 456 4099382 457 3521289 458 3970648 459 3677541 460 4079228 461 3597395 462 4193246 463 3636067 464 4149554 465 3816268 466 4144861 467 3713655 468 4371845 469 3759434 470 4256198 471 3917470 472 4329156 473 3833531 474 4460976 475 3894478 476 4423557 477 4044321 478 4413897 479 3953036 480 4681138 481 3995061 482 4506031 483 4175086 484 4604012 485 4099625 486 4749210 487 4118035 488 4701592 489 4297374 490 4726045 491 4201534 492 4946799 493 4244214 494 4788990 495 4457140 496 4895256 497 4336498 498 5042300 499 4372303 500 5015750 501 4562335 502 4982308 503 4458366 504 5266683 505 4528816 506 5082736 507 4698763 508 5188532 509 4590511 510 5377630 511 4643083 512 5295233 513 4839593 514 5281916 515 4752088 516 5566812 517 4771726 518 5392402 519 4976681 520 5532715 521 4861484 522 5669038 523 4907340 524 5601825 525 5157494 526 5591639 527 4999968 528 5899902 529 5047070 530 5728854 531 5268416 532 5825249 533 5141862 534 5993320 535 5218988 536 5929606 537 5412823 538 5911374 539 5294481 540 6267915 541 5333109 542 6020753 543 5562636 544 6150980 545 5461768 546 6342782 547 5479029 548 6257065 549 5718807 550 6279106 551 5577599 552 6584632 553 5637666 554 6354671 555 5904148 556 6485046 557 5727711 558 6684981 559 5779153 560 6654977 561 6029821 562 6583626 563 5880226 564 6937877 565 5967338 566 6699150 567 6201556 568 6841936 569 6035272 570 7081250 571 6087604 572 6957791 573 6349169 574 6946208 575 6229348 576 7320230 577 6245880 578 7054921 579 6513562 580 7238292 581 6363239 582 7413512 583 6407618 584 7326968 585 6725843 586 7297386 587 6513793 588 7702776 589 6568951 590 7463252 591 6850389 592 7577345 593 6678063 594 7803086 595 6786811 596 7696555 597 7022650 598 7671536 599 6844310 600 8136830 601 6901462 602 7810774 603 7201690 604 7953441 605 7058817 606 8190496 607 7070866 608 8091694 609 7386852 610 8101575 611 7186476 612 8494428 613 7243502 614 8184954 615 7598420 616 8372693 617 7359564 618 8595994 619 7417806 620 8531155 621 7740775 622 8449761 623 7548877 624 8915254 625 7642220 626 8583987 627 7922591 628 8753495 629 7714469 630 9085856 631 7774920 632 8900536 633 8107376 634 8855917 635 7943832 636 9333415 637 7972610 638 8996254 639 8302232 640 9234168 641 8079471 642 9441686 643 8140951 644 9328248 645 8540546 646 9273950 647 8264779 648 9788795 649 8330900 650 9472509 651 8699522 652 9599753 653 8453887 654 9881666 655 8570203 656 9754682 657 8887150 658 9718776 659 8644421 660 10287651 661 8709693 662 9847392 663 9082411 664 10049060 665 8910471 666 10340921 667 8903844 668 10188253 669 9283250 670 10202240 671 9036823 672 10718487 673 9100730 674 10290932 675 9553817 676 10492441 677 9232829 678 10797436 679 9316939 680 10718320 681 9696683 682 10596366 683 9433444 684 11172399 685 9561727 686 10765370 687 9906482 688 10965481 689 9638750 690 11340540 691 9705894 692 11110675 693 10148723 694 11055728 695 9905607 696 11664634 697 9913798 698 11212187 699 10334673 700 11517443 701 10051973 702 11771118 703 10122409 704 11605384 705 10619542 706 11530477 707 10282471 708 12153303 709 10334364 710 11762000 711 10781822 712 11927118 713 10476738 714 12283226 715 10621769 716 12079833 717 10998017 718 12015641 719 10692077 720 12763047 721 10787237 722 12181427 723 11224142 724 12413211 725 10981700 726 12776940 727 10985104 728 12619477 729 11461530 730 12591055 731 11133643 732 13191086 733 11207645 734 12681837 735 11780189 736 12937887 737 11361216 738 13306433 739 11432370 740 13176407 741 11921625 742 13047160 743 11583266 744 13742036 745 11735769 746 13195621 747 12164602 748 13450445 749 11835664 750 13918108 751 11890077 752 13637689 753 12395681 754 13546305 755 12122115 756 14313721 757 12122932 758 13720856 759 12642093 760 14081828 761 12278901 762 14383212 763 12381836 764 14160662 765 12976036 766 14077631 767 12517530 768 14856537 769 12595801 770 14378482 771 13131541 772 14526995 773 12755249 774 14954636 775 12919888 776 14727031 777 13407792 778 14622524 779 12997337 780 15512257 781 13084146 782 14808172 783 13645338 784 15130589 785 13330082 786 15518970 787 13325084 788 15273938 789 13891011 790 15275204 791 13516226 792 16037173 793 13576439 794 15368594 795 14241830 796 15656438 797 13739873 798 16134880 799 13824825 800 15966922 801 14423490 802 15749798 803 13997673 804 16604778 805 14200263 806 15944830 807 14676549 808 16256736 809 14248305 810 16820019 811 14334579 812 16468166 813 14943836 814 16336608 815 14602528 816 17239103 817 14594408 818 16527688 819 15258078 820 16942091 821 14768042 822 17316676 823 14855192 824 17054738 825 15593820 826 16957552 827 15031011 828 17858504 829 15120183 830 17235030 831 15762408 832 17467094 833 15329491 834 17941292 835 15490102 836 17655839 837 16053808 838 17530794 839 15565556 840 18655058 841 15658112 842 17736690 843 16322253 844 18064492 845 15947231 846 18592669 847 15968120 848 18295850 849 16607062 850 18267997 851 16112707 852 19138619 853 16205005 854 18394094 855 17018922 856 18719142 857 16390131 858 19239676 859 16482797 860 19033138 861 17218628 862 18781101 863 16669072 864 19841999 865 16877719 866 18994409 867 17477386 868 19381655 869 16958455 870 20020534 871 17050866 872 19584552 873 17786490 874 19425606 875 17390429 876 20484722 877 17334382 878 19641453 879 18069935 880 20162556 881 17525991 882 20626139 883 17623131 884 20231022 885 18494870 886 20081590 887 17816006 888 21200322 889 17952240 890 20435165 891 18698523 892 20675759 893 18111136 894 21260560 895 18333269 896 20967818 897 18987895 898 20749734 899 18406474 900 22039353 901 18508595 902 20983824 903 19333202 904 21384446 905 18834977 906 21964964 907 18806845 908 21590527 909 19622036 910 21618688 911 19008175 912 22631488 913 19118095 914 21661929 915 20056620 916 22057896 917 19353959 918 22699688 919 19415571 920 22464282 921 20242090 922 22126344 923 19623988 924 23390307 925 19861030 926 22361043 927 20579932 928 22796412 929 19931204 930 23563388 931 20079398 932 23008694 933 20888221 934 22833004 935 20393015 936 24133752 937 20350763 938 23119104 939 21215922 940 23647256 941 20560956 942 24155388 943 20666716 944 23765132 945 21755582 946 23563076 947 20879896 948 24845020 949 20991641 950 23955860 951 21879929 952 24307728 953 21201853 954 24931804 955 21458189 956 24478391 957 22225183 958 24286861 959 21571222 960 25816354 961 21636672 962 24539742 963 22574696 964 24979813 965 22005992 966 25734844 967 21963811 968 25271234 969 22901399 970 25201109 971 22183577 972 26429030 973 22343585 974 25285489 975 23408467 976 25775739 977 22517568 978 26467344 979 22637930 980 26226299 981 23613339 982 25793562 983 22852851 984 27241066 985 23127921 986 26050788 987 23994830 988 26525942 989 23192451 990 27476768 991 23306722 992 26816547 993 24299364 994 26620972 995 23699471 996 28027597 997 23649413 998 26826010 999 24676168 1000 27525505