0 1 1 3 2 14 3 46 4 117 5 251 6 478 7 834 8 1361 9 2107 10 3126 11 4478 12 6229 13 8451 14 11222 15 14626 16 18753 17 23699 18 29566 19 36462 20 44501 21 53803 22 64494 23 76706 24 90577 25 106251 26 123878 27 143614 28 165621 29 190067 30 217126 31 246978 32 279809 33 315811 34 355182 35 398126 36 444853 37 495579 38 550526 39 609922 40 674001 41 743003 42 817174 43 896766 44 982037 45 1073251 46 1170678 47 1274594 48 1385281 49 1503027 50 1628126 51 1760878 52 1901589 53 2050571 54 2208142 55 2374626 56 2550353 57 2735659 58 2930886 59 3136382 60 3352501 61 3579603 62 3818054 63 4068226 64 4330497 65 4605251 66 4892878 67 5193774 68 5508341 69 5836987 70 6180126 71 6538178 72 6911569 73 7300731 74 7706102 75 8128126 76 8567253 77 9023939 78 9498646 79 9991842 80 10504001 81 11035603 82 11587134 83 12159086 84 12751957 85 13366251 86 14002478 87 14661154 88 15342801 89 16047947 90 16777126 91 17530878 92 18309749 93 19114291 94 19945062 95 20802626 96 21687553 97 22600419 98 23541806 99 24512302 100 25512501 101 26543003 102 27604414 103 28697346 104 29822417 105 30980251 106 32171478 107 33396734 108 34656661 109 35951907 110 37283126 111 38650978 112 40056129 113 41499251 114 42981022 115 44502126 116 46063253 117 47665099 118 49308366 119 50993762 120 52722001 121 54493803 122 56309894 123 58171006 124 60077877 125 62031251 126 64031878 127 66080514 128 68177921 129 70324867 130 72522126 131 74770478 132 77070709 133 79423611 134 81829982 135 84290626 136 86806353 137 89377979 138 92006326 139 94692222 140 97436501 141 100240003 142 103103574 143 106028066 144 109014337 145 112063251 146 115175678 147 118352494 148 121594581 149 124902827 150 128278126 151 131721378 152 135233489 153 138815371 154 142467942 155 146192126 156 149988853 157 153859059 158 157803686 159 161823682 160 165920001 161 170093603 162 174345454 163 178676526 164 183087797 165 187580251 166 192154878 167 196812674 168 201554641 169 206381787 170 211295126 171 216295678 172 221384469 173 226562531 174 231830902 175 237190626 176 242642753 177 248188339 178 253828446 179 259564142 180 265396501 181 271326603 182 277355534 183 283484386 184 289714257 185 296046251 186 302481478 187 309021054 188 315666101 189 322417747 190 329277126 191 336245378 192 343323649 193 350513091 194 357814862 195 365230126 196 372760053 197 380405819 198 388168606 199 396049602 200 404050001 201 412171003 202 420413814 203 428779646 204 437269717 205 445885251 206 454627478 207 463497634 208 472496961 209 481626707 210 490888126 211 500282478 212 509811029 213 519475051 214 529275822 215 539214626 216 549292753 217 559511499 218 569872166 219 580376062 220 591024501 221 601818803 222 612760294 223 623850306 224 635090177 225 646481251 226 658024878 227 669722414 228 681575221 229 693584667 230 705752126 231 718078978 232 730566609 233 743216411 234 756029782 235 769008126 236 782152853 237 795465379 238 808947126 239 822599522 240 836424001 241 850422003 242 864594974 243 878944366 244 893471637 245 908178251 246 923065678 247 938135394 248 953388881 249 968827627 250 984453126 251 1000266878 252 1016270389 253 1032465171 254 1048852742 255 1065434626 256 1082212353 257 1099187459 258 1116361486 259 1133735982 260 1151312501 261 1169092603 262 1187077854 263 1205269826 264 1223670097 265 1242280251 266 1261101878 267 1280136574 268 1299385941 269 1318851587 270 1338535126 271 1358438178 272 1378562369 273 1398909331 274 1419480702 275 1440278126 276 1461303253 277 1482557739 278 1504043246 279 1525761442 280 1547714001 281 1569902603 282 1592328934 283 1614994686 284 1637901557 285 1661051251 286 1684445478 287 1708085954 288 1731974401 289 1756112547 290 1780502126 291 1805144878 292 1830042549 293 1855196891 294 1880609662 295 1906282626 296 1932217553 297 1958416219 298 1984880406 299 2011611902 300 2038612501 301 2065884003 302 2093428214 303 2121246946 304 2149342017 305 2177715251 306 2206368478 307 2235303534 308 2264522261 309 2294026507 310 2323818126 311 2353898978 312 2384270929 313 2414935851 314 2445895622 315 2477152126 316 2508707253 317 2540562899 318 2572720966 319 2605183362 320 2637952001 321 2671028803 322 2704415694 323 2738114606 324 2772127477 325 2806456251 326 2841102878 327 2876069314 328 2911357521 329 2946969467 330 2982907126 331 3019172478 332 3055767509 333 3092694211 334 3129954582 335 3167550626 336 3205484353 337 3243757779 338 3282372926 339 3321331822 340 3360636501 341 3400289003 342 3440291374 343 3480645666 344 3521353937 345 3562418251 346 3603840678 347 3645623294 348 3687768181 349 3730277427 350 3773153126 351 3816397378 352 3860012289 353 3903999971 354 3948362542 355 3993102126 356 4038220853 357 4083720859 358 4129604286 359 4175873282 360 4222530001 361 4269576603 362 4317015254 363 4364848126 364 4413077397 365 4461705251 366 4510733878 367 4560165474 368 4610002241 369 4660246387 370 4710900126 371 4761965678 372 4813445269 373 4865341131 374 4917655502 375 4970390626 376 5023548753 377 5077132139 378 5131143046 379 5185583742 380 5240456501 381 5295763603 382 5351507334 383 5407689986 384 5464313857 385 5521381251 386 5578894478 387 5636855854 388 5695267701 389 5754132347 390 5813452126 391 5873229378 392 5933466449 393 5994165691 394 6055329462 395 6116960126 396 6179060053 397 6241631619 398 6304677206 399 6368199202 400 6432200001 401 6496682003 402 6561647614 403 6627099246 404 6693039317 405 6759470251 406 6826394478 407 6893814434 408 6961732561 409 7030151307 410 7099073126 411 7168500478 412 7238435829 413 7308881651 414 7379840422 415 7451314626 416 7523306753 417 7595819299 418 7668854766 419 7742415662 420 7816504501 421 7891123803 422 7966276094 423 8041963906 424 8118189777 425 8194956251 426 8272265878 427 8350121214 428 8428524821 429 8507479267 430 8586987126 431 8667050978 432 8747673409 433 8828857011 434 8910604382 435 8992918126 436 9075800853 437 9159255179 438 9243283726 439 9327889122 440 9413074001 441 9498841003 442 9585192774 443 9672131966 444 9759661237 445 9847783251 446 9936500678 447 10025816194 448 10115732481 449 10206252227 450 10297378126 451 10389112878 452 10481459189 453 10574419771 454 10667997342 455 10762194626 456 10857014353 457 10952459259 458 11048532086 459 11145235582 460 11242572501 461 11340545603 462 11439157654 463 11538411426 464 11638309697 465 11738855251 466 11840050878 467 11941899374 468 12044403541 469 12147566187 470 12251390126 471 12355878178 472 12461033169 473 12566857931 474 12673355302 475 12780528126 476 12888379253 477 12996911539 478 13106127846 479 13216031042 480 13326624001 481 13437909603 482 13549890734 483 13662570286 484 13775951157 485 13890036251 486 14004828478 487 14120330754 488 14236546001 489 14353477147 490 14471127126 491 14589498878 492 14708595349 493 14828419491 494 14948974262 495 15070262626 496 15192287553 497 15315052019 498 15438559006 499 15562811502 500 15687812501 501 15813565003 502 15940072014 503 16067336546 504 16195361617 505 16324150251 506 16453705478 507 16584030334 508 16715127861 509 16847001107 510 16979653126 511 17113086978 512 17247305729 513 17382312451 514 17518110222 515 17654702126 516 17792091253 517 17930280699 518 18069273566 519 18209072962 520 18349682001 521 18491103803 522 18633341494 523 18776398206 524 18920277077 525 19064981251 526 19210513878 527 19356878114 528 19504077121 529 19652114067 530 19800992126 531 19950714478 532 20101284309 533 20252704811 534 20404979182 535 20558110626 536 20712102353 537 20866957579 538 21022679526 539 21179271422 540 21336736501 541 21495078003 542 21654299174 543 21814403266 544 21975393537 545 22137273251 546 22300045678 547 22463714094 548 22628281781 549 22793752027 550 22960128126 551 23127413378 552 23295611089 553 23464724571 554 23634757142 555 23805712126 556 23977592853 557 24150402659 558 24324144886 559 24498822882 560 24674440001 561 24850999603 562 25028505054 563 25206959726 564 25386366997 565 25566730251 566 25748052878 567 25930338274 568 26113589841 569 26297810987 570 26483005126 571 26669175678 572 26856326069 573 27044459731 574 27233580102 575 27423690626 576 27614794753 577 27806895939 578 27999997646 579 28194103342 580 28389216501 581 28585340603 582 28782479134 583 28980635586 584 29179813457 585 29380016251 586 29581247478 587 29783510654 588 29986809301 589 30191146947 590 30396527126 591 30602953378 592 30810429249 593 31018958291 594 31228544062 595 31439190126 596 31650900053 597 31863677419 598 32077525806 599 32292448802 600 32508450001 601 32725533003 602 32943701414 603 33162958846 604 33383308917 605 33604755251 606 33827301478 607 34050951234 608 34275708161 609 34501575907 610 34728558126 611 34956658478 612 35185880629 613 35416228251 614 35647705022 615 35880314626 616 36114060753 617 36348947099 618 36584977366 619 36822155262 620 37060484501 621 37299968803 622 37540611894 623 37782417506 624 38025389377 625 38269531251 626 38514846878 627 38761340014 628 39009014421 629 39257873867 630 39507922126 631 39759162978 632 40011600209 633 40265237611 634 40520078982 635 40776128126 636 41033388853 637 41291864979 638 41551560326 639 41812478722 640 42074624001 641 42338000003 642 42602610574 643 42868459566 644 43135550837 645 43403888251 646 43673475678 647 43944316994 648 44216416081 649 44489776827 650 44764403126 651 45040298878 652 45317467989 653 45595914371 654 45875641942 655 46156654626 656 46438956353 657 46722551059 658 47007442686 659 47293635182 660 47581132501 661 47869938603 662 48160057454 663 48451493026 664 48744249297 665 49038330251 666 49333739878 667 49630482174 668 49928561141 669 50227980787 670 50528745126 671 50830858178 672 51134323969 673 51439146531 674 51745329902 675 52052878126 676 52361795253 677 52672085339 678 52983752446 679 53296800642 680 53611234001 681 53927056603 682 54244272534 683 54562885886 684 54882900757 685 55204321251 686 55527151478 687 55851395554 688 56177057601 689 56504141747 690 56832652126 691 57162592878 692 57493968149 693 57826782091 694 58161038862 695 58496742626 696 58833897553 697 59172507819 698 59512577606 699 59854111102 700 60197112501 701 60541586003 702 60887535814 703 61234966146 704 61583881217 705 61934285251 706 62286182478 707 62639577134 708 62994473461 709 63350875707 710 63708788126 711 64068214978 712 64429160529 713 64791629051 714 65155624822 715 65521152126 716 65888215253 717 66256818499 718 66626966166 719 66998662562 720 67371912001 721 67746718803 722 68123087294 723 68501021806 724 68880526677 725 69261606251 726 69644264878 727 70028506914 728 70414336721 729 70801758667 730 71190777126 731 71581396478 732 71973621109 733 72367455411 734 72762903782 735 73159970626 736 73558660353 737 73958977379 738 74360926126 739 74764511022 740 75169736501 741 75576607003 742 75985126974 743 76395300866 744 76807133137 745 77220628251 746 77635790678 747 78052624894 748 78471135381 749 78891326627 750 79313203126 751 79736769378 752 80162029889 753 80588989171 754 81017651742 755 81448022126 756 81880104853 757 82313904459 758 82749425486 759 83186672482 760 83625650001 761 84066362603 762 84508814854 763 84953011326 764 85398956597 765 85846655251 766 86296111878 767 86747331074 768 87200317441 769 87655075587 770 88111610126 771 88569925678 772 89030026869 773 89491918331 774 89955604702 775 90421090626 776 90888380753 777 91357479739 778 91828392246 779 92301122942 780 92775676501 781 93252057603 782 93730270934 783 94210321186 784 94692213057 785 95175951251 786 95661540478 787 96148985454 788 96638290901 789 97129461547 790 97622502126 791 98117417378 792 98614212049 793 99112890891 794 99613458662 795 100115920126 796 100620280053 797 101126543219 798 101634714406 799 102144798402 800 102656800001 801 103170724003 802 103686575214 803 104204358446 804 104724078517 805 105245740251 806 105769348478 807 106294908034 808 106822423761 809 107351900507 810 107883343126 811 108416756478 812 108952145429 813 109489514851 814 110028869622 815 110570214626 816 111113554753 817 111658894899 818 112206239966 819 112755594862 820 113306964501 821 113860353803 822 114415767694 823 114973211106 824 115532688977 825 116094206251 826 116657767878 827 117223378814 828 117791044021 829 118360768467 830 118932557126 831 119506414978 832 120082347009 833 120660358211 834 121240453582 835 121822638126 836 122406916853 837 122993294779 838 123581776926 839 124172368322 840 124765074001 841 125359899003 842 125956848374 843 126555927166 844 127157140437 845 127760493251 846 128365990678 847 128973637794 848 129583439681 849 130195401427 850 130809528126 851 131425824878 852 132044296789 853 132664948971 854 133287786542 855 133912814626 856 134540038353 857 135169462859 858 135801093286 859 136434934782 860 137070992501 861 137709271603 862 138349777254 863 138992514626 864 139637488897 865 140284705251 866 140934168878 867 141585884974 868 142239858741 869 142896095387 870 143554600126 871 144215378178 872 144878434769 873 145543775131 874 146211404502 875 146881328126 876 147553551253 877 148228079139 878 148904917046 879 149584070242 880 150265544001 881 150949343603 882 151635474334 883 152323941486 884 153014750357 885 153707906251 886 154403414478 887 155101280354 888 155801509201 889 156504106347 890 157209077126 891 157916426878 892 158626160949 893 159338284691 894 160052803462 895 160769722626 896 161489047553 897 162210783619 898 162934936206 899 163661510702 900 164390512501 901 165121947003 902 165855819614 903 166592135746 904 167330900817 905 168072120251 906 168815799478 907 169561943934 908 170310559061 909 171061650307 910 171815223126 911 172571282978 912 173329835329 913 174090885651 914 174854439422 915 175620502126 916 176389079253 917 177160176299 918 177933798766 919 178709952162 920 179488642001 921 180269873803 922 181053653094 923 181839985406 924 182628876277 925 183420331251 926 184214355878 927 185010955714 928 185810136321 929 186611903267 930 187416262126 931 188223218478 932 189032777909 933 189844946011 934 190659728382 935 191477130626 936 192297158353 937 193119817179 938 193945112726 939 194773050622 940 195603636501 941 196436876003 942 197272774774 943 198111338466 944 198952572737 945 199796483251 946 200643075678 947 201492355694 948 202344328981 949 203199001227 950 204056378126 951 204916465378 952 205779268689 953 206644793771 954 207513046342 955 208384032126 956 209257756853 957 210134226259 958 211013446086 959 211895422082 960 212780160001 961 213667665603 962 214557944654 963 215451002926 964 216346846197 965 217245480251 966 218146910878 967 219051143874 968 219958185041 969 220868040187 970 221780715126 971 222696215678 972 223614547669 973 224535716931 974 225459729302 975 226386590626 976 227316306753 977 228248883539 978 229184326846 979 230122642542 980 231063836501 981 232007914603 982 232954882734 983 233904746786 984 234857512657 985 235813186251 986 236771773478 987 237733280254 988 238697712501 989 239665076147 990 240635377126 991 241608621378 992 242584814849 993 243563963491 994 244546073262 995 245531150126 996 246519200053 997 247510229019 998 248504243006 999 249501248002 1000 250501250001