0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 30 10 42 11 55 12 75 13 96 14 127 15 161 16 208 17 260 18 330 19 407 20 509 21 621 22 765 23 925 24 1127 25 1350 26 1627 27 1934 28 2310 29 2725 30 3227 31 3782 32 4446 33 5178 34 6044 35 7000 36 8122 37 9355 38 10791 39 12370 40 14195 41 16196 42 18494 43 21012 44 23887 45 27029 46 30596 47 34492 48 38894 49 43689 50 49082 51 54952 52 61525 53 68664 54 76627 55 85266 56 94868 57 105264 58 116778 59 129232 60 142982 61 157826 62 174166 63 191788 64 211131 65 231956 66 254755 67 279274 68 306051 69 334804 70 366130 71 399733 72 436263 73 475390 74 517836 75 563255 76 612427 77 664974 78 721756 79 782374 80 847761 81 917479 82 992551 83 1072522 84 1158494 85 1249970 86 1348157 87 1452536 88 1564405 89 1683201 90 1810340 91 1945235 92 2089406 93 2242220 94 2405326 95 2578068 96 2762214 97 2957053 98 3164504 99 3383831 100 3617081 101 3863468 102 4125203 103 4401470 104 4694632 105 5003814 106 5331561 107 5676973 108 6042759 109 6427958 110 6835484 111 7264346 112 7717642 113 8194318 114 8697698 115 9226697 116 9784844 117 10370990 118 10988909 119 11637423 120 12320535 121 13036993 122 13791077 123 14581506 124 15412805 125 16283627 126 17198796 127 18156930 128 19163134 129 20215950 130 21320810 131 22476230 132 23687942 133 24954387 134 26281657 135 27668162 136 29120326 137 30636482 138 32223447 139 33879524 140 35611893 141 37418782 142 39307792 143 41277126 144 43334784 145 45478884 146 47717893 147 50049906 148 52483815 149 55017642 150 57660779 151 60411221 152 63278835 153 66261534 154 69369726 155 72601310 156 75967199 157 79465214 158 83106856 159 86889929 160 90826485 161 94914251 162 99165913 163 103579186 164 108167351 165 112928052 166 117875246 167 123006573 168 128336637 169 133862998 170 139600998 171 145548200 172 151720631 173 158115793 174 164750498 175 171622250 176 178748614 177 186127025 178 193775891 179 201692668 180 209896561 181 218384967 182 227177997 183 236273070 184 245691157 185 255429623 186 265510409 187 275930912 188 286713994 189 297857010 190 309383850 191 321291915 192 333606086 193 346323717 194 359470799 195 373044745 196 387072592 197 401551732 198 416510377 199 431945982 200 447887894 201 464333544 202 481313531 203 498825377 204 516900877 205 535537546 206 554768515 207 574591396 208 595040601 209 616113746 210 637846664 211 660237086 212 683322206 213 707099780 214 731608501 215 756846262 216 782853210 217 809627263 218 837210173 219 865600016 220 894840073 221 924928482 222 955910215 223 987783580 224 1020595192 225 1054343424 226 1089076683 227 1124793550 228 1161544158 229 1199327180 230 1238194649 231 1278145461 232 1319233484 233 1361457726 234 1404874065 235 1449481760 236 1495338629 237 1542444074 238 1590858026 239 1640580170 240 1691672496 241 1744134841 242 1798031441 243 1853362449 244 1910194259 245 1968527226 246 2028430102 247 2089903579 248 2153018711 249 2217776404 250 2284250199 251 2352441391 252 2422425931 253 2494205368 254 2567858276 255 2643386619 256 2720871520 257 2800315228 258 2881801629 259 2965333428 260 3050997193 261 3138795959 262 3228819188 263 3321070417 264 3415641940 265 3512537644 266 3611852883 267 3713592092 268 3817853585 269 3924642213 270 4034059492 271 4146110856 272 4260900958 273 4378435673 274 4498823017 275 4622069516 276 4748286462 277 4877480877 278 5009767586 279 5145154302 280 5283759299 281 5425590832 282 5570770881 283 5719308450 284 5871329134 285 6026842541 286 6185978137 287 6348746341 288 6515280420 289 6685591431 290 6859816715 291 7037968204 292 7220187201 293 7406486362 294 7597011241 295 7791775420 296 7990928631 297 8194485220 298 8402599369 299 8615286438 300 8832704961 301 9054871137 302 9281948157 303 9513953292 304 9751054297 305 9993269346 306 10240771064 307 10493578774 308 10751869870 309 11015664660 310 11285145611 311 11560334263 312 11841418078 313 12128419634 314 12421531711 315 12720778204 316 13026357088 317 13338293404 318 13656790663 319 13981875294 320 14313756263 321 14652461205 322 14998204863 323 15351016372 324 15711116144 325 16078534618 326 16453498234 327 16836039010 328 17226389312 329 17624582548 330 18030857369 331 18445248863 332 18868001855 333 19299152930 334 19738953445 335 20187441772 336 20644875715 337 21111295217 338 21586964907 339 22071926625 340 22566451691 341 23070583652 342 23584600916 343 24108549023 344 24642713381 345 25187141320 346 25742125626 347 26307715761 348 26884211772 349 27471665036 350 28070383278 351 28680420112 352 29302090830 353 29935451074 354 30580824121 355 31238267979 356 31908113790 357 32590421725 358 33285531208 359 33993504911 360 34714690448 361 35449152755 362 36197248074 363 36959043982 364 37734905205 365 38524901751 366 39329407289 367 40148494592 368 40982546178 369 41831637362 370 42696159949 371 43576192191 372 44472135054 373 45384069489 374 46312406104 375 47257228922 376 48218958075 377 49197680428 378 50193826119 379 51207485246 380 52239097824 381 53288756962 382 54356913033 383 55443662548 384 56549466140 385 57674423463 386 58819005914 387 59983316722 388 61167837895 389 62372676008 390 63598324206 391 64844892797 392 66112885963 393 67402417502 394 68714003137 395 70047760608 396 71404217046 397 72783493874 398 74186130181 399 75612251502 400 77062408759 401 78536731349 402 80035782578 403 81559696154 404 83109047631 405 84683974786 406 86285065972 407 87912463483 408 89566768368 409 91248127158 410 92957154173 411 94694000674 412 96459294090 413 98253190164 414 100076330033 415 101928874366 416 103811477904 417 105724305979 418 107668027512 419 109642813012 420 111649345440 421 113687800203 422 115758874926 423 117862750404 424 120000138796 425 122171226015 426 124376739380 427 126616870433 428 128892361511 429 131203409524 430 133550772453 431 135934653087 432 138355824944 433 140814496391 434 143311457135 435 145846921679 436 148421695750 437 151035999720 438 153690656014 439 156385891380 440 159122544833 441 161900849215 442 164721660784 443 167585219057 444 170492397390 445 173443441676 446 176439243074 447 179480054408 448 182566784506 449 185699692834 450 188879706595 451 192107092476 452 195382795908 453 198707090520 454 202080940678 455 205504627531 456 208979134271 457 212504749245 458 216082475206 459 219712608328 460 223396170750 461 227133466188 462 230925536929 463 234772694806 464 238676002144 465 242635778592 466 246653107250 467 250728316236 468 254862509276 469 259056022639 470 263309981468 471 267624730809 472 272001417085 473 276440393812 474 280942829486 475 285509086744 476 290140356005 477 294837008730 478 299600258055 479 304430484916 480 309328925056 481 314295968545 482 319332874556 483 324440042998 484 329618756295 485 334869423892 486 340193352317 487 345590961199 488 351063581060 489 356611641394 490 362236497543 491 367938589597 492 373719297566 493 379579071800 494 385519317861 495 391540497061 496 397644040376 497 403830419755 498 410101092474 499 416456541848 500 422898251301 501 429426715201 502 436043444007 503 442748943869 504 449544752172 505 456431386488 506 463410412046 507 470482358626 508 477648819120 509 484910335197 510 492268528361 511 499723952897 512 507278258812 513 514932012671 514 522686893906 515 530543482176 516 538503486186 517 546567498335 518 554737257584 519 563013369856 520 571397604230 521 579890579812 522 588494096784 523 597208788248 524 606036485337 525 614977834820 526 624034699768 527 633207741429 528 642498854706 529 651908714949 530 661439249912 531 671091149920 532 680866375396 533 690765631306 534 700790911794 535 710942937278 536 721223735518 537 731634042032 538 742175919220 539 752850118603 540 763658737070 541 774602541775 542 785683665184 543 796902890956 544 808262386999 545 819762953120 546 831406793760 547 843194725776 548 855128989992 549 867210419972 550 879441294016 551 891822463297 552 904356243489 553 917043502981 554 929886595948 555 942886408960 556 956045334513 557 969364277010 558 982845668430 559 996490431910 560 1010301038812 561 1024278430641 562 1038425119274 563 1052742065582 564 1067231821810 565 1081895367810 566 1096735297395 567 1111752610363 568 1126949941965 569 1142328311574 570 1157890397082 571 1173637238435 572 1189571556020 573 1205694410000 574 1222008564463 575 1238515100786 576 1255216826663 577 1272114844277 578 1289212006170 579 1306509436395 580 1324010032165 581 1341714939043 582 1359627100191 583 1377747683679 584 1396079678526 585 1414624274930 586 1433384509015 587 1452361594205 588 1471558613588 589 1490976803416 590 1510619295059 591 1530487348662 592 1550584143754 593 1570910963990 594 1591471038380 595 1612265675188 596 1633298152766 597 1654569803619 598 1676083956767 599 1697841970055 600 1719847223085 601 1742101098621 602 1764607028210 603 1787366420704 604 1810382759424 605 1833657478939 606 1857194115746 607 1880994131230 608 1905061114982 609 1929396554813 610 1954004094778 611 1978885250319 612 2004043719822 613 2029481045951 614 2055200982867 615 2081205101626 616 2107497212051 617 2134078913196 618 2160954071994 619 2188124316704 620 2215593571239 621 2243363492686 622 2271438063390 623 2299818970473 624 2328510254638 625 2357513632609 626 2386833204939 627 2416470719234 628 2446430335735 629 2476713832550 630 2507325431140 631 2538266941323 632 2569542645710 633 2601154385430 634 2633106505744 635 2665400880410 636 2698041917217 637 2731031522133 638 2764374167052 639 2798071791434 640 2832128931177 641 2866547558831 642 2901332275879 643 2936485089282 644 2972010665990 645 3007911046990 646 3044190966285 647 3080852500209 648 3117900449759 649 3155336926174 650 3193166799072 651 3231392215995 652 3270018115031 653 3309046679638 654 3348482918044 655 3388329050946 656 3428590156658 657 3469268492709 658 3510369209136 659 3551894601738 660 3593849892166 661 3636237414063 662 3679062462411 663 3722327410098 664 3766037625351 665 3810195519894 666 3854806536921 667 3899873128433 668 3945400812488 669 3991392080974 670 4037852528540 671 4084784688403 672 4132194231761 673 4180083732711 674 4228458940770 675 4277322472437 676 4326680155412 677 4376534648204 678 4426891858511 679 4477754488297 680 4529128525222 681 4581016714293 682 4633425124913 683 4686356546697 684 4739817130699 685 4793809710710 686 4848340521300 687 4903412441962 688 4959031790714 689 5015201492338 690 5071927950170 691 5129214135850 692 5187066537946 693 5245488174563 694 5304485621377 695 5364061944527 696 5424223806776 697 5484974321843 698 5546320241499 699 5608264728696 700 5670814624094 701 5733973139484 702 5797747206382 703 5862140086992 704 5927158803672 705 5992806668624 706 6059090796981 707 6126014552641 708 6193585143440 709 6261805984537 710 6330684378491 711 6400223793381 712 6470431626442 713 6541311398258 714 6612870602766 715 6685112814758 716 6758045624808 717 6831672661522 718 6906001614144 719 6981036166798 720 7056784107400 721 7133249175136 722 7210439258673 723 7288358154050 724 7367013850587 725 7446410200782 726 7526555296736 727 7607453049115 728 7689111652812 729 7771535076246 730 7854731619194 731 7938705309667 732 8023464552277 733 8109013434192 734 8195360467042 735 8282509798950 736 8370470048542 737 8459245424481 738 8548844654579 739 8639272009884 740 8730536327353 741 8822641940027 742 8915597796205 743 9009408292767 744 9104082489383 745 9199624846316 746 9296044536853 747 9393346086576 748 9491538782315 749 9590627214580 750 9690620786040 751 9791524153985 752 9893346836962 753 9996093558629 754 10099773955671 755 10204392820100 756 10309959906717 757 10416480075455 758 10523963201585 759 10632414214906 760 10741843111165 761 10852254889616 762 10963659668843 763 11076062519549 764 11189473683142 765 11303898301386 766 11419346740883 767 11535824216453 768 11653341219952 769 11771903038803 770 11891520292536 771 12012198343266 772 12133947938150 773 12256774513610 774 12380688946903 775 12505696750760 776 12631808932609 777 12759031081083 778 12887374336217 779 13016844364687 780 13147452439143 781 13279204303877 782 13412111366687 783 13546179451580 784 13681420101540 785 13817839219884 786 13955448487323 787 14094253888634 788 14234267242274 789 14375494614100 790 14517947962865 791 14661633437658 792 14806563137622 793 14952743294631 794 15100186150821 795 15248898023100 796 15398891296582 797 15550172372832 798 15702753782600 799 15856642014268 800 16011849744328 801 16168383547581 802 16326256248881 803 16485474511752 804 16646051309452 805 16807993393809 806 16971313889206 807 17136019638035 808 17302123915878 809 17469633655296 810 17638562285799 811 17808916832431 812 17980710878684 813 18153951541716 814 18328652561740 815 18504821150344 816 18682471204595 817 18861610030073 818 19042251683493 819 19224403566844 820 19408079896509 821 19593288170521 822 19780042767782 823 19968351284695 824 20158228262827 825 20349681396564 826 20542725392951 827 20737368046831 828 20933624230807 829 21131501839772 830 21331015914804 831 21532174453276 832 21734992664854 833 21939478649009 834 22145647786921 835 22353508282644 836 22563075688966 837 22774358314169 838 22987371885586 839 23202124818215 840 23418633014109 841 23636904994557 842 23856956839325 843 24078797178586 844 24302442269879 845 24527900851911 846 24755189363047 847 24984316653027 848 25215299341232 849 25448146388063 850 25682874596931 851 25919493041551 852 26158018709486 853 26398460787373 854 26640836450049 855 26885154999680 856 27131433798534 857 27379682263940 858 27629917948729 859 27882150388058 860 28136397325458 861 28392668413577 862 28650981589789 863 28911346626901 864 29173781656352 865 29438296570699 866 29704909698648 867 29973631055282 868 30244479166678 869 30517464170114 870 30792604792301 871 31069911295393 872 31349402606973 873 31631089113718 874 31914989947307 875 32201115621779 876 32489485473078 877 32780110142231 878 33073009172783 879 33368193335542 880 33665682381859 881 33965487211977 882 34267627788399 883 34572115143656 884 34878969451588 885 35188201876698 886 35499832807522 887 35813873543391 888 36130344687810 889 36449257674549 890 36770633325501 891 37094483211843 892 37420828374008 893 37749680520272 894 38081060913091 895 38414981400710 896 38751463467899 897 39090519102541 898 39432170015163 899 39776428336320 900 40123316002516 901 40472845286627 902 40825038354692 903 41179907624895 904 41537475493068 905 41897754522380 906 42260767342026 907 42626526663209 908 42995055348725 909 43366366257520 910 43740482489574 911 44117417054629 912 44497193290177 913 44879824356391 914 45265333831921 915 45653735030539 916 46045051772258 917 46439297524167 918 46836496351354 919 47236661877293 920 47639818412495 921 48045979736515 922 48455170408958 923 48867404368697 924 49282706424707 925 49701090674854 926 50122582181273 927 50547195204012 928 50974955058682 929 51405876167218 930 51839984102509 931 52277293451631 932 52717830045046 933 53161608634709 934 53608655312472 935 54058984998427 936 54512624046205 937 54969587543697 938 55429902110195 939 55893583004766 940 56360657112625 941 56831139863764 942 57305058413271 943 57782428365338 944 58263277145336 945 58747620531383 946 59235486223042 947 59726890175805 948 60221860363764 949 60720412919491 950 61222576095638 951 61728366205257 952 62237811779938 953 62750929312950 954 63267747618865 955 63788283374636 956 64312565678175 957 64840611389890 958 65372449895093 959 65908098241119 960 66447586101134 961 66990930709094 962 67538162030146 963 68089297488462 964 68644367341495 965 69203389203416 966 69766393628182 967 70333398423453 968 70904434440167 969 71479519679234 970 72058685292729 971 72641949478481 972 73229343690104 973 73820886322087 974 74416609133865 975 75016530720206 976 75620683146812 977 76229085208503 978 76841769281544 979 77458754364496 980 78080073144612 981 78705744824003 982 79335802405222 983 79970265297625 984 80609166819590 985 81252526587448 986 81900378239784 987 82552741603725 988 83209650638456 989 83871125381722 990 84537200117763 991 85207895098657 992 85883244934248 993 86563270090747 994 87248005508015 995 87937471870294 996 88631704447935 997 89330724142991 998 90034566560846 999 90743252825212 1000 91456818877024