0 1 1 4 2 13 3 36 4 87 5 190 6 386 7 734 8 1324 9 2284 10 3790 11 6080 12 9473 13 14378 14 21323 15 30974 16 44159 17 61898 18 85440 19 116286 20 156240 21 207446 22 272432 23 354162 24 456097 25 582238 26 737205 27 926298 28 1155567 29 1431892 30 1763074 31 2157904 32 2626276 33 3179278 34 3829294 35 4590118 36 5477081 37 6507152 38 7699091 39 9073576 40 10653343 41 12463340 42 14530896 43 16885860 44 19560800 45 22591172 46 26015504 47 29875596 48 34216737 49 39087888 50 44541933 51 50635896 52 57431175 53 64993794 54 73394674 55 82709866 56 93020860 57 104414856 58 116985054 59 130830964 60 146058737 61 162781454 62 181119499 63 201200890 64 223161631 65 247146086 66 273307376 67 301807730 68 332818928 69 366522698 70 403111136 71 442787150 72 485764929 73 532270362 74 582541557 75 636829310 76 695397599 77 758524104 78 826500754 79 899634220 80 978246516 81 1062675546 82 1153275678 83 1250418346 84 1354492681 85 1465906084 86 1585084915 87 1712475124 88 1848542911 89 1993775416 90 2148681440 91 2313792104 92 2489661632 93 2676868072 94 2876014048 95 3087727544 96 3312662721 97 3551500668 98 3804950285 99 4073749100 100 4358664119 101 4660492710 102 4980063522 103 5318237334 104 5675908044 105 6054003588 106 6453486894 107 6875356872 108 7320649441 109 7790438482 110 8285836939 111 8807997846 112 9358115391 113 9937426018 114 10547209568 115 11188790342 116 11863538320 117 12572870302 118 13318251088 119 14101194698 120 14923265633 121 15786080054 122 16691307125 123 17640670274 124 18635948495 125 19678977692 126 20771652066 127 21915925416 128 23113812612 129 24367390982 130 25678801742 131 27050251470 132 28484013625 133 29982429976 134 31547912211 135 33182943456 136 34890079839 137 36671952100 138 38531267248 139 40470810124 140 42493445152 141 44602117996 142 46799857264 143 49089776260 144 51475074785 145 53959040840 146 56545052525 147 59236579840 148 62037186535 149 64950532010 150 67980373266 151 71130566754 152 74405070428 153 77807945696 154 81343359422 155 85015585980 156 88829009361 157 92788125174 158 96897542859 159 101161987794 160 105586303455 161 110175453630 162 114934524688 163 119868727738 164 124983401008 165 130284012114 166 135776160384 167 141465579238 168 147358138625 169 153459847346 170 159776855605 171 166315457446 172 173082093247 173 180083352272 174 187325975282 175 194816857028 176 202563048980 177 210571761938 178 218850368702 179 227406406802 180 236247581289 181 245381767404 182 254817013491 183 264561543788 184 274623761279 185 285012250608 186 295735781056 187 306803309392 188 318223982976 189 330007142736 190 342162326208 191 354699270640 192 367627916161 193 380958408820 194 394701103885 195 408866569012 196 423465587479 197 438509161486 198 454008515522 199 469975099598 200 486420592748 201 503356906396 202 520796187790 203 538750823504 204 557233443009 205 576256922106 206 595834386635 207 615979216046 208 636705047039 209 658025777274 210 679955569152 211 702508853454 212 725700333264 213 749544987750 214 774058076016 215 799255141026 216 825152013601 217 851764816270 218 879109967413 219 907204185258 220 936064491951 221 965708217700 222 996153004994 223 1027416812672 224 1059517920292 225 1092474932350 226 1126306782574 227 1161032738294 228 1196672404889 229 1233245730080 230 1270773008531 231 1309274886296 232 1348772365343 233 1389286808156 234 1430839942416 235 1473453865524 236 1517151049440 237 1561954345364 238 1607886988496 239 1654972602876 240 1703235206305 241 1752699215104 242 1803389449197 243 1855331137032 244 1908549920583 245 1963071860434 246 2018923440946 247 2076131575258 248 2134723610620 249 2194727333560 250 2256170975134 251 2319083216260 252 2383493193137 253 2449430502494 254 2516925207179 255 2586007841578 256 2656709417119 257 2729061427862 258 2803095856176 259 2878845178242 260 2956342369904 261 3035620912346 262 3116714797856 263 3199658535678 264 3284487157953 265 3371236225482 266 3459941833845 267 3550640619342 268 3643369765023 269 3738167006808 270 3835070639698 271 3934119523804 272 4035353090740 273 4138811349834 274 4244534894430 275 4352564908282 276 4462943172041 277 4575712069556 278 4690914594547 279 4808594357092 280 4928795590207 281 5051563156520 282 5176942555040 283 5304979927736 284 5435722066496 285 5569216419896 286 5705511100064 287 5844654889640 288 5986697248833 289 6131688322284 290 6279678946317 291 6430720655996 292 6584865692279 293 6742167009270 294 6902678281570 295 7066453911430 296 7233549036300 297 7404019536180 298 7577922041070 299 7755313938520 300 7936253381281 301 8120799294754 302 8309011384843 303 8500950145606 304 8696676867007 305 8896253642770 306 9099743378336 307 9307209798614 308 9518717456144 309 9734331739054 310 9954118879120 311 10178145959930 312 10406480925153 313 10639192586598 314 10876350632693 315 11118025636754 316 11364289065359 317 11615213286828 318 11870871579810 319 12131338141656 320 12396688097220 321 12666997507446 322 12942343378062 323 13222803668382 324 13508457300217 325 13799384166568 326 14095665140755 327 14397382085328 328 14704617861087 329 15017456336212 330 15335982395504 331 15660281949404 332 15990441943456 333 16326550367548 334 16668696265264 335 17016969743348 336 17371461981281 337 17732265240632 338 18099472874861 339 18473179338896 340 18853480198823 341 19240472141690 342 19634252985426 343 20034921688530 344 20442578360220 345 20857324270352 346 21279261859454 347 21708494748876 348 22145127751057 349 22589266879558 350 23041019359563 351 23500493638146 352 23967799394655 353 24443047551214 354 24926350283344 355 25417821030346 356 25917574506160 357 26425726709986 358 26942394937024 359 27467697789334 360 28001755186817 361 28544688377954 362 29096619951029 363 29657673845110 364 30227975361151 365 30807651173216 366 31396829339826 367 31995639315060 368 32604211960148 369 33222679554818 370 33851175808766 371 34489835873250 372 35138796352809 373 35798195316732 374 36468172311027 375 37148868370140 376 37840426028799 377 38542989333984 378 39256703857024 379 39981716705440 380 40718176535296 381 41466233563296 382 42226039579008 383 42997747957216 384 43781513670401 385 44577493300964 386 45385845053965 387 46206728769604 388 47040305935831 389 47886739701086 390 48746194887170 391 49618838001854 392 50504837252012 393 51404362556492 394 52317585559118 395 53244679641824 396 54185819937921 397 55141183345098 398 56110948538955 399 57095295986270 400 58094407958399 401 59108468544810 402 60137663666752 403 61182181090654 404 62242210442064 405 63317943219318 406 64409572807344 407 65517294491602 408 66641305472161 409 67781804877502 410 68938993778869 411 70113075204346 412 71304254153071 413 72512737609588 414 73738734558338 415 74982455997872 416 76244114955620 417 77523926502382 418 78822107766958 419 80138877950918 420 81474458343513 421 82829072336304 422 84202945438355 423 85596305291144 424 87009381683615 425 88442406567372 426 89895614072016 427 91369240520196 428 92863524443232 429 94378706596452 430 95915029974672 431 97472739827820 432 99052083676705 433 100653311328496 434 102276674892781 435 103922428797336 436 105590829804039 437 107282137024930 438 108996611938418 439 110734518405194 440 112496122684732 441 114281693451496 442 116091501811294 443 117925821317780 444 119784927989105 445 121669100324270 446 123578619320075 447 125513768487770 448 127474833869855 449 129462104057030 450 131475870205296 451 133516426052754 452 135584067937008 453 137679094812266 454 139801808266592 455 141952512539310 456 144131514538561 457 146339123858554 458 148575652797429 459 150841416374814 460 153136732349535 461 155461921237480 462 157817306329618 463 160203213709708 464 162619972272628 465 165067913742394 466 167547372690334 467 170058686553418 468 172602195652745 469 175178243211716 470 177787175374835 471 180429341226196 472 183105092808127 473 185814785139992 474 188558776237152 475 191337427129608 476 194151101881280 477 197000167608968 478 199884994501472 479 202805955838872 480 205763428011969 481 208757790541404 482 211789426097421 483 214858720519308 484 217966062834999 485 221111845280838 486 224296463321506 487 227520315669622 488 230783804305996 489 234087334499556 490 237431314827438 491 240816157195240 492 244242276857441 493 247710092437490 494 251220025948555 495 254772502813942 496 258367951887679 497 262006805475266 498 265689499354592 499 269416472796518 500 273188168586128 501 277005033043646 502 280867516045520 503 284776071045674 504 288731155096929 505 292733228872086 506 296782756685685 507 300880206515426 508 305026050023759 509 309220762579644 510 313464823280482 511 317758714973704 512 322102924279044 513 326497941610470 514 330944261198286 515 335442381111406 516 339992803279801 517 344596033516600 518 349252581540883 519 353962961000128 520 358727689492831 521 363547288591300 522 368422283864624 523 373353204901292 524 378340585332512 525 383384962855180 526 388486879255024 527 393646880429924 528 398865516413409 529 404143341397800 530 409480913758061 531 414878796075296 532 420337555160423 533 425857762078026 534 431439992170386 535 437084825081154 536 442792844779740 537 448564639585344 538 454400802191166 539 460301929688796 540 466268623592785 541 472301489864854 542 478401138938827 543 484568185745202 544 490803249735903 545 497106954909214 546 503479929834896 547 509922807678938 548 516436226229040 549 523020827919730 550 529677259857664 551 536406173847110 552 543208226415617 553 550084078839314 554 557034397168949 555 564059852255558 556 571161119776319 557 578338880260592 558 585593819116146 559 592926626655012 560 600337998120084 561 607828633711346 562 615399238612286 563 623050523016498 564 630783202154473 565 638597996320012 566 646495630897395 567 654476836388172 568 662542348438143 569 670692907864528 570 678929260683328 571 687252158136304 572 695662356718720 573 704160618206704 574 712747709684800 575 721424403573712 576 730191477658241 577 739049715114836 578 747999904539917 579 757042839977812 580 766179320948887 581 775410152477870 582 784736145122370 583 794158115001006 584 803676883822316 585 813293278913276 586 823008133248014 587 832822285476720 588 842736579954753 589 852751866771354 590 862869001779147 591 873088846623246 592 883412268770559 593 893840141539290 594 904373344128640 595 915012761648110 596 925759285147600 597 936613811647110 598 947577244166640 599 958650491756290 600 969834469526561 601 981130098678254 602 992538306533173 603 1004060026564426 604 1015696198426927 605 1027447767988100 606 1039315687358786 607 1051300914923744 608 1063404415372964 609 1075627159732574 610 1087970125395950 611 1100434296155030 612 1113020662231833 613 1125730220309568 614 1138563973564563 615 1151522931697784 616 1164608110966559 617 1177820534216508 618 1191161230913680 619 1204631237176276 620 1218231595807200 621 1231963356326196 622 1245827575002192 623 1259825314885852 624 1273957645842337 625 1288225644583648 626 1302630394701805 627 1317172986701608 628 1331854518033607 629 1346676093127282 630 1361638823424434 631 1376743827412154 632 1391992230656636 633 1407385165836568 634 1422923772776734 635 1438609198481828 636 1454442597170481 637 1470425130308862 638 1486557966645131 639 1502842282243466 640 1519279260518303 641 1535870092268790 642 1552615975713456 643 1569518116524450 644 1586577727862640 645 1603796030412282 646 1621174252415904 647 1638713629709406 648 1656415405757377 649 1674280831687978 650 1692311166328693 651 1710507676241646 652 1728871635759135 653 1747404327019384 654 1766107040002514 655 1784981072566076 656 1804027730481460 657 1823248327469866 658 1842644185238494 659 1862216633516954 660 1881967010093897 661 1901896660853204 662 1922006939811059 663 1942299209152580 664 1962774839268671 665 1983435208793096 666 2004281704639776 667 2025315722039640 668 2046538664578368 669 2067951944233688 670 2089556981412896 671 2111355204990600 672 2133348052346689 673 2155536969403852 674 2177923410665997 675 2200508839256220 676 2223294726954999 677 2246282554238614 678 2269473810317794 679 2292869993175910 680 2316472609608076 681 2340283175259796 682 2364303214665838 683 2388534261289336 684 2412977857561121 685 2437635554918594 686 2462508913845515 687 2487599503911334 688 2512908903810751 689 2538438701403506 690 2564190493754400 691 2590165887172854 692 2616366497253392 693 2642793948915662 694 2669449876444688 695 2696335923531354 696 2723453743313121 697 2750804998414278 698 2778391360987125 699 2806214512752690 700 2834276145041679 701 2862577958835660 702 2891121664808482 703 2919908983367224 704 2948941644694084 705 2978221388787798 706 3007749965505294 707 3037529134603582 708 3067560665781881 709 3097846338723272 710 3128387943137299 711 3159187278802096 712 3190246155606751 713 3221566393593908 714 3253149823002608 715 3284998284310652 716 3317113628277920 717 3349497715989212 718 3382152418897328 719 3415079618866388 720 3448281208215393 721 3481759089761304 722 3515515176863085 723 3549551393465264 724 3583869674141735 725 3618471964139802 726 3653360219424466 727 3688536406722226 728 3724002503565852 729 3759760498338672 730 3795812390319102 731 3832160189725420 732 3868805917760785 733 3905751606657766 734 3942999299723851 735 3980551051386466 736 4018408927238239 737 4056575004082510 738 4095051369979088 739 4133840124289514 740 4172943377723312 741 4212363252383746 742 4252101881813824 743 4292161411042550 744 4332543996631425 745 4373251806720450 746 4414287021075125 747 4455651831132950 748 4497348440050175 749 4539379062748800 750 4581745925963826 751 4624451268290004 752 4667497340229588 753 4710886404239586 754 4754620734779262 755 4798702618357890 756 4843134353582761 757 4887918251206684 758 4933056634176499 759 4978551837681084 760 5024406209199615 761 5070622108550080 762 5117201907938048 763 5164147992004928 764 5211462757877248 765 5259148615215424 766 5307207986262784 767 5355643305894848 768 5404457021668865 769 5453651593872836 770 5503229495575565 771 5553193212676196 772 5603545243954007 773 5654288101118462 774 5705424308859522 775 5756956404897438 776 5808886940033580 777 5861218478200748 778 5913953596513742 779 5967094885320192 780 6020644948251649 781 6074606402274154 782 6128981877739851 783 6183774018438078 784 6238985481646719 785 6294618938183818 786 6350677072459456 787 6407162582527102 788 6464078180136016 789 6521426590783126 790 6579210553765168 791 6637432822231090 792 6696096163234721 793 6755203357786910 794 6814757200908725 795 6874760501684122 796 6935216083312879 797 6996126783163796 798 7057495452828162 799 7119324958172688 800 7181618179393508 801 7244378011069646 802 7307607362216750 803 7371309156341094 804 7435486331493849 805 7500141840324816 806 7565278650137235 807 7630899742942056 808 7697008115512479 809 7763606779438764 810 7830698761183312 811 7898287102135204 812 7966374858665824 813 8034965102183940 814 8104060919191056 815 8173665411337036 816 8243781695476001 817 8314412903721680 818 8385562183503853 819 8457232697624248 820 8529427624312711 821 8602150157283650 822 8675403505792754 823 8749190894693162 824 8823515564492732 825 8898380771410760 826 8973789787434974 827 9049745900378804 828 9126252413938929 829 9203312647752270 830 9280929937454091 831 9359107634735546 832 9437849107401503 833 9517157739428646 834 9597036931023856 835 9677490098682034 836 9758520675245040 837 9840132109960074 838 9922327868538336 839 10005111433213966 840 10088486302803265 841 10172455992763354 842 10257024035251957 843 10342193979186622 844 10427969390304223 845 10514353851220744 846 10601350961491346 847 10688964337669868 848 10777197613369460 849 10866054439322650 850 10955538483441694 851 11045653430879210 852 11136402984089097 853 11227790862886884 854 11319820804511219 855 11412496563684788 856 11505821912675519 857 11599800641358072 858 11694436557275616 859 11789733485701032 860 11885695269699264 861 11982325770189096 862 12079628866005216 863 12177608453960568 864 12276268448908993 865 12375612783807292 866 12475645409778445 867 12576370296174252 868 12677791430638263 869 12779912819168998 870 12882738486183458 871 12986272474580054 872 13090518845802700 873 13195481679904324 874 13301165075610670 875 13407573150384392 876 13514710040489441 877 13622579901054866 878 13731186906139787 879 13840535248797782 880 13950629141141567 881 14061472814407970 882 14173070519023200 883 14285426524667526 884 14398545120341136 885 14512430614429406 886 14627087334768464 887 14742519628711050 888 14858731863192673 889 14975728424797174 890 15093513719823477 891 15212092174351746 892 15331468234309839 893 15451646365540060 894 15572631053866210 895 15694426805160040 896 15817038145408900 897 15940469620782790 898 16064725797701710 899 16189811262903310 900 16315730623510841 901 16442488507100504 902 16570089561770003 903 16698538456206496 904 16827839879754847 905 16957998542486180 906 17089019175266736 907 17220906529826124 908 17353665378826784 909 17487300515932844 910 17621816755879280 911 17757218934541380 912 17893511909004513 913 18030700557633288 914 18168789780141933 915 18307784497664064 916 18447689652822759 917 18588510209800938 918 18730251154412050 919 18872917494170146 920 19016514258361180 921 19161046498113696 922 19306519286469822 923 19452937718456572 924 19600306911157457 925 19748632003783478 926 19897918157745355 927 20048170556725138 928 20199394406748127 929 20351594936255102 930 20504777396174864 931 20658947059996154 932 20814109223840816 933 20970269206536338 934 21127432349688704 935 21285604017755558 936 21444789598119681 937 21604994501161842 938 21766224160334901 939 21928484032237286 940 22091779596686783 941 22256116356794640 942 22421499839039986 943 22587935593343620 944 22755429193143060 945 22923986235466962 946 23093612341009854 947 23264313154207186 948 23436094343310697 949 23608961600463148 950 23782920641774323 951 23957977207396396 952 24134137061599615 953 24311405992848304 954 24489789813877184 955 24669294361767056 956 24849925498021760 957 25031689108644496 958 25214591104214464 959 25398637419963824 960 25583834015854977 961 25770186876657204 962 25957702012024589 963 26146385456573300 964 26336243269959191 965 26527281536955726 966 26719506367532226 967 26912923896931470 968 27107540285748588 969 27303361720009308 970 27500394411248526 971 27698644596589200 972 27898118538821569 973 28098822526481722 974 28300762873931467 975 28503945921437550 976 28708378035251199 977 28914065607687994 978 29121015057208064 979 29329232828495630 980 29538725392539856 981 29749499246715046 982 29961560914861168 983 30174916947364706 984 30389573921239841 985 30605538440208974 986 30822817134784565 987 31041416662350314 988 31261343707242671 989 31482604980832676 990 31705207221608130 991 31929157195255104 992 32154461694740772 993 32381127540395582 994 32609161579995758 995 32838570688846134 996 33069361769863321 997 33301541753658208 998 33535117598619795 999 33770096290998360 1000 34006484844988959