0 1 1 1 2 1 3 2 4 3 5 5 6 6 7 10 8 14 9 19 10 25 11 36 12 48 13 64 14 84 15 111 16 146 17 191 18 244 19 315 20 404 21 515 22 651 23 823 24 1035 25 1295 26 1616 27 2011 28 2492 29 3076 30 3787 31 4650 32 5695 33 6952 34 8463 35 10280 36 12460 37 15059 38 18162 39 21858 40 26254 41 31463 42 37641 43 44933 44 53554 45 63704 46 75653 47 89683 48 106162 49 125445 50 148020 51 174389 52 205169 53 241013 54 282761 55 331261 56 387609 57 452932 58 528627 59 616188 60 717461 61 834340 62 969218 63 1124611 64 1303555 65 1509303 66 1745807 67 2017230 68 2328630 69 2685412 70 3093990 71 3561311 72 4095615 73 4705705 74 5402065 75 6196023 76 7100798 77 8130780 78 9302786 79 10635015 80 12148708 81 13866962 82 15816452 83 18026353 84 20530323 85 23364972 86 26572531 87 30199157 88 34297595 89 38925697 90 44149533 91 50041354 92 56683567 93 64166508 94 72592626 95 82074492 96 92739609 97 104727744 98 118197056 99 133321256 100 150296009 101 169336458 102 190684731 103 214606680 104 241401134 105 271396493 106 304960717 107 342498536 108 384462913 109 431351466 110 483720586 111 542181853 112 607417361 113 680177067 114 761296667 115 851694201 116 952391582 117 1064511627 118 1189301844 119 1328133115 120 1482527131 121 1654154735 122 1844868978 123 2056704578 124 2291914660 125 2552972980 126 2842616610 127 3163848718 128 3519989330 129 3914680683 130 4351944355 131 4836191379 132 5372288466 133 5965570371 134 6621918595 135 7347778829 136 8150249903 137 9037109420 138 10016917152 139 11099046344 140 12293805640 141 13612479887 142 15067469275 143 16672343948 144 18442005551 145 20392753341 146 22542474498 147 24910727385 148 27518959242 149 30390612800 150 33551379516 151 37029327852 152 40855200504 153 45062572382 154 49688192535 155 54772180933 156 60358425862 157 66494819546 158 73233723891 159 80632256912 160 88752829363 161 97663495233 162 107438576119 163 118159078788 164 129913425188 165 142797954750 166 156917767892 167 172387333192 168 189331467881 169 207886058200 170 228199204475 171 250432081173 172 274760261161 173 301374745587 174 330483503439 175 362312688659 176 397108434685 177 435138299043 178 476693340717 179 522089837960 180 571671701123 181 625812495650 182 684918251528 183 749429852340 184 819826287728 185 896627477949 186 980398049643 187 1071750652004 188 1171350345929 189 1279918504206 190 1398237892860 191 1527157261030 192 1667597233919 193 1820555685569 194 1987114581094 195 2168446273050 196 2365821418340 197 2580616359143 198 2814322296041 199 3068553905441 200 3345059974513 201 3645733468387 202 3972623828892 203 4327948735956 204 4714108341578 205 5133698967607 206 5589529586941 207 6084637781691 208 6622308785527 209 7206094072808 210 7839833373180 211 8527676272067 212 9274107665367 213 10083972860915 214 10962506962568 215 11915364033532 216 12948651024973 217 14068961591879 218 15283415271801 219 16599696692458 220 18026100749358 221 19571578050298 222 21245787018360 223 23059146481212 224 25022895754724 225 27149155488752 226 29450996875465 227 31942512023106 228 34638893671818 229 37556516479353 230 40713028826515 231 44127446681659 232 47820259224751 233 51813537194718 234 56131054400006 235 60798412644278 236 65843181479306 237 71295042200095 238 77185948445369 239 83550292105502 240 90425087844348 241 97850164071599 242 105868374894214 243 114525819862995 244 123872087249000 245 133960506794259 246 144848428878033 247 156597514987979 248 169274057972017 249 182949315735095 250 197699878383946 251 213608051420761 252 230762276528897 253 249257571282371 254 269196011256189 255 290687234394329 256 313848993049929 257 338807732277508 258 365699221757786 259 394669218414122 260 425874189535171 261 459482071715811 262 495673097890807 263 534640666242749 264 576592285772679 265 621750570516510 266 670354320270418 267 722659657745077 268 778941263136344 269 839493674235853 270 904632696283305 271 974696887573933 272 1050049168910801 273 1131078520517670 274 1218201818484302 275 1311865772263870 276 1412549019413079 277 1520764336665019 278 1637061028454879 279 1762027449231890 280 1896293725756127 281 2040534633330849 282 2195472697457274 283 2361881472098743 284 2540589072311576 285 2732481909327483 286 2938508712346176 287 3159684782461680 288 3397096569782174 289 3651906516118210 290 3925358262296643 291 4218782159057389 292 4533601188933052 293 4871337235206438 294 5233617814125812 295 5622183203197001 296 6038894091972600 297 6485739684534220 298 6964846390829558 299 7478487033118103 300 8029090716044087 301 8619253283264320 302 9251748522311628 303 9929540036956585 304 10655793962630527 305 11433892441393873 306 12267448046762851 307 13160319071750534 308 14116625887415321 309 15140768281903815 310 16237444005285225 311 17411668427916911 312 18668795556854377 313 20014540315572549 314 21455002353520230 315 22996691288179067 316 24646553669592805 317 26412001568944251 318 28300943106271625 319 30321814817756628 320 32483616206309054 321 34795946374873773 322 37269043116833487 323 39913824363887300 324 42741932398755931 325 45765780734339327 326 48998604104102092 327 52454511467058864 328 56148542512350821 329 60096727571201435 330 64316151464674869 331 68825021200204848 332 73642738094426643 333 78789974241573057 334 84288753957955022 335 90162540131659767 336 96436326165395156 337 103136733453047338 338 110292115142584689 339 117932666139283420 340 126090540171960796 341 134799973894514418 342 144097418921590499 343 154021681791659823 344 164614072841905636 345 175918564012494214 346 187981956657586318 347 200854059411648612 348 214587877289707848 349 229239812105453347 350 244869875499419286 351 261541914701666769 352 279323852444920530 353 298287941202331654 354 318511033300969861 355 340074867141680320 356 363066371227664139 357 387577986296813779 358 413708007425322987 359 441560946474675726 360 471247916930314532 361 502887041591337102 362 536603885361524084 363 572531913700034406 364 610812979203123360 365 651597836991729289 366 695046691618689141 367 741329776301909370 368 790627967467702687 369 843133435559346213 370 899050335391587695 371 958595537178976776 372 1021999401844413100 373 1089506601930424265 374 1161376992082480502 375 1237886530646324755 376 1319328256747138754 377 1406013324645258778 378 1498272100174524989 379 1596455321341983791 380 1700935328382887637 381 1812107365669241491 382 1930390961302292539 383 2056231387152464608 384 2190101205767737725 385 2332501907323760915 386 2483965643693541550 387 2645057063270012958 388 2816375254342358567 389 2998555801182367727 390 3192272961438441336 391 3398241969579231307 392 3617221475869909391 393 3850016126279416491 394 4097479293777181966 395 4360515967160398637 396 4640085808946020241 397 4937206389299291032 398 5252956608727454818 399 5588480317439802014 400 5944990145419669525 401 6323771552157391190 402 6726187111542856020 403 7153681042036967687 404 7607783999233129460 405 8090118142235470983 406 8602402492743724651 407 9146458599740973212 408 9724216530637511112 409 10337721203406386483 410 10989139082741317674 411 11680765256601450020 412 12415030918576630600 413 13194511274488080722 414 14021933901311213328 415 14900187579120149373 416 15832331627081416176 417 16821605766742281149 418 17871440546887396023 419 18985468356057076948 420 20167535060585512840 421 21421712297422229054 422 22752310463566323241 423 24163892434905179148 424 25661288060671577269 425 27249609470250430521 426 28934267243390931046 427 30720987484936012302 428 32615829860486229243 429 34625206638981017854 430 36755902804533949067 431 39015097288934446309 432 41410385393689687652 433 43949802459051187311 434 46641848856134708913 435 49495516366278681658 436 52520316031737796732 437 55726307549315121603 438 59124130299850171807 439 62725036093444696347 440 66540923733101304442 441 70584375485844667108 442 74868695574772912353 443 79407950791322133837 444 84217013353085522162 445 89311606117797253336 446 94708350291973763063 447 100424815757383520433 448 106479574168354610500 449 112892254957037712716 450 119683604415658681638 451 126875548008333695309 452 134491256099191809445 453 142555213266503155524 454 151093291409103514644 455 160132826833807432280 456 169702701551672274210 457 179833428992838800014 458 190557244391640705041 459 201908200074996892235 460 213922265932072135397 461 226637435324024474010 462 240093836740835710035 463 254333851492598069937 464 269402237774286831661 465 285346261422985214832 466 302215833741926348713 467 320063656745294333318 468 338945376237124738870 469 358919743116923654284 470 380048783368362888949 471 402397977166433519871 472 426036447606852143126 473 451037159540404662745 474 477477129068329538182 475 505437644233699314300 476 535004497522608380209 477 566268230767884436274 478 599324393132745768141 479 634273812830962531337 480 671222883331066487016 481 710283864771673323718 482 751575201412787170381 483 795221855928005423006 484 841355661447706394290 485 890115692244128182391 486 941648654062318887661 487 996109295082776548340 488 1053660838623255734334 489 1114475438670297149544 490 1178734659461970849777 491 1246629980327994117895 492 1318363327134302212428 493 1394147631665754620841 494 1474207420432420813987 495 1558779434373771774461 496 1648113281098590921184 497 1742472121290066346002 498 1842133391081651938591 499 1947389562204189243410 500 2058548941894641287904 501 2175936514555452524081 502 2299894827358272667930 503 2430784921988877878759 504 2568987314950889427269 505 2714903028854108589236 506 2868954677351492786987 507 3031587606402857758616 508 3203271094800488869074 509 3384499616912670767955 510 3575794170878658642322 511 3777703675517166417008 512 3990806439510162449825 513 4215711706461052131849 514 4453061279750111717061 515 4703531231157323713737 516 4967833697572590403747 517 5246718770171907853604 518 5540976480816237123154 519 5851438890501138686615 520 6178982285094126231364 521 6524529483682457541889 522 6889052265296258227894 523 7273573919873874863978 524 7679171929814755474878 525 8106980788585326331295 526 8558194963361063958233 527 9034072008828606633851 528 9535935839832113926272 529 10065180170711656225299 530 10623272129788187952138 531 11211756057638792841694 532 11832257498463078510419 533 12486487394059388199319 534 13176246490641386432906 535 13903429968975333144740 536 14670032309089807180811 537 15478152401094932906057 538 16329998914484347812879 539 17227895938618116145968 540 18174288907991266661566 541 19171750826261721730860 542 20222988803994406633327 543 21330850925496343507996 544 22498333461183802586584 545 23728588442395044050952 546 25024931616718893434772 547 26390850802442246317803 548 27830014661974823623398 549 29346281914709183290522 550 30943711011136398428772 551 32626570290711660989823 552 34399348647442980049362 553 36266766727932079999842 554 38233788688202441944036 555 40305634536496046752855 556 42487793090964352558961 557 44786035582126050933909 558 47206429931858345316485 559 49755355741746420781290 560 52439520025673658805327 561 55265973722715411732394 562 58242129028635224518874 563 61375777585597829261699 564 64675109572143166630995 565 68148733736930224610407 566 71805698422400657929427 567 75655513626140916597600 568 79708174150592797102689 569 83974183893572254393689 570 88464581335177809383521 571 93190966278679344741209 572 98165527906372359088579 573 103401074213611726271771 574 108911062887930348019564 575 114709633702618853412567 576 120811642498157198536923 577 127232696827625764812267 578 133989193346590647018401 579 141098357030986870969984 580 148578282311274181807439 581 156447976214490630659031 582 164727403610997941803106 583 173437534666416541767999 584 182600394604872256497000 585 192239115893768483884846 586 202377992966417774643913 587 213042539603384755903363 588 224259549100052521241098 589 236057157352910461149487 590 248464909004310228539948 591 261513826790935578112678 592 275236484249121602136628 593 289667081936221206520593 594 304841527335804516822235 595 320797518621156981926622 596 337574632460890451084924 597 355214416057838658929716 598 373760483622585611752558 599 393258617491074986551427 600 413756874106827958693049 601 435305695097210086151116 602 457958023685250251911799 603 481769426688318931551494 604 506798222368106191021138 605 533105614407120345657446 606 560755832301227338113957 607 589816278469600396491310 608 620357682399018959550606 609 652454262152475296897986 610 686183893589000194382318 611 721628287655919327372733 612 758873176133211372932048 613 798008506225340628394255 614 839128644416037373837582 615 882332590018733760592725 616 927724198877250606543298 617 975412417690241913126301 618 1025511529456737338110795 619 1078141410560867941169174 620 1133427800039813239167714 621 1191502581601756996170087 622 1252504078988899574247115 623 1316577365305515277190894 624 1383874586961815857274268 625 1454555302911716553930877 626 1528786839896109641112972 627 1606744664433201615608859 628 1688612772333957399065506 629 1774584096553504223579411 630 1864860934229077487235639 631 1959655393791021783352903 632 2059189863076620151206640 633 2163697499415863865368505 634 2273422742705377782137839 635 2388621852529777269230876 636 2509563470441017950811085 637 2636529208553423137484128 638 2769814265667911952825611 639 2909728072190508327631339 640 3056594965171004435125951 641 3210754894844047836387180 642 3372564164121107335061290 643 3542396202543447249385796 644 3720642376278294248503180 645 3907712835807813755354212 646 4104037403038953440540056 647 4310066499635925124300065 648 4526272118462485016469296 649 4753148840101735408242039 650 4991214896514119831919205 651 5241013283982314464234446 652 5503112927592892575199312 653 5778109899600811185876779 654 6066628694132890351974510 655 6369323560791502185276741 656 6686879899839541377717561 657 7020015721762466655067067 658 7369483174133644313044277 659 7736070138834481633253336 660 8120601902822793859158777 661 8523942905779587437698164 662 8946998568118921104496578 663 9390717202994753191262155 664 9856092016106780710717172 665 10344163197270146950532835 666 10856020107896799099658795 667 11392803568713986249938420 668 11955708252244394104863173 669 12545985184766277557421483 670 13164944362688463744267198 671 13813957488486553843826920 672 14494460831582193290333568 673 15207958219777885211547391 674 15956024167116050692385937 675 16740307144282487267795820 676 17562532997953092171843437 677 18424508525756849132209690 678 19328125213831231552761268 679 20275363144244991865737455 680 21268295079893021801303192 681 22309090734793642215740792 682 23400021238077259724175932 683 24543463800310220005484997 684 25741906591187628807554540 685 26997953838015587275564141 686 28314331154827306561821297 687 29693891112398809282020846 688 31139619059890966159790007 689 32654639209303451342450852 690 34242220994427458606619668 691 35905785716483732354064660 692 37648913489177414046747291 693 39475350496445357451900225 694 41389016576763964929874462 695 43394013148478062759617971 696 45494631491255267501951629 697 47695361399415275874157518 698 50000900223583411977203432 699 52416162317819820155677385 700 54946288910136367266374114 701 57596658415077397086339697 702 60372897207867142064447484 703 63280890880458071673653797 704 66326796000712762788170213 705 69517052396856572678984001 706 72858395990314478447815540 707 76357872201029686567056865 708 80022849950422126461276996 709 83861036288215584817744708 710 87880491670514388432944627 711 92089645917675026785221233 712 96497314881769717377663347 713 101112717854705310823968444 714 105945495749420481780651374 715 111005730087961206144166752 716 116303962831711203618100280 717 121851217090551226003631336 718 127659018749324842053671652 719 133739419051616007104030601 720 140105018182585364203435785 721 146768989894381450041950077 722 153745107219534229660816716 723 161047769319661288481990312 724 168692029518870534579021730 725 176693624573332953735486921 726 185069005230728497724074980 727 193835368135538864648861130 728 203010689138581372334662932 729 212613758071645184064315321 730 222664215050718622715539200 731 233182588373976429642813553 732 244190334083547808192890141 733 255709877262997346950877635 734 267764655145546338292380203 735 280379162111223976393155718 736 293578996654497277334395388 737 307390910407362459692194371 738 321842859306526021525570900 739 336964056997032548943911129 740 352785030568651974602736022 741 369337678725387590858070901 742 386655332492758026920085223 743 404772818571901726498710178 744 423726525454208776263702739 745 443554472414956188691454152 746 464296381509473988243736595 747 485993752700548228671979677 748 508689942251246285330227824 749 532430244522970288699623700 750 557261977324487513332026952 751 583234570963785843408451809 752 610399661161047828207976256 753 638811185987655026990364777 754 668525487003124073125663723 755 699601414769056356701087508 756 732100438926762627950844527 757 766086763033013549385455305 758 801627444356585362445337711 759 838792518846719647749874485 760 877655131493526112573482392 761 918291672309522251489303080 762 960781918171162924127625455 763 1005209180769152424642181628 764 1051660460926802190752443051 765 1100226609556475840969356207 766 1151002495535512383159914781 767 1204087180794705655264086832 768 1259584102924718484215164602 769 1317601265618481299991814243 770 1378251437280955261634326323 771 1441652358151376740339658143 772 1507926956297545243720827343 773 1577203572856607347723825870 774 1649616196912441299920713825 775 1725304710415886466276575193 776 1804415143571020168317112721 777 1887099941128176075036095478 778 1973518240042770452910120072 779 2063836158977957770430569573 780 2158227100149039256742192472 781 2256872064028087291098189784 782 2359959977448806188720078173 783 2467688035673903583540362352 784 2580262059010595665099813422 785 2697896864583978350546731469 786 2820816653903283651256542454 787 2949255416882156722698745064 788 3083457353001472998966078501 789 3223677310331502957997169766 790 3370181243159884110915226125 791 3523246689002497664264656374 792 3683163265806452691523890084 793 3850233190187560337959326177 794 4024771817579439431701255520 795 4207108205207323980202695206 796 4397585698837271545254010576 797 4596562544290374306807596715 798 4804412524752306367109060526 799 5021525624950659680071060311 800 5248308723316608268508412562 801 5485186313293036987071005659 802 5732601254998986424530080813 803 5991015558509622634111816657 804 6260911200062578105956747847 805 6542790972554933361559021022 806 6837179371750986543379046390 807 7144623519678776999460100546 808 7465694126753790386928845074 809 7800986494230843256673481721 810 8151121558650560782739960754 811 8516746980014568117768651572 812 8898538275494285936037237309 813 9297200000551479142588091421 814 9713466979425264245173555684 815 10148105587019539200168148854 816 10601915084307608917212438835 817 11075729009456521770984813787 818 11570416626963198186222222808 819 12086884437187180775613499448 820 12626077748761701013660494439 821 13188982316465075973467584754 822 13776626047239200463791982510 823 14390080777150397159971779687 824 15030464122201158428159620544 825 15698941406018646288445765380 826 16396727667568290423625168560 827 17125089752167701133015456309 828 17885348489208526984640969057 829 18678880960131072922242474274 830 19507122860339642073198677182 831 20371570958894884651886046338 832 21273785659974177431154562205 833 22215393670251401775154318796 834 23198090776514746432605245370 835 24223644738014490533625845171 836 25293898298213496966377144541 837 26410772320800496199193726536 838 27576269055021608759198941159 839 28792475535588042493184514019 840 30061567122629023748561886639 841 31385811187377852672977280027 842 32767570949507103308877756129 843 34209309472265463020106888530 844 35713593821815194493766595510 845 37283099397424721746589700200 846 38920614439437145012462809482 847 40629044722211563132715775768 848 42411418439521770714144565800 849 44270891290195156033037091850 850 46210751772085392652528042930 851 48234426692794718127322204240 852 50345486905897263802184373348 853 52547653281762935621480315765 854 54844802922443887789072860615 855 57240975630461543976622552791 856 59740380641723654892551224995 857 62347403633206871285851484262 858 65066614016463123695244889384 859 67902772528446539556683498406 860 70860839131614182293312431348 861 73945981235727341304866832589 862 77163582254273052517310032987 863 80519250508936732856184046381 864 84018828496089020395986537376 865 87668402529801843089944838848 866 91474312776483287675701667896 867 95443163696816696949241242063 868 99581834911309633897317778023 869 103897492506401578775613239611 870 108397600798748675295560439789 871 113089934575998152642676891936 872 117982591833087594569499044188 873 123084007023853619010221793891 874 128402964848514322810709117538 875 133948614598398627292873676730 876 139730485080137170487762384577 877 145758500142402201222636125041 878 152042994829191976221495383426 879 158594732184596995524427124676 880 165424920734965180923966724478 881 172545232675399342064929324801 882 179967822788577354025299036718 883 187705348124981910502076585883 884 195770988474767121115264154220 885 204178467662672101452803960874 886 212942075698621911049704933170 887 222076691817932232472596811803 888 231597808446361166840306856034 889 241521556126627949785540829362 890 251864729444449657039844942514 891 262644813993631574682818134841 892 273880014421290539009093369395 893 285589283595891716003147242786 894 297792352942443984393375425637 895 310509763990925832817166023230 896 323762901185808803231275150290 897 337574026006407551729182673162 898 351966312449721224870995933041 899 366963883929438632550789885622 900 382591851646866676322354413556 901 398876354491706266434213797751 902 415844600532849960940520814115 903 433524910161709429411002499152 904 451946760953006424941653456704 905 471140834310476935758751662802 906 491139063967552862943146010319 907 511974686415797689545261913383 908 533682293336690914355875428712 909 556297886115279349411515717508 910 579858932517250962195166232784 911 604404425614137695120514065498 912 629974945044627376658261293713 913 656612720703360462832478717793 914 684361698952115228950172230726 915 713267611451944295383321569081 916 743378046718626919655007004040 917 774742524507744575944724277532 918 807412573139783497301685583481 919 841441809879916479079313641873 920 876886024491529520611409059899 921 913803266087136386833353476214 922 952253933405078790663692511312 923 992300868645341389769467700533 924 1034009455002932791254881424881 925 1077447718042596235686268586158 926 1122686431064131012303604435849 927 1169799224613328147801852197842 928 1218862700299466776607924191269 929 1269956549086481312766040588746 930 1323163674231310259732162010516 931 1378570319049575980208836889875 932 1436266199695638109073039300503 933 1496344643151212620420648299941 934 1558902730624171967691157993108 935 1624041446566840657226458638437 936 1691865833531094273930292683339 937 1762485153085860206237885595060 938 1836013053031225437746461116437 939 1912567741152283079081481160382 940 1992272165765116337016649297289 941 2075254203316929139145519223350 942 2161646853312309468827025321333 943 2251588440847957932263979975747 944 2345222827048954362479347112132 945 2442699627710773266805667319576 946 2544174440462820285182419289905 947 2649809080781251093990349063078 948 2759771827191278551677780062908 949 2874237676012078592672283243630 950 2993388606010799268721351106684 951 3117413853346066439953430521514 952 3246510197195794517255616146896 953 3380882256479058226915527359600 954 3520742798097294057877951008915 955 3666313057136185659417058916812 956 3817823069486280416898654742717 957 3975512017357693552052837183578 958 4139628588182217918701404952006 959 4310431347414782101341781959952 960 4488189125765525268279110620921 961 4673181421413795587632018252193 962 4865698817776171074162683228397 963 5066043417422159906566089486591 964 5274529292753605279645184082446 965 5491482954087011562075668355380 966 5717243835802070375487291933002 967 5952164801244612565959101485175 968 6196612667098094255335211176347 969 6450968747964559285164087936043 970 6715629421923858833634921792083 971 6991006717868770664230337115897 972 7277528925443601071107508934890 973 7575641228444892964748560139796 974 7885806362575062908795151808156 975 8208505298473171262115757064890 976 8544237950981655845116328215593 977 8893523915643756045647290877755 978 9256903233463587928323951585222 979 9634937184999429537863380117779 980 10028209114900810349534325088595 981 10437325288041500269401235091182 982 10862915778443537397587601033684 983 11305635392232053440527275123044 984 11766164625906931681874799652533 985 12245210661265301489453405655858 986 12743508398358621069800457108004 987 13261821527919666727322967938911 988 13800943644748223338561998010139 989 14361699403599700989977593101851 990 14944945719178383684338267824199 991 15551573011896595605364155936323 992 16182506501122851802773958194291 993 16838707547706095585600638187322 994 17521175047629524190981735005045 995 18230946878716324397935345940295 996 18969101402380997564069387323601 997 19736759022493911125289963259911 998 20535083803503395352968854571749 999 21365285150039177637110585346827 1000 22228619550303344256833190896858