0 1 1 2 2 7 3 24 4 69 5 170 6 371 7 736 8 1353 9 2338 10 3839 11 6040 12 9165 13 13482 14 19307 15 27008 16 37009 17 49794 18 65911 19 85976 20 110677 21 140778 22 177123 23 220640 24 272345 25 333346 26 404847 27 488152 28 584669 29 695914 30 823515 31 969216 32 1134881 33 1322498 34 1534183 35 1772184 36 2038885 37 2336810 38 2668627 39 3037152 40 3445353 41 3896354 42 4393439 43 4940056 44 5539821 45 6196522 46 6914123 47 7696768 48 8548785 49 9474690 50 10479191 51 11567192 52 12743797 53 14014314 54 15384259 55 16859360 56 18445561 57 20149026 58 21976143 59 23933528 60 26028029 61 28266730 62 30656955 63 33206272 64 35922497 65 38813698 66 41888199 67 45154584 68 48621701 69 52298666 70 56194867 71 60319968 72 64683913 73 69296930 74 74169535 75 79312536 76 84737037 77 90454442 78 96476459 79 102815104 80 109482705 81 116491906 82 123855671 83 131587288 84 139700373 85 148208874 86 157127075 87 166469600 88 176251417 89 186487842 90 197194543 91 208387544 92 220083229 93 232298346 94 245050011 95 258355712 96 272233313 97 286701058 98 301777575 99 317481880 100 333833381 101 350851882 102 368557587 103 386971104 104 406113449 105 426006050 106 446670751 107 468129816 108 490405933 109 513522218 110 537502219 111 562369920 112 588149745 113 614866562 114 642545687 115 671212888 116 700894389 117 731616874 118 763407491 119 796293856 120 830304057 121 865466658 122 901810703 123 939365720 124 978161725 125 1018229226 126 1059599227 127 1102303232 128 1146373249 129 1191841794 130 1238741895 131 1287107096 132 1336971461 133 1388369578 134 1441336563 135 1495908064 136 1552120265 137 1610009890 138 1669614207 139 1730971032 140 1794118733 141 1859096234 142 1925943019 143 1994699136 144 2065405201 145 2138102402 146 2212832503 147 2289637848 148 2368561365 149 2449646570 150 2532937571 151 2618479072 152 2706316377 153 2796495394 154 2889062639 155 2984065240 156 3081550941 157 3181568106 158 3284165723 159 3389393408 160 3497301409 161 3607940610 162 3721362535 163 3837619352 164 3956763877 165 4078849578 166 4203930579 167 4332061664 168 4463298281 169 4597696546 170 4735313247 171 4876205848 172 5020432493 173 5168052010 174 5319123915 175 5473708416 176 5631866417 177 5793659522 178 5959150039 179 6128400984 180 6301476085 181 6478439786 182 6659357251 183 6844294368 184 7033317753 185 7226494754 186 7423893455 187 7625582680 188 7831631997 189 8042111722 190 8257092923 191 8476647424 192 8700847809 193 8929767426 194 9163480391 195 9402061592 196 9645586693 197 9894132138 198 10147775155 199 10406593760 200 10670666761 201 10940073762 202 11214895167 203 11495212184 204 11781106829 205 12072661930 206 12369961131 207 12673088896 208 12982130513 209 13297172098 210 13618300599 211 13945603800 212 14279170325 213 14619089642 214 14965452067 215 15318348768 216 15677871769 217 16044113954 218 16417169071 219 16797131736 220 17184097437 221 17578162538 222 17979424283 223 18387980800 224 18803931105 225 19227375106 226 19658413607 227 20097148312 228 20543681829 229 20998117674 230 21460560275 231 21931114976 232 22409888041 233 22896986658 234 23392518943 235 23896593944 236 24409321645 237 24930812970 238 25461179787 239 26000534912 240 26548992113 241 27106666114 242 27673672599 243 28250128216 244 28836150581 245 29431858282 246 30037370883 247 30652808928 248 31278293945 249 31913948450 250 32559895951 251 33216260952 252 33883168957 253 34560746474 254 35249121019 255 35948421120 256 36658776321 257 37380317186 258 38113175303 259 38857483288 260 39613374789 261 40380984490 262 41160448115 263 41951902432 264 42755485257 265 43571335458 266 44399592959 267 45240398744 268 46093894861 269 46960224426 270 47839531627 271 48731961728 272 49637661073 273 50556777090 274 51489458295 275 52435854296 276 53396115797 277 54370394602 278 55358843619 279 56361616864 280 57378869465 281 58410757666 282 59457438831 283 60519071448 284 61595815133 285 62687830634 286 63795279835 287 64918325760 288 66057132577 289 67211865602 290 68382691303 291 69569777304 292 70773292389 293 71993406506 294 73230290771 295 74484117472 296 75755060073 297 77043293218 298 78348992735 299 79672335640 300 81013500141 301 82372665642 302 83750012747 303 85145723264 304 86559980209 305 87992967810 306 89444871511 307 90915877976 308 92406175093 309 93915951978 310 95445398979 311 96994707680 312 98564070905 313 100153682722 314 101763738447 315 103394434648 316 105045969149 317 106718541034 318 108412350651 319 110127599616 320 111864490817 321 113623228418 322 115404017863 323 117207065880 324 119032580485 325 120880770986 326 122751847987 327 124646023392 328 126563510409 329 128504523554 330 130469278655 331 132457992856 332 134470884621 333 136508173738 334 138570081323 335 140656829824 336 142768643025 337 144905746050 338 147068365367 339 149256728792 340 151471065493 341 153711605994 342 155978582179 343 158272227296 344 160592775961 345 162940464162 346 165315529263 347 167718210008 348 170148746525 349 172607380330 350 175094354331 351 177609912832 352 180154301537 353 182727767554 354 185330559399 355 187962927000 356 190625121701 357 193317396266 358 196040004883 359 198793203168 360 201577248169 361 204392398370 362 207238913695 363 210117055512 364 213027086637 365 215969271338 366 218943875339 367 221951165824 368 224991411441 369 228064882306 370 231171850007 371 234312587608 372 237487369653 373 240696472170 374 243940172675 375 247218750176 376 250532485177 377 253881659682 378 257266557199 379 260687462744 380 264144662845 381 267638445546 382 271169100411 383 274736918528 384 278342192513 385 281985216514 386 285666286215 387 289385698840 388 293143753157 389 296940749482 390 300776989683 391 304652777184 392 308568416969 393 312524215586 394 316520481151 395 320557523352 396 324635653453 397 328755184298 398 332916430315 399 337119707520 400 341365333521 401 345653627522 402 349984910327 403 354359504344 404 358777733589 405 363239923690 406 367746401891 407 372297497056 408 376893539673 409 381534861858 410 386221797359 411 390954681560 412 395733851485 413 400559645802 414 405432404827 415 410352470528 416 415320186529 417 420335898114 418 425399952231 419 430512697496 420 435674484197 421 440885664298 422 446146591443 423 451457620960 424 456819109865 425 462231416866 426 467694902367 427 473209928472 428 478776858989 429 484396059434 430 490067897035 431 495792740736 432 501570961201 433 507402930818 434 513289023703 435 519229615704 436 525225084405 437 531275809130 438 537382170947 439 543544552672 440 549763338873 441 556038915874 442 562371671759 443 568761996376 444 575210281341 445 581716920042 446 588282307643 447 594906841088 448 601590919105 449 608334942210 450 615139312711 451 622004434712 452 628930714117 453 635918558634 454 642968377779 455 650080582880 456 657255587081 457 664493805346 458 671795654463 459 679161553048 460 686591921549 461 694087182250 462 701647759275 463 709274078592 464 716966568017 465 724725657218 466 732551777719 467 740445362904 468 748406848021 469 756436670186 470 764535268387 471 772703083488 472 780940558233 473 789248137250 474 797626267055 475 806075396056 476 814595974557 477 823188454762 478 831853290779 479 840590938624 480 849401856225 481 858286503426 482 867245341991 483 876278835608 484 885387449893 485 894571652394 486 903831912595 487 913168701920 488 922582493737 489 932073763362 490 941642988063 491 951290647064 492 961017221549 493 970823194666 494 980709051531 495 990675279232 496 1000722366833 497 1010850805378 498 1021061087895 499 1031353709400 500 1041729166901 501 1052187959402 502 1062730587907 503 1073357555424 504 1084069366969 505 1094866529570 506 1105749552271 507 1116718946136 508 1127775224253 509 1138918901738 510 1150150495739 511 1161470525440 512 1172879512065 513 1184377978882 514 1195966451207 515 1207645456408 516 1219415523909 517 1231277185194 518 1243230973811 519 1255277425376 520 1267417077577 521 1279650470178 522 1291978145023 523 1304400646040 524 1316918519245 525 1329532312746 526 1342242576747 527 1355049863552 528 1367954727569 529 1380957725314 530 1394059415415 531 1407260358616 532 1420561117781 533 1433962257898 534 1447464346083 535 1461067951584 536 1474773645785 537 1488582002210 538 1502493596527 539 1516509006552 540 1530628812253 541 1544853595754 542 1559183941339 543 1573620435456 544 1588163666721 545 1602814225922 546 1617572706023 547 1632439702168 548 1647415811685 549 1662501634090 550 1677697771091 551 1693004826592 552 1708423406697 553 1723954119714 554 1739597576159 555 1755354388760 556 1771225172461 557 1787210544426 558 1803311124043 559 1819527532928 560 1835860394929 561 1852310336130 562 1868877984855 563 1885563971672 564 1902368929397 565 1919293493098 566 1936338300099 567 1953503989984 568 1970791204601 569 1988200588066 570 2005732786767 571 2023388449368 572 2041168226813 573 2059072772330 574 2077102741435 575 2095258791936 576 2113541583937 577 2131951779842 578 2150490044359 579 2169157044504 580 2187953449605 581 2206879931306 582 2225937163571 583 2245125822688 584 2264446587273 585 2283900138274 586 2303487158975 587 2323208335000 588 2343064354317 589 2363055907242 590 2383183686443 591 2403448386944 592 2423850706129 593 2444391343746 594 2465071001911 595 2485890385112 596 2506850200213 597 2527951156458 598 2549193965475 599 2570579341280 600 2592108000281 601 2613780661282 602 2635598045487 603 2657560876504 604 2679669880349 605 2701925785450 606 2724329322651 607 2746881225216 608 2769582228833 609 2792433071618 610 2815434494119 611 2838587239320 612 2861892052645 613 2885349681962 614 2908960877587 615 2932726392288 616 2956646981289 617 2980723402274 618 3004956415391 619 3029346783256 620 3053895270957 621 3078602646058 622 3103469678603 623 3128497141120 624 3153685808625 625 3179036458626 626 3204549871127 627 3230226828632 628 3256068116149 629 3282074521194 630 3308246833795 631 3334585846496 632 3361092354361 633 3387767154978 634 3414611048463 635 3441624837464 636 3468809327165 637 3496165325290 638 3523693642107 639 3551395090432 640 3579270485633 641 3607320645634 642 3635546390919 643 3663948544536 644 3692527932101 645 3721285381802 646 3750221724403 647 3779337793248 648 3808634424265 649 3838112455970 650 3867772729471 651 3897616088472 652 3927643379277 653 3957855450794 654 3988253154539 655 4018837344640 656 4049608877841 657 4080568613506 658 4111717413623 659 4143056142808 660 4174585668309 661 4206306860010 662 4238220590435 663 4270327734752 664 4302629170777 665 4335125778978 666 4367818442479 667 4400708047064 668 4433795481181 669 4467081635946 670 4500567405147 671 4534253685248 672 4568141375393 673 4602231377410 674 4636524595815 675 4671021937816 676 4705724313317 677 4740632634922 678 4775747817939 679 4811070780384 680 4846602442985 681 4882343729186 682 4918295565151 683 4954458879768 684 4990834604653 685 5027423674154 686 5064227025355 687 5101245598080 688 5138480334897 689 5175932181122 690 5213602084823 691 5251490996824 692 5289599870709 693 5327929662826 694 5366481332291 695 5405255840992 696 5444254153593 697 5483477237538 698 5522926063055 699 5562601603160 700 5602504833661 701 5642636733162 702 5682998283067 703 5723590467584 704 5764414273729 705 5805470691330 706 5846760713031 707 5888285334296 708 5930045553413 709 5972042371498 710 6014276792499 711 6056749823200 712 6099462473225 713 6142415755042 714 6185610683967 715 6229048278168 716 6272729558669 717 6316655549354 718 6360827276971 719 6405245771136 720 6449912064337 721 6494827191938 722 6539992192183 723 6585408106200 724 6631075978005 725 6676996854506 726 6723171785507 727 6769601823712 728 6816288024729 729 6863231447074 730 6910433152175 731 6957894204376 732 7005615670941 733 7053598622058 734 7101844130843 735 7150353273344 736 7199127128545 737 7248166778370 738 7297473307687 739 7347047804312 740 7396891359013 741 7447005065514 742 7497390020499 743 7548047323616 744 7598978077481 745 7650183387682 746 7701664362783 747 7753422114328 748 7805457756845 749 7857772407850 750 7910367187851 751 7963243220352 752 8016401631857 753 8069843551874 754 8123570112919 755 8177582450520 756 8231881703221 757 8286469012586 758 8341345523203 759 8396512382688 760 8451970741689 761 8507721753890 762 8563766576015 763 8620106367832 764 8676742292157 765 8733675514858 766 8790907204859 767 8848438534144 768 8906270677761 769 8964404813826 770 9022842123527 771 9081583791128 772 9140631003973 773 9199984952490 774 9259646830195 775 9319617833696 776 9379899162697 777 9440492020002 778 9501397611519 779 9562617146264 780 9624151836365 781 9686002897066 782 9748171546731 783 9810659006848 784 9873466502033 785 9936595260034 786 10000046511735 787 10063821491160 788 10127921435477 789 10192347585002 790 10257101183203 791 10322183476704 792 10387595715289 793 10453339151906 794 10519415042671 795 10585824646872 796 10652569226973 797 10719650048618 798 10787068380635 799 10854825495040 800 10922922667041 801 10991361175042 802 11060142300647 803 11129267328664 804 11198737547109 805 11268554247210 806 11338718723411 807 11409232273376 808 11480096197993 809 11551311801378 810 11622880390879 811 11694803277080 812 11767081773805 813 11839717198122 814 11912710870347 815 11986064114048 816 12059778256049 817 12133854626434 818 12208294558551 819 12283099389016 820 12358270457717 821 12433809107818 822 12509716685763 823 12585994541280 824 12662644027385 825 12739666500386 826 12817063319887 827 12894835848792 828 12972985453309 829 13051513502954 830 13130421370555 831 13209710432256 832 13289382067521 833 13369437659138 834 13449878593223 835 13530706259224 836 13611922049925 837 13693527361450 838 13775523593267 839 13857912148192 840 13940694432393 841 14023871855394 842 14107445830079 843 14191417772696 844 14275789102861 845 14360561243562 846 14445735621163 847 14531313665408 848 14617296809425 849 14703686489730 850 14790484146231 851 14877691222232 852 14965309164437 853 15053339422954 854 15141783451299 855 15230642706400 856 15319918648601 857 15409612741666 858 15499726452783 859 15590261252568 860 15681218615069 861 15772600017770 862 15864406941595 863 15956640870912 864 16049303293537 865 16142395700738 866 16235919587239 867 16329876451224 868 16424267794341 869 16519095121706 870 16614359941907 871 16710063767008 872 16806208112553 873 16902794497570 874 16999824444575 875 17097299479576 876 17195221132077 877 17293590935082 878 17392410425099 879 17491681142144 880 17591404629745 881 17691582434946 882 17792216108311 883 17893307203928 884 17994857279413 885 18096867895914 886 18199340618115 887 18302277014240 888 18405678656057 889 18509547118882 890 18613883981583 891 18718690826584 892 18823969239869 893 18929720810986 894 19035947133051 895 19142649802752 896 19249830420353 897 19357490589698 898 19465631918215 899 19574256016920 900 19683364500421 901 19792958986922 902 19903041098227 903 20013612459744 904 20124674700489 905 20236229453090 906 20348278353791 907 20460823042456 908 20573865162573 909 20687406361258 910 20801448289259 911 20915992600960 912 21031040954385 913 21146595011202 914 21262656436727 915 21379226899928 916 21496308073429 917 21613901633514 918 21732009260131 919 21850632636896 920 21969773451097 921 22089433393698 922 22209614159343 923 22330317446360 924 22451544956765 925 22573298396266 926 22695579474267 927 22818389903872 928 22941731401889 929 23065605688834 930 23190014488935 931 23314959530136 932 23440442544101 933 23566465266218 934 23693029435603 935 23820136795104 936 23947789091305 937 24075988074530 938 24204735498847 939 24334033122072 940 24463882705773 941 24594286015274 942 24725244819659 943 24856760891776 944 24988836008241 945 25121471949442 946 25254670499543 947 25388433446488 948 25522762582005 949 25657659701610 950 25793126604611 951 25929165094112 952 26065776977017 953 26202964064034 954 26340728169679 955 26479071112280 956 26617994713981 957 26757500800746 958 26897591202363 959 27038267752448 960 27179532288449 961 27321386651650 962 27463832687175 963 27606872243992 964 27750507174917 965 27894739336618 966 28039570589619 967 28185002798304 968 28331037830921 969 28477677559586 970 28624923860287 971 28772778612888 972 28921243701133 973 29070321012650 974 29220012438955 975 29370319875456 976 29521245221457 977 29672790380162 978 29824957258679 979 29977747768024 980 30131163823125 981 30285207342826 982 30439880249891 983 30595184471008 984 30751121936793 985 30907694581794 986 31064904344495 987 31222753167320 988 31381242996637 989 31540375782762 990 31700153479963 991 31860578046464 992 32021651444449 993 32183375640066 994 32345752603431 995 32508784308632 996 32672472733733 997 32836819860778 998 33001827675795 999 33167498168800 1000 33333833333801