0 1 1 1 2 4 3 5 4 8 5 12 6 17 7 24 8 36 9 48 10 65 11 88 12 116 13 152 14 200 15 257 16 328 17 420 18 532 19 668 20 840 21 1045 22 1296 23 1604 24 1972 25 2416 26 2952 27 3592 28 4357 29 5272 30 6356 31 7640 32 9168 33 10964 34 13080 35 15576 36 18497 37 21920 38 25932 39 30604 40 36048 41 42392 42 49752 43 58288 44 68184 45 79617 46 92820 47 108060 48 125600 49 145776 50 168972 51 195572 52 226064 53 260988 54 300908 55 346513 56 398572 57 457900 58 525464 59 602352 60 689724 61 788936 62 901520 63 1029108 64 1173600 65 1337124 66 1521969 67 1730784 68 1966508 69 2232336 70 2531920 71 2869316 72 3248952 73 3675836 74 4155544 75 4694152 76 5298520 77 5976264 78 6735693 79 7586144 80 8537964 81 9602464 82 10792304 83 12121480 84 13605308 85 15260872 86 17107028 87 19164432 88 21456032 89 24007136 90 26845464 91 30001729 92 33509776 93 37406636 94 41733272 95 46534748 96 51860364 97 57764552 98 64307092 99 71553380 100 79575464 101 88452388 102 98270592 103 109125112 104 121120124 105 134369461 106 148998096 107 165142876 108 182953220 109 202592948 110 224241240 111 248093624 112 274364192 113 303286844 114 335116664 115 370132592 116 408639092 117 450967976 118 497481632 119 548575260 120 604679233 121 666263072 122 733838364 123 807961788 124 889240048 125 978333616 126 1075960668 127 1182903160 128 1300011580 129 1428210088 130 1568503960 131 1721985672 132 1889841528 133 2073360736 134 2273943260 135 2493108200 136 2732505025 137 2993923552 138 3279304504 139 3590753464 140 3930553424 141 4301178196 142 4705309624 143 5145853340 144 5625955776 145 6149025312 146 6718752152 147 7339129704 148 8014480600 149 8749481696 150 9549190824 151 10419078920 152 11365061280 153 12393530965 154 13511398460 155 14726130632 156 16045792424 157 17479095736 158 19035447832 159 20725003328 160 22558724312 161 24548440496 162 26706913836 163 29047912340 164 31586284804 165 34338040796 166 37320441432 167 40552091872 168 44053040156 169 47844888800 170 51950908948 171 56396162501 172 61207639012 173 66414396332 174 72047711304 175 78141247432 176 84731228084 177 91856621948 178 99559348200 179 107884489528 180 116880519872 181 126599555448 182 137097616152 183 148434904820 184 160676114080 185 173890746544 186 188153456956 187 203544426688 188 220149755424 189 238061879760 190 257380029717 191 278210707360 192 300668198100 193 324875126568 194 350963040736 195 379073035488 196 409356428952 197 441975474336 198 477104119300 199 514928828160 200 555649448024 201 599480132648 202 646650340728 203 697405888392 204 752010071944 205 810744878392 206 873912263248 207 941835512988 208 1014860711452 209 1093358289400 210 1177724675713 211 1268384072264 212 1365790330516 213 1470428950392 214 1582819226352 215 1703516517304 216 1833114663912 217 1972248580596 218 2121596998164 219 2281885383928 220 2453889069024 221 2638436558868 222 2836413056584 223 3048764232416 224 3276500215392 225 3520699840016 226 3782515185408 227 4063176383112 228 4363996730064 229 4686378149520 230 5031816975648 231 5401910103553 232 5798361552624 233 6222989419220 234 6677733266892 235 7164662006904 236 7685982247064 237 8244047163120 238 8841365951912 239 9480613847136 240 10164642758120 241 10896492599480 242 11679403294772 243 12516827522588 244 13412444283016 245 14370173269884 246 15394190127856 247 16488942682256 248 17659168131452 249 18909911292948 250 20246544001952 251 21674785659124 252 23200725031076 253 24830843416133 254 26572039180464 255 28431653782012 256 30417499411704 257 32537888265948 258 34801663585080 259 37218232606696 260 39797601458420 261 42550412145704 262 45487981804904 263 48622344259956 264 51966294062760 265 55533433211384 266 59338220602392 267 63396024424540 268 67723177716272 269 72337037165740 270 77256045390604 271 82499796954772 272 88089108225840 273 94046091346472 274 100394232617584 275 107158475425632 276 114365308031329 277 122042856562320 278 130220983378104 279 138931391175616 280 148207733228768 281 158085729975124 282 168603292375004 283 179800652497208 284 191720501597416 285 204408136179928 286 217911612569256 287 232281910318180 288 247573105020500 289 263842551138736 290 281151075244376 291 299563180330432 292 319147261901904 293 339975836326880 294 362125782214660 295 385678595635896 296 410720659769760 297 437343529866212 298 465644234466644 299 495725593588664 300 527696554902929 301 561672548996384 302 597775864567012 303 636136044741900 304 676890305788728 305 720183979227592 306 766170978727624 307 815014293259680 308 866886507703328 309 921970352516592 310 980459284171120 311 1042558097777800 312 1108483573767840 313 1178465160602384 314 1252745695201064 315 1331582163250060 316 1415246501679272 317 1504026445305128 318 1598226420145012 319 1698168486059248 320 1804193331072892 321 1916661320286272 322 2035953602451112 323 2162473276981688 324 2296646624776240 325 2438924406411841 326 2589783230970076 327 2749726999405724 328 2919288426586800 329 3099030645830876 330 3289548900469888 331 3491472327228280 332 3705465835896032 333 3932232090548024 334 4172513597854504 335 4427094907724680 336 4696804932369792 337 4982519390205688 338 5285163380721324 339 5605714097365756 340 5945203685882488 341 6304722255246892 342 6685421049371760 343 7088515788177876 344 7515290186378764 345 7967099659426712 346 8445375226570528 347 8951627620750740 348 9487451616263388 349 10054530585705240 350 10654641297516764 351 11289658966770917 352 11961562572518412 353 12672440454849080 354 13424496206297552 355 14220054872975952 356 15061569480726944 357 15951627903204464 358 16892960089657136 359 17888445670171988 360 18941121957911096 361 20054192368876800 362 21231035279803204 363 22475213346734712 364 23790483308007928 365 25180806295508552 366 26650358680255748 367 28203543479688448 368 29845002354303024 369 31579628223715460 370 33412578533730344 371 35349289206424072 372 37395489307937332 373 39557216470403880 374 41840833105043360 375 44253043446426420 376 46800911469916272 377 49491879725088120 378 52333789131247621 379 55334899783465176 380 58503912818566732 381 61849993394234256 382 65382794836995216 383 69112484016181452 384 73049768005090160 385 77205922093579896 386 81592819217969760 387 86222960878745864 388 91109509620020160 389 96266323146705624 390 101707990160552072 391 107449868000140728 392 113508122172388200 393 119899767868919056 394 126642713565200336 395 133755806803286028 396 141258882265546332 397 149172812251942888 398 157519559676959076 399 166322233709630160 400 175605148186046432 401 185393882927945196 402 195715348109248312 403 206597851819187560 404 218071170975703300 405 230166625752062272 406 242917157687415873 407 256357411657973176 408 270523821895890268 409 285454702251880232 410 301190340904542192 411 317773099731171272 412 335247518564983800 413 353660424571898900 414 373061046993291040 415 393501137512742892 416 415035096514442364 417 437720105515835320 418 461616266070421064 419 486786745447802216 420 513297929414984512 421 541219582458103440 422 570625015796808496 423 601591263562609540 424 634199267529835140 425 668534070802999736 426 704685020885945528 427 742745982577918032 428 782815561159294684 429 824997336354077812 430 869400107578839592 431 916138151008140088 432 965331489014016204 433 1017106172562899488 434 1071594577176818720 435 1128935713096926209 436 1189275550316782384 437 1252767359179929772 438 1319572067271574804 439 1389858633367722288 440 1463804439236305584 441 1541595700124811072 442 1623427894807100160 443 1709506216098026812 444 1800046042789692176 445 1895273434006691600 446 1995425647018976696 447 2100751679602171728 448 2211512838084748848 449 2327983332268851116 450 2450450898469529668 451 2579217451973620308 452 2714599770273811492 453 2856930208499116648 454 3006557448527243480 455 3163847283326573960 456 3329183438149855096 457 3502968430274832800 458 3685624469058288292 459 3877594398154196736 460 4079342681829901556 461 4291356437395683040 462 4514146515858519604 463 4748248633005429904 464 4994224553214916928 465 5252663328403089013 466 5524182594618584768 467 5809429928906772156 468 6109084269186071888 469 6423857400001495680 470 6754495507141826584 471 7101780804245483156 472 7466533234658975304 473 7849612251950233524 474 8251918682636077324 475 8674396674840781368 476 9118035736760422732 477 9583872868985435176 478 10072994794912838116 479 10586540293659271232 480 11125702640087179400 481 11691732156759734520 482 12285938882844581416 483 12909695365214283244 484 13564439577221969336 485 14251677970863321884 486 14972988668293901044 487 15730024798932394284 488 16524517988644904696 489 17358282007797245168 490 18233216585258806384 491 19151311395742233780 492 20114650228193383224 493 21125415343282259472 494 22185892028387197576 495 23298473358838144952 496 24465665174565971921 497 25690091281692523408 498 26974498889018741068 499 28321764289799920608 500 29734898799637231768 501 31217054961792631032 502 32771533031723251912 503 34401787753130557544 504 36111435438360069564 505 37904261366541071220 506 39784227513421745384 507 41755480627466289312 508 43822360667407149048 509 45989409617087115124 510 48261380694116713280 511 50643247969581389584 512 53140216416759869040 513 55757732407595614764 514 58501494676465449260 515 61377465771612553868 516 64391884015493002708 517 67551275996192096472 518 70862469612998622188 519 74332607700221437768 520 77969162254358289152 521 81779949290781328032 522 85773144357228928760 523 89957298732552476960 524 94341356340359758000 525 98934671408466934208 526 103747026906380791968 527 108788653794381917336 528 114070251119213521001 529 119603006992860069216 530 125398620492424738212 531 131469324520733228704 532 137827909668962134864 533 144487749124313191596 534 151462824667580980304 535 158767753807347731704 536 166417818099485411872 537 174428992702705409816 538 182817977223024824912 539 191602227902216537168 540 200799991207633645108 541 210430338883200734780 542 220513204523845938556 543 231069421738267483888 544 242120763967637808096 545 253689986030648721960 546 265800867468254321728 547 278478257764523697752 548 291748123523174846156 549 305637597682689520184 550 320175030856353301920 551 335390044887128434448 552 351313588711017088864 553 367977996626455062000 554 385417049071293449016 555 403666036013150200452 556 422761823063288081768 557 442742920428703883712 558 463649554821871217624 559 485523744452507207280 560 508409377230835915040 561 532352292317177984769 562 557400365158245793944 563 583603596156271322552 564 611014203123123729248 565 639686717677822077072 566 669678085752321764648 567 701047772377239033572 568 733857870926211191412 569 768173217004877894324 570 804061507178103629124 571 841593422736976181960 572 880842758715318317832 573 921886558374037892616 574 964805253380545770352 575 1009682809919700328224 576 1056606880982395267624 577 1105668965087922185592 578 1156964571706621536200 579 1210593393660194164528 580 1266659486788306551600 581 1325271457181798714924 582 1386542656295009152112 583 1450591384262390332400 584 1517541101757715323804 585 1587520650747892252376 586 1660664484507630653500 587 1737112907275958529856 588 1817012323950999096612 589 1900515500235402066912 590 1987781833661404199720 591 2078977635941803254060 592 2174276427111086690016 593 2273859241939582443584 594 2377914949122937236236 595 2486640583769394515377 596 2600241693728263413216 597 2718932700324793529760 598 2842937274089312817072 599 2972488726091974770156 600 3107830415518956784984 601 3249216174151367689080 602 3396910748434489916920 603 3551190259852470576588 604 3712342684352098320960 605 3880668351588894285840 606 4056480464799585870388 607 4240105642137033265392 608 4431884480336879893864 609 4632172141619790823144 610 4841338964769038442288 611 5059771101360437157948 612 5287871178160421669416 613 5526058986748317136500 614 5774772201460614895304 615 6034467126798560006520 616 6305619475485487872760 617 6588725178407173256336 618 6884301227717205832584 619 7192886554439993638376 620 7515042941956483235540 621 7851355976812317753588 622 8202436038344843861648 623 8568919328684198136100 624 8951468944744912874496 625 9350775993887995470528 626 9767560754999335257892 627 10202573886798854851508 628 10656597685265966530096 629 11130447392140709364696 630 11624972556536725665425 631 12141058451781906681792 632 12679627549685199454236 633 13241641054514035718364 634 13828100499056044944128 635 14440049405231261317688 636 15078575011817267367320 637 15744810071949565253888 638 16439934723163058935780 639 17165178432848228806704 640 17921822022107321711132 641 18711199771111807693456 642 19534701609182858203152 643 20393775392941623683008 644 21289929276005792980132 645 22224734173843718383988 646 23199826327537243119688 647 24216909970349453185808 648 25277760101144338652048 649 26384225368861757068216 650 27538231072413345033512 651 28741782280533602791744 652 29996967076295260065888 653 31305959931179444776616 654 32671025213779635427016 655 34094520838413877141680 656 35578902059122533070676 657 37126725414739481643880 658 38740652830943168541892 659 40423455885420562210324 660 42178020242512440398404 661 44007350263952586275520 662 45914573802566710576976 663 47902947186059885062300 664 49975860398294029946064 665 52136842465739894544224 666 54389567057081701755201 667 56737858304257277755688 668 59185696853532449935180 669 61737226155536520012132 670 64396759003525821111176 671 67168784329495184346424 672 70057974268123384193264 673 73069191498918454187536 674 76207496877322652401952 675 79478157365945688317272 676 82886654277518791615688 677 86438691841601851514036 678 90140206107532134516984 679 93997374196576237364992 680 98016623916737554522052 681 102204643754180668350220 682 106568393255761995234960 683 111115113817703415348972 684 115852339896013597888772 685 120787910654850656071456 686 125929982069630376665576 687 131287039502317783665312 688 136867910766996630050568 689 142681779704492399834244 690 148738200285530866465764 691 155047111262646683473024 692 161618851391815806909000 693 168464175245573204675996 694 175594269640193869510328 695 183020770700361652168312 696 190755781585628435002688 697 198811890903876341915128 698 207202191837939176411460 699 215940302012517800924160 700 225040384129538491522168 701 234517167401154699196560 702 244385969810682981043056 703 254662721232894024699469 704 265363987446251096133648 705 276506995070902921918508 706 288109657467496998745272 707 300190601633184181038340 708 312769196132538345865624 709 325865580102517147799224 710 339500693372043105324456 711 353696307738290923388440 712 368475059443328394275520 713 383860482896376375505296 714 399877045688630862199556 715 416550184949328578133248 716 433906345093538963872872 717 451973017014032832116080 718 470778778771513022740448 719 490353337839497520231872 720 510727574962223855973600 721 531933589686097172013940 722 554004747627435731115068 723 576975729541580381900456 724 600882582260830749817232 725 625762771571153675154932 726 651655237100182450762276 727 678600449291691232403448 728 706640468544490877651304 729 735819006596554570261504 730 766181490238146732684000 731 797775127440800551323724 732 830648975992172492058788 733 864854014730099649181296 734 900443217472601676160056 735 937471629744108386169496 736 975996448401860461220728 737 1016077104270228534432620 738 1057775347894630690808812 739 1101155338530804183278704 740 1146283736489408829576568 741 1193229798960313157218705 742 1242065479445444400116872 743 1292865530933775403665256 744 1345707612956881969659172 745 1400672402668538210091832 746 1457843710097031154672552 747 1517308597724276422999224 748 1579157504551409871046584 749 1643484374816322482316892 750 1710386791534605363064144 751 1779966115041584827086960 752 1852327626719561670717064 753 1927580678101032597115684 754 2005838845545572397518376 755 2087220090695201186783840 756 2171846926920461344258624 757 2259846591977091692577404 758 2351351227101120991829764 759 2446498062778419613404420 760 2545429611433256056693688 761 2648293867289213895215528 762 2755244513664946418138384 763 2866441137976690443094128 764 2982049454729238707822924 765 3102241536787194693400168 766 3227196055228815577619872 767 3357098528095600645540420 768 3492141578362017966597764 769 3632525201461393601800888 770 3778457042716028727731884 771 3930152685032076337979296 772 4087835947232614085946320 773 4251739193415708516757956 774 4422103653738095434648224 775 4599179757039416450502668 776 4783227475736769608436984 777 4974516683434671144809732 778 5173327525711402539451448 779 5379950804559150604345288 780 5594688376972359048330657 781 5817853568196316252352616 782 6049771600166226369264404 783 6290780035685872031200112 784 6541229238914497437182096 785 6801482852750743041188752 786 7071918293723372461018352 787 7352927265020171361488064 788 7644916288308791949466176 789 7948307255026492867708984 790 8263537997839707955510584 791 8591062882999196200846732 792 8931353424342209530681724 793 9284898919719692886029568 794 9652207110654032846172600 795 10033804866061330248570144 796 10430238890901619843457280 797 10842076460650929757475032 798 11269906182520602133256108 799 11714338784381918155470144 800 12176007932387823021719268 801 12655571078318469692713560 802 13153710337713432548050592 803 13671133399890824518084144 804 14208574470992228366219680 805 14766795251232366724040976 806 15346585947573831651252384 807 15948766323090021906211168 808 16574186784323741434698800 809 17223729507994745948787772 810 17898309608456939826739560 811 18598876347354974546084120 812 19326414386980737796580336 813 20081945088882708710969652 814 20866527859335446399001968 815 21681261543332637232068752 816 22527285868825216505892128 817 23405782942986165339555912 818 24317978802345731319144624 819 25265145018705103470950784 820 26248600362803058436047041 821 27269712527778859534928656 822 28329899914545813032186276 823 29430633481263443452231032 824 30573438659172324232654056 825 31759897337134278603496432 826 32991649917302033544165512 827 34270397444426557397721492 828 35597903811397335288114152 829 36975998043700829986376752 830 38406576665575438989576940 831 39891606150737497069594860 832 41433125460652391317928088 833 43033248673427762658393080 834 44694167706512180333114748 835 46418155136492708686906544 836 48207567119398559829318208 837 50064846415035669570932388 838 51992525518998674001545132 839 53993229906132533727982820 840 56069681389346093135826952 841 58224701597814312766602064 842 60461215578744921153601476 843 62782255527028953429589792 844 65190964647243231804332400 845 67690601152626459737010960 846 70284542405809418082457320 847 72976289206243937627360480 848 75769470229445056866837680 849 78667846623336244527938560 850 81675316767168960635280072 851 84795921198675344582775440 852 88033847715306660492572880 853 91393436655610505723927016 854 94879186367006914430418428 855 98495758866437592037068952 856 102247985700583826163635652 857 106140874012577373473700952 858 110179612822365070435936660 859 114369579528132310025372408 860 118716346636443128695053672 861 123225688729015733794598913 862 127903589674322147535910248 863 132756250092479538840500052 864 137790095082189061731689784 865 143011782218775922989701324 866 148428209832692280937491828 867 154046525578162764471068512 868 159874135301981232313459320 869 165918712222807217345544000 870 172188206431661685949495516 871 178690854724684657073166224 872 185435190779592255759931052 873 192430055687658323860838608 874 199684608853446183355736160 875 207208339274929969390384188 876 215011077217072563522585752 877 223103006292369010571997624 878 231494675962320861592210744 879 240197014474278637562768548 880 249221342248577046301473168 881 258579385731391222186029224 882 268283291729262629595907844 883 278345642241780918911262284 884 288779469809463513038320792 885 299598273394448620867889200 886 310816034812210318561470224 887 322447235733116930968583536 888 334506875273286830153520364 889 347010488194849602411903832 890 359974163736396001941653608 891 373414565095097918784857560 892 387348949582700462810949860 893 401795189478332954855672972 894 416771793601854901131733440 895 432297929632247701716293360 896 448393447196383733249570920 897 465078901754352407437080580 898 482375579308398713605873728 899 500305521963434512103252604 900 518891554368017397756298824 901 538157311065657258761808472 902 558127264787307712620231904 903 578826755716929441819242821 904 600282021763076132957999840 905 622520229870552338672575284 906 645569508407327268582445080 907 669458980663060433055512096 908 694218799496805414660909180 909 719880183172708074866392856 910 746475452423806492008568636 911 774038068785373192059663564 912 802602674240617146778351076 913 832205132222984974402028632 914 862882570020769237293699040 915 894673422631248193706457700 916 927617478113147364969554952 917 961755924487830418621142488 918 997131398241296794357390328 919 1033788034480787902339360576 920 1071771518801584352366022880 921 1111129140921415341164860748 922 1151909850141799888698769288 923 1194164312697599994267516176 924 1237944971058089969760143304 925 1283306105244936237753945872 926 1330303896234639865454560936 927 1378996491515222226204787020 928 1429444072869234674985415264 929 1481708926457548308130391668 930 1535855515280832147502796896 931 1591950554098159900811771536 932 1650063086884799343459706204 933 1710264566913936973467108788 934 1772628939549876604471853536 935 1837232727843126770788316264 936 1904155121020761108594950120 937 1973478065968501205982747108 938 2045286361804135841176582848 939 2119667757645157218104963528 940 2196713053676867006931253200 941 2276516205630686060529228352 942 2359174432785995078103746220 943 2444788329612542784849446976 944 2533461981174287073462804728 945 2625303082419486817192777500 946 2720423061485941621015276981 947 2818937207154487665643447888 948 2920964800588204193962957536 949 3026629251499271375594418600 950 3136058238890050691233354760 951 3249383856519738182537235144 952 3366742763252873614545406440 953 3488276338451079652083367000 954 3614130842574659578746392160 955 3744457583166105039666417792 956 3879413086393162091670660332 957 4019159274334879999026924352 958 4163863648200028369498878688 959 4313699477673420220834080212 960 4468845996592027433203537156 961 4629488605159326972374572544 962 4795819078913077659626867904 963 4968035784668704727536690264 964 5146343903667669725270197572 965 5330955662167633535315072760 966 5522090569718887579079799304 967 5719975665379440162994879864 968 5924845772129309034359776812 969 6136943759752995513960033064 970 6356520816467808205488258008 971 6583836729584673670520168640 972 6819160175497326297687428624 973 7062769019305318821686960132 974 7314950624386147787473535960 975 7576002172241954233006838156 976 7846230992956748770635973296 977 8125954906610932189103241000 978 8415502576011048109059657204 979 8715213871104223830086438104 980 9025440245458640376709145472 981 9346545125203634312116515184 982 9678904310835683889057392308 983 10022906392309582672054856060 984 10378953177847567407689418228 985 10747460136913056506631473088 986 11128856857809984309709017152 987 11523587520383498043114992764 988 11932111384313033114626946624 989 12354903293504512701727183392 990 12792454197104644435987840321 991 13245271687677025823595272296 992 13713880557097036776555517684 993 14198823370740308686272828776 994 14700661060557931741238492704 995 15219973537650513098207490488 996 15757360324972746038515791916 997 16313441210820312867855550264 998 16888856923771741121745959164 999 17484269829779283295650002744 1000 18100364652125015066336900792