0 1 1 1 2 2 3 2 4 4 5 5 6 7 7 10 8 15 9 19 10 26 11 36 12 49 13 64 14 85 15 111 16 147 17 191 18 245 19 315 20 405 21 515 22 652 23 823 24 1036 25 1295 26 1617 27 2011 28 2493 29 3076 30 3788 31 4650 32 5696 33 6952 34 8464 35 10280 36 12461 37 15059 38 18163 39 21858 40 26255 41 31463 42 37642 43 44933 44 53555 45 63704 46 75654 47 89683 48 106163 49 125445 50 148021 51 174389 52 205170 53 241013 54 282762 55 331261 56 387610 57 452932 58 528628 59 616188 60 717462 61 834340 62 969219 63 1124611 64 1303556 65 1509303 66 1745808 67 2017230 68 2328631 69 2685412 70 3093991 71 3561311 72 4095616 73 4705705 74 5402066 75 6196023 76 7100799 77 8130780 78 9302787 79 10635015 80 12148709 81 13866962 82 15816453 83 18026353 84 20530324 85 23364972 86 26572532 87 30199157 88 34297596 89 38925697 90 44149534 91 50041354 92 56683568 93 64166508 94 72592627 95 82074492 96 92739610 97 104727744 98 118197057 99 133321256 100 150296010 101 169336458 102 190684732 103 214606680 104 241401135 105 271396493 106 304960718 107 342498536 108 384462914 109 431351466 110 483720587 111 542181853 112 607417362 113 680177067 114 761296668 115 851694201 116 952391583 117 1064511627 118 1189301845 119 1328133115 120 1482527132 121 1654154735 122 1844868979 123 2056704578 124 2291914661 125 2552972980 126 2842616611 127 3163848718 128 3519989331 129 3914680683 130 4351944356 131 4836191379 132 5372288467 133 5965570371 134 6621918596 135 7347778829 136 8150249904 137 9037109420 138 10016917153 139 11099046344 140 12293805641 141 13612479887 142 15067469276 143 16672343948 144 18442005552 145 20392753341 146 22542474499 147 24910727385 148 27518959243 149 30390612800 150 33551379517 151 37029327852 152 40855200505 153 45062572382 154 49688192536 155 54772180933 156 60358425863 157 66494819546 158 73233723892 159 80632256912 160 88752829364 161 97663495233 162 107438576120 163 118159078788 164 129913425189 165 142797954750 166 156917767893 167 172387333192 168 189331467882 169 207886058200 170 228199204476 171 250432081173 172 274760261162 173 301374745587 174 330483503440 175 362312688659 176 397108434686 177 435138299043 178 476693340718 179 522089837960 180 571671701124 181 625812495650 182 684918251529 183 749429852340 184 819826287729 185 896627477949 186 980398049644 187 1071750652004 188 1171350345930 189 1279918504206 190 1398237892861 191 1527157261030 192 1667597233920 193 1820555685569 194 1987114581095 195 2168446273050 196 2365821418341 197 2580616359143 198 2814322296042 199 3068553905441 200 3345059974514 201 3645733468387 202 3972623828893 203 4327948735956 204 4714108341579 205 5133698967607 206 5589529586942 207 6084637781691 208 6622308785528 209 7206094072808 210 7839833373181 211 8527676272067 212 9274107665368 213 10083972860915 214 10962506962569 215 11915364033532 216 12948651024974 217 14068961591879 218 15283415271802 219 16599696692458 220 18026100749359 221 19571578050298 222 21245787018361 223 23059146481212 224 25022895754725 225 27149155488752 226 29450996875466 227 31942512023106 228 34638893671819 229 37556516479353 230 40713028826516 231 44127446681659 232 47820259224752 233 51813537194718 234 56131054400007 235 60798412644278 236 65843181479307 237 71295042200095 238 77185948445370 239 83550292105502 240 90425087844349 241 97850164071599 242 105868374894215 243 114525819862995 244 123872087249001 245 133960506794259 246 144848428878034 247 156597514987979 248 169274057972018 249 182949315735095 250 197699878383947 251 213608051420761 252 230762276528898 253 249257571282371 254 269196011256190 255 290687234394329 256 313848993049930 257 338807732277508 258 365699221757787 259 394669218414122 260 425874189535172 261 459482071715811 262 495673097890808 263 534640666242749 264 576592285772680 265 621750570516510 266 670354320270419 267 722659657745077 268 778941263136345 269 839493674235853 270 904632696283306 271 974696887573933 272 1050049168910802 273 1131078520517670 274 1218201818484303 275 1311865772263870 276 1412549019413080 277 1520764336665019 278 1637061028454880 279 1762027449231890 280 1896293725756128 281 2040534633330849 282 2195472697457275 283 2361881472098743 284 2540589072311577 285 2732481909327483 286 2938508712346177 287 3159684782461680 288 3397096569782175 289 3651906516118210 290 3925358262296644 291 4218782159057389 292 4533601188933053 293 4871337235206438 294 5233617814125813 295 5622183203197001 296 6038894091972601 297 6485739684534220 298 6964846390829559 299 7478487033118103 300 8029090716044088 301 8619253283264320 302 9251748522311629 303 9929540036956585 304 10655793962630528 305 11433892441393873 306 12267448046762852 307 13160319071750534 308 14116625887415322 309 15140768281903815 310 16237444005285226 311 17411668427916911 312 18668795556854378 313 20014540315572549 314 21455002353520231 315 22996691288179067 316 24646553669592806 317 26412001568944251 318 28300943106271626 319 30321814817756628 320 32483616206309055 321 34795946374873773 322 37269043116833488 323 39913824363887300 324 42741932398755932 325 45765780734339327 326 48998604104102093 327 52454511467058864 328 56148542512350822 329 60096727571201435 330 64316151464674870 331 68825021200204848 332 73642738094426644 333 78789974241573057 334 84288753957955023 335 90162540131659767 336 96436326165395157 337 103136733453047338 338 110292115142584690 339 117932666139283420 340 126090540171960797 341 134799973894514418 342 144097418921590500 343 154021681791659823 344 164614072841905637 345 175918564012494214 346 187981956657586319 347 200854059411648612 348 214587877289707849 349 229239812105453347 350 244869875499419287 351 261541914701666769 352 279323852444920531 353 298287941202331654 354 318511033300969862 355 340074867141680320 356 363066371227664140 357 387577986296813779 358 413708007425322988 359 441560946474675726 360 471247916930314533 361 502887041591337102 362 536603885361524085 363 572531913700034406 364 610812979203123361 365 651597836991729289 366 695046691618689142 367 741329776301909370 368 790627967467702688 369 843133435559346213 370 899050335391587696 371 958595537178976776 372 1021999401844413101 373 1089506601930424265 374 1161376992082480503 375 1237886530646324755 376 1319328256747138755 377 1406013324645258778 378 1498272100174524990 379 1596455321341983791 380 1700935328382887638 381 1812107365669241491 382 1930390961302292540 383 2056231387152464608 384 2190101205767737726 385 2332501907323760915 386 2483965643693541551 387 2645057063270012958 388 2816375254342358568 389 2998555801182367727 390 3192272961438441337 391 3398241969579231307 392 3617221475869909392 393 3850016126279416491 394 4097479293777181967 395 4360515967160398637 396 4640085808946020242 397 4937206389299291032 398 5252956608727454819 399 5588480317439802014 400 5944990145419669526 401 6323771552157391190 402 6726187111542856021 403 7153681042036967687 404 7607783999233129461 405 8090118142235470983 406 8602402492743724652 407 9146458599740973212 408 9724216530637511113 409 10337721203406386483 410 10989139082741317675 411 11680765256601450020 412 12415030918576630601 413 13194511274488080722 414 14021933901311213329 415 14900187579120149373 416 15832331627081416177 417 16821605766742281149 418 17871440546887396024 419 18985468356057076948 420 20167535060585512841 421 21421712297422229054 422 22752310463566323242 423 24163892434905179148 424 25661288060671577270 425 27249609470250430521 426 28934267243390931047 427 30720987484936012302 428 32615829860486229244 429 34625206638981017854 430 36755902804533949068 431 39015097288934446309 432 41410385393689687653 433 43949802459051187311 434 46641848856134708914 435 49495516366278681658 436 52520316031737796733 437 55726307549315121603 438 59124130299850171808 439 62725036093444696347 440 66540923733101304443 441 70584375485844667108 442 74868695574772912354 443 79407950791322133837 444 84217013353085522163 445 89311606117797253336 446 94708350291973763064 447 100424815757383520433 448 106479574168354610501 449 112892254957037712716 450 119683604415658681639 451 126875548008333695309 452 134491256099191809446 453 142555213266503155524 454 151093291409103514645 455 160132826833807432280 456 169702701551672274211 457 179833428992838800014 458 190557244391640705042 459 201908200074996892235 460 213922265932072135398 461 226637435324024474010 462 240093836740835710036 463 254333851492598069937 464 269402237774286831662 465 285346261422985214832 466 302215833741926348714 467 320063656745294333318 468 338945376237124738871 469 358919743116923654284 470 380048783368362888950 471 402397977166433519871 472 426036447606852143127 473 451037159540404662745 474 477477129068329538183 475 505437644233699314300 476 535004497522608380210 477 566268230767884436274 478 599324393132745768142 479 634273812830962531337 480 671222883331066487017 481 710283864771673323718 482 751575201412787170382 483 795221855928005423006 484 841355661447706394291 485 890115692244128182391 486 941648654062318887662 487 996109295082776548340 488 1053660838623255734335 489 1114475438670297149544 490 1178734659461970849778 491 1246629980327994117895 492 1318363327134302212429 493 1394147631665754620841 494 1474207420432420813988 495 1558779434373771774461 496 1648113281098590921185 497 1742472121290066346002 498 1842133391081651938592 499 1947389562204189243410 500 2058548941894641287905 501 2175936514555452524081 502 2299894827358272667931 503 2430784921988877878759 504 2568987314950889427270 505 2714903028854108589236 506 2868954677351492786988 507 3031587606402857758616 508 3203271094800488869075 509 3384499616912670767955 510 3575794170878658642323 511 3777703675517166417008 512 3990806439510162449826 513 4215711706461052131849 514 4453061279750111717062 515 4703531231157323713737 516 4967833697572590403748 517 5246718770171907853604 518 5540976480816237123155 519 5851438890501138686615 520 6178982285094126231365 521 6524529483682457541889 522 6889052265296258227895 523 7273573919873874863978 524 7679171929814755474879 525 8106980788585326331295 526 8558194963361063958234 527 9034072008828606633851 528 9535935839832113926273 529 10065180170711656225299 530 10623272129788187952139 531 11211756057638792841694 532 11832257498463078510420 533 12486487394059388199319 534 13176246490641386432907 535 13903429968975333144740 536 14670032309089807180812 537 15478152401094932906057 538 16329998914484347812880 539 17227895938618116145968 540 18174288907991266661567 541 19171750826261721730860 542 20222988803994406633328 543 21330850925496343507996 544 22498333461183802586585 545 23728588442395044050952 546 25024931616718893434773 547 26390850802442246317803 548 27830014661974823623399 549 29346281914709183290522 550 30943711011136398428773 551 32626570290711660989823 552 34399348647442980049363 553 36266766727932079999842 554 38233788688202441944037 555 40305634536496046752855 556 42487793090964352558962 557 44786035582126050933909 558 47206429931858345316486 559 49755355741746420781290 560 52439520025673658805328 561 55265973722715411732394 562 58242129028635224518875 563 61375777585597829261699 564 64675109572143166630996 565 68148733736930224610407 566 71805698422400657929428 567 75655513626140916597600 568 79708174150592797102690 569 83974183893572254393689 570 88464581335177809383522 571 93190966278679344741209 572 98165527906372359088580 573 103401074213611726271771 574 108911062887930348019565 575 114709633702618853412567 576 120811642498157198536924 577 127232696827625764812267 578 133989193346590647018402 579 141098357030986870969984 580 148578282311274181807440 581 156447976214490630659031 582 164727403610997941803107 583 173437534666416541767999 584 182600394604872256497001 585 192239115893768483884846 586 202377992966417774643914 587 213042539603384755903363 588 224259549100052521241099 589 236057157352910461149487 590 248464909004310228539949 591 261513826790935578112678 592 275236484249121602136629 593 289667081936221206520593 594 304841527335804516822236 595 320797518621156981926622 596 337574632460890451084925 597 355214416057838658929716 598 373760483622585611752559 599 393258617491074986551427 600 413756874106827958693050 601 435305695097210086151116 602 457958023685250251911800 603 481769426688318931551494 604 506798222368106191021139 605 533105614407120345657446 606 560755832301227338113958 607 589816278469600396491310 608 620357682399018959550607 609 652454262152475296897986 610 686183893589000194382319 611 721628287655919327372733 612 758873176133211372932049 613 798008506225340628394255 614 839128644416037373837583 615 882332590018733760592725 616 927724198877250606543299 617 975412417690241913126301 618 1025511529456737338110796 619 1078141410560867941169174 620 1133427800039813239167715 621 1191502581601756996170087 622 1252504078988899574247116 623 1316577365305515277190894 624 1383874586961815857274269 625 1454555302911716553930877 626 1528786839896109641112973 627 1606744664433201615608859 628 1688612772333957399065507 629 1774584096553504223579411 630 1864860934229077487235640 631 1959655393791021783352903 632 2059189863076620151206641 633 2163697499415863865368505 634 2273422742705377782137840 635 2388621852529777269230876 636 2509563470441017950811086 637 2636529208553423137484128 638 2769814265667911952825612 639 2909728072190508327631339 640 3056594965171004435125952 641 3210754894844047836387180 642 3372564164121107335061291 643 3542396202543447249385796 644 3720642376278294248503181 645 3907712835807813755354212 646 4104037403038953440540057 647 4310066499635925124300065 648 4526272118462485016469297 649 4753148840101735408242039 650 4991214896514119831919206 651 5241013283982314464234446 652 5503112927592892575199313 653 5778109899600811185876779 654 6066628694132890351974511 655 6369323560791502185276741 656 6686879899839541377717562 657 7020015721762466655067067 658 7369483174133644313044278 659 7736070138834481633253336 660 8120601902822793859158778 661 8523942905779587437698164 662 8946998568118921104496579 663 9390717202994753191262155 664 9856092016106780710717173 665 10344163197270146950532835 666 10856020107896799099658796 667 11392803568713986249938420 668 11955708252244394104863174 669 12545985184766277557421483 670 13164944362688463744267199 671 13813957488486553843826920 672 14494460831582193290333569 673 15207958219777885211547391 674 15956024167116050692385938 675 16740307144282487267795820 676 17562532997953092171843438 677 18424508525756849132209690 678 19328125213831231552761269 679 20275363144244991865737455 680 21268295079893021801303193 681 22309090734793642215740792 682 23400021238077259724175933 683 24543463800310220005484997 684 25741906591187628807554541 685 26997953838015587275564141 686 28314331154827306561821298 687 29693891112398809282020846 688 31139619059890966159790008 689 32654639209303451342450852 690 34242220994427458606619669 691 35905785716483732354064660 692 37648913489177414046747292 693 39475350496445357451900225 694 41389016576763964929874463 695 43394013148478062759617971 696 45494631491255267501951630 697 47695361399415275874157518 698 50000900223583411977203433 699 52416162317819820155677385 700 54946288910136367266374115 701 57596658415077397086339697 702 60372897207867142064447485 703 63280890880458071673653797 704 66326796000712762788170214 705 69517052396856572678984001 706 72858395990314478447815541 707 76357872201029686567056865 708 80022849950422126461276997 709 83861036288215584817744708 710 87880491670514388432944628 711 92089645917675026785221233 712 96497314881769717377663348 713 101112717854705310823968444 714 105945495749420481780651375 715 111005730087961206144166752 716 116303962831711203618100281 717 121851217090551226003631336 718 127659018749324842053671653 719 133739419051616007104030601 720 140105018182585364203435786 721 146768989894381450041950077 722 153745107219534229660816717 723 161047769319661288481990312 724 168692029518870534579021731 725 176693624573332953735486921 726 185069005230728497724074981 727 193835368135538864648861130 728 203010689138581372334662933 729 212613758071645184064315321 730 222664215050718622715539201 731 233182588373976429642813553 732 244190334083547808192890142 733 255709877262997346950877635 734 267764655145546338292380204 735 280379162111223976393155718 736 293578996654497277334395389 737 307390910407362459692194371 738 321842859306526021525570901 739 336964056997032548943911129 740 352785030568651974602736023 741 369337678725387590858070901 742 386655332492758026920085224 743 404772818571901726498710178 744 423726525454208776263702740 745 443554472414956188691454152 746 464296381509473988243736596 747 485993752700548228671979677 748 508689942251246285330227825 749 532430244522970288699623700 750 557261977324487513332026953 751 583234570963785843408451809 752 610399661161047828207976257 753 638811185987655026990364777 754 668525487003124073125663724 755 699601414769056356701087508 756 732100438926762627950844528 757 766086763033013549385455305 758 801627444356585362445337712 759 838792518846719647749874485 760 877655131493526112573482393 761 918291672309522251489303080 762 960781918171162924127625456 763 1005209180769152424642181628 764 1051660460926802190752443052 765 1100226609556475840969356207 766 1151002495535512383159914782 767 1204087180794705655264086832 768 1259584102924718484215164603 769 1317601265618481299991814243 770 1378251437280955261634326324 771 1441652358151376740339658143 772 1507926956297545243720827344 773 1577203572856607347723825870 774 1649616196912441299920713826 775 1725304710415886466276575193 776 1804415143571020168317112722 777 1887099941128176075036095478 778 1973518240042770452910120073 779 2063836158977957770430569573 780 2158227100149039256742192473 781 2256872064028087291098189784 782 2359959977448806188720078174 783 2467688035673903583540362352 784 2580262059010595665099813423 785 2697896864583978350546731469 786 2820816653903283651256542455 787 2949255416882156722698745064 788 3083457353001472998966078502 789 3223677310331502957997169766 790 3370181243159884110915226126 791 3523246689002497664264656374 792 3683163265806452691523890085 793 3850233190187560337959326177 794 4024771817579439431701255521 795 4207108205207323980202695206 796 4397585698837271545254010577 797 4596562544290374306807596715 798 4804412524752306367109060527 799 5021525624950659680071060311 800 5248308723316608268508412563 801 5485186313293036987071005659 802 5732601254998986424530080814 803 5991015558509622634111816657 804 6260911200062578105956747848 805 6542790972554933361559021022 806 6837179371750986543379046391 807 7144623519678776999460100546 808 7465694126753790386928845075 809 7800986494230843256673481721 810 8151121558650560782739960755 811 8516746980014568117768651572 812 8898538275494285936037237310 813 9297200000551479142588091421 814 9713466979425264245173555685 815 10148105587019539200168148854 816 10601915084307608917212438836 817 11075729009456521770984813787 818 11570416626963198186222222809 819 12086884437187180775613499448 820 12626077748761701013660494440 821 13188982316465075973467584754 822 13776626047239200463791982511 823 14390080777150397159971779687 824 15030464122201158428159620545 825 15698941406018646288445765380 826 16396727667568290423625168561 827 17125089752167701133015456309 828 17885348489208526984640969058 829 18678880960131072922242474274 830 19507122860339642073198677183 831 20371570958894884651886046338 832 21273785659974177431154562206 833 22215393670251401775154318796 834 23198090776514746432605245371 835 24223644738014490533625845171 836 25293898298213496966377144542 837 26410772320800496199193726536 838 27576269055021608759198941160 839 28792475535588042493184514019 840 30061567122629023748561886640 841 31385811187377852672977280027 842 32767570949507103308877756130 843 34209309472265463020106888530 844 35713593821815194493766595511 845 37283099397424721746589700200 846 38920614439437145012462809483 847 40629044722211563132715775768 848 42411418439521770714144565801 849 44270891290195156033037091850 850 46210751772085392652528042931 851 48234426692794718127322204240 852 50345486905897263802184373349 853 52547653281762935621480315765 854 54844802922443887789072860616 855 57240975630461543976622552791 856 59740380641723654892551224996 857 62347403633206871285851484262 858 65066614016463123695244889385 859 67902772528446539556683498406 860 70860839131614182293312431349 861 73945981235727341304866832589 862 77163582254273052517310032988 863 80519250508936732856184046381 864 84018828496089020395986537377 865 87668402529801843089944838848 866 91474312776483287675701667897 867 95443163696816696949241242063 868 99581834911309633897317778024 869 103897492506401578775613239611 870 108397600798748675295560439790 871 113089934575998152642676891936 872 117982591833087594569499044189 873 123084007023853619010221793891 874 128402964848514322810709117539 875 133948614598398627292873676730 876 139730485080137170487762384578 877 145758500142402201222636125041 878 152042994829191976221495383427 879 158594732184596995524427124676 880 165424920734965180923966724479 881 172545232675399342064929324801 882 179967822788577354025299036719 883 187705348124981910502076585883 884 195770988474767121115264154221 885 204178467662672101452803960874 886 212942075698621911049704933171 887 222076691817932232472596811803 888 231597808446361166840306856035 889 241521556126627949785540829362 890 251864729444449657039844942515 891 262644813993631574682818134841 892 273880014421290539009093369396 893 285589283595891716003147242786 894 297792352942443984393375425638 895 310509763990925832817166023230 896 323762901185808803231275150291 897 337574026006407551729182673162 898 351966312449721224870995933042 899 366963883929438632550789885622 900 382591851646866676322354413557 901 398876354491706266434213797751 902 415844600532849960940520814116 903 433524910161709429411002499152 904 451946760953006424941653456705 905 471140834310476935758751662802 906 491139063967552862943146010320 907 511974686415797689545261913383 908 533682293336690914355875428713 909 556297886115279349411515717508 910 579858932517250962195166232785 911 604404425614137695120514065498 912 629974945044627376658261293714 913 656612720703360462832478717793 914 684361698952115228950172230727 915 713267611451944295383321569081 916 743378046718626919655007004041 917 774742524507744575944724277532 918 807412573139783497301685583482 919 841441809879916479079313641873 920 876886024491529520611409059900 921 913803266087136386833353476214 922 952253933405078790663692511313 923 992300868645341389769467700533 924 1034009455002932791254881424882 925 1077447718042596235686268586158 926 1122686431064131012303604435850 927 1169799224613328147801852197842 928 1218862700299466776607924191270 929 1269956549086481312766040588746 930 1323163674231310259732162010517 931 1378570319049575980208836889875 932 1436266199695638109073039300504 933 1496344643151212620420648299941 934 1558902730624171967691157993109 935 1624041446566840657226458638437 936 1691865833531094273930292683340 937 1762485153085860206237885595060 938 1836013053031225437746461116438 939 1912567741152283079081481160382 940 1992272165765116337016649297290 941 2075254203316929139145519223350 942 2161646853312309468827025321334 943 2251588440847957932263979975747 944 2345222827048954362479347112133 945 2442699627710773266805667319576 946 2544174440462820285182419289906 947 2649809080781251093990349063078 948 2759771827191278551677780062909 949 2874237676012078592672283243630 950 2993388606010799268721351106685 951 3117413853346066439953430521514 952 3246510197195794517255616146897 953 3380882256479058226915527359600 954 3520742798097294057877951008916 955 3666313057136185659417058916812 956 3817823069486280416898654742718 957 3975512017357693552052837183578 958 4139628588182217918701404952007 959 4310431347414782101341781959952 960 4488189125765525268279110620922 961 4673181421413795587632018252193 962 4865698817776171074162683228398 963 5066043417422159906566089486591 964 5274529292753605279645184082447 965 5491482954087011562075668355380 966 5717243835802070375487291933003 967 5952164801244612565959101485175 968 6196612667098094255335211176348 969 6450968747964559285164087936043 970 6715629421923858833634921792084 971 6991006717868770664230337115897 972 7277528925443601071107508934891 973 7575641228444892964748560139796 974 7885806362575062908795151808157 975 8208505298473171262115757064890 976 8544237950981655845116328215594 977 8893523915643756045647290877755 978 9256903233463587928323951585223 979 9634937184999429537863380117779 980 10028209114900810349534325088596 981 10437325288041500269401235091182 982 10862915778443537397587601033685 983 11305635392232053440527275123044 984 11766164625906931681874799652534 985 12245210661265301489453405655858 986 12743508398358621069800457108005 987 13261821527919666727322967938911 988 13800943644748223338561998010140 989 14361699403599700989977593101851 990 14944945719178383684338267824200 991 15551573011896595605364155936323 992 16182506501122851802773958194292 993 16838707547706095585600638187322 994 17521175047629524190981735005046 995 18230946878716324397935345940295 996 18969101402380997564069387323602 997 19736759022493911125289963259911 998 20535083803503395352968854571750 999 21365285150039177637110585346827 1000 22228619550303344256833190896859