0 1 1 1 2 2 3 4 4 6 5 10 6 14 7 21 8 27 9 40 10 52 11 70 12 92 13 124 14 156 15 206 16 264 17 335 18 425 19 539 20 673 21 847 22 1052 23 1300 24 1611 25 1990 26 2433 27 2977 28 3638 29 4420 30 5367 31 6496 32 7829 33 9439 34 11341 35 13590 36 16270 37 19425 38 23135 39 27525 40 32697 41 38745 42 45844 43 54168 44 63875 45 75247 46 88493 47 103892 48 121846 49 142701 50 166871 51 194920 52 227388 53 264927 54 308327 55 358418 56 416133 57 482653 58 559199 59 647169 60 748266 61 864284 62 997217 63 1149589 64 1323983 65 1523379 66 1751275 67 2011469 68 2308282 69 2646704 70 3032213 71 3470966 72 3970073 73 4537403 74 5181687 75 5913111 76 6742704 77 7682965 78 8748159 79 9953972 80 11318026 81 12860329 82 14602930 83 16570607 84 18791295 85 21295951 86 24119057 87 27299587 88 30880661 89 34910334 90 39442563 91 44537158 92 50260637 93 56687697 94 63900815 95 71991911 96 81063574 97 91229392 98 102615603 99 115362987 100 129627155 101 145580928 102 163416495 103 183346572 104 205606668 105 230458660 106 258191690 107 289126063 108 323616992 109 362056687 110 404878904 111 452564074 112 505642179 113 564699050 114 630382137 115 703405824 116 784558054 117 874709513 118 974819245 119 1085944851 120 1209252879 121 1346027747 122 1497683950 123 1665780693 124 1852032612 125 2058326974 126 2286740884 127 2539557755 128 2819287801 129 3128691749 130 3470801208 131 3848946824 132 4266787025 133 4728337513 134 5238004716 135 5800625933 136 6421504837 137 7106458161 138 7861864161 139 8694712133 140 9612659845 141 10624098473 142 11738214692 143 12965067743 144 14315669097 145 15802067502 146 17437443209 147 19236215591 148 21214148316 149 23388474956 150 25778032111 151 28403400392 152 31287060603 153 34453569072 154 37929733892 155 41744820899 156 45930770967 157 50522433899 158 55557824386 159 61078406538 160 67129386387 161 73760045861 162 81024097763 163 88980068631 164 97691714696 165 107228483389 166 117665991676 167 129086566104 168 141579818252 169 155243265109 170 170183003539 171 186514451649 172 204363126186 173 223865510208 174 245169978200 175 268437797921 176 293844212800 177 321579628570 178 351850866291 179 384882546585 180 420918572118 181 460223728753 182 503085415621 183 549815533711 184 600752487095 185 656263384682 186 716746395747 187 782633297531 188 854392220573 189 932530636949 190 1017598540230 191 1110191922234 192 1210956499192 193 1320591736021 194 1439855179325 195 1569567162652 196 1710615822788 197 1863962564553 198 2030647919200 199 2211797865514 200 2408630632003 201 2622464063693 202 2854723490650 203 3106950272903 204 3380810958353 205 3678107161063 206 4000786177826 207 4350952466819 208 4730879919824 209 5143025150963 210 5590041745888 211 6074795610334 212 6600381457628 213 7170140604486 214 7787680006461 215 8456892829900 216 9181980501244 217 9967476440667 218 10818271537411 219 11739641603781 220 12737276755567 221 13817313099649 222 14986366693405 223 16251570062146 224 17620611369512 225 19101776579202 226 20703994573700 227 22436885743462 228 24310814039373 229 26336942894341 230 28527295176159 231 30894817636245 232 33453449876407 233 36218198514987 234 39205216608639 235 42431888907912 236 45916923196875 237 49680448380128 238 53744119425177 239 58131230074042 240 62866833495489 241 67977871685947 242 73493314026798 243 79444305929044 244 85864327814148 245 92789365688345 246 100258093639730 247 108312069417968 248 116995943728954 249 126357684556378 250 136448817006728 251 147324680377236 252 159044703068178 253 171672696971763 254 185277172321654 255 199931674869750 256 215715146237372 257 232712309802878 258 251014083164808 259 270718019499664 260 291928779333439 261 314758635356338 262 339328011706571 263 365766060982433 264 394211280675582 265 424812172328909 266 457727945716722 267 493129271785155 268 531199086628892 269 572133451042687 270 616142468333683 271 663451265072621 272 714301038258478 273 768950174199662 274 827675442660940 275 890773272635341 276 958561113874466 277 1031378890844495 278 1109590554297252 279 1193585737977050 280 1283781525926755 281 1380624339284729 282 1484591948890215 283 1596195623158906 284 1715982418931590 285 1844537625992253 286 1982487373489786 287 2130501410781388 288 2289296072177290 289 2459637439032471 290 2642344710568212 291 2838293798577481 292 3048421158342647 293 3273727873377778 294 3515284008097710 295 3774233247521563 296 4051797840677651 297 4349283869239192 298 4668086859623489 299 5009697763373240 300 5375709326634075 301 5767822875820789 302 6187855543807810 303 6637747967151333 304 7119572481121080 305 7635541847549775 306 8188018545952923 307 8779524666343603 308 9412752439054180 309 10090575444777010 310 10816060543902573 311 11592480574490140 312 12423327863192813 313 13312328603542699 314 14263458152607856 315 15280957307194770 316 16369349616210597 317 17533459798767917 318 18778433332136412 319 20109757286471915 320 21533282479747093 321 23055247039294001 322 24682301451654792 323 26421535198733453 324 28280505072528334 325 30267265277117285 326 32390399423080969 327 34659054536341691 328 37082977198663661 329 39672551957749115 330 42438842139191127 331 45393633213479372 332 48549478868278690 333 51919749957839209 334 55518686497127447 335 59361452894621793 336 63464196612501012 337 67844110469928645 338 72519498803161902 339 77509847724251439 340 82835899716971023 341 88519732842263881 342 94584844821583958 343 101056242301267979 344 107960535601037067 345 115326039286221029 346 123182878902215494 347 131563104252980965 348 140500809603834351 349 150032261233817430 350 160196032766213215 351 171033148753265290 352 182587236993779034 353 194904690118107159 354 208034836977549394 355 222030124433790035 356 236946310152457627 357 252842667067108586 358 269782200188312467 359 287831876504903194 360 307062868733580295 361 327550813749430714 362 349376086546589745 363 372624090659801298 364 397385565995050538 365 423756915111712860 366 451840549017821993 367 481745253640207792 368 513586578160000679 369 547487246511362665 370 583577593372291597 371 621996026099476646 372 662889514093624451 373 706414107213234168 374 752735484901500723 375 802029537832741697 376 854482983935652770 377 910294020812346126 378 969673016628905090 379 1032843241726615412 380 1100041643275868273 381 1171519665482157301 382 1247544117933626670 383 1328398094892361676 384 1414381948420879120 385 1505814318464646616 386 1603033223121596344 387 1706397212578322998 388 1816286590314298200 389 1933104705456393249 390 2057279320301892774 391 2189264057332045711 392 2329539930201701081 393 2478616963521048435 394 2637035906426403653 395 2805370045309059006 396 2984227121273094760 397 3174251358296866743 398 3376125608311354290 399 3590573619848637614 400 3818362437178252582 401 4060304937342951404 402 4317262512800447072 403 4590147907915054239 404 4879928217886819530 405 5187628059292717044 406 5514332921795773426 407 5861192711234841422 408 6229425494732871538 409 6620321459177878797 410 7035247094921031167 411 7475649617319952201 412 7943061639299489757 413 8439106108977218528 414 8965501527007024944 415 9524067459250381352 416 10116730361078011222 417 10745529730652354543 418 11412624609310627143 419 12120300448335605016 420 12870976362257735506 421 13667212790109769997 422 14511719587028356612 423 15407364569998447831 424 16357182542616354641 425 17364384825306360015 426 18432369318626768828 427 19564731129009884400 428 20765273787638193259 429 22038021095034849812 430 23387229625452970220 431 24817401927231746826 432 26333300456961329010 433 27939962287584227767 434 29642714632445406940 435 31447191229814748887 436 33359349634495086536 437 35385489465915280083 438 37532271664427732345 439 39806738810588903639 440 42216336564804276170 441 44768936288082159811 442 47472858907525525698 443 50336900093917768971 444 53370356821958487385 445 56583055387799956679 446 59985380962114919508 447 63588308761429411673 448 67403436924419883351 449 71443021184859095650 450 75720011437291136883 451 80248090296995542936 452 85041713760706190460 453 90116154080578848601 454 95487544969331927253 455 101172929261153041711 456 107190309158979140624 457 113558699206089999051 458 120298182126653796089 459 127429967687930669843 460 134976454744251903774 461 142961296631808669770 462 151409470091487770850 463 160347347906798060461 464 169802775453050783219 465 179805151364747850191 466 190385512538215619647 467 201576623698439932764 468 213413071770211045598 469 225931365306796252376 470 239170039241737306717 471 253169765243794745196 472 267973467968741139639 473 283626447517627138879 474 300176508426264145377 475 317674095528181186506 476 336172437050072993401 477 355727695318027049333 478 376399125471326686564 479 398249242601884513360 480 421343997757805053303 481 445752963272956834532 482 471549527907068257322 483 498811102306585631746 484 527619335321514266894 485 558060341741823586615 486 590224942044573803850 487 624208914774112621819 488 660113262208187339944 489 698044489997128069777 490 738114901496899931791 491 780442907554627498396 492 825153352542307441447 493 872377857475998391641 494 922255181098779352725 495 974931599851489842272 496 1030561307700470187902 497 1089306836841874227648 498 1151339500351965540394 499 1216839857908169290351 500 1285998205760665574717 501 1359015092195181149237 502 1436101859788256164287 503 1517481215823267208663 504 1603387832302282437149 505 1694068977062476001931 506 1789785177579498144910 507 1890810919121158081730 508 1997435378995909273273 509 2109963198729702951716 510 2228715296094122687066 511 2354029719006599704512 512 2486262543421977232132 513 2625788817442263112389 514 2773003553979796731713 515 2928322774427355893684 516 3092184605908024730035 517 3265050434807608557940 518 3447406119423763832949 519 3639763264708789767334 520 3842660562227570113437 521 4056665198609101210900 522 4282374335929047938079 523 4520416667633141615962 524 4771454053786233919213 525 5036183239621128360691 526 5315337661553742058607 527 5609689345039153392589 528 5920050898854669543841 529 6247277610624421304546 530 6592269648632709874126 531 6955974375224057145524 532 7339388777343683042445 533 7743562020047502937002 534 8169598129091818956444 535 8618658809015118231971 536 9091966403433372810630 537 9590807004601946330370 538 10116533719636641033953 539 10670570101150576623548 540 11254413750436426609263 541 11869640101723094440838 542 12517906396445525730908 543 13200955856904717590661 544 13920622069144751166241 545 14678833585354719326548 546 15477618756597215883203 547 16319110807192678256642 548 17205553162631093113438 549 18139305043461242698999 550 19122847338202762673097 551 20158788768961031333332 552 21249872364077956767238 553 22398982252847697310507 554 23609150798043069570908 555 24883566082761423448345 556 26225579768885019615584 557 27638715345287580277422 558 29126676784781119193400 559 30693357629714158144732 560 32342850527078494305513 561 34079457234986674894601 562 35907699123419722331867 563 37832328193246159126517 564 39858338638650774375668 565 41990978979318459223172 566 44235764789965518861087 567 46598492056133082931366 568 49085251186524113838499 569 51702441713614134856170 570 54456787715763797093414 571 57355353995648044419119 572 60405563051458340123146 573 63615212879072048068903 574 66992495645181706411844 575 70546017273279945063594 576 74284817986366141785647 577 78218393852324486819682 578 82356719380081525459678 579 86710271216932274691257 580 91290052999787759112276 581 96107621415593982287205 582 101175113528760662309518 583 106505275436171185859397 584 112111492313179351233179 585 118007819916989523132050 586 124209017616919303364707 587 130730583024317056177465 588 137588788298302464082640 589 144800718207079523320599 590 152384310028288142361127 591 160358395375778290517465 592 168742744044257704772211 593 177558109967549951527550 594 186826279390649473551784 595 196570121360447641603124 596 206813640644872172186382 597 217582033195308326871004 598 228901744272495388923315 599 240800529361697387023052 600 253307518008770989504225 601 266453280714882046076420 602 280269899033991377541590 603 294791039023930112232574 604 310052028208848820763230 605 326089936218148312134524 606 342943659274613360277857 607 360654008712474816822259 608 379263803714448355932552 609 398817968465545125806912 610 419363633930546178849556 611 440950244471590686738083 612 463629669532269093072750 613 487456320625055044649153 614 512487273869773147909559 615 538782398342207423388782 616 566404490503824067045290 617 595419414996043327140142 618 625896252095461093718182 619 657907452140030460364197 620 691528997250376520368553 621 726840570685279969665246 622 763925734185833325950034 623 802872113679002484267404 624 843771593728218084459349 625 886720521136339645362428 626 931819918124780009933046 627 979175705531920255450260 628 1028898936494082276640662 629 1081106041093440027034111 630 1135919082479232640472341 631 1193466024991686436986831 632 1253881014842047045121181 633 1317304673927270289892584 634 1383884407384106996702395 635 1453774725514757473270163 636 1527137580744847188198668 637 1604142720304413918892863 638 1684968055353776631852543 639 1769800047308817071735139 640 1858834112154221779255269 641 1952275043568859094794930 642 2050337455724573025785598 643 2153246246658532978627663 644 2261237083159753061410584 645 2374556908152770310806676 646 2493464471605612856954122 647 2618230886035397427298143 648 2749140207733030961226467 649 2886490044878872365688552 650 3030592193773695621622871 651 3181773304464220424734706 652 3340375577099697090436802 653 3506757490415905152483890 654 3681294563805301231639392 655 3864380154497309679526486 656 4056426291440738940505605 657 4257864547551426409253284 658 4469146952062313014375779 659 4690746944790649497182101 660 4923160374217783770714579 661 5166906541361422578960060 662 5422529291508244791621859 663 5690598155966742741634336 664 5971709546096025560459657 665 6266488001966538903323171 666 6575587498113079550351877 667 6899692808949646881369288 668 7239520936529417925676937 669 7595822603452024650193422 670 7969383813844194520190663 671 8361027485469289987008087 672 8771615156156191500953202 673 9202048767878951533885426 674 9653272531965549208694695 675 10126274879067573002176793 676 10622090497682601717310109 677 11141802465188161205197357 678 11686544475520256628536686 679 12257503167811382744392230 680 12855920560492454521173141 681 13483096595561087767322487 682 14140391797924958351462122 683 14829230054944441620364728 684 15551101521523249637208453 685 16307565656330260766564162 686 17100254394980053333456859 687 17930875466254785526672101 688 18801215857715898723929432 689 19713145437331697251626299 690 20668620738036075265957847 691 21669688912435624396308909 692 22718491865196981348202753 693 23817270570974733665782234 694 24968369586082429861041591 695 26174241762466484962811225 696 27437453172914986067699721 697 28760688256821914319701308 698 30146755196232085778545180 699 31598591532314586173708040 700 33119270032852636160318864 701 34712004821797180532563245 702 36380157782410074678717211 703 38127245246022150338988913 704 39956944978951742511699273 705 41873103480672157706665421 706 43879743606882160643198766 707 45981072531723674116010719 708 48181490064005662137459746 709 50485597332934543878647580 710 52898205859519650231227431 711 55424347030519255302041528 712 58069281992518829392806883 713 60838511984490577627738010 714 63737789127972339675853188 715 66773127694826890234190070 716 69950815873399952945841148 717 73277428054789335608059710 718 76759837661868939763385793 719 80405230544682678575171951 720 84221118966835054503720511 721 88215356208560171988080272 722 92396151813249880002286458 723 96772087505367614492715500 724 101352133808868028414994375 725 106145667396486928435638292 726 111162489201562169673421937 727 116412843325397490263000537 728 121907436774588702000536406 729 127657460064198924119393665 730 133674608724197690131770683 731 139971105748171765371616097 732 146559725024974556324361628 733 153453815795710343328347099 734 160667328180250554093855174 735 168214839819356478935569085 736 176111583680437709870863908 737 184373477077013048248900438 738 193017151954062349837903223 739 202059986493668989587697060 740 211520138097655218346362710 741 221416577806312238292752334 742 231769126214825456553351989 743 242598490951599071760175436 744 253926305785395258379824199 745 265775171431028147802830478 746 278168698126294186862636311 747 291131550055885139812985378 748 304689491701220907754287600 749 318869436198463816803232798 750 333699495790437304876622506 751 349209034461777889377370641 752 365428722850403509398348594 753 382390595532292233423600512 754 400128110780636876245740913 755 418676212904682311454468074 756 438071397277967576192217695 757 458351778170293928844557003 758 479557159502527673405790846 759 501729108648333181116301798 760 524911033412122453612074944 761 549148262317913909721297574 762 574488128349420703512753934 763 600980056287549729446935974 764 628675653797592995613317030 765 657628806424746039263068160 766 687895776663200615932262317 767 719535307270944739447472805 768 752608729009570066236130963 769 787180072995849331116899953 770 823316187859613594305993990 771 861086861910546242686132229 772 900564950524927368373310505 773 941826508972125275563577101 774 984950930909751691020011926 775 1030021092785891970638077930 776 1077123504396702427306144284 777 1126348465857953374343109154 778 1177790231259800863957077711 779 1231547179285213362266455751 780 1287721991084075153736921130 781 1346421835707058616387785583 782 1407758563415917313306569731 783 1471848907199925262093724795 784 1538814692841790780847007359 785 1608783057890531913632476495 786 1681886679913532067835239104 787 1758264014415327020402543711 788 1838059542826626917182544355 789 1921424030983679221407950867 790 2008514798535351532867001630 791 2099495999733288946768122114 792 2194538916079201768167728754 793 2293822261322800485069410407 794 2397532499324140571428175742 795 2505864175315207036597695453 796 2619020261117484490490659762 797 2737212514895062719620607442 798 2860661856046549551153051400 799 2989598755863744962849043419 800 3124263644610704728635003486 801 3264907335703534397721594564 802 3411791467699039621565690032 803 3565188964829266238860686077 804 3725384516849030623863371305 805 3892675078994820773961469417 806 4067370392885982235176738298 807 4249793529232947379561588724 808 4440281453252466054529744740 809 4639185613726411650199709947 810 4846872556678817262224153766 811 5063724564685407904920794251 812 5290140322871088859674797426 813 5526535612693698204711534071 814 5773344034656890025459910251 815 6031017761141360066344855271 816 6300028320591819107218595722 817 6580867414347243187588390370 818 6874047767454050618440789504 819 7180104014856061721644621510 820 7499593624411460704445564323 821 7833097858245594863157577154 822 8181222774009392751183583315 823 8544600267676562039269433220 824 8923889159578624444020312722 825 9319776325445368961060213588 826 9732977874289547707680136921 827 10164240375048718884321397615 828 10614342133974158332219990720 829 11084094524836841718412765554 830 11574343374103751420436562721 831 12085970403324322072200622426 832 12619894731056823301536589010 833 13177074436758034093968149699 834 13758508189156816898350205861 835 14365236941733308773716723649 836 14998345698030548413811433465 837 15658965349634621377800738576 838 16348274589772979383977506578 839 17067501905598655500362840711 840 17817927652350815659029541718 841 18600886212709654318667037488 842 19417768244796231547797348859 843 20270023022405671271306675659 844 21159160871205383266735954261 845 22086755704778861626515339070 846 23054447664550352348691594960 847 24063945867786516534942982984 848 25117031268038362304888188315 849 26215559632560440430746755990 850 27361464641424832497045414853 851 28556761113235088376698166032 852 29803548362540247671048896398 853 31104013694251711089604650051 854 32460436040576288804953064526 855 33875189746197570101312539072 856 35350748507665130578525342034 857 36889689473187370930258689156 858 38494697509269287185704077634 859 40168569640891583957051970994 860 41914219672192607737909797124 861 43734682994890002788271186085 862 45633121591965153451090304179 863 47612829244430810674089392496 864 49677236949311212760513587465 865 51829918557284970709269386757 866 54074596638774434866815089195 867 56415148587611697161855882190 868 58855612971771284591314434622 869 61400196141033508145329781644 870 64053279101830857016308279467 871 66819424669933354975057637010 872 69703384912047974522220772869 873 72710108887842663072379378005 874 75844750704357867693907930971 875 79112677895238326401093163901 876 82519480137705965035897552927 877 86070978320701725876421227385 878 89773233978150747937774841667 879 93632559101852300639397881026 880 97655526349063986931936014114 881 101848979660439819074669504392 882 106220045304594633110634798689 883 110776143366203849883461046177 884 115524999695208677024295628951 885 120474658335383448774613540031 886 125633494451234852200433726565 887 131010227772943333388438840904 888 136613936579826021633523964015 889 142454072243599176000473220215 890 148540474353547531250464576933 891 154883386446569205807416274517 892 161493472365959201664987847330 893 168381833273723272377850691090 894 175560025342178319515276085330 895 183040078151596895042050878825 896 190834513821693193457461854569 897 198956366905827612599966175262 898 207419205077928007065587786835 899 216237150643289765063338411256 900 225424902905625382176713446790 901 234997761423989016586141819039 902 244971650194504285050314377590 903 255363142793176159718771911193 904 266189488517472078297725559393 905 277468639565815286019745834585 906 289219279295646953097777621455 907 301460851602284907453832164161 908 314213591462438006147241692678 909 327498556687928552471412581193 910 341337660936933027941605982213 911 355753708031876234567592172876 912 370770427635008185943060482500 913 386412512334659416616187870202 914 402705656197211438400699934017 915 419676594841937729845374497997 916 437353147098069742923954556767 917 455764258305725033356078723765 918 474940045324703826184267118431 919 494911843317619430469293911395 920 515712254376380207314016346271 921 537375198063689834868708606964 922 559935963943981943692638420765 923 583431266181058641989161840653 924 607899300282663822629763119243 925 633379802075295553383701990374 926 659914108995751396991312633521 927 687545223789210605093427557851 928 716317880707092188438900633152 929 746278614301492629878956771356 930 777475830916706218526823515329 931 809959882982169740107425619444 932 843783146215156660143661546159 933 879000099845679458365543530454 934 915667409980347899431161909692 935 953844016226381637918291668001 936 993591221701593552460410364591 937 1034972786560951901927585198431 938 1078055025175301137308851993847 939 1122906907102979771221750702302 940 1169600162000425920914096990628 941 1218209388623414287155929742818 942 1268812168076329740317643375964 943 1321489181472860182023082359336 944 1376324332177692815334228560032 945 1433404872805231792513570614245 946 1492821537158029886302045101639 947 1554668677294551373041208500723 948 1619044405923066826448028827204 949 1686050744325932690103755936233 950 1755793776026239107383551260233 951 1828383806416828944787599996356 952 1903935528580009761082547001993 953 1982568195534909822236953553899 954 2064405799158380436929452387455 955 2149577256034631883970135947110 956 2238216600498421158464870410935 957 2330463185146599554915427567711 958 2426461889103189772513069006001 959 2526363334333909594387986155114 960 2630324110317206266920249474474 961 2738507007390427326763535686478 962 2851081259101744839943303331660 963 2968222793910886757887130759225 964 3090114496594627522964730962766 965 3216946479726367268203868533839 966 3348916365613002312441654795704 967 3486229579086677503687863981170 968 3629099651563931954176652977546 969 3777748536800223534823381991006 970 3932406938783864176460885675827 971 4093314652230038696135050876051 972 4260720916152836028427776923409 973 4434884781011116075842723054755 974 4616075489942590983533486958901 975 4804572874619740831014661527076 976 5000667766281135302120745020017 977 5204662422512420960602525929259 978 5416870970372684931017064879468 979 5637619866484148084787404937692 980 5867248374726202823991004685973 981 6106109062198722305209268842505 982 6354568314144360114596570593279 983 6613006868545264248106451047398 984 6881820371136279678459184919752 985 7161419951604344405822429759114 986 7452232821772430014928305505791 987 7754702896596076517030883537303 988 8069291438831360549139804476549 989 8396477728265055652784934777751 990 8736759756430834040669927563415 991 9090654947769663691039610770013 992 9458700908228116439000450238021 993 9841456202325167769425398244720 994 10239501159756284096054904754780 995 10653438712643207565465970616580 996 11083895264578912106264939410601 997 11531521592659770242096289309490 998 11996993783741092015995696215687 999 12481014206197931736206159646117 1000 12984312518520462987343473997753