0 0 1 4 2 32 3 106 4 252 5 495 6 855 7 1359 8 2029 9 2891 10 3970 11 5286 12 6866 13 8732 14 10910 15 13425 16 16297 17 19553 18 23215 19 27309 20 31860 21 36888 22 42420 23 48478 24 55088 25 62275 26 70059 27 78467 28 87521 29 97247 30 107670 31 118810 32 130694 33 143344 34 156786 35 171045 36 186141 37 202101 38 218947 39 236705 40 255400 41 275052 42 295688 43 317330 44 340004 45 363735 46 388543 47 414455 48 441493 49 469683 50 499050 51 529614 52 561402 53 594436 54 628742 55 664345 56 701265 57 739529 58 779159 59 820181 60 862620 61 906496 62 951836 63 998662 64 1047000 65 1096875 66 1148307 67 1201323 68 1255945 69 1312199 70 1370110 71 1429698 72 1490990 73 1554008 74 1618778 75 1685325 76 1753669 77 1823837 78 1895851 79 1969737 80 2045520 81 2123220 82 2202864 83 2284474 84 2368076 85 2453695 86 2541351 87 2631071 88 2722877 89 2816795 90 2912850 91 3011062 92 3111458 93 3214060 94 3318894 95 3425985 96 3535353 97 3647025 98 3761023 99 3877373 100 3996100 101 4117224 102 4240772 103 4366766 104 4495232 105 4626195 106 4759675 107 4895699 108 5034289 109 5175471 110 5319270 111 5465706 112 5614806 113 5766592 114 5921090 115 6078325 116 6238317 117 6401093 118 6566675 119 6735089 120 6906360 121 7080508 122 7257560 123 7437538 124 7620468 125 7806375 126 7995279 127 8187207 128 8382181 129 8580227 130 8781370 131 8985630 132 9193034 133 9403604 134 9617366 135 9834345 136 10054561 137 10278041 138 10504807 139 10734885 140 10968300 141 11205072 142 11445228 143 11688790 144 11935784 145 12186235 146 12440163 147 12697595 148 12958553 149 13223063 150 13491150 151 13762834 152 14038142 153 14317096 154 14599722 155 14886045 156 15176085 157 15469869 158 15767419 159 16068761 160 16373920 161 16682916 162 16995776 163 17312522 164 17633180 165 17957775 166 18286327 167 18618863 168 18955405 169 19295979 170 19640610 171 19989318 172 20342130 173 20699068 174 21060158 175 21425425 176 21794889 177 22168577 178 22546511 179 22928717 180 23315220 181 23706040 182 24101204 183 24500734 184 24904656 185 25312995 186 25725771 187 26143011 188 26564737 189 26990975 190 27421750 191 27857082 192 28296998 193 28741520 194 29190674 195 29644485 196 30102973 197 30566165 198 31034083 199 31506753 200 31984200 201 32466444 202 32953512 203 33445426 204 33942212 205 34443895 206 34950495 207 35462039 208 35978549 209 36500051 210 37026570 211 37558126 212 38094746 213 38636452 214 39183270 215 39735225 216 40292337 217 40854633 218 41422135 219 41994869 220 42572860 221 43156128 222 43744700 223 44338598 224 44937848 225 45542475 226 46152499 227 46767947 228 47388841 229 48015207 230 48647070 231 49284450 232 49927374 233 50575864 234 51229946 235 51889645 236 52554981 237 53225981 238 53902667 239 54585065 240 55273200 241 55967092 242 56666768 243 57372250 244 58083564 245 58800735 246 59523783 247 60252735 248 60987613 249 61728443 250 62475250 251 63228054 252 63986882 253 64751756 254 65522702 255 66299745 256 67082905 257 67872209 258 68667679 259 69469341 260 70277220 261 71091336 262 71911716 263 72738382 264 73571360 265 74410675 266 75256347 267 76108403 268 76966865 269 77831759 270 78703110 271 79580938 272 80465270 273 81356128 274 82253538 275 83157525 276 84068109 277 84985317 278 85909171 279 86839697 280 87776920 281 88720860 282 89671544 283 90628994 284 91593236 285 92564295 286 93542191 287 94526951 288 95518597 289 96517155 290 97522650 291 98535102 292 99554538 293 100580980 294 101614454 295 102654985 296 103702593 297 104757305 298 105819143 299 106888133 300 107964300 301 109047664 302 110138252 303 111236086 304 112341192 305 113453595 306 114573315 307 115700379 308 116834809 309 117976631 310 119125870 311 120282546 312 121446686 313 122618312 314 123797450 315 124984125 316 126178357 317 127380173 318 128589595 319 129806649 320 131031360 321 132263748 322 133503840 323 134751658 324 136007228 325 137270575 326 138541719 327 139820687 328 141107501 329 142402187 330 143704770 331 145015270 332 146333714 333 147660124 334 148994526 335 150336945 336 151687401 337 153045921 338 154412527 339 155787245 340 157170100 341 158561112 342 159960308 343 161367710 344 162783344 345 164207235 346 165639403 347 167079875 348 168528673 349 169985823 350 171451350 351 172925274 352 174407622 353 175898416 354 177397682 355 178905445 356 180421725 357 181946549 358 183479939 359 185021921 360 186572520 361 188131756 362 189699656 363 191276242 364 192861540 365 194455575 366 196058367 367 197669943 368 199290325 369 200919539 370 202557610 371 204204558 372 205860410 373 207525188 374 209198918 375 210881625 376 212573329 377 214274057 378 215983831 379 217702677 380 219430620 381 221167680 382 222913884 383 224669254 384 226433816 385 228207595 386 229990611 387 231782891 388 233584457 389 235395335 390 237215550 391 239045122 392 240884078 393 242732440 394 244590234 395 246457485 396 248334213 397 250220445 398 252116203 399 254021513 400 255936400 401 257860884 402 259794992 403 261738746 404 263692172 405 265655295 406 267628135 407 269610719 408 271603069 409 273605211 410 275617170 411 277638966 412 279670626 413 281712172 414 283763630 415 285825025 416 287896377 417 289977713 418 292069055 419 294170429 420 296281860 421 298403368 422 300534980 423 302676718 424 304828608 425 306990675 426 309162939 427 311345427 428 313538161 429 315741167 430 317954470 431 320178090 432 322412054 433 324656384 434 326911106 435 329176245 436 331451821 437 333737861 438 336034387 439 338341425 440 340659000 441 342987132 442 345325848 443 347675170 444 350035124 445 352405735 446 354787023 447 357179015 448 359581733 449 361995203 450 364419450 451 366854494 452 369300362 453 371757076 454 374224662 455 376703145 456 379192545 457 381692889 458 384204199 459 386726501 460 389259820 461 391804176 462 394359596 463 396926102 464 399503720 465 402092475 466 404692387 467 407303483 468 409925785 469 412559319 470 415204110 471 417860178 472 420527550 473 423206248 474 425896298 475 428597725 476 431310549 477 434034797 478 436770491 479 439517657 480 442276320 481 445046500 482 447828224 483 450621514 484 453426396 485 456242895 486 459071031 487 461910831 488 464762317 489 467625515 490 470500450 491 473387142 492 476285618 493 479195900 494 482118014 495 485051985 496 487997833 497 490955585 498 493925263 499 496906893 500 499900500 501 502906104 502 505923732 503 508953406 504 511995152 505 515048995 506 518114955 507 521193059 508 524283329 509 527385791 510 530500470 511 533627386 512 536766566 513 539918032 514 543081810 515 546257925 516 549446397 517 552647253 518 555860515 519 559086209 520 562324360 521 565574988 522 568838120 523 572113778 524 575401988 525 578702775 526 582016159 527 585342167 528 588680821 529 592032147 530 595396170 531 598772910 532 602162394 533 605564644 534 608979686 535 612407545 536 615848241 537 619301801 538 622768247 539 626247605 540 629739900 541 633245152 542 636763388 543 640294630 544 643838904 545 647396235 546 650966643 547 654550155 548 658146793 549 661756583 550 665379550 551 669015714 552 672665102 553 676327736 554 680003642 555 683692845 556 687395365 557 691111229 558 694840459 559 698583081 560 702339120 561 706108596 562 709891536 563 713687962 564 717497900 565 721321375 566 725158407 567 729009023 568 732873245 569 736751099 570 740642610 571 744547798 572 748466690 573 752399308 574 756345678 575 760305825 576 764279769 577 768267537 578 772269151 579 776284637 580 780314020 581 784357320 582 788414564 583 792485774 584 796570976 585 800670195 586 804783451 587 808910771 588 813052177 589 817207695 590 821377350 591 825561162 592 829759158 593 833971360 594 838197794 595 842438485 596 846693453 597 850962725 598 855246323 599 859544273 600 863856600 601 868183324 602 872524472 603 876880066 604 881250132 605 885634695 606 890033775 607 894447399 608 898875589 609 903318371 610 907775770 611 912247806 612 916734506 613 921235892 614 925751990 615 930282825 616 934828417 617 939388793 618 943963975 619 948553989 620 953158860 621 957778608 622 962413260 623 967062838 624 971727368 625 976406875 626 981101379 627 985810907 628 990535481 629 995275127 630 1000029870 631 1004799730 632 1009584734 633 1014384904 634 1019200266 635 1024030845 636 1028876661 637 1033737741 638 1038614107 639 1043505785 640 1048412800 641 1053335172 642 1058272928 643 1063226090 644 1068194684 645 1073178735 646 1078178263 647 1083193295 648 1088223853 649 1093269963 650 1098331650 651 1103408934 652 1108501842 653 1113610396 654 1118734622 655 1123874545 656 1129030185 657 1134201569 658 1139388719 659 1144591661 660 1149810420 661 1155045016 662 1160295476 663 1165561822 664 1170844080 665 1176142275 666 1181456427 667 1186786563 668 1192132705 669 1197494879 670 1202873110 671 1208267418 672 1213677830 673 1219104368 674 1224547058 675 1230005925 676 1235480989 677 1240972277 678 1246479811 679 1252003617 680 1257543720 681 1263100140 682 1268672904 683 1274262034 684 1279867556 685 1285489495 686 1291127871 687 1296782711 688 1302454037 689 1308141875 690 1313846250 691 1319567182 692 1325304698 693 1331058820 694 1336829574 695 1342616985 696 1348421073 697 1354241865 698 1360079383 699 1365933653 700 1371804700 701 1377692544 702 1383597212 703 1389518726 704 1395457112 705 1401412395 706 1407384595 707 1413373739 708 1419379849 709 1425402951 710 1431443070 711 1437500226 712 1443574446 713 1449665752 714 1455774170 715 1461899725 716 1468042437 717 1474202333 718 1480379435 719 1486573769 720 1492785360 721 1499014228 722 1505260400 723 1511523898 724 1517804748 725 1524102975 726 1530418599 727 1536751647 728 1543102141 729 1549470107 730 1555855570 731 1562258550 732 1568679074 733 1575117164 734 1581572846 735 1588046145 736 1594537081 737 1601045681 738 1607571967 739 1614115965 740 1620677700 741 1627257192 742 1633854468 743 1640469550 744 1647102464 745 1653753235 746 1660421883 747 1667108435 748 1673812913 749 1680535343 750 1687275750 751 1694034154 752 1700810582 753 1707605056 754 1714417602 755 1721248245 756 1728097005 757 1734963909 758 1741848979 759 1748752241 760 1755673720 761 1762613436 762 1769571416 763 1776547682 764 1783542260 765 1790555175 766 1797586447 767 1804636103 768 1811704165 769 1818790659 770 1825895610 771 1833019038 772 1840160970 773 1847321428 774 1854500438 775 1861698025 776 1868914209 777 1876149017 778 1883402471 779 1890674597 780 1897965420 781 1905274960 782 1912603244 783 1919950294 784 1927316136 785 1934700795 786 1942104291 787 1949526651 788 1956967897 789 1964428055 790 1971907150 791 1979405202 792 1986922238 793 1994458280 794 2002013354 795 2009587485 796 2017180693 797 2024793005 798 2032424443 799 2040075033 800 2047744800 801 2055433764 802 2063141952 803 2070869386 804 2078616092 805 2086382095 806 2094167415 807 2101972079 808 2109796109 809 2117639531 810 2125502370 811 2133384646 812 2141286386 813 2149207612 814 2157148350 815 2165108625 816 2173088457 817 2181087873 818 2189106895 819 2197145549 820 2205203860 821 2213281848 822 2221379540 823 2229496958 824 2237634128 825 2245791075 826 2253967819 827 2262164387 828 2270380801 829 2278617087 830 2286873270 831 2295149370 832 2303445414 833 2311761424 834 2320097426 835 2328453445 836 2336829501 837 2345225621 838 2353641827 839 2362078145 840 2370534600 841 2379011212 842 2387508008 843 2396025010 844 2404562244 845 2413119735 846 2421697503 847 2430295575 848 2438913973 849 2447552723 850 2456211850 851 2464891374 852 2473591322 853 2482311716 854 2491052582 855 2499813945 856 2508595825 857 2517398249 858 2526221239 859 2535064821 860 2543929020 861 2552813856 862 2561719356 863 2570645542 864 2579592440 865 2588560075 866 2597548467 867 2606557643 868 2615587625 869 2624638439 870 2633710110 871 2642802658 872 2651916110 873 2661050488 874 2670205818 875 2679382125 876 2688579429 877 2697797757 878 2707037131 879 2716297577 880 2725579120 881 2734881780 882 2744205584 883 2753550554 884 2762916716 885 2772304095 886 2781712711 887 2791142591 888 2800593757 889 2810066235 890 2819560050 891 2829075222 892 2838611778 893 2848169740 894 2857749134 895 2867349985 896 2876972313 897 2886616145 898 2896281503 899 2905968413 900 2915676900 901 2925406984 902 2935158692 903 2944932046 904 2954727072 905 2964543795 906 2974382235 907 2984242419 908 2994124369 909 3004028111 910 3013953670 911 3023901066 912 3033870326 913 3043861472 914 3053874530 915 3063909525 916 3073966477 917 3084045413 918 3094146355 919 3104269329 920 3114414360 921 3124581468 922 3134770680 923 3144982018 924 3155215508 925 3165471175 926 3175749039 927 3186049127 928 3196371461 929 3206716067 930 3217082970 931 3227472190 932 3237883754 933 3248317684 934 3258774006 935 3269252745 936 3279753921 937 3290277561 938 3300823687 939 3311392325 940 3321983500 941 3332597232 942 3343233548 943 3353892470 944 3364574024 945 3375278235 946 3386005123 947 3396754715 948 3407527033 949 3418322103 950 3429139950 951 3439980594 952 3450844062 953 3461730376 954 3472639562 955 3483571645 956 3494526645 957 3505504589 958 3516505499 959 3527529401 960 3538576320 961 3549646276 962 3560739296 963 3571855402 964 3582994620 965 3594156975 966 3605342487 967 3616551183 968 3627783085 969 3639038219 970 3650316610 971 3661618278 972 3672943250 973 3684291548 974 3695663198 975 3707058225 976 3718476649 977 3729918497 978 3741383791 979 3752872557 980 3764384820 981 3775920600 982 3787479924 983 3799062814 984 3810669296 985 3822299395 986 3833953131 987 3845630531 988 3857331617 989 3869056415 990 3880804950 991 3892577242 992 3904373318 993 3916193200 994 3928036914 995 3939904485 996 3951795933 997 3963711285 998 3975650563 999 3987613793 1000 3999601000