0 0 1 0 2 13 3 46 4 83 5 191 6 272 7 509 8 687 9 1010 10 1291 11 2019 12 2364 13 3468 14 4132 15 5079 16 6072 17 8298 18 9234 19 12189 20 13621 21 15984 22 18095 23 22965 24 24886 25 29942 26 33248 27 38385 28 42073 29 51053 30 53882 31 64609 32 70619 33 78663 34 85424 35 96024 36 101521 37 118804 38 127940 39 140598 40 149375 41 172123 42 179424 43 205334 44 218216 45 234223 46 249491 47 282311 48 294211 49 326408 50 342446 51 368763 52 389114 53 434612 54 451025 55 488502 56 511564 57 547367 58 576037 59 636895 60 654271 61 721071 62 755629 63 798107 64 836726 65 896264 66 921917 67 1008017 68 1051015 69 1111588 70 1145577 71 1246341 72 1281833 73 1390679 74 1446751 75 1510284 76 1568571 77 1668171 78 1709039 79 1843912 80 1900632 81 1998248 82 2072267 83 2227029 84 2273446 85 2399500 86 2483960 87 2598727 88 2682335 89 2869713 90 2922008 91 3081569 92 3180737 93 3318619 94 3426577 95 3598203 96 3676068 97 3913339 98 4019423 99 4173514 100 4277935 101 4543007 102 4629727 103 4910125 104 5044345 105 5181215 106 5331378 107 5641896 108 5749232 109 6076792 110 6200318 111 6425650 112 6577957 113 6939357 114 7057780 115 7350911 116 7539735 117 7786534 118 7988722 119 8327922 120 8442717 121 8842212 122 9063882 123 9363374 124 9591308 125 9975822 126 10116783 127 10615697 128 10872949 129 11215262 130 11413748 131 11957290 132 12127049 133 12591257 134 12879053 135 13196246 136 13481713 137 14096963 138 14298907 139 14939816 140 15166052 141 15604069 142 15941222 143 16526990 144 16764220 145 17324538 146 17688764 147 18119167 148 18491767 149 19267933 150 19480639 151 20286215 152 20678215 153 21206341 154 21540614 155 22215404 156 22488753 157 23386194 158 23840698 159 24453369 160 24834055 161 25628445 162 25957097 163 26953321 164 27450993 165 27954569 166 28475428 167 29540440 168 29851806 169 30874667 170 31299075 171 32022327 172 32590187 173 33765537 174 34152894 175 34990101 176 35552939 177 36377636 178 37009806 179 38300266 180 38652069 181 39984601 182 40523535 183 41430277 184 42100808 185 43208562 186 43675094 187 44930003 188 45658403 189 46521451 190 47102908 191 48648364 192 49174339 193 50767259 194 51572039 195 52383934 196 53100026 197 54785058 198 55306244 199 57041167 200 57748283 201 58925426 202 59825034 203 61350638 204 61936712 205 63414699 206 64364887 207 65605425 208 66515069 209 68235305 210 68698712 211 70739985 212 71759817 213 73145105 214 74202409 215 75892525 216 76622498 217 78461851 218 79576223 219 81072527 220 81910992 221 83936878 222 84704271 223 87086465 224 88125895 225 89434850 226 90665420 227 93167784 228 93972124 229 96539249 230 97538477 231 98910518 232 100199217 233 102890441 234 103732692 235 105900758 236 107278580 237 109144388 238 110301432 239 113189966 240 113973087 241 116932885 242 118300109 243 120327485 244 121840208 245 123974244 246 124998365 247 127779881 248 129337867 249 131481339 250 132798024 251 136112244 252 137074081 253 140033181 254 141740407 255 143487030 256 145244458 257 148785066 258 149956332 259 152985876 260 154342078 261 156729351 262 158590102 263 162365484 264 163527282 265 166565728 266 168155282 267 170760310 268 172726438 269 176747504 270 177835938 271 181943699 272 183904687 273 186125943 274 188236114 275 191356788 276 192739718 277 197103362 278 199300810 279 202184337 280 203733137 281 208275301 282 209779330 283 214415832 284 216732950 285 219132095 286 221142486 287 225186568 288 226814436 289 231455249 290 233379705 291 236697093 292 239199937 293 244308477 294 245787874 295 249896042 296 252460776 297 255687189 298 258356037 299 263144571 300 264605208 301 269230765 302 272000819 303 275716487 304 278407230 305 282918290 306 284734740 307 290554837 308 292852171 309 296777464 310 299101463 311 305136949 312 307017355 313 313166045 314 316258613 315 319129473 316 322254520 317 328623332 318 330732830 319 336444106 320 339069128 321 343440317 322 346176774 323 352181142 324 354445073 325 359503919 326 362937107 327 367540648 328 370968848 329 376914768 330 378648255 331 385833906 332 389426042 333 394184160 334 397860702 335 403737772 336 405886672 337 413446741 338 416978821 339 422074216 340 425001014 341 431896572 342 434393189 343 441220583 344 445143303 345 449274497 346 453330776 347 461533040 348 464204344 349 472545328 350 475439044 351 480669411 352 484560363 353 493171021 354 496024415 355 502944538 356 507316558 357 512109730 358 516575116 359 525600340 360 528032997 361 536746317 362 541356565 363 547018267 364 550742520 365 558223448 366 561357186 367 570960951 368 575603437 369 581962791 370 585798726 371 594145504 372 597372339 373 607425171 374 611772405 375 617228929 376 622270282 377 631523522 378 634511804 379 645024993 380 649050137 381 656125436 382 661483982 383 672314800 384 675960944 385 682830815 386 688348197 387 695622456 388 701192590 389 712501972 390 715314986 391 725673724 392 730640438 393 738361926 394 744208635 395 753558217 396 757172141 397 769149153 398 775169405 399 781765072 400 786670042 401 798985724 402 803070648 403 814262982 404 820508980 405 827284143 406 832577008 407 843963622 408 848030814 409 861054182 410 866185342 411 874942725 412 881538830 413 892845180 414 897153575 415 907897908 416 914216348 417 923336076 418 929311680 419 943244116 420 946458939 421 960583349 422 967677705 423 977042579 424 984128793 425 995076265 426 999886505 427 1012305908 428 1019652314 429 1028004631 430 1033874578 431 1048952910 432 1054025699 433 1069312951 434 1075711779 435 1083704705 436 1091439935 437 1105681497 438 1110884263 439 1126773822 440 1132603516 441 1141819827 442 1148869120 443 1165167464 444 1170498867 445 1183584605 446 1191871885 447 1202965243 448 1210188709 449 1227116659 450 1231670551 451 1246911551 452 1255477283 453 1266997855 454 1275712852 455 1286860998 456 1292456525 457 1310240217 458 1319174645 459 1330499171 460 1337447594 461 1355677882 462 1360454528 463 1378914202 464 1387901580 465 1397569013 466 1406945619 467 1425856237 468 1431724299 469 1447923054 470 1455479630 471 1468335957 472 1477932215 473 1495377421 474 1501884250 475 1516951350 476 1525016766 477 1538168273 478 1548238009 479 1568546235 480 1574006429 481 1592501953 482 1602818191 483 1614209599 484 1623735482 485 1640422582 486 1647487809 487 1668762309 488 1679313233 489 1693605240 490 1701045468 491 1722820020 492 1729958793 493 1750021219 494 1759731765 495 1770555599 496 1781415122 497 1800489814 498 1807968196 499 1830754767 500 1839940493 501 1855242179 502 1866807229 503 1890119943 504 1896832915 505 1915544020 506 1925870664 507 1940565701 508 1952474953 509 1976576963 510 1982672752 511 2003317817 512 2015593613 513 2031185847 514 2043550357 515 2063323135 516 2071493688 517 2093941921 518 2104525489 519 2121431421 520 2130901350 521 2156631098 522 2164974556 523 2190999624 524 2204005724 525 2216053857 526 2229247592 527 2253506560 528 2261620854 529 2287373998 530 2297999276 531 2315829607 532 2326932496 533 2351690282 534 2360801586 535 2382825425 536 2396580469 537 2415195731 538 2429257469 539 2451362599 540 2458970715 541 2487588741 542 2501948079 543 2521158989 544 2534866042 545 2558069158 546 2565830799 547 2595352494 548 2610111236 549 2629710841 550 2640632029 551 2668246335 552 2677923396 553 2703736486 554 2719012428 555 2735003563 556 2750371465 557 2781436361 558 2791530307 559 2819882820 560 2830718362 561 2848836728 562 2864736719 563 2896756723 564 2907277227 565 2932969186 566 2949193898 567 2967892016 568 2984107258 569 3017098988 570 3025494400 571 3058826278 572 3072910460 573 3095268608 574 3109440184 575 3135493246 576 3146896371 577 3181220556 578 3197486946 579 3220517214 580 3233993518 581 3263684440 582 3275308481 583 3306889069 584 3324431943 585 3342032307 586 3359928854 587 3395954404 588 3406320526 589 3439733004 590 3454136128 591 3478540015 592 3496525103 593 3533618861 594 3544933658 595 3569137686 596 3587849144 597 3612956583 598 3629749191 599 3667893239 600 3678133623 601 3716653106 602 3732883868 603 3758463004 604 3777894704 605 3806479494 606 3819515956 607 3859125441 608 3878011823 609 3900113676 610 3915942502 611 3952445238 612 3965182639 613 4005903817 614 4026329955 615 4047754288 616 4063864499 617 4105332627 618 4119109807 619 4160979344 620 4177285692 621 4204269004 622 4225450540 623 4261640288 624 4274837202 625 4309305797 626 4330877085 627 4355833409 628 4377528747 629 4417690017 630 4427759242 631 4471950912 632 4493903030 633 4523537150 634 4545898190 635 4581666844 636 4596472666 637 4632437196 638 4652483438 639 4682622677 640 4701044600 641 4747229196 642 4762578119 643 4809189821 644 4828412465 645 4852946582 646 4874026771 647 4921449663 648 4937352789 649 4980175802 650 4997947462 651 5024673401 652 5048785746 653 5097460066 654 5113636577 655 5152674539 656 5176770117 657 5209380715 658 5230272565 659 5280223309 660 5292404056 661 5342801195 662 5368066417 663 5397552239 664 5422798888 665 5456143162 666 5472858542 667 5520651296 668 5546487554 669 5581130076 670 5601789754 671 5648846328 672 5663952576 673 5716960792 674 5743543626 675 5772095042 676 5796904418 677 5850811708 678 5868725368 679 5914912502 680 5935497552 681 5971925489 682 5996167759 683 6051436107 684 6068989342 685 6113314924 686 6137331360 687 6174675305 688 6202258261 689 6253634081 690 6268167683 691 6325291922 692 6353847112 693 6383810128 694 6412680012 695 6458853904 696 6477637532 697 6531452886 698 6560801132 699 6600030792 700 6620372549 701 6679857843 702 6698265559 703 6753630753 704 6781042049 705 6812644848 706 6842943316 707 6894723520 708 6914798364 709 6976232692 710 7000592908 711 7041405974 712 7072180061 713 7130043609 714 7146921666 715 7189213293 716 7220650271 717 7262793556 718 7294573246 719 7358478476 720 7375614091 721 7430364653 722 7461042681 723 7504203011 724 7536657324 725 7587261628 726 7607195509 727 7673133610 728 7699364192 729 7743730100 730 7770086537 731 7831730515 732 7853805013 733 7921303685 734 7955141627 735 7986290997 736 8018988026 737 8080443200 738 8102853716 739 8171930506 740 8198955502 741 8239592693 742 8269004000 743 8339127538 744 8361871803 745 8418107082 746 8453527284 747 8500488017 748 8531105697 749 8592101285 750 8611329422 751 8683609858 752 8719166022 753 8767598656 754 8800225680 755 8858618390 756 8879690929 757 8953620179 758 8990684951 759 9033929959 760 9062296159 761 9137339843 762 9162286536 763 9226591548 764 9264391000 765 9302676248 766 9340845445 767 9410556293 768 9436264303 769 9513573945 770 9537793055 771 9589569931 772 9628488648 773 9706957760 774 9732631836 775 9793900433 776 9833200269 777 9877516504 778 9917410910 779 9991615432 780 10011450701 781 10083937221 782 10120480389 783 10172912529 784 10207947036 785 10273159730 786 10300397753 787 10382929063 788 10424193505 789 10479481663 790 10512474300 791 10583694014 792 10609189341 793 10685848073 794 10728114363 795 10772621131 796 10815072041 797 10900605517 798 10923874483 799 11003336272 800 11037968690 801 11095228111 802 11138706089 803 11217154583 804 11245991520 805 11303775679 806 11343264731 807 11402177316 808 11446244490 809 11535466902 810 11559379621 811 11649239448 812 11686608052 813 11746795916 814 11787006347 815 11859539855 816 11888257537 817 11973258169 818 12019243365 819 12068038862 820 12104257992 821 12197262262 822 12228191078 823 12321871550 824 12368482574 825 12414269152 826 12454191188 827 12549152638 828 12579573052 829 12675218537 830 12713188637 831 12777223913 832 12821864880 833 12900165310 834 12932392961 835 13010091724 836 13052307940 837 13115768820 838 13164994446 839 13263918168 840 13286632870 841 13382915618 842 13432831076 843 13499531940 844 13549665482 845 13624304670 846 13657388904 847 13736656599 848 13786733447 849 13854767326 850 13893455141 851 13989393693 852 14023393371 853 14127069201 854 14170977733 855 14223778860 856 14275690150 857 14380744298 858 14410266390 859 14516033002 860 14557538648 861 14616958851 862 14670290792 863 14777456780 864 14813334960 865 14899234648 866 14953286488 867 15021488653 868 15066717945 869 15164915647 870 15193176655 871 15293309142 872 15348043402 873 15421174394 874 15471562587 875 15548050629 876 15584841511 877 15696969310 878 15753165622 879 15828245704 880 15869472439 881 15983069985 882 16015674113 883 16130041137 884 16179932081 885 16240337419 886 16297985845 887 16413813595 888 16451542059 889 16550798904 890 16597100956 891 16668273868 892 16726911007 893 16836494739 894 16875755472 895 16970379287 896 17021508795 897 17091962941 898 17151855717 899 17264386129 900 17296608611 901 17408535766 902 17462462914 903 17530542666 904 17591169308 905 17688795512 906 17729564051 907 17852927973 908 17914612339 909 17996643617 910 18036101495 911 18161007179 912 18200620618 913 18313650256 914 18376631324 915 18443064962 916 18506290021 917 18614652149 918 18654747947 919 18782812967 920 18832021855 921 18917730807 922 18982284707 923 19100407967 924 19134224784 925 19235866218 926 19301213684 927 19387942368 928 19451565252 929 19583631756 930 19617855494 931 19725868421 932 19792291649 933 19881217887 934 19948193326 935 20040337186 936 20081884413 937 20217168256 938 20274535562 939 20365089623 940 20418598160 941 20555522514 942 20601069750 943 20729785586 944 20797799564 945 20861235853 946 20923021779 947 21062445203 948 21108528215 949 21236387385 950 21289769599 951 21383646190 952 21440787254 953 21582752504 954 21629369253 955 21743142537 956 21814529635 957 21898685860 958 21970648080 959 22093723496 960 22132412804 961 22273232374 962 22338780344 963 22435456386 964 22508559302 965 22625743736 966 22666104155 967 22814057804 968 22881585278 969 22970153590 970 23029302088 971 23178993436 972 23229094316 973 23357371316 974 23432806856 975 23507441315 976 23582213084 977 23734536940 978 23785210674 979 23923099890 980 23975844536 981 24077746062 982 24154944278 983 24309974010 984 24360590634 985 24484829986 986 24555953538 987 24643737607 988 24712562739 989 24860033601 990 24898412954 991 25057028032 992 25134071626 993 25240209162 994 25307878645 995 25435700091 996 25488732511 997 25650095256 998 25730933108 999 25836315985 1000 25901475508