0 1 1 1 2 3 3 5 4 9 5 13 6 22 7 30 8 45 9 61 10 85 11 111 12 150 13 190 14 247 15 309 16 390 17 478 18 593 19 715 20 870 21 1038 22 1243 23 1465 24 1735 25 2023 26 2368 27 2740 28 3175 29 3643 30 4189 31 4771 32 5443 33 6163 34 6982 35 7858 36 8852 37 9908 38 11098 39 12366 40 13780 41 15284 42 16958 43 18730 44 20692 45 22772 46 25058 47 27478 48 30133 49 32933 50 35993 51 39223 52 42733 53 46433 54 50448 55 54668 56 59233 57 64033 58 69203 59 74633 60 80474 61 86594 62 93161 63 100043 64 107402 65 115106 66 123335 67 131933 68 141098 69 150674 70 160853 71 171479 72 182763 73 194523 74 206990 75 219982 76 233723 77 248031 78 263151 79 278873 80 295463 81 312711 82 330876 83 349748 84 369608 85 390216 86 411876 87 434348 88 457928 89 482376 90 508012 91 534564 92 562376 93 591176 94 621300 95 652476 96 685065 97 718761 98 753951 99 790329 100 828273 101 867477 102 908346 103 950538 104 994485 105 1039845 106 1087041 107 1135731 108 1186366 109 1238566 110 1292811 111 1348721 112 1406766 113 1466566 114 1528621 115 1592511 116 1658766 117 1726966 118 1797631 119 1870341 120 1945647 121 2023087 122 2103244 123 2185656 124 2270895 125 2358499 126 2449073 127 2542111 128 2638251 129 2736987 130 2838946 131 2943622 132 3051676 133 3162556 134 3276958 135 3394330 136 3515356 137 3639484 138 3767434 139 3898606 140 4033756 141 4172284 142 4314934 143 4461106 144 4611581 145 4765709 146 4924309 147 5086731 148 5253781 149 5424809 150 5600660 151 5780632 152 5965609 153 6154889 154 6349343 155 6548269 156 6752578 157 6961514 158 7176029 159 7395367 160 7620466 161 7850570 162 8086659 163 8327921 164 8575378 165 8828218 166 9087449 167 9352259 168 9623699 169 9900899 170 10184954 171 10474994 172 10772099 173 11075399 174 11386019 175 11703029 176 12027599 177 12358799 178 12697784 179 13043624 180 13397520 181 13758480 182 14127752 183 14504344 184 14889488 185 15282192 186 15683736 187 16093064 188 16511504 189 16938000 190 17373864 191 17818040 192 18271889 193 18734289 194 19206651 195 19687853 196 20179289 197 20679837 198 21190942 199 21711414 200 22242749 201 22783757 202 23335917 203 23898039 204 24471654 205 25055502 206 25651167 207 26257389 208 26875734 209 27504942 210 28146633 211 28799475 212 29465142 213 30142302 214 30832611 215 31534737 216 32250391 217 32978167 218 33719832 219 34473980 220 35242359 221 36023563 222 36819397 223 37628379 224 38452371 225 39289891 226 40142782 227 41009562 228 41892132 229 42788932 230 43701922 231 44629542 232 45573732 233 46532932 234 47509142 235 48500722 236 49509732 237 50534532 238 51577162 239 52635982 240 53713093 241 54806773 242 55919185 243 57048607 244 58197181 245 59363185 246 60548824 247 61752292 248 62975857 249 64217713 250 65480107 251 66761233 252 68063402 253 69384722 254 70727569 255 72090051 256 73474522 257 74879090 258 76306175 259 77753797 260 79224442 261 80716130 262 82231325 263 83768047 264 85328827 265 86911595 266 88518950 267 90148822 268 91803787 269 93481775 270 95185431 271 96912593 272 98665975 273 100443415 274 102247604 275 104076380 276 105932504 277 107813720 278 109722860 279 111657668 280 113620952 281 115610456 282 117629060 283 119674412 284 121749464 285 123851864 286 125984540 287 128145140 288 130336665 289 132556665 290 134808215 291 137088865 292 139401665 293 141744165 294 144119490 295 146525090 296 148964165 297 151434165 298 153938265 299 156473915 300 159044366 301 161646966 302 164285043 303 166955945 304 169662974 305 172403478 306 175180837 307 177992295 308 180841310 309 183725126 310 186647175 311 189604701 312 192601215 313 195633855 314 198706212 315 201815424 316 204965055 317 208152243 318 211380633 319 214647255 320 217955835 321 221303403 322 224693658 323 228123630 324 231597100 325 235110988 326 238669158 327 242268530 328 245912940 329 249599308 330 253331554 331 257106486 332 260928108 333 264793228 334 268705822 335 272662698 336 276667917 337 280718173 338 284817613 339 288962931 340 293158245 341 297400249 342 301693148 343 306033520 344 310425657 345 314866137 346 319359223 347 323901493 348 328497298 349 333143098 350 337843333 351 342594463 352 347400898 353 352259098 354 357173563 355 362140633 356 367164898 357 372242698 358 377378593 359 382568923 360 387818339 361 393123059 362 398487826 363 403908858 364 409390867 365 414930071 366 420531275 367 426190573 368 431912863 369 437694239 370 443539568 371 449444944 372 455415328 373 461446688 374 467544080 375 473703472 376 479929888 377 486219296 378 492576816 379 498998288 380 505488928 381 512044576 382 518670416 383 525362288 384 532125473 385 538955681 386 545858291 387 552829013 388 559873193 389 566986541 390 574174502 391 581432654 392 588766541 393 596171741 394 603653765 395 611208191 396 618840630 397 626546526 398 634331591 399 642191269 400 650131238 401 658146942 402 666244161 403 674418203 404 682674950 405 691009710 406 699428331 407 707926121 408 716509031 409 725172231 410 733921776 411 742752836 412 751671431 413 760672731 414 769762861 415 778936851 416 788200931 417 797550131 418 806990646 419 816517506 420 826137012 421 835844052 422 845645034 423 855534846 424 865519860 425 875594964 426 885766638 427 896029626 428 906390516 429 916844052 430 927396786 431 938043462 432 948790741 433 959633221 434 970577673 435 981618695 436 992763021 437 1004005249 438 1015352224 439 1026798396 440 1038350721 441 1050003649 442 1061764099 443 1073626521 444 1085597946 445 1097672674 446 1109857849 447 1122147771 448 1134549546 449 1147057474 450 1159678775 451 1172407597 452 1185251274 453 1198203954 454 1211272933 455 1224452359 456 1237749643 457 1251158779 458 1264687294 459 1278329182 460 1292091931 461 1305969535 462 1319969599 463 1334085961 464 1348326343 465 1362684583 466 1377168364 467 1391771524 468 1406501864 469 1421353064 470 1436333044 471 1451435484 472 1466668264 473 1482025064 474 1497513884 475 1513128244 476 1528876264 477 1544751464 478 1560761924 479 1576901164 480 1593177385 481 1609583945 482 1626129167 483 1642806409 484 1659623953 485 1676575157 486 1693668426 487 1710896954 488 1728269269 489 1745778565 490 1763433329 491 1781226755 492 1799167454 493 1817248454 494 1835478491 495 1853850593 496 1872373454 497 1891040102 498 1909859357 499 1928824079 500 1947943214 501 1967209622 502 1986632207 503 2006203829 504 2025933519 505 2045813967 506 2065854332 507 2086047304 508 2106401999 509 2126911107 510 2147583873 511 2168412815 512 2189407307 513 2210559867 514 2231879826 515 2253359702 516 2275008956 517 2296819932 518 2318802222 519 2340948170 520 2363267324 521 2385752028 522 2408411962 523 2431239294 524 2454243836 525 2477417756 526 2500770822 527 2524295202 528 2548000797 529 2571879597 530 2595941637 531 2620178907 532 2644601397 533 2669201097 534 2693988132 535 2718954312 536 2744109897 537 2769446697 538 2794974927 539 2820686397 540 2846591458 541 2872681738 542 2898967725 543 2925441047 544 2952112146 545 2978972650 546 3006033139 547 3033285057 548 3060739122 549 3088386778 550 3116238697 551 3144286323 552 3172540467 553 3200992387 554 3229653034 555 3258513666 556 3287585187 557 3316858855 558 3346345715 559 3376036837 560 3405943407 561 3436056495 562 3466387240 563 3496926712 564 3527686192 565 3558656560 566 3589849240 567 3621255112 568 3652885552 569 3684731440 570 3716804296 571 3749094808 572 3781614640 573 3814354480 574 3847325944 575 3880519720 576 3913947569 577 3947599985 578 3981488875 579 4015604733 580 4049959417 581 4084543421 582 4119368750 583 4154425702 584 4189726429 585 4225261229 586 4261042205 587 4297059655 588 4333325830 589 4369830830 590 4406587055 591 4443584605 592 4480835830 593 4518330830 594 4556082105 595 4594079555 596 4632335830 597 4670840830 598 4709607155 599 4748624705 600 4787906231 601 4827441431 602 4867243208 603 4907301260 604 4947628439 605 4988214443 606 5029072277 607 5070191435 608 5111585075 609 5153242691 610 5195177390 611 5237378666 612 5279859780 613 5322610020 614 5365642802 615 5408947414 616 5452537220 617 5496401508 618 5540553798 619 5584983170 620 5629703300 621 5674703268 622 5719996698 623 5765572670 624 5811444965 625 5857602453 626 5904059073 627 5950803695 628 5997850205 629 6045187473 630 6092829544 631 6140765076 632 6189008273 633 6237547793 634 6286397787 635 6335546913 636 6385009482 637 6434773938 638 6484854753 639 6535240371 640 6585945210 641 6636957714 642 6688292463 643 6739937685 644 6791908122 645 6844192002 646 6896804013 647 6949732383 648 7002991963 649 7056570763 650 7110483798 651 7164719078 652 7219291563 653 7274189263 654 7329427303 655 7384993473 656 7440903063 657 7497143863 658 7553731108 659 7610652588 660 7667923704 661 7725532024 662 7783493116 663 7841794548 664 7900451832 665 7959452536 666 8018812340 667 8078518588 668 8138587128 669 8199005304 670 8259788908 671 8320925284 672 8382430393 673 8444291353 674 8506524295 675 8569116337 676 8632083553 677 8695413061 678 8759121106 679 8823194578 680 8887649893 681 8952473941 682 9017683081 683 9083264203 684 9149233838 685 9215578646 686 9282315331 687 9349430553 688 9416940958 689 9484833206 690 9553124117 691 9621800119 692 9690878206 693 9760344806 694 9830216855 695 9900480781 696 9971153695 697 10042221791 698 10113702356 699 10185581584 700 10257876703 701 10330573907 702 10403690601 703 10477212743 704 10551157915 705 10625512075 706 10700292746 707 10775485886 708 10851109196 709 10927148396 710 11003621366 711 11080513826 712 11157843596 713 11235596396 714 11313790226 715 11392410566 716 11471475596 717 11550970796 718 11630914286 719 11711291546 720 11792120877 721 11873387517 722 11955109949 723 12037273411 724 12119896325 725 12202963929 726 12286494828 727 12370474016 728 12454920281 729 12539818617 730 12625187751 731 12711012677 732 12797312306 733 12884071386 734 12971309013 735 13059009935 736 13147193186 737 13235843514 738 13324980139 739 13414587561 740 13504685186 741 13595257514 742 13686323889 743 13777868811 744 13869911811 745 13962437139 746 14055464514 747 14148978186 748 14242997811 749 14337507639 750 14432527515 751 14528041437 752 14624069439 753 14720595519 754 14817639648 755 14915185824 756 15013254208 757 15111828544 758 15210929184 759 15310539872 760 15410680896 761 15511336000 762 15612525664 763 15714233376 764 15816479808 765 15919248448 766 16022559904 767 16126397664 768 16230782529 769 16335697729 770 16441164259 771 16547165349 772 16653721929 773 16760817229 774 16868472374 775 16976670334 776 17085432429 777 17194741629 778 17304619189 779 17415048079 780 17526049750 781 17637606910 782 17749741207 783 17862435349 784 17975710918 785 18089550622 786 18203976241 787 18318970219 788 18434554534 789 18550711630 790 18667463419 791 18784792345 792 18902720519 793 19021230119 794 19140343456 795 19260042708 796 19380350119 797 19501247867 798 19622758397 799 19744863619 800 19867586179 801 19990907987 802 20114851622 803 20239398994 804 20364572884 805 20490354932 806 20616768122 807 20743794094 808 20871455764 809 20999734772 810 21128654238 811 21258195530 812 21388381972 813 21519194932 814 21650657666 815 21782751542 816 21915500021 817 22048884197 818 22182927737 819 22317611735 820 22452959789 821 22588952993 822 22725615152 823 22862927084 824 23000912801 825 23139553121 826 23278871987 827 23418850217 828 23559511962 829 23700837762 830 23842851977 831 23985535147 832 24128911562 833 24272961762 834 24417710247 835 24563137277 836 24709267562 837 24856081362 838 25003603317 839 25151813687 840 25300737323 841 25450354203 842 25600689390 843 25751722862 844 25903479611 845 26055939615 846 26209128079 847 26363024697 848 26517654887 849 26672998343 850 26829080412 851 26985880788 852 27143425032 853 27301692552 854 27460709124 855 27620454156 856 27780953352 857 27942186120 858 28104178380 859 28266909252 860 28430404872 861 28594644360 862 28759653780 863 28925412252 864 29091946057 865 29259234025 866 29427302655 867 29596130777 868 29765744817 869 29936123605 870 30107293786 871 30279233898 872 30451970805 873 30625483045 874 30799797409 875 30974892435 876 31150795134 877 31327483750 878 31504985515 879 31683278673 880 31862390382 881 32042298886 882 32223031565 883 32404566367 884 32586930894 885 32770103094 886 32954110495 887 33138931045 888 33324592495 889 33511072495 890 33698399020 891 33886549720 892 34075552495 893 34265384995 894 34456075345 895 34647600895 896 34839989995 897 35033219995 898 35227319170 899 35422264870 900 35618085596 901 35814758396 902 36012311998 903 36210723450 904 36410021404 905 36610182908 906 36811236842 907 37013159950 908 37215981340 909 37419677756 910 37624278230 911 37829759506 912 38036150845 913 38243428685 914 38451622517 915 38660708779 916 38870716885 917 39081623273 918 39293457588 919 39506195960 920 39719868265 921 39934450633 922 40149972863 923 40366411085 924 40583795330 925 40802101418 926 41021359613 927 41241545735 928 41462689970 929 41684768138 930 41907810659 931 42131793041 932 42356745938 933 42582644858 934 42809520377 935 43037348003 936 43266158547 937 43495927203 938 43726685018 939 43958407186 940 44191124675 941 44424812679 942 44659502403 943 44895168725 944 45131843087 945 45369500367 946 45608171928 947 45847832648 948 46088514128 949 46330190928 950 46572894888 951 46816600568 952 47061339728 953 47307086928 954 47553874168 955 47801675688 956 48050523728 957 48300392528 958 48551314248 959 48803263128 960 49056271569 961 49310313489 962 49565421531 963 49821569613 964 50078790297 965 50337057501 966 50596404030 967 50856803478 968 51118288893 969 51380833869 970 51644471373 971 51909174999 972 52174977958 973 52441853518 974 52709835135 975 52978896077 976 53249069718 977 53520329326 978 53792708521 979 54066180243 980 54340778358 981 54616475806 982 54893306371 983 55171242993 984 55450319703 985 55730509111 986 56011845496 987 56294301468 988 56577911223 989 56862647371 990 57148544357 991 57435574459 992 57723772371 993 58013110371 994 58303623070 995 58595282746 996 58888124260 997 59182119556 998 59477303746 999 59773648774 1000 60071189668