0 1 1 34 2 169 3 478 4 1033 5 1906 6 3169 7 4894 8 7153 9 10018 10 13561 11 17854 12 22969 13 28978 14 35953 15 43966 16 53089 17 63394 18 74953 19 87838 20 102121 21 117874 22 135169 23 154078 24 174673 25 197026 26 221209 27 247294 28 275353 29 305458 30 337681 31 372094 32 408769 33 447778 34 489193 35 533086 36 579529 37 628594 38 680353 39 734878 40 792241 41 852514 42 915769 43 982078 44 1051513 45 1124146 46 1200049 47 1279294 48 1361953 49 1448098 50 1537801 51 1631134 52 1728169 53 1828978 54 1933633 55 2042206 56 2154769 57 2271394 58 2392153 59 2517118 60 2646361 61 2779954 62 2917969 63 3060478 64 3207553 65 3359266 66 3515689 67 3676894 68 3842953 69 4013938 70 4189921 71 4370974 72 4557169 73 4748578 74 4945273 75 5147326 76 5354809 77 5567794 78 5786353 79 6010558 80 6240481 81 6476194 82 6717769 83 6965278 84 7218793 85 7478386 86 7744129 87 8016094 88 8294353 89 8578978 90 8870041 91 9167614 92 9471769 93 9782578 94 10100113 95 10424446 96 10755649 97 11093794 98 11438953 99 11791198 100 12150601 101 12517234 102 12891169 103 13272478 104 13661233 105 14057506 106 14461369 107 14872894 108 15292153 109 15719218 110 16154161 111 16597054 112 17047969 113 17506978 114 17974153 115 18449566 116 18933289 117 19425394 118 19925953 119 20435038 120 20952721 121 21479074 122 22014169 123 22558078 124 23110873 125 23672626 126 24243409 127 24823294 128 25412353 129 26010658 130 26618281 131 27235294 132 27861769 133 28497778 134 29143393 135 29798686 136 30463729 137 31138594 138 31823353 139 32518078 140 33222841 141 33937714 142 34662769 143 35398078 144 36143713 145 36899746 146 37666249 147 38443294 148 39230953 149 40029298 150 40838401 151 41658334 152 42489169 153 43330978 154 44183833 155 45047806 156 45922969 157 46809394 158 47707153 159 48616318 160 49536961 161 50469154 162 51412969 163 52368478 164 53335753 165 54314866 166 55305889 167 56308894 168 57323953 169 58351138 170 59390521 171 60442174 172 61506169 173 62582578 174 63671473 175 64772926 176 65887009 177 67013794 178 68153353 179 69305758 180 70471081 181 71649394 182 72840769 183 74045278 184 75262993 185 76493986 186 77738329 187 78996094 188 80267353 189 81552178 190 82850641 191 84162814 192 85488769 193 86828578 194 88182313 195 89550046 196 90931849 197 92327794 198 93737953 199 95162398 200 96601201 201 98054434 202 99522169 203 101004478 204 102501433 205 104013106 206 105539569 207 107080894 208 108637153 209 110208418 210 111794761 211 113396254 212 115012969 213 116644978 214 118292353 215 119955166 216 121633489 217 123327394 218 125036953 219 126762238 220 128503321 221 130260274 222 132033169 223 133822078 224 135627073 225 137448226 226 139285609 227 141139294 228 143009353 229 144895858 230 146798881 231 148718494 232 150654769 233 152607778 234 154577593 235 156564286 236 158567929 237 160588594 238 162626353 239 164681278 240 166753441 241 168842914 242 170949769 243 173074078 244 175215913 245 177375346 246 179552449 247 181747294 248 183959953 249 186190498 250 188439001 251 190705534 252 192990169 253 195292978 254 197614033 255 199953406 256 202311169 257 204687394 258 207082153 259 209495518 260 211927561 261 214378354 262 216847969 263 219336478 264 221843953 265 224370466 266 226916089 267 229480894 268 232064953 269 234668338 270 237291121 271 239933374 272 242595169 273 245276578 274 247977673 275 250698526 276 253439209 277 256199794 278 258980353 279 261780958 280 264601681 281 267442594 282 270303769 283 273185278 284 276087193 285 279009586 286 281952529 287 284916094 288 287900353 289 290905378 290 293931241 291 296978014 292 300045769 293 303134578 294 306244513 295 309375646 296 312528049 297 315701794 298 318896953 299 322113598 300 325351801 301 328611634 302 331893169 303 335196478 304 338521633 305 341868706 306 345237769 307 348628894 308 352042153 309 355477618 310 358935361 311 362415454 312 365917969 313 369442978 314 372990553 315 376560766 316 380153689 317 383769394 318 387407953 319 391069438 320 394753921 321 398461474 322 402192169 323 405946078 324 409723273 325 413523826 326 417347809 327 421195294 328 425066353 329 428961058 330 432879481 331 436821694 332 440787769 333 444777778 334 448791793 335 452829886 336 456892129 337 460978594 338 465089353 339 469224478 340 473384041 341 477568114 342 481776769 343 486010078 344 490268113 345 494550946 346 498858649 347 503191294 348 507548953 349 511931698 350 516339601 351 520772734 352 525231169 353 529714978 354 534224233 355 538759006 356 543319369 357 547905394 358 552517153 359 557154718 360 561818161 361 566507554 362 571222969 363 575964478 364 580732153 365 585526066 366 590346289 367 595192894 368 600065953 369 604965538 370 609891721 371 614844574 372 619824169 373 624830578 374 629863873 375 634924126 376 640011409 377 645125794 378 650267353 379 655436158 380 660632281 381 665855794 382 671106769 383 676385278 384 681691393 385 687025186 386 692386729 387 697776094 388 703193353 389 708638578 390 714111841 391 719613214 392 725142769 393 730700578 394 736286713 395 741901246 396 747544249 397 753215794 398 758915953 399 764644798 400 770402401 401 776188834 402 782004169 403 787848478 404 793721833 405 799624306 406 805555969 407 811516894 408 817507153 409 823526818 410 829575961 411 835654654 412 841762969 413 847900978 414 854068753 415 860266366 416 866493889 417 872751394 418 879038953 419 885356638 420 891704521 421 898082674 422 904491169 423 910930078 424 917399473 425 923899426 426 930430009 427 936991294 428 943583353 429 950206258 430 956860081 431 963544894 432 970260769 433 977007778 434 983785993 435 990595486 436 997436329 437 1004308594 438 1011212353 439 1018147678 440 1025114641 441 1032113314 442 1039143769 443 1046206078 444 1053300313 445 1060426546 446 1067584849 447 1074775294 448 1081997953 449 1089252898 450 1096540201 451 1103859934 452 1111212169 453 1118596978 454 1126014433 455 1133464606 456 1140947569 457 1148463394 458 1156012153 459 1163593918 460 1171208761 461 1178856754 462 1186537969 463 1194252478 464 1202000353 465 1209781666 466 1217596489 467 1225444894 468 1233326953 469 1241242738 470 1249192321 471 1257175774 472 1265193169 473 1273244578 474 1281330073 475 1289449726 476 1297603609 477 1305791794 478 1314014353 479 1322271358 480 1330562881 481 1338888994 482 1347249769 483 1355645278 484 1364075593 485 1372540786 486 1381040929 487 1389576094 488 1398146353 489 1406751778 490 1415392441 491 1424068414 492 1432779769 493 1441526578 494 1450308913 495 1459126846 496 1467980449 497 1476869794 498 1485794953 499 1494755998 500 1503753001 501 1512786034 502 1521855169 503 1530960478 504 1540102033 505 1549279906 506 1558494169 507 1567744894 508 1577032153 509 1586356018 510 1595716561 511 1605113854 512 1614547969 513 1624018978 514 1633526953 515 1643071966 516 1652654089 517 1662273394 518 1671929953 519 1681623838 520 1691355121 521 1701123874 522 1710930169 523 1720774078 524 1730655673 525 1740575026 526 1750532209 527 1760527294 528 1770560353 529 1780631458 530 1790740681 531 1800888094 532 1811073769 533 1821297778 534 1831560193 535 1841861086 536 1852200529 537 1862578594 538 1872995353 539 1883450878 540 1893945241 541 1904478514 542 1915050769 543 1925662078 544 1936312513 545 1947002146 546 1957731049 547 1968499294 548 1979306953 549 1990154098 550 2001040801 551 2011967134 552 2022933169 553 2033938978 554 2044984633 555 2056070206 556 2067195769 557 2078361394 558 2089567153 559 2100813118 560 2112099361 561 2123425954 562 2134792969 563 2146200478 564 2157648553 565 2169137266 566 2180666689 567 2192236894 568 2203847953 569 2215499938 570 2227192921 571 2238926974 572 2250702169 573 2262518578 574 2274376273 575 2286275326 576 2298215809 577 2310197794 578 2322221353 579 2334286558 580 2346393481 581 2358542194 582 2370732769 583 2382965278 584 2395239793 585 2407556386 586 2419915129 587 2432316094 588 2444759353 589 2457244978 590 2469773041 591 2482343614 592 2494956769 593 2507612578 594 2520311113 595 2533052446 596 2545836649 597 2558663794 598 2571533953 599 2584447198 600 2597403601 601 2610403234 602 2623446169 603 2636532478 604 2649662233 605 2662835506 606 2676052369 607 2689312894 608 2702617153 609 2715965218 610 2729357161 611 2742793054 612 2756272969 613 2769796978 614 2783365153 615 2796977566 616 2810634289 617 2824335394 618 2838080953 619 2851871038 620 2865705721 621 2879585074 622 2893509169 623 2907478078 624 2921491873 625 2935550626 626 2949654409 627 2963803294 628 2977997353 629 2992236658 630 3006521281 631 3020851294 632 3035226769 633 3049647778 634 3064114393 635 3078626686 636 3093184729 637 3107788594 638 3122438353 639 3137134078 640 3151875841 641 3166663714 642 3181497769 643 3196378078 644 3211304713 645 3226277746 646 3241297249 647 3256363294 648 3271475953 649 3286635298 650 3301841401 651 3317094334 652 3332394169 653 3347740978 654 3363134833 655 3378575806 656 3394063969 657 3409599394 658 3425182153 659 3440812318 660 3456489961 661 3472215154 662 3487987969 663 3503808478 664 3519676753 665 3535592866 666 3551556889 667 3567568894 668 3583628953 669 3599737138 670 3615893521 671 3632098174 672 3648351169 673 3664652578 674 3681002473 675 3697400926 676 3713848009 677 3730343794 678 3746888353 679 3763481758 680 3780124081 681 3796815394 682 3813555769 683 3830345278 684 3847183993 685 3864071986 686 3881009329 687 3897996094 688 3915032353 689 3932118178 690 3949253641 691 3966438814 692 3983673769 693 4000958578 694 4018293313 695 4035678046 696 4053112849 697 4070597794 698 4088132953 699 4105718398 700 4123354201 701 4141040434 702 4158777169 703 4176564478 704 4194402433 705 4212291106 706 4230230569 707 4248220894 708 4266262153 709 4284354418 710 4302497761 711 4320692254 712 4338937969 713 4357234978 714 4375583353 715 4393983166 716 4412434489 717 4430937394 718 4449491953 719 4468098238 720 4486756321 721 4505466274 722 4524228169 723 4543042078 724 4561908073 725 4580826226 726 4599796609 727 4618819294 728 4637894353 729 4657021858 730 4676201881 731 4695434494 732 4714719769 733 4734057778 734 4753448593 735 4772892286 736 4792388929 737 4811938594 738 4831541353 739 4851197278 740 4870906441 741 4890668914 742 4910484769 743 4930354078 744 4950276913 745 4970253346 746 4990283449 747 5010367294 748 5030504953 749 5050696498 750 5070942001 751 5091241534 752 5111595169 753 5132002978 754 5152465033 755 5172981406 756 5193552169 757 5214177394 758 5234857153 759 5255591518 760 5276380561 761 5297224354 762 5318122969 763 5339076478 764 5360084953 765 5381148466 766 5402267089 767 5423440894 768 5444669953 769 5465954338 770 5487294121 771 5508689374 772 5530140169 773 5551646578 774 5573208673 775 5594826526 776 5616500209 777 5638229794 778 5660015353 779 5681856958 780 5703754681 781 5725708594 782 5747718769 783 5769785278 784 5791908193 785 5814087586 786 5836323529 787 5858616094 788 5880965353 789 5903371378 790 5925834241 791 5948354014 792 5970930769 793 5993564578 794 6016255513 795 6039003646 796 6061809049 797 6084671794 798 6107591953 799 6130569598 800 6153604801 801 6176697634 802 6199848169 803 6223056478 804 6246322633 805 6269646706 806 6293028769 807 6316468894 808 6339967153 809 6363523618 810 6387138361 811 6410811454 812 6434542969 813 6458332978 814 6482181553 815 6506088766 816 6530054689 817 6554079394 818 6578162953 819 6602305438 820 6626506921 821 6650767474 822 6675087169 823 6699466078 824 6723904273 825 6748401826 826 6772958809 827 6797575294 828 6822251353 829 6846987058 830 6871782481 831 6896637694 832 6921552769 833 6946527778 834 6971562793 835 6996657886 836 7021813129 837 7047028594 838 7072304353 839 7097640478 840 7123037041 841 7148494114 842 7174011769 843 7199590078 844 7225229113 845 7250928946 846 7276689649 847 7302511294 848 7328393953 849 7354337698 850 7380342601 851 7406408734 852 7432536169 853 7458724978 854 7484975233 855 7511287006 856 7537660369 857 7564095394 858 7590592153 859 7617150718 860 7643771161 861 7670453554 862 7697197969 863 7724004478 864 7750873153 865 7777804066 866 7804797289 867 7831852894 868 7858970953 869 7886151538 870 7913394721 871 7940700574 872 7968069169 873 7995500578 874 8022994873 875 8050552126 876 8078172409 877 8105855794 878 8133602353 879 8161412158 880 8189285281 881 8217221794 882 8245221769 883 8273285278 884 8301412393 885 8329603186 886 8357857729 887 8386176094 888 8414558353 889 8443004578 890 8471514841 891 8500089214 892 8528727769 893 8557430578 894 8586197713 895 8615029246 896 8643925249 897 8672885794 898 8701910953 899 8731000798 900 8760155401 901 8789374834 902 8818659169 903 8848008478 904 8877422833 905 8906902306 906 8936446969 907 8966056894 908 8995732153 909 9025472818 910 9055278961 911 9085150654 912 9115087969 913 9145090978 914 9175159753 915 9205294366 916 9235494889 917 9265761394 918 9296093953 919 9326492638 920 9356957521 921 9387488674 922 9418086169 923 9448750078 924 9479480473 925 9510277426 926 9541141009 927 9572071294 928 9603068353 929 9634132258 930 9665263081 931 9696460894 932 9727725769 933 9759057778 934 9790456993 935 9821923486 936 9853457329 937 9885058594 938 9916727353 939 9948463678 940 9980267641 941 10012139314 942 10044078769 943 10076086078 944 10108161313 945 10140304546 946 10172515849 947 10204795294 948 10237142953 949 10269558898 950 10302043201 951 10334595934 952 10367217169 953 10399906978 954 10432665433 955 10465492606 956 10498388569 957 10531353394 958 10564387153 959 10597489918 960 10630661761 961 10663902754 962 10697212969 963 10730592478 964 10764041353 965 10797559666 966 10831147489 967 10864804894 968 10898531953 969 10932328738 970 10966195321 971 11000131774 972 11034138169 973 11068214578 974 11102361073 975 11136577726 976 11170864609 977 11205221794 978 11239649353 979 11274147358 980 11308715881 981 11343354994 982 11378064769 983 11412845278 984 11447696593 985 11482618786 986 11517611929 987 11552676094 988 11587811353 989 11623017778 990 11658295441 991 11693644414 992 11729064769 993 11764556578 994 11800119913 995 11835754846 996 11871461449 997 11907239794 998 11943089953 999 11979011998 1000 12015006001