0 0 1 1 2 14 3 53 4 132 5 265 6 466 7 749 8 1128 9 1617 10 2230 11 2981 12 3884 13 4953 14 6202 15 7645 16 9296 17 11169 18 13278 19 15637 20 18260 21 21161 22 24354 23 27853 24 31672 25 35825 26 40326 27 45189 28 50428 29 56057 30 62090 31 68541 32 75424 33 82753 34 90542 35 98805 36 107556 37 116809 38 126578 39 136877 40 147720 41 159121 42 171094 43 183653 44 196812 45 210585 46 224986 47 240029 48 255728 49 272097 50 289150 51 306901 52 325364 53 344553 54 364482 55 385165 56 406616 57 428849 58 451878 59 475717 60 500380 61 525881 62 552234 63 579453 64 607552 65 636545 66 666446 67 697269 68 729028 69 761737 70 795410 71 830061 72 865704 73 902353 74 940022 75 978725 76 1018476 77 1059289 78 1101178 79 1144157 80 1188240 81 1233441 82 1279774 83 1327253 84 1375892 85 1425705 86 1476706 87 1528909 88 1582328 89 1636977 90 1692870 91 1750021 92 1808444 93 1868153 94 1929162 95 1991485 96 2055136 97 2120129 98 2186478 99 2254197 100 2323300 101 2393801 102 2465714 103 2539053 104 2613832 105 2690065 106 2767766 107 2846949 108 2927628 109 3009817 110 3093530 111 3178781 112 3265584 113 3353953 114 3443902 115 3535445 116 3628596 117 3723369 118 3819778 119 3917837 120 4017560 121 4118961 122 4222054 123 4326853 124 4433372 125 4541625 126 4651626 127 4763389 128 4876928 129 4992257 130 5109390 131 5228341 132 5349124 133 5471753 134 5596242 135 5722605 136 5850856 137 5981009 138 6113078 139 6247077 140 6383020 141 6520921 142 6660794 143 6802653 144 6946512 145 7092385 146 7240286 147 7390229 148 7542228 149 7696297 150 7852450 151 8010701 152 8171064 153 8333553 154 8498182 155 8664965 156 8833916 157 9005049 158 9178378 159 9353917 160 9531680 161 9711681 162 9893934 163 10078453 164 10265252 165 10454345 166 10645746 167 10839469 168 11035528 169 11233937 170 11434710 171 11637861 172 11843404 173 12051353 174 12261722 175 12474525 176 12689776 177 12907489 178 13127678 179 13350357 180 13575540 181 13803241 182 14033474 183 14266253 184 14501592 185 14739505 186 14980006 187 15223109 188 15468828 189 15717177 190 15968170 191 16221821 192 16478144 193 16737153 194 16998862 195 17263285 196 17530436 197 17800329 198 18072978 199 18348397 200 18626600 201 18907601 202 19191414 203 19478053 204 19767532 205 20059865 206 20355066 207 20653149 208 20954128 209 21258017 210 21564830 211 21874581 212 22187284 213 22502953 214 22821602 215 23143245 216 23467896 217 23795569 218 24126278 219 24460037 220 24796860 221 25136761 222 25479754 223 25825853 224 26175072 225 26527425 226 26882926 227 27241589 228 27603428 229 27968457 230 28336690 231 28708141 232 29082824 233 29460753 234 29841942 235 30226405 236 30614156 237 31005209 238 31399578 239 31797277 240 32198320 241 32602721 242 33010494 243 33421653 244 33836212 245 34254185 246 34675586 247 35100429 248 35528728 249 35960497 250 36395750 251 36834501 252 37276764 253 37722553 254 38171882 255 38624765 256 39081216 257 39541249 258 40004878 259 40472117 260 40942980 261 41417481 262 41895634 263 42377453 264 42862952 265 43352145 266 43845046 267 44341669 268 44842028 269 45346137 270 45854010 271 46365661 272 46881104 273 47400353 274 47923422 275 48450325 276 48981076 277 49515689 278 50054178 279 50596557 280 51142840 281 51693041 282 52247174 283 52805253 284 53367292 285 53933305 286 54503306 287 55077309 288 55655328 289 56237377 290 56823470 291 57413621 292 58007844 293 58606153 294 59208562 295 59815085 296 60425736 297 61040529 298 61659478 299 62282597 300 62909900 301 63541401 302 64177114 303 64817053 304 65461232 305 66109665 306 66762366 307 67419349 308 68080628 309 68746217 310 69416130 311 70090381 312 70768984 313 71451953 314 72139302 315 72831045 316 73527196 317 74227769 318 74932778 319 75642237 320 76356160 321 77074561 322 77797454 323 78524853 324 79256772 325 79993225 326 80734226 327 81479789 328 82229928 329 82984657 330 83743990 331 84507941 332 85276524 333 86049753 334 86827642 335 87610205 336 88397456 337 89189409 338 89986078 339 90787477 340 91593620 341 92404521 342 93220194 343 94040653 344 94865912 345 95695985 346 96530886 347 97370629 348 98215228 349 99064697 350 99919050 351 100778301 352 101642464 353 102511553 354 103385582 355 104264565 356 105148516 357 106037449 358 106931378 359 107830317 360 108734280 361 109643281 362 110557334 363 111476453 364 112400652 365 113329945 366 114264346 367 115203869 368 116148528 369 117098337 370 118053310 371 119013461 372 119978804 373 120949353 374 121925122 375 122906125 376 123892376 377 124883889 378 125880678 379 126882757 380 127890140 381 128902841 382 129920874 383 130944253 384 131972992 385 133007105 386 134046606 387 135091509 388 136141828 389 137197577 390 138258770 391 139325421 392 140397544 393 141475153 394 142558262 395 143646885 396 144741036 397 145840729 398 146945978 399 148056797 400 149173200 401 150295201 402 151422814 403 152556053 404 153694932 405 154839465 406 155989666 407 157145549 408 158307128 409 159474417 410 160647430 411 161826181 412 163010684 413 164200953 414 165397002 415 166598845 416 167806496 417 169019969 418 170239278 419 171464437 420 172695460 421 173932361 422 175175154 423 176423853 424 177678472 425 178939025 426 180205526 427 181477989 428 182756428 429 184040857 430 185331290 431 186627741 432 187930224 433 189238753 434 190553342 435 191874005 436 193200756 437 194533609 438 195872578 439 197217677 440 198568920 441 199926321 442 201289894 443 202659653 444 204035612 445 205417785 446 206806186 447 208200829 448 209601728 449 211008897 450 212422350 451 213842101 452 215268164 453 216700553 454 218139282 455 219584365 456 221035816 457 222493649 458 223957878 459 225428517 460 226905580 461 228389081 462 229879034 463 231375453 464 232878352 465 234387745 466 235903646 467 237426069 468 238955028 469 240490537 470 242032610 471 243581261 472 245136504 473 246698353 474 248266822 475 249841925 476 251423676 477 253012089 478 254607178 479 256208957 480 257817440 481 259432641 482 261054574 483 262683253 484 264318692 485 265960905 486 267609906 487 269265709 488 270928328 489 272597777 490 274274070 491 275957221 492 277647244 493 279344153 494 281047962 495 282758685 496 284476336 497 286200929 498 287932478 499 289670997 500 291416500 501 293169001 502 294928514 503 296695053 504 298468632 505 300249265 506 302036966 507 303831749 508 305633628 509 307442617 510 309258730 511 311081981 512 312912384 513 314749953 514 316594702 515 318446645 516 320305796 517 322172169 518 324045778 519 325926637 520 327814760 521 329710161 522 331612854 523 333522853 524 335440172 525 337364825 526 339296826 527 341236189 528 343182928 529 345137057 530 347098590 531 349067541 532 351043924 533 353027753 534 355019042 535 357017805 536 359024056 537 361037809 538 363059078 539 365087877 540 367124220 541 369168121 542 371219594 543 373278653 544 375345312 545 377419585 546 379501486 547 381591029 548 383688228 549 385793097 550 387905650 551 390025901 552 392153864 553 394289553 554 396432982 555 398584165 556 400743116 557 402909849 558 405084378 559 407266717 560 409456880 561 411654881 562 413860734 563 416074453 564 418296052 565 420525545 566 422762946 567 425008269 568 427261528 569 429522737 570 431791910 571 434069061 572 436354204 573 438647353 574 440948522 575 443257725 576 445574976 577 447900289 578 450233678 579 452575157 580 454924740 581 457282441 582 459648274 583 462022253 584 464404392 585 466794705 586 469193206 587 471599909 588 474014828 589 476437977 590 478869370 591 481309021 592 483756944 593 486213153 594 488677662 595 491150485 596 493631636 597 496121129 598 498618978 599 501125197 600 503639800 601 506162801 602 508694214 603 511234053 604 513782332 605 516339065 606 518904266 607 521477949 608 524060128 609 526650817 610 529250030 611 531857781 612 534474084 613 537098953 614 539732402 615 542374445 616 545025096 617 547684369 618 550352278 619 553028837 620 555714060 621 558407961 622 561110554 623 563821853 624 566541872 625 569270625 626 572008126 627 574754389 628 577509428 629 580273257 630 583045890 631 585827341 632 588617624 633 591416753 634 594224742 635 597041605 636 599867356 637 602702009 638 605545578 639 608398077 640 611259520 641 614129921 642 617009294 643 619897653 644 622795012 645 625701385 646 628616786 647 631541229 648 634474728 649 637417297 650 640368950 651 643329701 652 646299564 653 649278553 654 652266682 655 655263965 656 658270416 657 661286049 658 664310878 659 667344917 660 670388180 661 673440681 662 676502434 663 679573453 664 682653752 665 685743345 666 688842246 667 691950469 668 695068028 669 698194937 670 701331210 671 704476861 672 707631904 673 710796353 674 713970222 675 717153525 676 720346276 677 723548489 678 726760178 679 729981357 680 733212040 681 736452241 682 739701974 683 742961253 684 746230092 685 749508505 686 752796506 687 756094109 688 759401328 689 762718177 690 766044670 691 769380821 692 772726644 693 776082153 694 779447362 695 782822285 696 786206936 697 789601329 698 793005478 699 796419397 700 799843100 701 803276601 702 806719914 703 810173053 704 813636032 705 817108865 706 820591566 707 824084149 708 827586628 709 831099017 710 834621330 711 838153581 712 841695784 713 845247953 714 848810102 715 852382245 716 855964396 717 859556569 718 863158778 719 866771037 720 870393360 721 874025761 722 877668254 723 881320853 724 884983572 725 888656425 726 892339426 727 896032589 728 899735928 729 903449457 730 907173190 731 910907141 732 914651324 733 918405753 734 922170442 735 925945405 736 929730656 737 933526209 738 937332078 739 941148277 740 944974820 741 948811721 742 952658994 743 956516653 744 960384712 745 964263185 746 968152086 747 972051429 748 975961228 749 979881497 750 983812250 751 987753501 752 991705264 753 995667553 754 999640382 755 1003623765 756 1007617716 757 1011622249 758 1015637378 759 1019663117 760 1023699480 761 1027746481 762 1031804134 763 1035872453 764 1039951452 765 1044041145 766 1048141546 767 1052252669 768 1056374528 769 1060507137 770 1064650510 771 1068804661 772 1072969604 773 1077145353 774 1081331922 775 1085529325 776 1089737576 777 1093956689 778 1098186678 779 1102427557 780 1106679340 781 1110942041 782 1115215674 783 1119500253 784 1123795792 785 1128102305 786 1132419806 787 1136748309 788 1141087828 789 1145438377 790 1149799970 791 1154172621 792 1158556344 793 1162951153 794 1167357062 795 1171774085 796 1176202236 797 1180641529 798 1185091978 799 1189553597 800 1194026400 801 1198510401 802 1203005614 803 1207512053 804 1212029732 805 1216558665 806 1221098866 807 1225650349 808 1230213128 809 1234787217 810 1239372630 811 1243969381 812 1248577484 813 1253196953 814 1257827802 815 1262470045 816 1267123696 817 1271788769 818 1276465278 819 1281153237 820 1285852660 821 1290563561 822 1295285954 823 1300019853 824 1304765272 825 1309522225 826 1314290726 827 1319070789 828 1323862428 829 1328665657 830 1333480490 831 1338306941 832 1343145024 833 1347994753 834 1352856142 835 1357729205 836 1362613956 837 1367510409 838 1372418578 839 1377338477 840 1382270120 841 1387213521 842 1392168694 843 1397135653 844 1402114412 845 1407104985 846 1412107386 847 1417121629 848 1422147728 849 1427185697 850 1432235550 851 1437297301 852 1442370964 853 1447456553 854 1452554082 855 1457663565 856 1462785016 857 1467918449 858 1473063878 859 1478221317 860 1483390780 861 1488572281 862 1493765834 863 1498971453 864 1504189152 865 1509418945 866 1514660846 867 1519914869 868 1525181028 869 1530459337 870 1535749810 871 1541052461 872 1546367304 873 1551694353 874 1557033622 875 1562385125 876 1567748876 877 1573124889 878 1578513178 879 1583913757 880 1589326640 881 1594751841 882 1600189374 883 1605639253 884 1611101492 885 1616576105 886 1622063106 887 1627562509 888 1633074328 889 1638598577 890 1644135270 891 1649684421 892 1655246044 893 1660820153 894 1666406762 895 1672005885 896 1677617536 897 1683241729 898 1688878478 899 1694527797 900 1700189700 901 1705864201 902 1711551314 903 1717251053 904 1722963432 905 1728688465 906 1734426166 907 1740176549 908 1745939628 909 1751715417 910 1757503930 911 1763305181 912 1769119184 913 1774945953 914 1780785502 915 1786637845 916 1792502996 917 1798380969 918 1804271778 919 1810175437 920 1816091960 921 1822021361 922 1827963654 923 1833918853 924 1839886972 925 1845868025 926 1851862026 927 1857868989 928 1863888928 929 1869921857 930 1875967790 931 1882026741 932 1888098724 933 1894183753 934 1900281842 935 1906393005 936 1912517256 937 1918654609 938 1924805078 939 1930968677 940 1937145420 941 1943335321 942 1949538394 943 1955754653 944 1961984112 945 1968226785 946 1974482686 947 1980751829 948 1987034228 949 1993329897 950 1999638850 951 2005961101 952 2012296664 953 2018645553 954 2025007782 955 2031383365 956 2037772316 957 2044174649 958 2050590378 959 2057019517 960 2063462080 961 2069918081 962 2076387534 963 2082870453 964 2089366852 965 2095876745 966 2102400146 967 2108937069 968 2115487528 969 2122051537 970 2128629110 971 2135220261 972 2141825004 973 2148443353 974 2155075322 975 2161720925 976 2168380176 977 2175053089 978 2181739678 979 2188439957 980 2195153940 981 2201881641 982 2208623074 983 2215378253 984 2222147192 985 2228929905 986 2235726406 987 2242536709 988 2249360828 989 2256198777 990 2263050570 991 2269916221 992 2276795744 993 2283689153 994 2290596462 995 2297517685 996 2304452836 997 2311401929 998 2318364978 999 2325341997 1000 2332333000