0 1 1 1 2 1 3 3 4 4 5 9 6 19 7 27 8 41 9 62 10 91 11 128 12 175 13 231 14 298 15 392 16 498 17 617 18 768 19 933 20 1134 21 1372 22 1627 23 1922 24 2260 25 2642 26 3070 27 3546 28 4071 29 4647 30 5307 31 6021 32 6792 33 7654 34 8576 35 9595 36 10714 37 11898 38 13187 39 14584 40 16092 41 17713 42 19451 43 21307 44 23285 45 25433 46 27708 47 30113 48 32699 49 35420 50 38330 51 41432 52 44678 53 48123 54 51772 55 55628 56 59695 57 63977 58 68477 59 73199 60 78208 61 83446 62 88918 63 94690 64 100703 65 107026 66 113664 67 120554 68 127768 69 135311 70 143188 71 151403 72 159962 73 168868 74 178127 75 187819 76 197873 77 208294 78 219165 79 230412 80 242121 81 254297 82 266864 83 279909 84 293439 85 307459 86 321975 87 336993 88 352518 89 368556 90 385204 91 402376 92 420079 93 438411 94 457285 95 476802 96 496969 97 517695 98 539084 99 561143 100 583879 101 607298 102 631408 103 656214 104 681724 105 708050 106 735093 107 762860 108 791466 109 820809 110 851007 111 882067 112 913885 113 946580 114 980161 115 1014635 116 1050010 117 1086294 118 1123494 119 1161618 120 1200795 121 1240911 122 1281975 123 1324117 124 1367222 125 1411423 126 1456729 127 1503021 128 1550435 129 1598980 130 1648665 131 1699498 132 1751489 133 1804645 134 1858976 135 1914626 136 1971468 137 2029511 138 2088902 139 2149511 140 2211488 141 2274842 142 2339441 143 2405436 144 2472838 145 2541656 146 2611900 147 2683580 148 2756705 149 2831285 150 2907481 151 2985151 152 3064306 153 3145108 154 3227414 155 3311389 156 3397044 157 3484232 158 3573121 159 3663722 160 3756046 161 3850103 162 3945905 163 4043461 164 4142783 165 4244047 166 4347098 167 4451947 168 4558773 169 4667418 170 4778064 171 4890722 172 5005232 173 5121777 174 5240370 175 5361022 176 5483745 177 5608551 178 5735451 179 5864457 180 5995762 181 6129196 182 6264772 183 6402684 184 6542761 185 6685200 186 6830014 187 6977028 188 7126442 189 7278269 190 7432522 191 7589213 192 7748356 193 7909962 194 8074045 195 8240813 196 8410083 197 8581868 198 8756379 199 8933430 200 9113235 201 9295807 202 9480958 203 9668903 204 9859657 205 10053233 206 10249645 207 10448907 208 10651032 209 10856034 210 11064138 211 11275146 212 11489073 213 11706145 214 11926163 215 12149356 216 12375739 217 12605109 218 12837698 219 13073521 220 13312593 221 13554928 222 13800542 223 14049448 224 14301662 225 14557424 226 14816523 227 15078974 228 15345020 229 15614447 230 15887501 231 16164197 232 16444319 233 16728114 234 17015599 235 17306789 236 17601700 237 17900348 238 18202748 239 18508916 240 18819109 241 19133101 242 19450909 243 19772791 244 20098520 245 20428357 246 20762319 247 21100175 248 21442189 249 21788378 250 22138759 251 22493348 252 22852163 253 23215219 254 23582534 255 23954380 256 24330518 257 24710965 258 25095996 259 25485369 260 25879362 261 26277992 262 26681015 263 27088710 264 27501096 265 27918190 266 28340010 267 28766574 268 29197899 269 29634003 270 30075175 271 30521161 272 30971980 273 31427922 274 31888732 275 32354703 276 32825854 277 33301926 278 33783215 279 34269740 280 34761520 281 35258573 282 35760919 283 36268575 284 36781561 285 37300181 286 37824168 287 38353541 288 38888607 289 39429096 290 39975318 291 40527292 292 41084746 293 41647991 294 42217048 295 42791936 296 43372675 297 43959285 298 44551785 299 45150195 300 45754836 301 46365426 302 46981986 303 47604838 304 48233699 305 48868894 306 49510444 307 50158062 308 50812076 309 51472507 310 52139376 311 52812703 312 53492510 313 54178816 314 54871643 315 55571327 316 56277573 317 56990402 318 57710153 319 58436528 320 59169869 321 59910197 322 60657212 323 61411257 324 62172355 325 62940527 326 63715795 327 64498181 328 65287706 329 66084392 330 66888592 331 67699996 332 68518627 333 69344839 334 70178321 335 71019430 336 71868189 337 72724283 338 73588072 339 74459579 340 75338827 341 76225838 342 77120636 343 78023242 344 78933680 345 79852318 346 80778833 347 81713248 348 82655934 349 83606565 350 84565515 351 85532807 352 86508113 353 87491808 354 88483917 355 89484463 356 90493470 357 91510962 358 92536962 359 93571494 360 94614943 361 95666971 362 96727603 363 97797225 364 98875498 365 99962811 366 101059189 367 102164289 368 103278503 369 104401856 370 105534373 371 106676078 372 107826997 373 108987153 374 110156572 375 111335654 376 112524048 377 113721779 378 114929250 379 116146107 380 117372756 381 118609222 382 119855149 383 121110944 384 122376634 385 123652244 386 124937800 387 126233328 388 127538853 389 128854401 390 130180389 391 131516451 392 132862614 393 134219296 394 135586130 395 136963537 396 138351544 397 139749780 398 141158669 399 142578238 400 144008514 401 145449523 402 146901293 403 148363849 404 149837219 405 151321835 406 152817318 407 154323695 408 155841401 409 157370054 410 158910092 411 160461542 412 162024020 413 163597965 414 165183406 415 166780370 416 168388885 417 170008979 418 171640679 419 173284013 420 174939430 421 176606536 422 178285360 423 179976352 424 181679117 425 183394108 426 185121354 427 186860456 428 188611870 429 190375625 430 192151750 431 193940273 432 195741224 433 197554630 434 199380521 435 201219361 436 203070743 437 204934696 438 206811687 439 208701306 440 210604023 441 212519867 442 214448426 443 216390171 444 218345133 445 220313341 446 222294825 447 224289615 448 226297740 449 228319230 450 230354566 451 232403326 452 234465541 453 236541693 454 238631359 455 240735024 456 242852719 457 244984017 458 247129406 459 249288917 460 251462581 461 253650428 462 255852490 463 258068796 464 260299378 465 262544732 466 264804423 467 267078482 468 269367408 469 271670763 470 273989049 471 276322297 472 278670067 473 281032862 474 283410715 475 285803657 476 288211720 477 290634936 478 293073336 479 295526952 480 297996297 481 300480921 482 302980857 483 305496619 484 308027756 485 310574785 486 313137739 487 315716163 488 318310577 489 320921014 490 323547507 491 326190088 492 328848791 493 331523647 494 334214690 495 336922448 496 339646458 497 342386753 498 345143864 499 347917325 500 350707670 501 353514932 502 356338643 503 359179338 504 362037052 505 364911818 506 367803670 507 370712642 508 373638767 509 376582079 510 379543123 511 382521421 512 385517008 513 388530430 514 391561208 515 394609891 516 397676514 517 400760594 518 403862683 519 406982816 520 410121028 521 413277353 522 416451827 523 419644483 524 422855357 525 426085009 526 429332948 527 432599209 528 435884355 529 439187892 530 442510386 531 445851872 532 449211854 533 452590899 534 455989044 535 459406324 536 462842775 537 466298433 538 469773333 539 473267511 540 476781544 541 480314926 542 483867694 543 487440426 544 491032615 545 494644842 546 498277144 547 501929010 548 505601024 549 509293223 550 513005644 551 516738323 552 520491298 553 524264604 554 528058279 555 531872915 556 535707993 557 539563550 558 543440181 559 547337364 560 551255697 561 555195217 562 559155400 563 563136845 564 567139591 565 571163675 566 575209135 567 579276009 568 583364334 569 587474148 570 591606060 571 595759536 572 599934615 573 604131907 574 608350877 575 612592138 576 616855729 577 621141111 578 625448900 579 629779135 580 634131855 581 638507098 582 642904904 583 647325310 584 651768356 585 656234666 586 660723693 587 665235476 588 669770642 589 674328641 590 678910103 591 683515067 592 688142981 593 692794476 594 697469593 595 702168371 596 706890850 597 711637070 598 716407070 599 721200890 600 726019171 601 730861351 602 735727471 603 740618173 604 745532894 605 750472279 606 755436369 607 760424597 608 765437611 609 770475452 610 775538161 611 780625778 612 785738345 613 790875901 614 796038488 615 801226762 616 806440148 617 811678687 618 816943038 619 822232623 620 827548104 621 832889522 622 838256297 623 843649092 624 849067950 625 854512912 626 859984020 627 865481316 628 871004841 629 876554637 630 882131377 631 887734471 632 893363962 633 899020524 634 904703566 635 910413765 636 916151164 637 921915168 638 927706457 639 933525074 640 939371062 641 945244463 642 951145321 643 957073677 644 963029575 645 969013703 646 975025458 647 981064883 648 987132669 649 993228210 650 999352200 651 1005504682 652 1011685048 653 1017893993 654 1024131562 655 1030397798 656 1036692745 657 1043016447 658 1049368947 659 1055750289 660 1062161178 661 1068600996 662 1075069788 663 1081568260 664 1088095793 665 1094653096 666 1101240214 667 1107856524 668 1114502738 669 1121178901 670 1127885058 671 1134621253 672 1141387532 673 1148183938 674 1155010517 675 1161867989 676 1168755723 677 1175673764 678 1182622835 679 1189602302 680 1196612891 681 1203654647 682 1210726934 683 1217830479 684 1224965329 685 1232131529 686 1239329125 687 1246558163 688 1253818688 689 1261110746 690 1268435074 691 1275791026 692 1283178649 693 1290598681 694 1298050475 695 1305534772 696 1313051619 697 1320600365 698 1328181754 699 1335795833 700 1343442649 701 1351122248 702 1358834678 703 1366579984 704 1374358214 705 1382170120 706 1390015043 707 1397893030 708 1405804836 709 1413749799 710 1421728677 711 1429741517 712 1437787655 713 1445867850 714 1453982151 715 1462130605 716 1470313260 717 1478530164 718 1486781364 719 1495066908 720 1503387565 721 1511742661 722 1520132245 723 1528557087 724 1537016512 725 1545511293 726 1554041479 727 1562606391 728 1571206805 729 1579842770 730 1588514335 731 1597221548 732 1605964459 733 1614743115 734 1623557566 735 1632408596 736 1641295518 737 1650218381 738 1659177972 739 1668173601 740 1677206058 741 1686275392 742 1695380911 743 1704523406 744 1713702928 745 1722919526 746 1732173250 747 1741464150 748 1750792275 749 1760157675 750 1769561151 751 1779002001 752 1788480276 753 1797996778 754 1807550804 755 1817143159 756 1826773894 757 1836442302 758 1846149191 759 1855894612 760 1865678616 761 1875501253 762 1885362575 763 1895262631 764 1905201473 765 1915179917 766 1925197248 767 1935253517 768 1945349543 769 1955484608 770 1965659534 771 1975874372 772 1986128402 773 1996422447 774 2006756560 775 2017130792 776 2027545195 777 2037999821 778 2048494721 779 2059029947 780 2069606332 781 2080223146 782 2090880442 783 2101579054 784 2112318251 785 2123098870 786 2133920964 787 2144783798 788 2155688212 789 2166634259 790 2177621992 791 2188651463 792 2199722726 793 2210835832 794 2221990835 795 2233188583 796 2244428333 797 2255710138 798 2267034849 799 2278401720 800 2289811605 801 2301264557 802 2312759828 803 2324298273 804 2335879947 805 2347504903 806 2359173195 807 2370884877 808 2382640002 809 2394438624 810 2406281608 811 2418168196 812 2430098443 813 2442073215 814 2454091753 815 2466154926 816 2478262789 817 2490414579 818 2502611168 819 2514852611 820 2527138963 821 2539470278 822 2551846612 823 2564268018 824 2576734552 825 2589247094 826 2601804873 827 2614407944 828 2627057190 829 2639751837 830 2652492771 831 2665280047 832 2678112889 833 2690992184 834 2703917989 835 2716890359 836 2729909350 837 2742975018 838 2756087418 839 2769246606 840 2782453479 841 2795707251 842 2809007979 843 2822356561 844 2835752210 845 2849195827 846 2862687469 847 2876226345 848 2889813359 849 2903448568 850 2917132029 851 2930863798 852 2944643933 853 2958472489 854 2972349524 855 2986275950 856 3000250968 857 3014274635 858 3028347866 859 3042469859 860 3056641532 861 3070862942 862 3085133285 863 3099453480 864 3113823586 865 3128243660 866 3142713760 867 3157233944 868 3171804269 869 3186424793 870 3201096445 871 3215818411 872 3230590750 873 3245414392 874 3260288522 875 3275214073 876 3290191104 877 3305218796 878 3320298085 879 3335429030 880 3350611690 881 3365846123 882 3381132389 883 3396470545 884 3411860651 885 3427303651 886 3442798718 887 3458345911 888 3473946177 889 3489598686 890 3505304388 891 3521063342 892 3536874716 893 3552739461 894 3568657638 895 3584629306 896 3600654525 897 3616733355 898 3632865855 899 3649052085 900 3665293006 901 3681587776 902 3697936456 903 3714340008 904 3730797589 905 3747310164 906 3763877794 907 3780499632 908 3797176646 909 3813908897 910 3830696446 911 3847539353 912 3864437680 913 3881391486 914 3898400833 915 3915466697 916 3932588223 917 3949765472 918 3966999423 919 3984289218 920 4001635839 921 4019039347 922 4036498882 923 4054015427 924 4071589045 925 4089219797 926 4106907745 927 4124652951 928 4142455476 929 4160315382 930 4178233662 931 4196209446 932 4214242797 933 4232334709 934 4250484311 935 4268692600 936 4286959639 937 4305284553 938 4323668342 939 4342111069 940 4360612797 941 4379173588 942 4397793506 943 4416472612 944 4435210970 945 4454009588 946 4472867583 947 4491785018 948 4510762904 949 4529800355 950 4548898385 951 4568057057 952 4587275483 953 4606554678 954 4625894707 955 4645295633 956 4664757520 957 4684280432 958 4703864432 959 4723509584 960 4743216913 961 4762985521 962 4782815473 963 4802707795 964 4822661588 965 4842677881 966 4862756739 967 4882897259 968 4903100473 969 4923366446 970 4943695243 971 4964086928 972 4984541567 973 5005059223 974 5025639962 975 5046284824 976 5066992898 977 5087764249 978 5108599920 979 5129498997 980 5150462526 981 5171490572 982 5192582219 983 5213738514 984 5234959524 985 5256245314 986 5277595950 987 5299011498 988 5320492023 989 5342037591 990 5363649259 991 5385326101 992 5407068184 993 5428876566 994 5450750320 995 5472690507 996 5494697194 997 5516769450 998 5538908339 999 5561113928 1000 5583386284