0 1 1 1 2 2 3 6 4 21 5 75 6 253 7 774 8 2130 9 5314 10 12169 11 25895 12 51756 13 98034 14 177282 15 307933 16 516327 17 839223 18 1326868 19 2046700 20 3087767 21 4565949 22 6630075 23 9469032 24 13319968 25 18477696 26 25305411 27 34246837 28 45839926 29 60732236 30 79698120 31 103657863 32 133698909 33 171099325 34 217353654 35 274201314 36 343657705 37 428048191 38 530045129 39 652708122 40 799527678 41 974472462 42 1182040333 43 1427313363 44 1716017040 45 2054583862 46 2450221534 47 2910985985 48 3445859427 49 4064833683 50 4778999016 51 5600638696 52 6543329547 53 7622048721 54 8853286951 55 10255168540 56 11847578348 57 13652296044 58 15693137895 59 17996106369 60 20589547834 61 23504318640 62 26773959876 63 30434881099 64 34526553337 65 39091711673 66 44176567722 67 49831032318 68 56108948733 69 63068336755 70 70771647957 71 79286032494 72 88683617770 73 99041799322 74 110443544273 75 122977707711 76 136739362356 77 151830141882 78 168358598266 79 186440573541 80 206199586335 81 227767233583 82 251283607804 83 276897730340 84 304768000959 85 335062664229 86 367960293075 87 403650289936 88 442333405944 89 484222278552 90 529541988043 91 578530633357 92 631439927678 93 688535814228 94 750099102720 95 816426126927 96 887829423829 97 964638434805 98 1047200229342 99 1135880251738 100 1231063091281 101 1333153276391 102 1442576093217 103 1559778429186 104 1685229642006 105 1819422454630 106 1962873876693 107 2116126152939 108 2279747739160 109 2454334306174 110 2640509772374 111 2838927365385 112 3050270713371 113 3275254966539 114 3514627949392 115 3769171344288 116 4039701906867 117 4327072713913 118 4632174444223 119 4955936693060 120 5299329320772 121 5663363836164 122 6049094815215 123 6457621355737 124 6890088568578 125 7347689105976 126 7831664727676 127 8343307905427 128 8883963466481 129 9455030276721 130 10057962964050 131 10694273682678 132 11365533918949 133 12073376339355 134 12819496681389 135 13605655687894 136 14433681085570 137 15305469608306 138 16222989066009 139 17188280459607 140 18203460142908 141 19270722032002 142 20392339862898 143 21570669498093 144 22808151282775 145 24107312451367 146 25470769585124 147 26901231121500 148 28401499916007 149 29974475857293 150 31623158536171 151 33350649969336 152 35160157378512 153 37054996025776 154 39038592105811 155 41114485695845 156 43286333764038 157 45557913237084 158 47933124127800 159 50415992723479 160 53010674835789 161 55721459113005 162 58552770415366 163 61509173254354 164 64595375296697 165 67816230933903 166 71176744918137 167 74682076065258 168 78337541025838 169 82148618124990 170 86120951271837 171 90260353939459 172 94572813216160 173 99064493928902 174 103741742839758 175 108611092916241 176 113679267676371 177 118953185609347 178 124439964672696 179 130146926866776 180 136081602887515 181 142251736858273 182 148665291141719 183 155330451232620 184 162255630732444 185 169449476406684 186 176920873325815 187 184678950090801 188 192733084144074 189 201092907166912 190 209768310564148 191 218769451037147 192 228106756245993 193 237790930561833 194 247832960910330 195 258244122707182 196 269035985886669 197 280220421024195 198 291809605553797 199 303816030081598 200 316252504796186 201 329132165976906 202 342468482601057 203 356275263050991 204 370566661922116 205 385357186932810 206 400661705937258 207 416495454042229 208 432874040828815 209 449813457680159 210 467330085216204 211 485440700836500 212 504162486372111 213 523513035847669 214 543510363354627 215 564172911036768 216 585519557189032 217 607569624470728 218 630342888234203 219 653859584970045 220 678140420869902 221 703206580508004 222 729079735642480 223 755782054137567 224 783336209007813 225 811765387585381 226 841093300811566 227 871344192653642 228 902542849648161 229 934714610571831 230 967885376241105 231 1002081619441618 232 1037330394988614 233 1073659349919510 234 1111096733819749 235 1149671409283099 236 1189412862507560 237 1230351214028046 238 1272517229587014 239 1315942331144217 240 1360658608026763 241 1406698828220667 242 1454096449805088 243 1502885632530448 244 1553101249541635 245 1604778899247497 246 1657954917337839 247 1712666388949140 248 1768951160980212 249 1826847854559028 250 1886395877661951 251 1947635437886601 252 2010607555379602 253 2075354075920456 254 2141917684162796 255 2210341917034275 256 2280671177296353 257 2352950747265249 258 2427226802695330 259 2503546426826214 260 2581957624594869 261 2662509337013995 262 2745251455717981 263 2830234837677734 264 2917511320085682 265 3007133735412258 266 3099155926635177 267 3193632762642823 268 3290620153813068 269 3390175067768850 270 3492355545311842 271 3597220716535549 272 3704830817119175 273 3815247204803607 274 3928532376050868 275 4044749982888396 276 4163964849939511 277 4286242991641437 278 4411651629652251 279 4540259210448136 280 4672135423112320 281 4807351217317088 282 4945978821500259 283 5088091761237525 284 5233764877812054 285 5383074346982764 286 5536097697952680 287 5692913832538791 288 5853603044544829 289 6018247039338397 290 6186928953633878 291 6359733375482562 292 6536746364471433 293 6718055472132063 294 6903749762561065 295 7093919833253562 296 7288657836151134 297 7488057498905710 298 7692214146360877 299 7901224722252083 300 8115187811127216 301 8334203660489046 302 8558374203161022 303 8787803079877921 304 9022595662102851 305 9262859075072115 306 9508702221069448 307 9760235802931144 308 10017572347783595 309 10280826231014769 310 10550113700481159 311 10825552900951740 312 11107263898790476 313 11395368706878924 314 11689991309780487 315 11991257689147873 316 12299295849375322 317 12614235843497168 318 12936209799334308 319 13265351945890155 320 13601798639997657 321 13945688393218969 322 14297161898999370 323 14656362060077022 324 15023434016150173 325 15398525171803411 326 15781785224694581 327 16173366194003982 328 16573422449147466 329 16982110738755066 330 17399590219916785 331 17826022487697183 332 18261571604920404 333 18706404132227290 334 19160689158406234 335 19624598330999429 336 20098305887186175 337 20581988684944911 338 21075826234495644 339 21580000730024452 340 22094697081691743 341 22620102947925957 342 23156408768004403 343 23703807794922928 344 24262496128556120 345 24832672749109752 346 25414539550867179 347 26008301376231405 348 26614166050064542 349 27232344414326388 350 27863050363013856 351 28506500877402991 352 29162916061595317 353 29832519178370261 354 30515536685345406 355 31212198271446330 356 31922736893687793 357 32647388814268039 358 33386393637977985 359 34139994349927074 360 34908437353587574 361 35691972509159110 362 36490853172255221 363 37305336232913739 364 38135682154932792 365 38982155015534238 366 39845022545356342 367 40724556168777513 368 41621031044572923 369 42534726106905835 370 43465924106655472 371 44414911653083264 372 45381979255839315 373 46367421367310937 374 47371536425315103 375 48394626896136676 376 49436999317914276 377 50498964344375652 378 51580836788924431 379 52682935669080121 380 53805584251273250 381 54949110095997528 382 56113845103320924 383 57300125558757555 384 58508292179502289 385 59738690161029969 386 60991669224061170 387 62267583661896406 388 63566792388120709 389 64889658984680507 390 66236551750334733 391 67607843749482102 392 69003912861366498 393 70425141829662418 394 71871918312442425 395 73344634932528567 396 74843689328229724 397 76369484204466850 398 77922427384288082 399 79502931860775693 400 81111415849346871 401 82748302840450311 402 84414021652660612 403 86109006486172476 404 87833696976696711 405 89588538249760045 406 91373980975410763 407 93190481423332184 408 95038501518366000 409 96918508896447504 410 98830976960954739 411 100776384939473605 412 102755217940980966 413 104767967013447804 414 106815129201864472 415 108897207606690103 416 111014711442728237 417 113168156098430733 418 115358063195632038 419 117584960649715890 420 119849382730216537 421 122151870121856559 422 124492969986023385 423 126873236022686602 424 129293228532758158 425 131753514480897566 426 134254667558764221 427 136797268248718947 428 139381903887976896 429 142009168733213926 430 144679664025628590 431 147393998056461873 432 150152786232976819 433 152956651144900195 434 155806222631328344 435 158702137848099384 436 161645041335633915 437 164635585087246401 438 167674428617929399 439 170762239033612812 440 173899691100900348 441 177087467317285372 442 180326257981848343 443 183616761266438033 444 186959683287338730 445 190355738177425632 446 193805648158810644 447 197310143615980795 448 200869963169431497 449 204485853749796873 450 208158570672479386 451 211888877712781006 452 215677547181538157 453 219525360001262691 454 223433105782791141 455 227401582902444510 456 231431598579700858 457 235523968955382954 458 239679519170363265 459 243899083444788559 460 248183505157826404 461 252533636927935850 462 256950340693664586 463 261434487794974869 464 265986959055100527 465 270608644862937343 466 275300445255969132 467 280063270003731828 468 284898038691817903 469 289805680806423445 470 294787135819440227 471 299843353274095104 472 304975292871139080 473 310183924555588392 474 315470228604019963 475 320835195712423581 476 326279827084613166 477 331805134521199492 478 337412140509126736 479 343101878311775231 480 348875392059632805 481 354733736841537093 482 360677978796491214 483 366709195206055210 484 372828474587315649 485 379036916786435799 486 385335633072788785 487 391725746233676146 488 398208390669634214 489 404784712490330742 490 411455869611054213 491 418223031849798267 492 425087381024943688 493 432050111053540398 494 439112428050191910 495 446275550426544697 496 453540708991384939 497 460909147051345115 498 468382120512222912 499 475960897980914928 500 483646760867967651 501 491441003490748201 502 499344933177237327 503 507359870370447156 504 515487148733466196 505 523728115255134100 506 532084130356348703 507 540556567997007849 508 549146815783588530 509 557856275077365864 510 566686361103274444 511 575638503059414595 512 584714144227206081 513 593914742082191809 514 603241768405494082 515 612696709395925958 516 622281065782760277 517 631996352939158923 518 641844100996264893 519 651825854957959750 520 661943174816289042 521 672197635667558274 522 682590827829102025 523 693124356956728807 524 703799844162844268 525 714618926135255346 526 725583255256657986 527 736694499724811037 528 747954343673398951 529 759364487293585911 530 770926646956264020 531 782642555334998188 532 794513961529670359 533 806542631190825725 534 818730346644723579 535 831078907019095464 536 843590128369613280 537 856265843807070016 538 869107903625275779 539 882118175429671797 540 895298544266665078 541 908650912753686412 542 922177201209974408 543 935879347788088263 544 949759308606151965 545 963819057880832637 546 978060588061055734 547 992485909962459810 548 1007097052902593577 549 1021896064836857983 550 1036885012495196041 551 1052065981519533146 552 1067441076601970622 553 1083012421623735246 554 1098782159794887501 555 1114752453794791315 556 1130925485913348048 557 1147303458192997494 558 1163888592571488670 559 1180683131025423169 560 1197689335714573859 561 1214909489126981715 562 1232345894224833576 563 1250000874591123624 564 1267876774577101387 565 1285975959450509073 566 1304300815544611047 567 1322853750408018268 568 1341637192955310508 569 1360653593618459180 570 1379905424499053607 571 1399395179521333569 572 1419125374586030970 573 1439098547725023472 574 1459317259256802948 575 1479784091942761611 576 1500501651144298681 577 1521472564980750457 578 1542699484488146666 579 1564185083778795966 580 1585932060201703485 581 1607943134503823283 582 1630221050992148629 583 1652768577696642990 584 1675588506534014634 585 1698683653472337754 586 1722056858696523025 587 1745710986774640511 588 1769648926825097844 589 1793873592684676602 590 1818387923077429818 591 1843194881784443557 592 1868297457814465503 593 1893698665575403503 594 1919401545046697020 595 1945409161952564452 596 1971724607936129279 597 1998351000734428005 598 2025291484354302867 599 2052549229249182288 600 2080127432496752056 601 2108029317977520216 602 2136258136554278667 603 2164817166252464461 604 2193709712441423806 605 2222939108016581780 606 2252508713582520768 607 2282421917636970639 608 2312682136755713685 609 2343292815778407349 610 2374257427995327774 611 2405579475335037210 612 2437262488552978321 613 2469310027420998439 614 2501725680917806817 615 2534513067420367938 616 2567675834896233942 617 2601217661096819238 618 2635142253751620373 619 2669453350763384235 620 2704154720404227672 621 2739250161512711614 622 2774743503691872790 623 2810638607508216137 624 2846939364691671003 625 2883649698336514251 626 2920773563103263376 627 2958314945421542752 628 2996277863693926131 629 3034666368500758521 630 3073484542805960575 631 3112736502163818628 632 3152426394926763524 633 3192558402454141380 634 3233136739321979439 635 3274165653533750169 636 3315649426732136770 637 3357592374411803256 638 3399998846133172284 639 3442873225737213907 640 3486219931561248433 641 3530043416655766577 642 3574348169002270098 643 3619138711732136118 644 3664419603346508325 645 3710195437937218267 646 3756470845408739949 647 3803250491701180950 648 3850539079014313282 649 3898341346032647218 650 3946662068151551321 651 3995506057704421911 652 4044878164190905212 653 4094783274506175426 654 4145226313171271986 655 4196212242564499245 656 4247746063153891863 657 4299832813730749159 658 4352477571644241700 659 4405685453037093404 660 4459461613082342439 661 4513811246221184205 662 4568739586401899691 663 4624251907319872504 664 4680353522658697872 665 4737049786332386928 666 4794346092728669587 667 4852247876953399333 668 4910760615076063238 669 4969889824376400540 670 5029641063592133112 671 5090019933167811159 672 5151032075504777485 673 5212683175212253677 674 5274978959359551558 675 5337925197729413266 676 5401527703072483321 677 5465792331362916047 678 5530724982055121721 679 5596331598341654826 680 5662618167412247790 681 5729590720713993598 682 5797255334212680669 683 5865618128655283395 684 5934685269833611744 685 6004462968849123334 686 6074957482378901390 687 6146175112942802001 688 6218122209171774099 689 6290805166077355587 690 6364230425322349048 691 6438404475492680472 692 6513333852370444443 693 6589025139208139233 694 6665484967004095255 695 6742720014779100332 696 6820737009854225244 697 6899542728129853020 698 6979143994365915447 699 7059547682463340273 700 7140760715746712586 701 7222790067248153856 702 7305642759992422132 703 7389325867283236891 704 7473846512990832041 705 7559211871840740585 706 7645429169703814458 707 7732505683887483054 708 7820448743428253965 709 7909265729385459459 710 7998964075136252229 711 8089551266671853950 712 8181034842895060186 713 8273422395919005194 714 8366721571367190177 715 8460940068674778543 716 8556085641391161732 717 8652166097483799178 718 8749189299643335978 719 8847163165590001845 720 8946095668381294927 721 9045994836720954079 722 9146868755269223180 723 9248725564954411092 724 9351573463285750863 725 9455420704667561781 726 9560275600714717891 727 9666146520569426592 728 9773041891219320936 729 9880970197816869256 730 9989939984000105755 731 10099959852214685693 732 10211038464037268814 733 10323184540500234660 734 10436406862417733424 735 10550714270713075999 736 10666115666747466885 737 10782620012650083621 738 10900236331649506414 739 11018973708406501642 740 11138841289348162913 741 11259848283003413367 742 11382003960339872913 743 11505317655102094098 744 11629798764151170310 745 11755456747805720022 746 11882301130184250789 747 12010341499548906715 748 12139587508650603112 749 12270048875075552078 750 12401735381593182726 751 12534656876505459801 752 12668823273997604427 753 12804244554490220731 754 12940930764992832096 755 13078892019458830800 756 13218138499141844803 757 13358680452953525449 758 13500528197822759855 759 13643692119056311764 760 13788182670700894644 761 13934010375906680820 762 14081185827292250431 763 14229719687310984009 764 14379622688618902482 765 14530905634443958408 766 14683579398956782252 767 14837654927642887523 768 14993143237676338593 769 15150055418294885025 770 15308402631176566242 771 15468196110817790374 772 15629447164912891125 773 15792167174735166507 774 15956367595519403293 775 16122059956845891046 776 16289255863025929586 777 16457966993488833762 778 16628205103170439401 779 16799982022903114311 780 16973309659807278220 781 17148199997684435538 782 17324665097411724834 783 17502717097337988925 784 17682368213681369479 785 17863630740928430039 786 18046517052234811380 787 18231039599827423116 788 18417210915408175479 789 18605043610559255197 790 18794550377149949403 791 18985743987745021512 792 19178637296014643008 793 19373243237145885088 794 19569574828255774115 795 19767645168805914837 796 19967467441018685334 797 20169054910295007660 798 20372420925633698152 799 20577578920052401383 800 20784542411010111741 801 20993325000831286621 802 21203940377131555222 803 21416402313245026946 804 21630724668653203401 805 21846921389415498015 806 22065006508601367273 807 22284994146724057594 808 22506898512175971870 809 22730733901665659694 810 22956514700656435309 811 23184255383806627315 812 23413970515411464176 813 23645674749846599574 814 23879382832013281662 815 24115109597785170273 816 24352869974456806147 817 24592678981193736243 818 24834551729484299208 819 25078503423593075080 820 25324549361016003307 821 25572704932937173169 822 25822985624687290695 823 26075407016203826172 824 26329984782492846348 825 26586734694092535436 826 26845672617538409031 827 27106814515830225057 828 27370176448900595866 829 27635774574085305616 830 27903625146595337060 831 28173744519990611883 832 28446149146655448729 833 28720855578275743065 834 28997880466317873034 835 29277240562509335454 836 29558952719321116125 837 29843033890451798611 838 30129501131313415669 839 30418371599519047502 840 30709662555372171018 841 31003391362357764282 842 31299575487635170353 843 31598232502532724703 844 31899380083044150420 845 32203036010326725402 846 32509218171201225754 847 32817944558653649605 848 33129233272338725567 849 33443102519085210063 850 33759570613402977756 851 34078655977991909316 852 34400377144252580767 853 34724752752798758661 854 35051801553971705331 855 35381542408356298480 856 35713994287298969368 857 36049176273427463864 858 36387107561172430635 859 36727807457290840749 860 37071295381391242974 861 37417590866460859060 862 37766713559394523296 863 38118683221525470639 864 38473519729157977717 865 38831243074101861013 866 39191873364208836542 867 39555430823910745338 868 39921935794759649073 869 40291408735969800135 870 40663870224961490497 871 41039340957906783714 872 41417841750277134390 873 41799393537392899462 874 42184017374974745653 875 42571734439696957451 876 42962566029742649976 877 43356533565360891102 878 43753658589425737206 879 44153962767997186921 880 44557467890884057275 881 44964195872208786603 882 45374168750974168624 883 45787408691632022080 884 46203937984653800339 885 46623779047103145369 886 47046954423210390495 887 47473486784949016356 888 47903398932614064484 889 48336713795402512932 890 48773454431995618383 891 49213644031143229177 892 49657305912250073698 893 50104463525964028568 894 50555140454766371100 895 51009360413564020467 896 51467147250283772049 897 51928524946468529425 898 52393517617875538482 899 52862149515076628118 900 53334445024060462021 901 53810428666836806011 902 54290125102042815437 903 54773559125551347126 904 55260755671081300386 905 55751739810809991570 906 56246536755987566713 907 56745171857553456759 908 57247670606754879900 909 57754058635767395554 910 58264361718317514514 911 58778605770307369805 912 59296816850441452791 913 59819021160855419079 914 60345245047746968772 915 60875515002008805628 916 61409857659863679687 917 61948299803501517933 918 62490868361718647563 919 63037590410559116440 920 63588493173958115312 921 64143604024387506384 922 64702950483503462835 923 65266560222796223877 924 65834461064241969958 925 66406680980956822716 926 66983248097852974296 927 67564190692296950647 928 68149537194770013421 929 68739316189530705101 930 69333556415279541990 931 69932286765825859698 932 70535536290756815769 933 71143334196108554095 934 71755709845039535769 935 72372692758506041034 936 72994312615939846990 937 73620599255928085726 938 74251582676895287549 939 74887293037787613987 940 75527760658759285248 941 76173016021861206822 942 76823089771731799918 943 77478012716290040433 944 78137815827430711155 945 78802530241721871907 946 79472187261104552344 947 80146818353594672120 948 80826455153987193147 949 81511129464562508673 950 82200873255795073911 951 82895718667064282956 952 83595698007367596732 953 84300843756035926716 954 85011188563451279191 955 85726765251766664785 956 86447606815628278058 957 87173746422899951904 958 87905217415389891540 959 88642053309579692859 960 89384287797355649929 961 90131954746742356425 962 90885088202638605786 963 91643722387555594894 964 92407891702357436077 965 93177630727003982243 966 93952974221295969957 967 94733957125622485278 968 95520614561710757178 969 96312981833378283370 970 97111094427287293377 971 97914988013701553679 972 98724698447245519780 973 99540261767665840042 974 100361714200595216138 975 101189092158318624981 976 102022432240541906991 977 102861771235162725567 978 103707146119043902636 979 104558594058789135156 980 105416152411521097455 981 106279858725661934293 982 107149750741716149539 983 108025866393055895360 984 108908243806708666824 985 109796921304147406824 986 110691937402083026235 987 111593330813259344221 988 112501140447250453614 989 113415405411260516292 990 114336165010925993488 991 115263458751120315967 992 116197326336760999013 993 117137807673619207173 994 118084942869131773710 995 119038772233215679722 996 119999336279084997889 997 120966675724070305815 998 121940831490440573937 999 122921844706227532978 1000 123909756706052525926