0 1 1 7 2 28 3 84 4 195 5 381 6 662 7 1058 8 1589 9 2275 10 3136 11 4192 12 5463 13 6969 14 8730 15 10766 16 13097 17 15743 18 18724 19 22060 20 25771 21 29877 22 34398 23 39354 24 44765 25 50651 26 57032 27 63928 28 71359 29 79345 30 87906 31 97062 32 106833 33 117239 34 128300 35 140036 36 152467 37 165613 38 179494 39 194130 40 209541 41 225747 42 242768 43 260624 44 279335 45 298921 46 319402 47 340798 48 363129 49 386415 50 410676 51 435932 52 462203 53 489509 54 517870 55 547306 56 577837 57 609483 58 642264 59 676200 60 711311 61 747617 62 785138 63 823894 64 863905 65 905191 66 947772 67 991668 68 1036899 69 1083485 70 1131446 71 1180802 72 1231573 73 1283779 74 1337440 75 1392576 76 1449207 77 1507353 78 1567034 79 1628270 80 1691081 81 1755487 82 1821508 83 1889164 84 1958475 85 2029461 86 2102142 87 2176538 88 2252669 89 2330555 90 2410216 91 2491672 92 2574943 93 2660049 94 2747010 95 2835846 96 2926577 97 3019223 98 3113804 99 3210340 100 3308851 101 3409357 102 3511878 103 3616434 104 3723045 105 3831731 106 3942512 107 4055408 108 4170439 109 4287625 110 4406986 111 4528542 112 4652313 113 4778319 114 4906580 115 5037116 116 5169947 117 5305093 118 5442574 119 5582410 120 5724621 121 5869227 122 6016248 123 6165704 124 6317615 125 6472001 126 6628882 127 6788278 128 6950209 129 7114695 130 7281756 131 7451412 132 7623683 133 7798589 134 7976150 135 8156386 136 8339317 137 8524963 138 8713344 139 8904480 140 9098391 141 9295097 142 9494618 143 9696974 144 9902185 145 10110271 146 10321252 147 10535148 148 10751979 149 10971765 150 11194526 151 11420282 152 11649053 153 11880859 154 12115720 155 12353656 156 12594687 157 12838833 158 13086114 159 13336550 160 13590161 161 13846967 162 14106988 163 14370244 164 14636755 165 14906541 166 15179622 167 15456018 168 15735749 169 16018835 170 16305296 171 16595152 172 16888423 173 17185129 174 17485290 175 17788926 176 18096057 177 18406703 178 18720884 179 19038620 180 19359931 181 19684837 182 20013358 183 20345514 184 20681325 185 21020811 186 21363992 187 21710888 188 22061519 189 22415905 190 22774066 191 23136022 192 23501793 193 23871399 194 24244860 195 24622196 196 25003427 197 25388573 198 25777654 199 26170690 200 26567701 201 26968707 202 27373728 203 27782784 204 28195895 205 28613081 206 29034362 207 29459758 208 29889289 209 30322975 210 30760836 211 31202892 212 31649163 213 32099669 214 32554430 215 33013466 216 33476797 217 33944443 218 34416424 219 34892760 220 35373471 221 35858577 222 36348098 223 36842054 224 37340465 225 37843351 226 38350732 227 38862628 228 39379059 229 39900045 230 40425606 231 40955762 232 41490533 233 42029939 234 42574000 235 43122736 236 43676167 237 44234313 238 44797194 239 45364830 240 45937241 241 46514447 242 47096468 243 47683324 244 48275035 245 48871621 246 49473102 247 50079498 248 50690829 249 51307115 250 51928376 251 52554632 252 53185903 253 53822209 254 54463570 255 55110006 256 55761537 257 56418183 258 57079964 259 57746900 260 58419011 261 59096317 262 59778838 263 60466594 264 61159605 265 61857891 266 62561472 267 63270368 268 63984599 269 64704185 270 65429146 271 66159502 272 66895273 273 67636479 274 68383140 275 69135276 276 69892907 277 70656053 278 71424734 279 72198970 280 72978781 281 73764187 282 74555208 283 75351864 284 76154175 285 76962161 286 77775842 287 78595238 288 79420369 289 80251255 290 81087916 291 81930372 292 82778643 293 83632749 294 84492710 295 85358546 296 86230277 297 87107923 298 87991504 299 88881040 300 89776551 301 90678057 302 91585578 303 92499134 304 93418745 305 94344431 306 95276212 307 96214108 308 97158139 309 98108325 310 99064686 311 100027242 312 100996013 313 101971019 314 102952280 315 103939816 316 104933647 317 105933793 318 106940274 319 107953110 320 108972321 321 109997927 322 111029948 323 112068404 324 113113315 325 114164701 326 115222582 327 116286978 328 117357909 329 118435395 330 119519456 331 120610112 332 121707383 333 122811289 334 123921850 335 125039086 336 126163017 337 127293663 338 128431044 339 129575180 340 130726091 341 131883797 342 133048318 343 134219674 344 135397885 345 136582971 346 137774952 347 138973848 348 140179679 349 141392465 350 142612226 351 143838982 352 145072753 353 146313559 354 147561420 355 148816356 356 150078387 357 151347533 358 152623814 359 153907250 360 155197861 361 156495667 362 157800688 363 159112944 364 160432455 365 161759241 366 163093322 367 164434718 368 165783449 369 167139535 370 168502996 371 169873852 372 171252123 373 172637829 374 174030990 375 175431626 376 176839757 377 178255403 378 179678584 379 181109320 380 182547631 381 183993537 382 185447058 383 186908214 384 188377025 385 189853511 386 191337692 387 192829588 388 194329219 389 195836605 390 197351766 391 198874722 392 200405493 393 201944099 394 203490560 395 205044896 396 206607127 397 208177273 398 209755354 399 211341390 400 212935401 401 214537407 402 216147428 403 217765484 404 219391595 405 221025781 406 222668062 407 224318458 408 225976989 409 227643675 410 229318536 411 231001592 412 232692863 413 234392369 414 236100130 415 237816166 416 239540497 417 241273143 418 243014124 419 244763460 420 246521171 421 248287277 422 250061798 423 251844754 424 253636165 425 255436051 426 257244432 427 259061328 428 260886759 429 262720745 430 264563306 431 266414462 432 268274233 433 270142639 434 272019700 435 273905436 436 275799867 437 277703013 438 279614894 439 281535530 440 283464941 441 285403147 442 287350168 443 289306024 444 291270735 445 293244321 446 295226802 447 297218198 448 299218529 449 301227815 450 303246076 451 305273332 452 307309603 453 309354909 454 311409270 455 313472706 456 315545237 457 317626883 458 319717664 459 321817600 460 323926711 461 326045017 462 328172538 463 330309294 464 332455305 465 334610591 466 336775172 467 338949068 468 341132299 469 343324885 470 345526846 471 347738202 472 349958973 473 352189179 474 354428840 475 356677976 476 358936607 477 361204753 478 363482434 479 365769670 480 368066481 481 370372887 482 372688908 483 375014564 484 377349875 485 379694861 486 382049542 487 384413938 488 386788069 489 389171955 490 391565616 491 393969072 492 396382343 493 398805449 494 401238410 495 403681246 496 406133977 497 408596623 498 411069204 499 413551740 500 416044251 501 418546757 502 421059278 503 423581834 504 426114445 505 428657131 506 431209912 507 433772808 508 436345839 509 438929025 510 441522386 511 444125942 512 446739713 513 449363719 514 451997980 515 454642516 516 457297347 517 459962493 518 462637974 519 465323810 520 468020021 521 470726627 522 473443648 523 476171104 524 478909015 525 481657401 526 484416282 527 487185678 528 489965609 529 492756095 530 495557156 531 498368812 532 501191083 533 504023989 534 506867550 535 509721786 536 512586717 537 515462363 538 518348744 539 521245880 540 524153791 541 527072497 542 530002018 543 532942374 544 535893585 545 538855671 546 541828652 547 544812548 548 547807379 549 550813165 550 553829926 551 556857682 552 559896453 553 562946259 554 566007120 555 569079056 556 572162087 557 575256233 558 578361514 559 581477950 560 584605561 561 587744367 562 590894388 563 594055644 564 597228155 565 600411941 566 603607022 567 606813418 568 610031149 569 613260235 570 616500696 571 619752552 572 623015823 573 626290529 574 629576690 575 632874326 576 636183457 577 639504103 578 642836284 579 646180020 580 649535331 581 652902237 582 656280758 583 659670914 584 663072725 585 666486211 586 669911392 587 673348288 588 676796919 589 680257305 590 683729466 591 687213422 592 690709193 593 694216799 594 697736260 595 701267596 596 704810827 597 708365973 598 711933054 599 715512090 600 719103101 601 722706107 602 726321128 603 729948184 604 733587295 605 737238481 606 740901762 607 744577158 608 748264689 609 751964375 610 755676236 611 759400292 612 763136563 613 766885069 614 770645830 615 774418866 616 778204197 617 782001843 618 785811824 619 789634160 620 793468871 621 797315977 622 801175498 623 805047454 624 808931865 625 812828751 626 816738132 627 820660028 628 824594459 629 828541445 630 832501006 631 836473162 632 840457933 633 844455339 634 848465400 635 852488136 636 856523567 637 860571713 638 864632594 639 868706230 640 872792641 641 876891847 642 881003868 643 885128724 644 889266435 645 893417021 646 897580502 647 901756898 648 905946229 649 910148515 650 914363776 651 918592032 652 922833303 653 927087609 654 931354970 655 935635406 656 939928937 657 944235583 658 948555364 659 952888300 660 957234411 661 961593717 662 965966238 663 970351994 664 974751005 665 979163291 666 983588872 667 988027768 668 992479999 669 996945585 670 1001424546 671 1005916902 672 1010422673 673 1014941879 674 1019474540 675 1024020676 676 1028580307 677 1033153453 678 1037740134 679 1042340370 680 1046954181 681 1051581587 682 1056222608 683 1060877264 684 1065545575 685 1070227561 686 1074923242 687 1079632638 688 1084355769 689 1089092655 690 1093843316 691 1098607772 692 1103386043 693 1108178149 694 1112984110 695 1117803946 696 1122637677 697 1127485323 698 1132346904 699 1137222440 700 1142111951 701 1147015457 702 1151932978 703 1156864534 704 1161810145 705 1166769831 706 1171743612 707 1176731508 708 1181733539 709 1186749725 710 1191780086 711 1196824642 712 1201883413 713 1206956419 714 1212043680 715 1217145216 716 1222261047 717 1227391193 718 1232535674 719 1237694510 720 1242867721 721 1248055327 722 1253257348 723 1258473804 724 1263704715 725 1268950101 726 1274209982 727 1279484378 728 1284773309 729 1290076795 730 1295394856 731 1300727512 732 1306074783 733 1311436689 734 1316813250 735 1322204486 736 1327610417 737 1333031063 738 1338466444 739 1343916580 740 1349381491 741 1354861197 742 1360355718 743 1365865074 744 1371389285 745 1376928371 746 1382482352 747 1388051248 748 1393635079 749 1399233865 750 1404847626 751 1410476382 752 1416120153 753 1421778959 754 1427452820 755 1433141756 756 1438845787 757 1444564933 758 1450299214 759 1456048650 760 1461813261 761 1467593067 762 1473388088 763 1479198344 764 1485023855 765 1490864641 766 1496720722 767 1502592118 768 1508478849 769 1514380935 770 1520298396 771 1526231252 772 1532179523 773 1538143229 774 1544122390 775 1550117026 776 1556127157 777 1562152803 778 1568193984 779 1574250720 780 1580323031 781 1586410937 782 1592514458 783 1598633614 784 1604768425 785 1610918911 786 1617085092 787 1623266988 788 1629464619 789 1635678005 790 1641907166 791 1648152122 792 1654412893 793 1660689499 794 1666981960 795 1673290296 796 1679614527 797 1685954673 798 1692310754 799 1698682790 800 1705070801 801 1711474807 802 1717894828 803 1724330884 804 1730782995 805 1737251181 806 1743735462 807 1750235858 808 1756752389 809 1763285075 810 1769833936 811 1776398992 812 1782980263 813 1789577769 814 1796191530 815 1802821566 816 1809467897 817 1816130543 818 1822809524 819 1829504860 820 1836216571 821 1842944677 822 1849689198 823 1856450154 824 1863227565 825 1870021451 826 1876831832 827 1883658728 828 1890502159 829 1897362145 830 1904238706 831 1911131862 832 1918041633 833 1924968039 834 1931911100 835 1938870836 836 1945847267 837 1952840413 838 1959850294 839 1966876930 840 1973920341 841 1980980547 842 1988057568 843 1995151424 844 2002262135 845 2009389721 846 2016534202 847 2023695598 848 2030873929 849 2038069215 850 2045281476 851 2052510732 852 2059757003 853 2067020309 854 2074300670 855 2081598106 856 2088912637 857 2096244283 858 2103593064 859 2110959000 860 2118342111 861 2125742417 862 2133159938 863 2140594694 864 2148046705 865 2155515991 866 2163002572 867 2170506468 868 2178027699 869 2185566285 870 2193122246 871 2200695602 872 2208286373 873 2215894579 874 2223520240 875 2231163376 876 2238824007 877 2246502153 878 2254197834 879 2261911070 880 2269641881 881 2277390287 882 2285156308 883 2292939964 884 2300741275 885 2308560261 886 2316396942 887 2324251338 888 2332123469 889 2340013355 890 2347921016 891 2355846472 892 2363789743 893 2371750849 894 2379729810 895 2387726646 896 2395741377 897 2403774023 898 2411824604 899 2419893140 900 2427979651 901 2436084157 902 2444206678 903 2452347234 904 2460505845 905 2468682531 906 2476877312 907 2485090208 908 2493321239 909 2501570425 910 2509837786 911 2518123342 912 2526427113 913 2534749119 914 2543089380 915 2551447916 916 2559824747 917 2568219893 918 2576633374 919 2585065210 920 2593515421 921 2601984027 922 2610471048 923 2618976504 924 2627500415 925 2636042801 926 2644603682 927 2653183078 928 2661781009 929 2670397495 930 2679032556 931 2687686212 932 2696358483 933 2705049389 934 2713758950 935 2722487186 936 2731234117 937 2739999763 938 2748784144 939 2757587280 940 2766409191 941 2775249897 942 2784109418 943 2792987774 944 2801884985 945 2810801071 946 2819736052 947 2828689948 948 2837662779 949 2846654565 950 2855665326 951 2864695082 952 2873743853 953 2882811659 954 2891898520 955 2901004456 956 2910129487 957 2919273633 958 2928436914 959 2937619350 960 2946820961 961 2956041767 962 2965281788 963 2974541044 964 2983819555 965 2993117341 966 3002434422 967 3011770818 968 3021126549 969 3030501635 970 3039896096 971 3049309952 972 3058743223 973 3068195929 974 3077668090 975 3087159726 976 3096670857 977 3106201503 978 3115751684 979 3125321420 980 3134910731 981 3144519637 982 3154148158 983 3163796314 984 3173464125 985 3183151611 986 3192858792 987 3202585688 988 3212332319 989 3222098705 990 3231884866 991 3241690822 992 3251516593 993 3261362199 994 3271227660 995 3281112996 996 3291018227 997 3300943373 998 3310888454 999 3320853490 1000 3330838501