0 1 1 0 2 1 3 1 4 3 5 3 6 4 7 4 8 10 9 12 10 14 11 16 12 19 13 21 14 24 15 27 16 64 17 72 18 84 19 94 20 108 21 120 22 136 23 150 24 169 25 185 26 206 27 225 28 249 29 270 30 297 31 321 32 831 33 918 34 1014 35 1115 36 1226 37 1342 38 1469 39 1602 40 1747 41 1898 42 2062 43 2233 44 2418 45 2611 46 2818 47 3034 48 3266 49 3507 50 3765 51 4033 52 4319 53 4616 54 4932 55 5260 56 5608 57 5969 58 6351 59 6747 60 7166 61 7599 62 8056 63 8529 64 26207 65 28009 66 29941 67 31943 68 34085 69 36308 70 38677 71 41134 72 43752 73 46461 74 49342 75 52327 76 55491 77 58767 78 62239 79 65827 80 69624 81 73551 82 77695 83 81979 84 86499 85 91164 86 96079 87 101155 88 106491 89 111999 90 117788 91 123755 92 130019 93 136479 94 143247 95 150224 96 157532 97 165056 98 172929 99 181038 100 189509 101 198230 102 207338 103 216705 104 226479 105 236534 106 247010 107 257783 108 269005 109 280534 110 292534 111 304865 112 317683 113 330850 114 344534 115 358579 116 373165 117 388138 118 403670 119 419609 120 436140 121 453091 122 470660 123 488678 124 507334 125 526461 126 546261 127 566547 128 2239706 129 2336282 130 2436354 131 2539915 132 2647176 133 2758123 134 2872974 135 2991725 136 3114593 137 3241575 138 3372904 139 3508570 140 3648814 141 3793635 142 3943274 143 4097732 144 4257266 145 4421870 146 4591809 147 4767088 148 4947971 149 5134465 150 5326852 151 5525131 152 5729593 153 5940248 154 6157387 155 6381022 156 6611462 157 6848712 158 7093090 159 7344613 160 7603599 161 7870067 162 8144354 163 8426472 164 8716768 165 9015266 166 9322313 167 9637936 168 9962502 169 10296030 170 10638898 171 10991138 172 11353128 173 11724903 174 12106862 175 12499033 176 12901825 177 13315280 178 13739808 179 14175454 180 14622650 181 15081433 182 15552247 183 16035143 184 16530566 185 17038571 186 17559625 187 18093776 188 18641503 189 19202869 190 19778354 191 20368025 192 20972386 193 21591496 194 22225872 195 22875589 196 23541165 197 24222679 198 24920674 199 25635222 200 26366879 201 27115733 202 27882342 203 28666799 204 29469687 205 30291092 206 31131611 207 31991347 208 32870899 209 33770375 210 34690401 211 35631077 212 36593044 213 37576420 214 38581848 215 39609452 216 40659902 217 41733315 218 42830376 219 43951221 220 45096538 221 46266468 222 47461728 223 48682452 224 49929373 225 51202644 226 52503001 227 53830604 228 55186218 229 56569996 230 57982720 231 59424563 232 60896310 233 62398141 234 63930872 235 65494676 236 67090386 237 68718196 238 70378943 239 72072828 240 73800720 241 75562813 242 77359994 243 79192479 244 81061159 245 82966258 246 84908699 247 86888700 248 88907203 249 90964448 250 93061382 251 95198253 252 97376042 253 99594990 254 101856098 255 104159631 256 567852809 257 582538824 258 597551430 259 612892037 260 628571262 261 644590591 262 660960912 263 677683798 264 694770420 265 712222416 266 730051254 267 748258664 268 766856392 269 785846254 270 805240304 271 825040439 272 845259018 273 865898029 274 886970134 275 908477424 276 930432877 277 952838664 278 975708094 279 999043446 280 1022858341 281 1047155159 282 1071947864 283 1097238934 284 1123042672 285 1149361664 286 1176210551 287 1203592039 288 1231521121 289 1260000599 290 1289045834 291 1318659754 292 1348858067 293 1379643821 294 1411033104 295 1443029079 296 1475648211 297 1508893789 298 1542782654 299 1577318234 300 1612517760 301 1648384775 302 1684936916 303 1722177872 304 1760125666 305 1798784126 306 1838171695 307 1878292336 308 1919164909 309 1960793523 310 2003197454 311 2046380971 312 2090363781 313 2135150288 314 2180760647 315 2227199430 316 2274487218 317 2322628744 318 2371645052 319 2421541031 320 2472338185 321 2524041571 322 2576673152 323 2630238168 324 2684759056 325 2740241214 326 2796707571 327 2854163716 328 2912633049 329 2972121343 330 3032652506 331 3094232491 332 3156885711 333 3220618312 334 3285455211 335 3351402762 336 3418486403 337 3486712669 338 3556107538 339 3626677762 340 3698449836 341 3771430722 342 3845647471 343 3921107251 344 3997837666 345 4075846103 346 4155160719 347 4235789136 348 4317760081 349 4401081384 350 4485782362 351 4571871089 352 4659377449 353 4748309754 354 4838698495 355 4930552218 356 5023902018 357 5118756689 358 5215147930 359 5313084799 360 5412599618 361 5513701681 362 5616423953 363 5720776003 364 5826791415 365 5934480026 366 6043876081 367 6154989681 368 6267855730 369 6382484607 370 6498911875 371 6617148209 372 6737229849 373 6859167738 374 6982998815 375 7108734330 376 7236411897 377 7366043066 378 7497666170 379 7631293055 380 7766962770 381 7904687473 382 8044506929 383 8186433626 384 8330508065 385 8476743035 386 8625179795 387 8775831476 388 8928740071 389 9083919046 390 9241411173 391 9401230249 392 9563419823 393 9727994039 394 9894997223 395 10064443886 396 10236379151 397 10410817866 398 10587805975 399 10767358705 400 10949522796 401 11134313847 402 11321779441 403 11511935546 404 11704830585 405 11900480912 406 12098935791 407 12300211981 408 12504359609 409 12711395809 410 12921371595 411 13134304520 412 13350246459 413 13569215378 414 13791264061 415 14016410883 416 14244709536 417 14476178821 418 14710873339 419 14948812338 420 15190051350 421 15434610039 422 15682544893 423 15933876038 424 16188660892 425 16446920036 426 16708711868 427 16974057421 428 17243016071 429 17515609321 430 17791897527 431 18071902683 432 18355686148 433 18643270376 434 18934717755 435 19230051246 436 19529334239 437 19832590196 438 20139883561 439 20451238293 440 20766719889 441 21086352824 442 21410203649 443 21738297378 444 22070701640 445 22407441956 446 22748587060 447 23094163028 448 23444239673 449 23798843619 450 24158045811 451 24521873419 452 24890398518 453 25263648844 454 25641697604 455 26024573123 456 26412349765 457 26805056411 458 27202768611 459 27605515852 460 28013374842 461 28426375668 462 28844596251 463 29268067275 464 29696867873 465 30131029347 466 30570632044 467 31015707908 468 31466338526 469 31922556451 470 32384444539 471 32852036003 472 33325414941 473 33804615220 474 34289722236 475 34780770508 476 35277846729 477 35780986091 478 36290276587 479 36805754107 480 37327507971 481 37855574733 482 38390045070 483 38930956254 484 39478400290 485 40032415162 486 40593094262 487 41160476283 488 41734656004 489 42315672849 490 42903622987 491 43498546599 492 44100541271 493 44709647908 494 45325965544 495 45949535862 496 46580459316 497 47218778361 498 47864594931 499 48517952251 500 49178953735 501 49847643401 502 50524126146 503 51208446808 504 51900711796 505 52600966733 506 53309319572 507 54025816778 508 54750567819 509 55483619996 510 56225084354 511 56975009028 512 454241403975 513 461088843747 514 468026433272 515 475055171285 516 482176099226 517 489390234128 518 496698637145 519 504102344803 520 511602437364 521 519199971116 522 526896046625 523 534691739344 524 542588170436 525 550586435711 526 558687676312 527 566893008718 528 575203595279 529 583620572501 530 592145124244 531 600778408297 532 609521629403 533 618375966922 534 627342647737 535 636422872161 536 645617889530 537 654928922362 538 664357241809 539 673904092927 540 683570769971 541 693358539872 542 703268720312 543 713302601415 544 723461523642 545 733746800618 546 744159796902 547 754701848982 548 765374345849 549 776178648168 550 787116168704 551 798188292653 552 809396457905 553 820742073503 554 832226602806 555 843851480086 556 855618193503 557 867528202887 558 879583022582 559 891784137317 560 904133087976 561 916631385565 562 929280596829 563 942082259428 564 955037967383 565 968149284303 566 981417831852 567 994845201035 568 1008433040470 569 1022182968909 570 1036096663373 571 1050175769682 572 1064421993638 573 1078837009573 574 1093422551371 575 1108180322275 576 1123112085733 577 1138219573173 578 1153504577997 579 1168968861333 580 1184614245827 581 1200442522681 582 1216455545301 583 1232655134264 584 1249043174138 585 1265621516386 586 1282392076018 587 1299356735807 588 1316517442756 589 1333876110200 590 1351434717549 591 1369195210284 592 1387159599492 593 1405329863198 594 1423708045751 595 1442296157001 596 1461096274985 597 1480110442959 598 1499340771908 599 1518789338942 600 1538458289615 601 1558349734123 602 1578465853028 603 1598808791267 604 1619380763659 605 1640183950305 606 1661220601938 607 1682492933083 608 1704003230839 609 1725753745807 610 1747746800691 611 1769984682643 612 1792469751665 613 1815204330671 614 1838190817426 615 1861431572334 616 1884929030152 617 1908685589222 618 1932703723023 619 1956985867076 620 1981534534060 621 2006352198400 622 2031441411194 623 2056804686273 624 2082444614921 625 2108363749565 626 2134564722167 627 2161050125553 628 2187822631572 629 2214884873924 630 2242239566150 631 2269889382044 632 2297837077345 633 2326085367742 634 2354637050370 635 2383494883343 636 2412661707035 637 2442140321155 638 2471933609836 639 2502044416261 640 2532475667511 641 2563230250746 642 2594311137877 643 2625721259242 644 2657463632116 645 2689541231892 646 2721957120388 647 2754714318611 648 2787815934843 649 2821265034854 650 2855064773939 651 2889218264590 652 2923728708283 653 2958599264764 654 2993833183651 655 3029433671125 656 3065404025510 657 3101747501378 658 3138467444918 659 3175567159682 660 3213050041725 661 3250919442708 662 3289178809131 663 3327831542803 664 3366881139818 665 3406331052695 666 3446184829163 667 3486445971613 668 3527118080004 669 3568204708636 670 3609709508837 671 3651636087436 672 3693988149213 673 3736769352635 674 3779983456544 675 3823634173167 676 3867725314537 677 3912260647234 678 3957244038607 679 4002679308731 680 4048570380897 681 4094921130795 682 4141735536778 683 4189017530804 684 4236771148454 685 4285000377043 686 4333709310023 687 4382901992272 688 4432582574223 689 4482755158942 690 4533423956052 691 4584593125931 692 4636266938051 693 4688449612307 694 4741145477120 695 4794358812588 696 4848094008334 697 4902355403728 698 4957147450271 699 5012474548898 700 5068341212079 701 5124751902972 702 5181711197312 703 5239223619585 704 5297293809484 705 5355926355115 706 5415125959210 707 5474897274216 708 5535245068244 709 5596174057132 710 5657689075081 711 5719794903701 712 5782496442355 713 5845798539118 714 5909706160900 715 5974224221327 716 6039357755584 717 6105111745229 718 6171491292785 719 6238501448498 720 6306147384659 721 6374434219233 722 6443367195025 723 6512951500192 724 6583192447106 725 6654095294844 726 6725665427821 727 6797908175102 728 6870828993910 729 6944433285769 730 7018726579754 731 7093714350642 732 7169402201882 733 7245795680516 734 7322900465150 735 7400722177656 736 7479266570832 737 7558539342145 738 7638546321154 739 7719293279971 740 7800786125718 741 7883030707717 742 7966033009679 743 8049798958967 744 8134334618497 745 8219645992667 746 8305739224419 747 8392620397846 748 8480295734933 749 8568771400271 750 8658053697552 751 8748148870897 752 8839063306546 753 8930803330810 754 9023375411485 755 9116785957943 756 9211041522248 757 9306148595808 758 9402113815816 759 9498943758473 760 9596645145100 761 9695224637533 762 9794689043982 763 9895045110934 764 9996299734368 765 10098459748179 766 10201532135106 767 10305523817363 768 10410441867260 769 10516293294287 770 10623085261226 771 10730824867699 772 10839519365942 773 10949175946592 774 11059801954199 775 11171404669413 776 11283991530020 777 11397569909540 778 11512147337968 779 11627731282647 780 11744329368692 781 11861949156209 782 11980598366376 783 12100284655019 784 12221015838344 785 12342799668821 786 12465644060646 787 12589556861915 788 12714546085778 789 12840619678915 790 12967785752387 791 13096052352454 792 13225427691101 793 13355919913091 794 13487537332319 795 13620288195112 796 13754180916223 797 13889223844510 798 14025425498650 799 14162794328997 800 14301338959160 801 14441067944051 802 14581990011151 803 14724113820971 804 14867448207982 805 15012001937200 806 15157783951116 807 15304803122417 808 15453068500547 809 15602589066875 810 15753373980969 811 15905432331830 812 16058773390203 813 16213406355889 814 16369340609734 815 16526585463425 816 16685150411134 817 16845044875324 818 17006278464569 819 17168860715382 820 17332801349655 821 17498110019008 822 17664796561931 823 17832870744085 824 18002342521657 825 18173221777625 826 18345518584782 827 18519242944556 828 18694405049680 829 18871015018906 830 19049083166030 831 19228619730512 832 19409635146112 833 19592139774102 834 19776144171595 835 19961658820595 836 20148694402715 837 20337261524077 838 20527370989688 839 20719033530969 840 20912260079767 841 21107061491660 842 21303448826506 843 21501433067537 844 21701025401508 845 21902236940457 846 22105079001538 847 22309562824500 848 22515699858092 849 22723501473273 850 22932979249266 851 23144144689471 852 23357009507144 853 23571585336970 854 23787884027459 855 24005917348191 856 24225697281802 857 24447235733969 858 24670544825071 859 24895636595773 860 25122523305443 861 25351217133348 862 25581730476710 863 25814075654680 864 26048265206009 865 26284311588561 866 26522227483888 867 26762025492295 868 27003718436993 869 27247319061980 870 27492840335860 871 27740295145202 872 27989696605301 873 28241057749028 874 28494391837220 875 28749712050385 876 29007031798695 877 29266364409110 878 29527723442462 879 29791122376009 880 30056574920088 881 30324094703560 882 30593695590120 883 30865391359097 884 31139196028895 885 31415123533162 886 31693188043849 887 31973403650311 888 32255784681960 889 32540345382660 890 32827100240662 891 33116063658307 892 33407250281517 893 33700674672469 894 33996351638731 895 34294295901168 896 34594522430400 897 34897046109952 898 35201882072322 899 35509045365139 900 35818551286815 901 36130415047872 902 36444652114070 903 36761277862916 904 37080307926337 905 37401757850239 906 37725643436815 907 38051980399211 908 38380784711348 909 38712072257708 910 39045859182754 911 39382161543804 912 39720995660025 913 40062377760348 914 40406324340134 915 40752851804145 916 41101976822744 917 41453715977995 918 41808086119488 919 42165104005418 920 42524786666122 921 42887151040149 922 43252214337385 923 43619993678292 924 43990506456594 925 44363769973431 926 44739801807914 927 45118619446207 928 45500240651605 929 45884683096825 930 46271964733700 931 46662103420319 932 47055117298631 933 47451024416449 934 47849843104630 935 48251591602329 936 48656288433730 937 49063952028084 938 49474601104511 939 49888254286835 940 50304930487898 941 50724648527686 942 51147427517248 943 51573286471541 944 52002244701460 945 52434321421416 946 52869536140931 947 53307908275550 948 53749457537974 949 54194203543625 950 54642166210053 951 55093365357167 952 55547821106143 953 56005553483027 954 56466582817239 955 56930929339762 956 57398613589961 957 57869656008373 958 58344077343080 959 58821898245915 960 59303139678363 961 59787822502287 962 60275967894308 963 60767596931065 964 61262731003082 965 61761391403487 966 62263599741462 967 62769377525414 968 63278746584948 969 63791728648503 970 64308345764870 971 64828619884327 972 65352573279674 973 65880228121753 974 66411606909170 975 66946732038215 976 67485626232059 977 68028312114217 978 68574812637318 979 69125150650885 980 69679349338835 981 70237431781590 982 70799421393110 983 71365341486589 984 71935215710993 985 72509067611004 986 73086921072457 987 73668799876547 988 74254728144729 989 74844729896554 990 75438829494131 991 76037051194142 992 76639419601247 993 77245959214292 994 77856694879235 995 78471651339026 996 79090853686026 997 79714326905998 998 80342096339637 999 80974187220686 1000 81610625136918