0 1 1 1 2 2 3 2 4 4 5 6 6 8 7 11 8 15 9 20 10 30 11 38 12 49 13 65 14 83 15 108 16 139 17 178 18 224 19 286 20 358 21 437 22 550 23 684 24 837 25 1037 26 1269 27 1553 28 1889 29 2295 30 2770 31 3359 32 4035 33 4843 34 5808 35 6951 36 8312 37 9902 38 11752 39 13958 40 16531 41 19541 42 23037 43 27162 44 31911 45 37488 46 43950 47 51463 48 60127 49 70229 50 81835 51 95296 52 110807 53 128683 54 149207 55 172784 56 199920 57 231074 58 266689 59 307538 60 354198 61 407634 62 468507 63 538037 64 617261 65 707571 66 810116 67 926832 68 1059330 69 1209872 70 1380371 71 1573743 72 1792652 73 2040455 74 2320439 75 2636999 76 2994257 77 3397607 78 3852714 79 4364998 80 4941978 81 5591878 82 6322297 83 7143515 84 8066111 85 9101904 86 10263879 87 11567312 88 13027527 89 14663538 90 16495022 91 18544085 92 20835486 93 23397426 94 26258195 95 29452944 96 33018621 97 36995294 98 41428952 99 46370363 100 51872700 101 57999746 102 64817861 103 72400312 104 80830571 105 90198219 106 100604140 107 112158111 108 124980582 109 139204051 110 154977018 111 172460918 112 191830097 113 213283675 114 237034716 115 263316824 116 292391929 117 324543317 118 360080857 119 399350286 120 442723713 121 490612240 122 543471612 123 601794649 124 666117140 125 737039690 126 815212086 127 901338123 128 996202340 129 1100654883 130 1215620421 131 1342126675 132 1481279965 133 1634289813 134 1802496282 135 1987343342 136 2190413531 137 2413430683 138 2658290052 139 2927036934 140 3221923061 141 3545394682 142 3900107990 143 4288982465 144 4715181061 145 5182135078 146 5693625753 147 6253733246 148 6866895460 149 7537968035 150 8272225070 151 9075380302 152 9953683085 153 10913907726 154 11963405804 155 13110198304 156 14362982369 157 15731176004 158 17225074016 159 18855801384 160 20635429686 161 22577103914 162 24695062476 163 27004725152 164 29522871760 165 32267650589 166 35258749922 167 38517532562 168 42067131600 169 45932566481 170 50141040298 171 54721916736 172 59707060892 173 65130935898 174 71030849323 175 77447150753 176 84423588102 177 92007369034 178 100249617513 179 109205627977 180 118935161001 181 129502778486 182 140978367529 183 153437327002 184 166961179528 185 181637990446 186 197562850741 187 214838405174 188 233575615795 189 253894055127 190 275922884636 191 299801521462 192 325680316218 193 353721413994 194 384099811243 195 417004068612 196 452637641900 197 491219747090 198 532986665225 199 578193020464 200 627113291278 201 680042948829 202 737300408391 203 799228568893 204 866196631032 205 938602023264 206 1016872727066 207 1101469149713 208 1192886985668 209 1291659389128 210 1398360063068 211 1513605822214 212 1638060530256 213 1772437603590 214 1917504255778 215 2074085211009 216 2243067030453 217 2425402292635 218 2622114801688 219 2834304206153 220 3063152166704 221 3309927634210 222 3575993431284 223 3862812826394 224 4171957172003 225 4505112870231 226 4864090293374 227 5250832113577 228 5667423237294 229 6116100191972 230 6599262527340 231 7119483837596 232 7679524580011 233 8282344546503 234 8931117371052 235 9629245372149 236 10380375836410 237 11188417378616 238 12057559247500 239 12992289673826 240 13997417851924 241 15078095443046 242 16239840265095 243 17488561773857 244 18830588870728 245 20272697075136 246 21822140674843 247 23486685152272 248 25274642179181 249 27194906577209 250 29256997302042 251 31471098101925 252 33848104721079 253 36399672023799 254 39138266222703 255 42077218137358 256 45230784729378 257 48614207939576 258 52243783553192 259 56136931441799 260 60312270274680 261 64789698147649 262 69590479766626 263 74737334164031 264 80254534961688 265 86168013074055 266 92505465240994 267 99296471739549 268 106572624197326 269 114367652885816 270 122717572271599 271 131660831046040 272 141238469579808 273 151494292285011 274 162475050969108 275 174230631268982 276 186814263481126 277 200282740627989 278 214696645932067 279 230120602412893 280 246623538168025 281 264278958267346 282 283165247454400 283 303365984415945 284 324970272743637 285 348073101415775 286 372775725580325 287 399186059565132 288 427419112811646 289 457597444894066 290 489851639434396 291 524320823116381 292 561153213678028 293 600506687283889 294 642549402675642 295 687460452248227 296 735430546425368 297 786662758828824 298 841373307745519 299 899792371678813 300 962164984186419 301 1028751962274209 302 1099830894334156 303 1175697196081352 304 1256665230131451 305 1343069477410938 306 1435265808717042 307 1533632814614229 308 1638573206590704 309 1750515333574334 310 1869914772661901 311 1997255997191575 312 2133054187476959 313 2277857125041525 314 2432247189274555 315 2596843507383527 316 2772304213907011 317 2959328831363950 318 3158660834171893 319 3371090333915365 320 3597456914978531 321 3838652686608072 322 4095625483813075 323 4369382236209327 324 4660992597796846 325 4971592753936187 326 5302389432734050 327 5654664215845629 328 6029778056793596 329 6429176059480045 330 6854392591763355 331 7307056653491993 332 7788897548919165 333 8301750958405327 334 8847565313761694 335 9428408527623332 336 10046475185781765 337 10704094125013208 338 11403736407678934 339 12148023853792441 340 12939738004816931 341 13781829594666256 342 14677428655780924 343 15629855134976271 344 16642630104531818 345 17719487737037434 346 18864387868337598 347 20081529285100876 348 21375363858949805 349 22750611445602924 350 24212275584938375 351 25765660223357355 352 27416387332401731 353 29170415455244398 354 31034059493391244 355 33014011505062582 356 35117362631244621 357 37351626468639153 358 39724763616021759 359 42245207600159081 360 44921892417536555 361 47764281543695397 362 50782398517734396 363 53986859443187461 364 57388907185072407 365 61000447467821032 366 64834087173415722 367 68903174694866609 368 73221842435760111 369 77805051985085709 370 82668641626568930 371 87829376451615258 372 93305001517441967 373 99114297821096984 374 105277141292492685 375 111814565384825114 376 118748826904057782 377 126103475498943244 378 133903427211773353 379 142175042007856423 380 150946205409282785 381 160246415044198747 382 170106871727793161 383 180560575503347946 384 191642427271391489 385 203389335852163472 386 215840330773062135 387 229036681724316060 388 243022024164194318 389 257842491881295145 390 273546857076829677 391 290186677945062065 392 307816454129290842 393 326493791142193602 394 346279573423015140 395 367238146791839303 396 389437511127361712 397 412949523396427026 398 437850111418226031 399 464219499877858148 400 492142448041732251 401 521708500428650460 402 553012251386610074 403 586153623723063475 404 621238162116829994 405 658377343010755926 406 697688900673591791 407 739297170805672957 408 783333453095289856 409 829936392826095557 410 879252382771679733 411 931435987396359977 412 986650389048736854 413 1045067858087863673 414 1106870248592636024 415 1172249520191469062 416 1241408287351794560 417 1314560398842029673 418 1391931547147199554 419 1473759910540355774 420 1560296829544703125 421 1651807518909084397 422 1748571817069502134 423 1850884976152749367 424 1959058492839185819 425 2073420983262483434 426 2194319104562464821 427 2322118524632471930 428 2457204942465766953 429 2599985163299826249 430 2750888229062496391 431 2910366608637646292 432 3078897450864861861 433 3256983902591510147 434 3445156495509990639 435 3643974606630724427 436 3854027993611997551 437 4075938410768234434 438 4310361309561455298 439 4557987627281334496 440 4819545668207344421 441 5095803083792145610 442 5387568954245479543 443 5695695978658963194 444 6021082778816583307 445 6364676321633884823 446 6727474466487485460 447 7110528645701357940 448 7514946681290972015 449 7941895747803625011 450 8392605487956645851 451 8868371288032098549 452 9370557721169166972 453 9900602168764514003 454 10460018625793815193 455 11050401702235655776 456 11673430829187430274 457 12330874679618094793 458 13024595814378345616 459 13756555567354643678 460 14528819177061848301 461 15343561180958883994 462 16203071084395381161 463 17109759317115725156 464 18066163491936217737 465 19074954982302654331 466 20138945831460668591 467 21261096012466401616 468 22444521055726190955 469 23692500061274813259 470 25008484115061694602 471 26396105132126614892 472 27859185142535942926 473 29401746046412142304 474 31028019859626120043 475 32742459473919571236 476 34549749956645312330 477 36454820419333579648 478 38462856478104411921 479 40579313340139307539 480 42809929544058921816 481 45160741386376182356 482 47638098068036293204 483 50248677598365811845 484 52999503488628719965 485 55897962278732521297 486 58951821934948064574 487 62169251162241797291 488 65558839674361867920 489 69129619471628187094 490 72891087169886208904 491 76853227438035367140 492 81026537593680808527 493 85422053414005074349 494 90051376221069926120 495 94926701305099559316 496 100060847745494106690 497 105467289703601237385 498 111160189252632903231 499 117154430822731806666 500 123465657336456060923 501 130110308119534388069 502 137105658666497757472 503 144469862357686512832 504 152221994215743125134 505 160382096801585466251 506 168971228352034079295 507 178011513269140966189 508 187526195067203012365 509 197539691904260472104 510 208077654812609506305 511 219167028763242607064 512 230836116697440005866 513 243114646667551671495 514 256033842231173151485 515 269626496262253489428 516 283927048331730090815 517 298971665834226446731 518 314798329034815781612 519 331446920225526571405 520 348959317179598137736 521 367379491117594751287 522 386753609387040219232 523 407130143086150674649 524 428559979864378823436 525 451096542141889115847 526 474795911000237488595 527 499716956024208877668 528 525921471357813189649 529 553474318278301042513 530 582443574594092558202 531 612900691180258897657 532 644920655989569113453 533 678582165898344632804 534 713967806736255880374 535 751164241897359012254 536 790262409932230598559 537 831357731534491328912 538 874550326359630823097 539 919945240151024980005 540 967652682628142028632 541 1017788276657320487589 542 1070473319228166965295 543 1125835054772972920160 544 1184006961410062752204 545 1245129050723585581860 546 1309348181677874755261 547 1376818389346903884048 548 1447701229141487109426 549 1522166137238299430951 550 1600390807965622028088 551 1682561588947101083097 552 1768873894788683546417 553 1859532640190454098496 554 1954752693379865817361 555 2054759350778140818435 556 2159788833893432543571 557 2270088809482010038921 558 2385918933996030413169 559 2507551423475597290770 560 2635271650049233040239 561 2769378766233472018484 562 2910186358325188335167 563 3058023130235965584069 564 3213233619110752785696 565 3376178944227111359984 566 3547237590689066991405 567 3726806229471416242051 568 3915300575497397735951 569 4113156285504377943598 570 4320829897441170785869 571 4538799813342995258544 572 4767567327660208961764 573 5007657703056856622475 574 5259621295868600467017 575 5524034733493616352741 576 5801502145996389046379 577 6092656454446022513524 578 6398160718546324418989 579 6718709546185886892151 580 7055030567752954081019 581 7407885978160625872459 582 7778074149543971108620 583 8166431317894124584874 584 8573833346958780721481 585 9001197572816280402965 586 9449484732805000598838 587 9919700982624334772149 588 10412900005462737266504 589 10930185217380184718624 590 11472712073244268161147 591 12041690477644605413057 592 12638387305566538618977 593 13264129037749350175781 594 13920304515732229509988 595 14608367822045886040739 596 15329841291138324788696 597 16086318656746217891493 598 16879468341903145758176 599 17711036897941240477745 600 18582852598984315438944 601 19496829198983009269884 602 20454969858495492128933 603 21459371248625186900509 604 22512227840106730102085 605 23615836385754348003172 606 24772600604673941208942 607 25985036077334483066849 608 27255775360811869712735 609 28587573333789737651171 610 29983312781612786896447 611 31446010231988708232542 612 32978822052220443912702 613 34585050819681869752342 614 36268151977543645876141 615 38031740788124920186309 616 39879599597157117177701 617 41815685422613283056877 618 43844137882139064079271 619 45969287474169575930676 620 48195664228217655548401 621 50528006740303226635309 622 52971271610608604571221 623 55530643300936519669888 624 58211544430102856329465 625 61019646526653670492069 626 63960881258831113317820 627 67041452162369743761156 628 70267846888108729124884 629 73646849992030263705397 630 77185556291065468861959 631 80891384809591669955656 632 84772093342247848303553 633 88835793659577963020044 634 93090967384720767739897 635 97546482570203196489397 636 102211611004897358324889 637 107096046283124558783732 638 112209922668840352522659 639 117563834788960417935747 640 123168858192068236238342 641 129036570809826655032379 642 135179075359699028445349 643 141609022730010019327833 644 148339636389621252494850 645 155384737865988269999205 646 162758773338048814925920 647 170476841391791865191879 648 178554721988120908902030 649 187008906695571586206380 650 195856630242082044652987 651 205115903441973412052864 652 214805547557636291968272 653 224945230157281247694206 654 235555502532345068198815 655 246657838741834791819919 656 258274676353068575583925 657 270429458950789037556901 658 283146680490790847345405 659 296451931576584365822730 660 310371947740599786377008 661 324934659816005149416835 662 340169246488003154345204 663 356106189116774297819621 664 372777328929398639173440 665 390215926681240326191063 666 408456724891106068499600 667 427536012760077350663527 668 447491693887782866337497 669 468363356903883375739837 670 490192349139179796318026 671 513021853464719947435269 672 536896968432235747705455 673 561864791856342304647583 674 587974507983677446334069 675 615277478399591430103527 676 643827336831095539079765 677 673680088009991358233850 678 704894210766539280403405 679 737530765532688899113954 680 771653506440228380928030 681 807328998206127198793820 682 844626738007387574603144 683 883619282554563447563854 684 924382380581251364319462 685 966995110977767222735355 686 1011540026805371426925491 687 1058103305436186866186176 688 1106774905076601607413225 689 1157648727940690000946463 690 1210822790350704284992391 691 1266399400055218001905220 692 1324485341065956672696175 693 1385192066325784196076939 694 1448635898535884680286947 695 1514938239481547181378509 696 1584225788209385577743817 697 1656630768425653879900018 698 1732291165498916104649057 699 1811350973464701366243346 700 1893960452449340466126708 701 1980276396944824073980899 702 2070462415383562308422558 703 2164689221483033333444924 704 2263134937847492656212225 705 2365985412332608760510372 706 2473434547703107856361580 707 2585684645132241931848575 708 2702946762113750136173674 709 2825441085383144325839840 710 2953397319467448071029757 711 3087055091506020761121508 712 3226664373015356437630072 713 3372485919295003836149265 714 3524791727199228653683227 715 3683865512031954561872381 716 3850003204350705613057461 717 4023513467495407056218807 718 4204718236695789205106363 719 4393953280641708462743254 720 4591568786435937089467892 721 4797929968889946232698845 722 5013417705159235386697543 723 5238429195753081339909681 724 5473378653000468578628154 725 5718698018093535140951068 726 5974837707874313758605130 727 6242267392581620047718976 728 6521476805820886308233339 729 6812976588068275796616755 730 7117299165079280472763665 731 7434999662622035309502036 732 7766656859011796525656406 733 8112874176987230837330289 734 8474280716527290965529207 735 8851532330269125356660373 736 9245312743260560987506200 737 9656334718844652677345944 738 10085341272545187961315715 739 10533106935901578832061103 740 11000439072275633348554514 741 11488179246730781629405473 742 11997204652175819665644940 743 12528429594045949499432532 744 13082807035884260358182589 745 13661330208286274000711570 746 14265034283764081589266834 747 14894998120185197295667448 748 15552346075555192045198763 749 16238249897015888283124733 750 16953930687044942605551388 751 17700660949966771161010144 752 18479766722003277571411803 753 19292629788217929955544977 754 20140689989848634381559323 755 21025447625655119081825445 756 21948465951049729087748012 757 22911373778936069457567308 758 23915868186329996683419346 759 24963717330994510531916585 760 26056763382497470633250418 761 27196925572265721171795843 762 28386203367389909551643522 763 29626679773128353301102459 764 30920524769246900012842226 765 32269998885530749958597563 766 33677456922025179264133425 767 35145351819769857987323772 768 36676238688018669353681466 769 38272778994179299923915391 770 39937744922945346114279584 771 41674023911343370274352777 772 43484623366692877124616452 773 45372675574739870890511780 774 47341442805509963756741289 775 49394322624729786039939373 776 51534853418964854653848837 777 53766720142936817210488762 778 56093760297826985479795493 779 58519970149703208170958882 780 61049511197565449293169656 781 63686716900883552013629599 782 66436099676877591663536085 783 69302358178186518736796861 784 72290384861998668085447166 785 75405273862134569652853805 786 78652329176021328965199021 787 82037073178969933423097668 788 85565255478640086505384798 789 89242862123072737931422554 790 93076125176205653518608300 791 97071532675309983132603885 792 101235838985347875750743695 793 105576075565841391835846008 794 110099562166436155944397069 795 114813918467965285906203157 796 119727076186484803481227934 797 124847291658408768033768200 798 130183158925576975037476503 799 135743623339822770349932918 800 141537995707353032891351838 801 147575966994030931714034899 802 153867623613482532307601600 803 160423463320772796892698931 804 167254411735275414104058739 805 174371839517279660510075864 806 181787580223809082699901785 807 189513948870101173406480690 808 197563761224231765292462369 809 205950353863399901842792297 810 214687605021489665380267820 811 223789956258669309771519170 812 233272434984953402000437777 813 243150677870872720830920186 814 253440955179684700793380659 815 264160196056850491931144102 816 275326014813876714926280395 817 286956738245046679493751652 818 299071434017023994976042532 819 311689940172832633864228920 820 324832895793321837205159054 821 338521772860840353998053695 822 352778909371559302973069310 823 367627543744657682870764193 824 383091850578406325136858584 825 399196977805085127700917119 826 415969085298664818756445797 827 433435384991204903469819675 828 451624182556055189702210956 829 470564920718159368214623758 830 490288224254033283171541340 831 510825946746358161618759180 832 532211219160612367365966072 833 554478500313688258270179496 834 577663629307100307813290706 835 601803880000144939525597614 836 626938017601205331023002783 837 653106357458346056568116018 838 680350826133432031344439036 839 708715024847150589224717105 840 738244295385628845793174959 841 768985788562761892105337948 842 800988535335899454805485314 843 834303520676214745818070951 844 868983760298915590520875091 845 905084380362380274846816255 846 942662700249420291531564528 847 981778318548130054765185046 848 1022493202354181061052557544 849 1064871780020989214426544992 850 1108981037488954588087407187 851 1154890618329854191016714350 852 1202672927647590528220565397 853 1252403239981790343292260145 854 1304159811366216961709901257 855 1358023995699646982400146321 856 1414080365592782166793478337 857 1472416837860842227246826596 858 1533124803837848508146490978 859 1596299264695179315516700163 860 1662038971953778643707478127 861 1730446573386463486706973819 862 1801628764514124110741797651 863 1875696445907166012939680022 864 1952764886511440219527780111 865 2032953893226067879130195524 866 2116387986969010299754645046 867 2203196585475009878708909715 868 2293514193079643267837878401 869 2387480597752607146990769758 870 2485241075653164015327602120 871 2586946603490793163800431523 872 2692754078984577156956570972 873 2802826549725742336364833680 874 2917333450759068079505750031 875 3036450851210531794248746882 876 3160361710300709949590397015 877 3289256143096001293519767128 878 3423331696362748209903596555 879 3562793634902828231212374906 880 3707855238763293585199993187 881 3858738111727081155048270900 882 4015672501506879741795723379 883 4178897632079792376804123750 884 4348662048616550202377353220 885 4525223975475767744161547253 886 4708851687751064890032407302 887 4899823896876793309752483247 888 5098430150816764076590422286 889 5304971249379620903477232336 890 5519759675224481113115487973 891 5743120041141184226940634384 892 5975389554210949548704115285 893 6216918497475429640079606441 894 6468070729765234334453637557 895 6729224204362835964961515746 896 7000771507199490435934176271 897 7283120415311449850316317873 898 7576694476307292317386716354 899 7881933609625654684485464831 900 8199294730391222370687640200 901 8529252396706302767728519287 902 8872299481245898501592125871 903 9228947868055919843688734124 904 9599729175486993785280406985 905 9985195506230295781078363492 906 10385920225457149266539980071 907 10802498768100569332835308228 908 11235549476354760319113342223 909 11685714468507771158915545966 910 12153660540263075219334102163 911 12640080099747833656827317823 912 13145692137449233566915949403 913 13671243232365314684628053302 914 14217508595703421418745939528 915 14785293153507862074779059982 916 15375432669648438018394254237 917 15988794910653381099654104641 918 16626280853924118915233997774 919 17288825940924870808270379979 920 17977401376997795820902700124 921 18693015479514198619751614327 922 19436715076134118616756364861 923 20209586955010686235760644176 924 21012759368842108736195023796 925 21847403594742755914485665179 926 22714735551976023772765458364 927 23616017479665435908411481068 928 24552559676676709569877175405 929 25525722305942525639053499090 930 26536917265583749945487582177 931 27587610129265466478475790597 932 28679322158314012176314084634 933 29813632388212182637730998725 934 30992179792183787144914625952 935 32216665524676188520304532333 936 33488855247650536947065269069 937 34810581542693702428968091419 938 36183746412074171424897592483 939 37610323871976284893000251655 940 39092362641263060473910690317 941 40631988929237916341205129139 942 42231409326000121949043984207 943 43892913799117317510103567320 944 45618878800471783141522305652 945 47411770487275239392362062073 946 49274148061389627762477133413 947 51208667231239215841360975245 948 53218083800752688176975844199 949 55305257389932083663722863337 950 57473155291809621018424996574 951 59724856470723441410159616803 952 62063555707018906817895465750 953 64492567893464135117188323683 954 67015332488857074202030128107 955 69635418134496141120596798979 956 72356527439388444022076012883 957 75182501940278728778734127511 958 78117327242798221696494721201 959 81165138350256464220261031864 960 84330225186831245815694050246 961 87617038322151191873733736024 962 91030194904513958876378139961 963 94574484810240135956020909821 964 98254877016928543329157318393 965 102076526208653934889526553233 966 106044779621433248571473687551 967 110165184137580908345859623401 968 114443493637878980192179162194 969 118885676620803948924244992114 970 123497924098378254544371765960 971 128286657778553014207413554703 972 133258538544378648370422031694 973 138420475240581763620730017634 974 143779633778541605132970301565 975 149343446571047497501272635582 976 155119622308619521624954546403 977 161116156089590082335263576268 978 167341339916574119764769871199 979 173803773572399723744120319307 980 180512375889031286207987588314 981 187476396423493686305562816423 982 194705427555297988943061445981 983 202209417020379039742020115848 984 209998680897083080122396642556 985 218083917060288427479318900670 986 226476219120307075447042499528 987 235187090863799505839542348144 988 244228461214538619794867060731 989 253612699732484115367363890194 990 263352632670275931003954052174 991 273461559606923690180163304837 992 283953270679161777412798331585 993 294842064431656243977754445999 994 306142766307989854235546446179 995 317870747805118389613814099435 996 330041946314784759617266659980 997 342672885676196754776954789545 998 355780697465123224264655737643 999 369383143045441647240226724141 1000 383498636410077101221714762993