0 0 1 4 2 32 3 104 4 250 5 492 6 845 7 1349 8 2021 9 2871 10 3949 11 5267 12 6830 13 8698 14 10878 15 13370 16 16244 17 19502 18 23139 19 27235 20 31787 21 36785 22 42319 23 48381 24 54956 25 62144 26 69932 27 78300 28 87358 29 97088 30 107465 31 118609 32 130497 33 143099 34 156545 35 170807 36 185850 37 201814 38 218666 39 236366 40 255064 41 274722 42 295295 43 316943 44 339623 45 363285 46 388099 47 414017 48 440984 49 469180 50 498552 51 529040 52 560834 53 593876 54 628101 55 663709 56 700637 57 738815 58 778453 59 819483 60 861830 61 905714 62 951062 63 997794 64 1046140 65 1096022 66 1147355 67 1200379 68 1255011 69 1311161 70 1369079 71 1428677 72 1489860 73 1552888 74 1617668 75 1684100 76 1752454 77 1822632 78 1894529 79 1968425 80 2044217 81 2121795 82 2201449 83 2283071 84 2366546 85 2452174 86 2539842 87 2629430 88 2721248 89 2815178 90 2911095 91 3009319 92 3109727 93 3212189 94 3317035 95 3424137 96 3533360 97 3645044 98 3759056 99 3875256 100 3993994 101 4115132 102 4238525 103 4364533 104 4493013 105 4623815 106 4757309 107 4893347 108 5031774 109 5172970 110 5316782 111 5463050 112 5612164 113 5763966 114 5918291 115 6075539 116 6235547 117 6398145 118 6563743 119 6732173 120 6903260 121 7077424 122 7254492 123 7434284 124 7617230 125 7803152 126 7991865 127 8183809 128 8378801 129 8576651 130 8777809 131 8982087 132 9189290 133 9399878 134 9613658 135 9830430 136 10050664 137 10274162 138 10500719 139 10730815 140 10964247 141 11200805 142 11440979 143 11684561 144 11931336 145 12181804 146 12435752 147 12692960 148 12953938 149 13218468 150 13486325 151 13758029 152 14033357 153 14312079 154 14594725 155 14881067 156 15170870 157 15464674 158 15762246 159 16063346 160 16368524 161 16677542 162 16990155 163 17306923 164 17627603 165 17951945 166 18280519 167 18613077 168 18949364 169 19289960 170 19634612 171 19983060 172 20335894 173 20692856 174 21053681 175 21418969 176 21788457 177 22161875 178 22539833 179 22922063 180 23308290 181 23699134 182 24094322 183 24493574 184 24897520 185 25305882 186 25718375 187 26135639 188 26557391 189 26983341 190 27414139 191 27849497 192 28289120 193 28733668 194 29182848 195 29636360 196 30094874 197 30558092 198 31025709 199 31498405 200 31975877 201 32457815 202 32944909 203 33436851 204 33933326 205 34435034 206 34941662 207 35452890 208 35969428 209 36490958 210 37017155 211 37548739 212 38085387 213 38626769 214 39173615 215 39725597 216 40282380 217 40844704 218 41412236 219 41984636 220 42562654 221 43145952 222 43734185 223 44328113 224 44927393 225 45531675 226 46141729 227 46757207 228 47377754 229 48004150 230 48636042 231 49273070 232 49916024 233 50564546 234 51218271 235 51877999 236 52543367 237 53214005 238 53890723 239 54573153 240 55260920 241 55954844 242 56654552 243 57359664 244 58071010 245 58788212 246 59510885 247 60239869 248 60974781 249 61715231 250 62462069 251 63214907 252 63973350 253 64738258 254 65509238 255 66285890 256 67069084 257 67858422 258 68653499 259 69455195 260 70263107 261 71076825 262 71897239 263 72723941 264 73556516 265 74395864 266 75241572 267 76093220 268 76951718 269 77816648 270 78687585 271 79565449 272 80449817 273 81340259 274 82237705 275 83141727 276 84051890 277 84969134 278 85893026 279 86823126 280 87760384 281 88704362 282 89654615 283 90612103 284 91576383 285 92547005 286 93524939 287 94509737 288 95500944 289 96499540 290 97505072 291 98517080 292 99536554 293 100563036 294 101596061 295 102636629 296 103684277 297 104738535 298 105800413 299 106869443 300 107945150 301 109028554 302 110119182 303 111216554 304 112321700 305 113434142 306 114553395 307 115680499 308 116814971 309 117956321 310 119105599 311 120262317 312 121425980 313 122597648 314 123776828 315 124963020 316 126157294 317 127359152 318 128568089 319 129785185 320 131009937 321 132241835 322 133481969 323 134729831 324 135984906 325 137248294 326 138519482 327 139797950 328 141084808 329 142379538 330 143681615 331 144992159 332 146310647 333 147636549 334 148970995 335 150313457 336 151663400 337 153021964 338 154388616 339 155762816 340 157145714 341 158536772 342 159935445 343 161342893 344 162758573 345 164181935 346 165614149 347 167054667 348 168502934 349 169960130 350 171425702 351 172899090 352 174381484 353 175872326 354 177371051 355 178878859 356 180395187 357 181919465 358 183452903 359 184994933 360 186544980 361 188104264 362 189672212 363 191248244 364 192833590 365 194427672 366 196029905 367 197641529 368 199261961 369 200890611 370 202528729 371 204175727 372 205831010 373 207495838 374 209169618 375 210851750 376 212543504 377 214244282 378 215953479 379 217672375 380 219400367 381 221136845 382 222883099 383 224638521 384 226402496 385 228176324 386 229959392 387 231751080 388 233552698 389 235363628 390 237183245 391 239012869 392 240851877 393 242699639 394 244557485 395 246424787 396 248300910 397 250187194 398 252083006 399 253987706 400 255902644 401 257827182 402 259760675 403 261704483 404 263657963 405 265620465 406 267593359 407 269575997 408 271567724 409 273569920 410 275581932 411 277603100 412 279634814 413 281676416 414 283727241 415 285788689 416 287860097 417 289940795 418 292032193 419 294133623 420 296244410 421 298365974 422 300497642 423 302638734 424 304790680 425 306952802 426 309124415 427 311306959 428 313499751 429 315702101 430 317915459 431 320139137 432 322372440 433 324616828 434 326871608 435 329136080 436 331411714 437 333697812 438 335993669 439 338300765 440 340618397 441 342945855 442 345284629 443 347634011 444 349993286 445 352363954 446 354745302 447 357136610 448 359539388 449 361952918 450 364376475 451 366811579 452 369257507 453 371713529 454 374181175 455 376659717 456 379148420 457 381648824 458 384160196 459 386681796 460 389215174 461 391759592 462 394314305 463 396880873 464 399458553 465 402046595 466 404646569 467 407257727 468 409879314 469 412512910 470 415157762 471 417813110 472 420480544 473 423159306 474 425848631 475 428550119 476 431263007 477 433986525 478 436722283 479 439469513 480 442227440 481 444997684 482 447779472 483 450572024 484 453376970 485 456193532 486 459020925 487 461860789 488 464712341 489 467574791 490 470449789 491 473336547 492 476234270 493 479144618 494 482066798 495 485000010 496 487945924 497 490903742 498 493872659 499 496854355 500 499848027 501 502852865 502 505870559 503 508900301 504 511941276 505 514995184 506 518061212 507 521138540 508 524228878 509 527331408 510 530445305 511 533572289 512 536711537 513 539862219 514 543026065 515 546202247 516 549389930 517 552590854 518 555804186 519 559029086 520 562267304 521 565518002 522 568780335 523 572056063 524 575344343 525 578644325 526 581957779 527 585283857 528 588621704 529 591973100 530 595337192 531 598713120 532 602102674 533 605504996 534 608919221 535 612347149 536 615787917 537 619240655 538 622707173 539 626186603 540 629678070 541 633183394 542 636701702 543 640232114 544 643776460 545 647333862 546 650903435 547 654487019 548 658083731 549 661692681 550 665315719 551 668951957 552 672600500 553 676263208 554 679939188 555 683627540 556 687330134 557 691046072 558 694774449 559 698517145 560 702273257 561 706041875 562 709824889 563 713621391 564 717430466 565 721254014 566 725091122 567 728940870 568 732805168 569 736683098 570 740573735 571 744478999 572 748397967 573 752329709 574 756276155 575 760236377 576 764209440 577 768197284 578 772198976 579 776213576 580 780243034 581 784286412 582 788342765 583 792414053 584 796499333 585 800597655 586 804710989 587 808838387 588 812978894 589 817134490 590 821304222 591 825487130 592 829685204 593 833897486 594 838123011 595 842363779 596 846618827 597 850887185 598 855170863 599 859468893 600 863780300 601 868107104 602 872448332 603 876803004 604 881173150 605 885557792 606 889955945 607 894369649 608 898797921 609 903239771 610 907697249 611 912169367 612 916655130 613 921156598 614 925672778 615 930202670 616 934748344 617 939308802 618 943883039 619 948473135 620 953078087 621 957696885 622 962331619 623 966981281 624 971644856 625 976324444 626 981019032 627 985727600 628 990452258 629 995191988 630 999945765 631 1004715709 632 1009500797 633 1014299999 634 1019115445 635 1023946107 636 1028790950 637 1033652114 638 1038528566 639 1043419266 640 1048326364 641 1053248822 642 1058185595 643 1063138843 644 1068107523 645 1073090585 646 1078090199 647 1083105317 648 1088134884 649 1093181080 650 1098242852 651 1103319140 652 1108412134 653 1113520776 654 1118644001 655 1123784009 656 1128939737 657 1134110115 658 1139297353 659 1144500383 660 1149718130 661 1154952814 662 1160203362 663 1165468694 664 1170751040 665 1176049322 666 1181362455 667 1186692679 668 1192038911 669 1197400061 670 1202778379 671 1208172777 672 1213582160 673 1219008788 674 1224451568 675 1229909400 676 1235384554 677 1240875932 678 1246382429 679 1251906325 680 1257446517 681 1263001895 682 1268574749 683 1274163971 684 1279768446 685 1285390474 686 1291028942 687 1296682730 688 1302354148 689 1308042078 690 1313745395 691 1319466419 692 1325204027 693 1330957089 694 1336727935 695 1342515437 696 1348318460 697 1354139344 698 1359976956 699 1365830156 700 1371701294 701 1377589232 702 1383492825 703 1389414433 704 1395352913 705 1401307115 706 1407279409 707 1413268647 708 1419273674 709 1425296870 710 1431337082 711 1437393150 712 1443467464 713 1449558866 714 1455666191 715 1461791839 716 1467934647 717 1474093445 718 1480270643 719 1486465073 720 1492675560 721 1498904524 722 1505150792 723 1511413184 724 1517694130 725 1523992452 726 1530306965 727 1536640109 728 1542990701 729 1549357551 730 1555743109 731 1562146187 732 1568565590 733 1575003778 734 1581459558 735 1587931730 736 1594422764 737 1600931462 738 1607456619 739 1614000715 740 1620562547 741 1627140905 742 1633738279 743 1640353461 744 1646985236 745 1653636104 746 1660304852 747 1666990260 748 1673694838 749 1680417368 750 1687156625 751 1693915129 752 1700691657 753 1707484979 754 1714297625 755 1721128367 756 1727975970 757 1734842974 758 1741728146 759 1748630246 760 1755551824 761 1762491642 762 1769448455 763 1776424823 764 1783419503 765 1790431245 766 1797462619 767 1804512377 768 1811579264 769 1818665860 770 1825770912 771 1832893160 772 1840035194 773 1847195756 774 1854373581 775 1861571269 776 1868787557 777 1876021175 778 1883274733 779 1890546963 780 1897836590 781 1905146234 782 1912474622 783 1919820474 784 1927186420 785 1934571182 786 1941973475 787 1949395939 788 1956837291 789 1964296241 790 1971775439 791 1979273597 792 1986789420 793 1994325568 794 2001880748 795 2009453660 796 2017046974 797 2024659392 798 2032289609 799 2039940305 800 2047610177 801 2055297915 802 2063006209 803 2070733751 804 2078479226 805 2086245334 806 2094030762 807 2101834190 808 2109658328 809 2117501858 810 2125363455 811 2133245839 812 2141147687 813 2149067669 814 2157008515 815 2164968897 816 2172947480 817 2180947004 818 2188966136 819 2197003536 820 2205061954 821 2213140052 822 2221236485 823 2229354013 824 2237491293 825 2245646975 826 2253823829 827 2262020507 828 2270235654 829 2278472050 830 2286728342 831 2295003170 832 2303299324 833 2311615446 834 2319950171 835 2328306299 836 2336682467 837 2345077305 838 2353493623 839 2361930053 840 2370385220 841 2378861944 842 2387358852 843 2395874564 844 2404411910 845 2412969512 846 2421545985 847 2430144169 848 2438762681 849 2447400131 850 2456059369 851 2464739007 852 2473437650 853 2482158158 854 2490899138 855 2499659190 856 2508441184 857 2517243722 858 2526065399 859 2534909095 860 2543773407 861 2552656925 862 2561562539 863 2570488841 864 2579434416 865 2588402164 866 2597390672 867 2606398520 868 2615428618 869 2624479548 870 2633549885 871 2642642549 872 2651756117 873 2660889159 874 2670044605 875 2679221027 876 2688416990 877 2697635434 878 2706874926 879 2716134026 880 2725415684 881 2734718462 882 2744040915 883 2753386003 884 2762752283 885 2772138305 886 2781547039 887 2790977037 888 2800426844 889 2809899440 890 2819393372 891 2828907180 892 2838443854 893 2848001936 894 2857579961 895 2867180929 896 2876803377 897 2886445835 898 2896111313 899 2905798343 900 2915505450 901 2925235654 902 2934987482 903 2944759454 904 2954554600 905 2964371442 906 2974208495 907 2984068799 908 2993950871 909 3003853221 910 3013778899 911 3023726417 912 3033694280 913 3043685548 914 3053698728 915 3063732320 916 3073789394 917 3083868452 918 3093967989 919 3104091085 920 3114236237 921 3124401935 922 3134591269 923 3144802731 924 3155034806 925 3165290594 926 3175568582 927 3185867250 928 3196189708 929 3206534438 930 3216899915 931 3227289259 932 3237700947 933 3248133449 934 3258589895 935 3269068757 936 3279568500 937 3290092264 938 3300638516 939 3311205716 940 3321797014 941 3332410872 942 3343045745 943 3353704793 944 3364386473 945 3375089235 946 3385816249 947 3396565967 948 3407336834 949 3418132030 950 3428950002 951 3439789190 952 3450652784 953 3461539226 954 3472446951 955 3483379159 956 3494334287 957 3505310765 958 3516311803 959 3527335833 960 3538381280 961 3549451364 962 3560544512 963 3571659144 964 3582798490 965 3593960972 966 3605145005 967 3616353829 968 3627585861 969 3638839511 970 3650118029 971 3661419827 972 3672743310 973 3684091738 974 3695463518 975 3706857050 976 3718275604 977 3729717582 978 3741181379 979 3752670275 980 3764182667 981 3775716945 982 3787276399 983 3798859421 984 3810464396 985 3822094624 986 3833748492 987 3845424380 988 3857125598 989 3868850528 990 3880597545 991 3892369969 992 3904166177 993 3915984539 994 3927828385 995 3939696087 996 3951586010 997 3963501494 998 3975440906 999 3987402606 1000 3999389944