0 1 1 3 2 7 3 20 4 49 5 110 6 227 7 435 8 786 9 1358 10 2259 11 3621 12 5627 13 8538 14 12655 15 18318 16 26049 17 36487 18 50236 19 68131 20 91412 21 121207 22 158659 23 205768 24 264786 25 337240 26 425738 27 534408 28 665866 29 822789 30 1011364 31 1237211 32 1502645 33 1814854 34 2184786 35 2615980 36 3114026 37 3695678 38 4371144 39 5141655 40 6026376 41 7049232 42 8209662 43 9520807 44 11022840 45 12726844 46 14629485 47 16779551 48 19219417 49 21930272 50 24947995 51 28357075 52 32151440 53 36323283 54 40986831 55 46197600 56 51892652 57 58170271 58 65183726 59 72863495 60 81216617 61 90483086 62 100693991 63 111711963 64 123781432 65 137134231 66 151550380 67 167120582 68 184291898 69 202967522 70 222928886 71 244713513 72 268585980 73 294051194 74 321446135 75 351500159 76 383781670 77 418066096 78 455398757 79 495907725 80 538699526 81 584662401 82 634810834 83 688047808 84 744391503 85 805645410 86 871420984 87 940401973 88 1014504985 89 1094842700 90 1179231122 91 1268464303 92 1365295842 93 1468149286 94 1575529037 95 1691005697 96 1815245286 97 1944596326 98 2081539697 99 2229733229 100 2385430794 101 2547696266 102 2722411033 103 2908699015 104 3101371478 105 3305905107 106 3526301257 107 3755473486 108 3994514003 109 4252052776 110 4523875920 111 4803909782 112 5102215695 113 5421702286 114 5750934070 115 6095381176 116 6466229777 117 6853442356 118 7251930799 119 7677890539 120 8130446707 121 8593603671 122 9080393132 123 9603158756 124 10143188799 125 10699920587 126 11296622204 127 11924436414 128 12564285157 129 13240425836 130 13963059025 131 14702375736 132 15467764209 133 16289046917 134 17143772687 135 18013945316 136 18938446292 137 19919449435 138 20915387679 139 21952676364 140 23064626626 141 24208886105 142 25376220274 143 26622084546 144 27931751533 145 29254782710 146 30642482882 147 32124807445 148 33634092693 149 35181346390 150 36837497560 151 38559309979 152 40295817396 153 42130284338 154 44077540128 155 46042676141 156 48071575277 157 50244566038 158 52476952823 159 54732525314 160 57130512857 161 59653279809 162 62183581536 163 64818107844 164 67633486678 165 70492212358 166 73395419939 167 76496385930 168 79722616876 169 82949795489 170 86339554694 171 89942861422 172 93564311649 173 97270866618 174 101238776156 175 105315699048 176 109398485949 177 113721901182 178 118279444943 179 122825001888 180 127522134209 181 132546561210 182 137643582375 183 142772964481 184 148239935372 185 153939761579 186 159601315412 187 165512103461 188 171808589487 189 178121627246 190 184526499990 191 191380121048 192 198433808914 193 205440281590 194 212827563633 195 220637482385 196 228395024594 197 236347967866 198 244864987485 199 253511024911 200 262135650760 201 271304989684 202 280895567088 203 290366484416 204 300189266689 205 310679220515 206 321188647403 207 331756651131 208 343057726902 209 354723262052 210 366226081066 211 378294369888 212 391097754324 213 403782529594 214 416678732770 215 430504647876 216 444570174024 217 458483271901 218 473229825763 219 488716288043 220 503940386196 221 519616162283 222 536400529451 223 553229030190 224 570001116834 225 587916543475 226 606484721144 227 624677392533 228 643656258717 229 663868575389 230 683872453467 231 704032624399 232 725662879253 233 747743897402 234 769414087266 235 792294990794 236 816435703653 237 840092486223 238 864259008351 239 890199353320 240 916265775727 241 942016587300 242 969473635119 243 998071323697 244 1025942678560 245 1054829548459 246 1085715627739 247 1116296950239 248 1146839043065 249 1179616402556 250 1213230201062 251 1245982546022 252 1280402654842 253 1316900617860 254 1352605317807 255 1388768059742 256 1427669438194 257 1466899603673 258 1505324337594 259 1546187659994 260 1588986768345 261 1630529528435 262 1673268636830 263 1719142106597 264 1764650516006 265 1809682107390 266 1857987072652 267 1907799436703 268 1956030793490 269 2006431063494 270 2060151779067 271 2112692495368 272 2165422806041 273 2222239691739 274 2279811801761 275 2335746849952 276 2395018108673 277 2457473587848 278 2517931540641 279 2579618761850 280 2646065817188 281 2712204895303 282 2777048155421 283 2846511980816 284 2918596606195 285 2988030253721 286 3060100777040 287 3137316309832 288 3212931923308 289 3288096114964 290 3369161292741 291 3451787255250 292 3531469815052 293 3615510976861 294 3704627570796 295 3790785894153 296 3877902566245 297 3972029574419 298 4066159425700 299 4157613817875 300 4255354547611 301 4357484564772 302 4455469436207 303 4556389465558 304 4665047881891 305 4771749883462 306 4876774015625 307 4990050253601 308 5106293287515 309 5217665845295 310 5334447639582 311 5459074393335 312 5579597402646 313 5700277243340 314 5830981438196 315 5962462351336 316 6089111168493 317 6223993371549 318 6365963960742 319 6501823915142 320 6640532093912 321 6790551031435 322 6938491526948 323 7082667778597 324 7238022201778 325 7398649941647 326 7551716040560 327 7711093800876 328 7882244644339 329 8048064628270 330 8212399049455 331 8390661487926 332 8571238585430 333 8743806315362 334 8926725737718 335 9120705876253 336 9306144165021 337 9493643390105 338 9697226173825 339 9899113141324 340 10093954871606 341 10303456283496 342 10521827439529 343 10729065298263 344 10943085494479 345 11174283631718 346 11399043380743 347 11619431946664 348 11858631990253 349 12102859391198 350 12334627603168 351 12578822795655 352 12839733356398 353 13089296661105 354 13338999515613 355 13610972101382 356 13882531418794 357 14142185235268 358 14420425198658 359 14712906706506 360 14989746983577 361 15272989162220 362 15580632638513 363 15881182721504 364 16172737054503 365 16488987998737 366 16814689484374 367 17121979325564 368 17443373492113 369 17789288250847 370 18120893407523 371 18449015813619 372 18807183012057 373 19167664916311 374 19509389090243 375 19873828509793 376 20260239033898 377 20625612247281 378 20995572848703 379 21399318553781 380 21796268479527 381 22177279424644 382 22589785615749 383 23018547241949 384 23421276475487 385 23838854431086 386 24291420036999 387 24726944797479 388 25152957419132 389 25618477316783 390 26091203014742 391 26535922164190 392 27007266509856 393 27511341254360 394 27988298902923 395 28465825539904 396 28988989029756 397 29507309212335 398 29999788425287 399 30531225259376 400 31088914041353 401 31611235646341 402 32147462894662 403 32732333636403 404 33298270452580 405 33845419371917 406 34443195612107 407 35056137869468 408 35629083846774 409 36231692001213 410 36881563221952 411 37497974445321 412 38107761592760 413 38777730604367 414 39447399529169 415 40077707702554 416 40754627342419 417 41471929113982 418 42142956801452 419 42824250224078 420 43571533642312 421 44299702566790 422 44995612621095 423 45754705376531 424 46541095100735 425 47272543311631 426 48034877352814 427 48863564774066 428 49652887560931 429 50424047018001 430 51272707523357 431 52129395889127 432 52928970218289 433 53782237888273 434 54695206651980 435 55549830220275 436 56407092653557 437 57351802686707 438 58280116347072 439 59157491941424 440 60111550109492 441 61110499439297 442 62036608071167 443 62991734227956 444 64037639697471 445 65039762284556 446 66006484119489 447 67070659149521 448 68156440421905 449 69162633292814 450 70227901721351 451 71378512406162 452 72458302511994 453 73527536541456 454 74710051898734 455 75883322296686 456 76980761328534 457 78168480667730 458 79425612186647 459 80589368878115 460 81775523336232 461 83082924668380 462 84345068820466 463 85547390652147 464 86869293894827 465 88233368823373 466 89490407987195 467 90808640842901 468 92245337631419 469 93599535303317 470 94922554688114 471 96389081679280 472 97859855356675 473 99222791849141 474 100688406550635 475 102256477918208 476 103708754464550 477 105169991363642 478 106789531610993 479 108367205173767 480 109851909155680 481 111479617704442 482 113179038949427 483 114739116489648 484 116357175502875 485 118135408722826 486 119821990140410 487 121447250021053 488 123250291255494 489 125079696518777 490 126761486140577 491 128555304970053 492 130494818350048 493 132295529241425 494 134082471925233 495 136071642190561 496 138029624177747 497 139851281457489 498 141839235202630 499 143939617544394 500 145864110439912 501 147835425381623 502 150018171253885 503 152104973179615 504 154088542421416 505 156287375484150 506 158545963427216 507 160609122916285 508 162788125559677 509 165167911977680 510 167387266739420 511 169557987029425 512 171981603261020 513 174394941073091 514 176617122570418 515 179026661548903 516 181602863470818 517 183963682568365 518 186349028067093 519 189007287592510 520 191573173416723 521 193979873835686 522 196641047241485 523 199409607406198 524 201927214052027 525 204555728395152 526 207453498855650 527 210173331515204 528 212794385028223 529 215725062230462 530 218680057531381 531 221376727264964 532 224276682978819 533 227413446496158 534 230294503773176 535 233162911537003 536 236376187707870 537 239512228804813 538 242416965956208 539 245614823703602 540 248985155260946 541 252042406037553 542 255192892711424 543 258695750358510 544 262010902574520 545 265158550297390 546 268677181381342 547 272272339176317 548 275529441481723 549 278996803989170 550 282789341272138 551 286288117591043 552 289717956767270 553 293574712863905 554 297385355660646 555 300874663693782 556 304691914818438 557 308767535302448 558 312463456859513 559 316217433386307 560 320422344018788 561 324442071862486 562 328203719041465 563 332399969937006 564 336746885132277 565 340664129701082 566 344784818976999 567 349339336939489 568 353568523948185 569 357648785946836 570 362246891719345 571 366851077957947 572 371024896491429 573 375553252143476 574 380450028111209 575 384899319090800 576 389348461710558 577 394362683879865 578 399212052102005 579 403687934597315 580 408660772291492 581 413884929470606 582 418577768542179 583 423447545725770 584 428881703546888 585 433970884524662 586 438802710893138 587 444249888241636 588 449782094463036 589 454755788219198 590 460096696022627 591 465943383256455 592 471278360117465 593 476525826109303 594 482467307038124 595 488288529600427 596 493593674275121 597 499451950672849 598 505693415552987 599 511295196181650 600 517020757552032 601 523464056750305 602 529561383082040 603 535259875103874 604 541674160646688 605 548285323479451 606 554191945038972 607 560457458844182 608 567396143767917 609 573768750674446 610 579930767550906 611 586928516744321 612 593882199559092 613 600148678210018 614 607011800509042 615 614425785413280 616 621090046827771 617 627790350233580 618 635384462209426 619 642658275357166 620 649354621581904 621 656864870015699 622 664723167013482 623 671715949525251 624 679029781738459 625 687216220857692 626 694800053383667 627 702007823338991 628 710202281811164 629 718468523422301 630 725848009103356 631 733846736571305 632 742604027319194 633 750506899804786 634 758314778830062 635 767213821130823 636 775854164686886 637 783698117040422 638 792444576640608 639 801736037758664 640 809991088724872 641 818489901299270 642 828093761931071 643 837086044282569 644 845488011601431 645 855031441598330 646 864810749825176 647 873477370222423 648 882754787452376 649 893042025313554 650 902384673580951 651 911448798230148 652 921819578218084 653 932039541884933 654 941202261156936 655 951337262024471 656 962266193274764 657 971985343719138 658 981820341855337 659 993025354777162 660 1003648802385774 661 1013413327084398 662 1024470255332820 663 1035984243111412 664 1046137707646497 665 1056850435412216 666 1068870254849105 667 1079881296089038 668 1090368539880581 669 1102390792398727 670 1114427630887837 671 1125104907418310 672 1136793714583662 673 1149582922531469 674 1160996668751310 675 1172335567559574 676 1185339610240455 677 1197844104644813 678 1209162576994810 679 1221910333678002 680 1235402165796177 681 1247271121944496 682 1259590837894547 683 1273561868953515 684 1286499684194415 685 1298597955577976 686 1312464609498156 687 1326580584519923 688 1338996420314760 689 1352418316592454 690 1367309130899024 691 1380679589133273 692 1393709027055254 693 1408724165144446 694 1423388166342812 695 1436478583463227 696 1451107989813398 697 1466842562704542 698 1480688114681499 699 1494803465671114 700 1510960219431173 701 1526115067696846 702 1540036657194959 703 1555954175152451 704 1572437077282548 705 1586847592249828 706 1602197268901385 707 1619449370062431 708 1635073148901484 709 1650001621711907 710 1667254146395673 711 1684385770564896 712 1699496776554192 713 1716213047444667 714 1734476894701879 715 1750596196289194 716 1766715190770668 717 1785307856769802 718 1803003696717207 719 1818989178826302 720 1837178025492625 721 1856341344803221 722 1873038942512319 723 1890528289078113 724 1910419358958635 725 1928630241488841 726 1945691626431221 727 1965422135579332 728 1985359834511303 729 2002775199286213 730 2021799143225278 731 2042900070241740 732 2061629883504909 733 2079982855453666 734 2101277050997181 735 2121872975012530 736 2140195685284222 737 2160890992219451 738 2183073721780677 739 2202391420829668 740 2222251817306114 741 2245077041480836 742 2266248359581351 743 2285706089781172 744 2308169671543161 745 2331282463865292 746 2351325944661733 747 2372895559853819 748 2397162023779810 749 2418882116764861 750 2439725351522769 751 2464001874353757 752 2487893065768809 753 2508864147930395 754 2532316658371440 755 2557882730516274 756 2580198539959560 757 2602683762124341 758 2628755226015190 759 2653301804495696 760 2675453737435564 761 2700920327289212 762 2727607549124286 763 2750648043898695 764 2775020624584262 765 2802800889668509 766 2827937131318516 767 2851557236798530 768 2879111885020225 769 2906730021323650 770 2930704005619896 771 2957181401573039 772 2986518771022050 773 3012259964777376 774 3037649815358918 775 3067295850042748 776 3095675400638253 777 3120859399686462 778 3149614396770479 779 3180304960173701 780 3206761825145549 781 3234216706420974 782 3265877818670483 783 3294904819899756 784 3321623912836738 785 3352767448769869 786 3384580493243487 787 3411961326442832 788 3441750060862320 789 3475269463825177 790 3504916588105446 791 3533521363238993 792 3567085910422183 793 3599799765902814 794 3628399980415778 795 3660745226707010 796 3695896396318604 797 3726244764204939 798 3757086842979677 799 3793013482886580 800 3826456629495276 801 3856638384913683 802 3891696733112820 803 3928208082728989 804 3959455485434952 805 3992863261165824 806 4030996696775043 807 4065087127381617 808 4097253018093680 809 4135095097572274 810 4172688194242778 811 4205141981236832 812 4241397228926096 813 4281492947150822 814 4316268853493230 815 4350833024466390 816 4391426313191428 817 4429863040912851 818 4463919621590660 819 4503234407374782 820 4544981393331734 821 4580617374025083 822 4617976427305467 823 4661175425287387 824 4700306281960482 825 4736421791640362 826 4778915169388873 827 4821975212501168 828 4858780591552976 829 4899285608705333 830 4944834417661885 831 4984639520195378 832 5023296158788460 833 5068972510047426 834 5113032687100755 835 5151432526986946 836 5195362082080934 837 5242913848714404 838 5283529159442906 839 5325200516923233 840 5373934272530056 841 5418764497111931 842 5459267927233889 843 5506801097781587 844 5555956878734281 845 5597680354520991 846 5642797842650245 847 5694330470816266 848 5739836128764258 849 5782997739058158 850 5834187864478915 851 5884553173128391 852 5927829534626823 853 5976750521691101 854 6030705336361351 855 6076965618086531 856 6123344497904740 857 6178097973449152 858 6229349387633372 859 6274737404433353 860 6327714018322785 861 6383632891974433 862 6430917420199383 863 6481036936860577 864 6539103639404124 865 6591054109415842 866 6639183231159134 867 6696331422652437 868 6753733667076126 869 6802493828076852 870 6856803665218004 871 6917785734280999 872 6970437074527741 873 7021959591135041 874 7083231703463044 875 7141688882404270 876 7192526124419022 877 7251366013160622 878 7314750583202523 879 7368323400595847 880 7423866492808627 881 7489034255273324 882 7548248762785128 883 7601867194586065 884 7665431024615785 885 7730649336970671 886 7785584192339914 887 7845704487388758 888 7914360375672143 889 7974233983831358 890 8031385295764299 891 8099687327630982 892 8166196160570272 893 8223125779507318 894 8288266758956654 895 8359850854469719 896 8420530847965587 897 8481957604147036 898 8554807339353381 899 8622180799739899 900 8681880145096093 901 8752330744691016 902 8826187713161395 903 8888081501468320 904 8954462730054487 905 9031457504719457 906 9099473201664268 907 9162797210576570 908 9238651600607218 909 9314116458277807 910 9377871405390301 911 9449772073488795 912 9530316127707117 913 9599020387971916 914 9666837602050309 915 9747961491750434 916 9824463684549991 917 9890917162567713 918 9968740259361446 919 10052097055714925 920 10121836852518564 921 10194964529628403 922 10280977773095705 923 10358145996516632 924 10428256660205230 925 10512196343768730 926 10597575831012517 927 10668990613091723 928 10748134392920942 929 10838420360661628 930 10916169548742446 931 10990940661598374 932 11080939816264546 933 11167612860337204 934 11241588241351415 935 11327286170190423 936 11421036801682812 937 11499621364385741 938 11580023961041377 939 11675745820900467 940 11763167870051656 941 11840762129273661 942 11933330623087476 943 12029631961158144 944 12109654499419026 945 12196555207872845 946 12297381184255579 947 12385303335017098 948 12467660277656724 949 12567142906828158 950 12665096946881465 951 12747470374207085 952 12841565313518925 953 12946630158689103 954 13035177672738243 955 13123436512096125 956 13229563979104634 957 13328430263184918 958 13414302501683061 959 13516054949082611 960 13624327101958378 961 13714030239912346 962 13809239482532269 963 13921414210960423 964 14020746607210166 965 14111403613752718 966 14220983916932189 967 14331391009077167 968 14423161358114668 969 14526200089334246 970 14643518904351672 971 14743273165662724 972 14840034495553697 973 14957268124455494 974 15068854237027165 975 15163912095815444 976 15275417520704899 977 15396743244013338 978 15497335378797797 979 15601452075005393 980 15725789557795547 981 15837878338708492 982 15937647721218648 983 16057945729307705 984 16182031998402359 985 16284335312954075 986 16396895836226552 987 16527420447516173 988 16639755015258461 989 16745744401474959 990 16874785710758114 991 17000446230557993 992 17105727478968621 993 17227572540404076 994 17363059578090092 995 17475893846555788 996 17589576168799595 997 17726890619435589 998 17853187839800511 999 17962997618837658 1000 18094640241465872