0 0 1 0 2 1 3 0 4 0 5 0 6 1 7 1 8 2 9 2 10 4 11 4 12 6 13 7 14 11 15 12 16 17 17 20 18 28 19 33 20 44 21 52 22 69 23 82 24 105 25 126 26 161 27 191 28 239 29 286 30 355 31 423 32 520 33 618 34 755 35 896 36 1084 37 1285 38 1549 39 1829 40 2190 41 2583 42 3079 43 3621 44 4297 45 5041 46 5960 47 6977 48 8214 49 9595 50 11264 51 13123 52 15353 53 17854 54 20828 55 24167 56 28116 57 32555 58 37780 59 43660 60 50538 61 58293 62 67332 63 77512 64 89332 65 102662 66 118076 67 135455 68 155490 69 178073 70 204036 71 233293 72 266823 73 304604 74 347806 75 396438 76 451920 77 514363 78 585434 79 665367 80 756170 81 858220 82 973939 83 1103901 84 1250988 85 1416078 86 1602628 87 1811818 88 2047833 89 2312319 90 2610258 91 2943870 92 3319163 93 3739048 94 4210773 95 4738137 96 5329820 97 5990794 98 6731504 99 7558254 100 8483663 101 9515800 102 10669783 103 11955844 104 13392202 105 14991701 106 16776299 107 18762081 108 20975406 109 23436423 110 26176840 111 29221587 112 32608867 113 36369601 114 40549613 115 45187100 116 50337159 117 56046738 118 62382064 119 69400747 120 77182205 121 85797073 122 95340650 123 105899043 124 117586639 125 130508435 126 144801373 127 160593180 128 178047925 129 197320525 130 218607447 131 242096336 132 268022073 133 296611718 134 328146048 135 362898951 136 401205964 137 443397287 138 489873229 139 541031234 140 597348858 141 659303548 142 727464632 143 802405013 144 884802597 145 975344138 146 1074836459 147 1184101155 148 1304097944 149 1435808993 150 1580374493 151 1738967101 152 1912940836 153 2103693804 154 2312832795 155 2542023053 156 2793169408 157 3068253418 158 3369531875 159 3699359435 160 4060408126 161 4455473696 162 4887716696 163 5360453207 164 5877419427 165 6442544245 166 7060241154 167 7735160965 168 8472512732 169 9277797100 170 10157158071 171 11117094387 172 12164847869 173 13308090489 174 14555350846 175 15915678016 176 17399109634 177 19016309213 178 20779082168 179 22699984439 180 24792889836 181 27072570986 182 29555321785 183 32258507458 184 35201251346 185 38403951363 186 41889034838 187 45680443461 188 49804462643 189 54289171138 190 59165355633 191 64465922916 192 70226906497 193 76486843804 194 83287882534 195 90675119726 196 98697823194 197 107408730309 198 116865392792 199 127129439808 200 138268058459 201 150353218059 202 163463305053 203 177682307995 204 193101620596 205 209819193743 206 227941522273 207 247582763124 208 268866932435 209 291926990806 210 316907268596 211 343962529056 212 373260645890 213 404981645382 214 439320669978 215 476487004932 216 516707355772 217 560224875245 218 607302786523 219 658223417394 220 713292217151 221 772836808901 222 837211437986 223 906796067900 224 982001307998 225 1063267567247 226 1151070524196 227 1245920360529 228 1348367830457 229 1459003612016 230 1578465041125 231 1707435609089 232 1846652450889 233 1996906025497 234 2159048437836 235 2333993361241 236 2522725289234 237 2726299748104 238 2945853599456 239 3182605605167 240 3437867898414 241 3713046989348 242 4009656538696 243 4329318885053 244 4673779293281 245 5044908101386 246 5444716609440 247 5875359980955 248 6339154967838 249 6838583693777 250 7376313452699 251 7955201529289 252 8578317313630 253 9248948358707 254 9970625086866 255 10747128285407 256 11582516743263 257 12481136421157 258 13447651362749 259 14487054838858 260 15604703932301 261 16806332962243 262 18098092215614 263 19486564012356 264 20978806082940 265 22582370715152 266 24305353343767 267 26156415244331 268 28144838009114 269 30280550326355 270 32574189053486 271 35037130732800 272 37681560077384 273 40520506916489 274 43567923043252 275 46838725392547 276 50348882275204 277 54115463738726 278 58156738346707 279 62492231752913 280 67142835377943 281 72130874376921 282 77480229672600 283 83216416704799 284 89366722480960 285 95960296619376 286 103028305327165 287 110604036469082 288 118723072564264 289 127423411891569 290 136745662865008 291 146733183387915 292 157432299323214 293 168892464613378 294 181166506818962 295 194310810914482 296 208385595262588 297 223455122294979 298 239588008761935 299 256857466947185 300 275341653433393 301 295123945036260 302 316293330861690 303 338944727600023 304 363179420320521 305 389105422380204 306 416837970968786 307 446499937640458 308 478222385393815 309 512145036496240 310 548416898788420 311 587196798346904 312 628654083548641 313 672969231155222 314 720334637732181 315 770955308711998 316 825049748038358 317 882850740988733 318 944606354106603 319 1010580824019219 320 1081055681229206 321 1156330758555737 322 1236725454099205 323 1322579874666210 324 1414256254951902 325 1512140253321312 326 1616642546336362 327 1728200296272926 328 1847278942562027 329 1974373862839082 330 2110012385299193 331 2254755667886337 332 2409200958500493 333 2573983719775786 334 2749780167432082 335 2937309671488922 336 3137337606521262 337 3350678064048924 338 3578197052519192 339 3820815559647001 340 4079513144628907 341 4355331393939318 342 4649377953125442 343 4962830424985694 344 5296940893985126 345 5653040321409494 346 6032543621885797 347 6436954616714932 348 6867871728812377 349 7326993562922265 350 7816125293158813 351 8337184946771472 352 8892210567422936 353 9483367288347637 354 10112955364002965 355 10783418128869300 356 11497351001060052 357 12257510434124945 358 13066824008533001 359 13928400496589470 360 14845541170982472 361 15821751117292359 362 16860751903900778 363 17966494292070613 364 19143172428575059 365 20395238120958005 366 21727416732625692 367 23144723210758382 368 24652479884529547 369 26256334454635898 370 27962279918761833 371 29776674756083077 372 31706265229607499 373 33758208026358369 374 35940095215016840 375 38259979632278563 376 40726402806546449 377 43348423414560131 378 46135648517068180 379 49098265447492695 380 52247076745201730 381 55593535879074668 382 59149786308335024 383 62928701490160687 384 66943928546576632 385 71209933056961120 386 75742047863959043 387 80556523208381687 388 85670581267978872 389 91102472255762881 390 96871535352136966 391 102998261458610652 392 109504361258535230 393 116412835395984555 394 123748050483627990 395 131535817563680256 396 139803476972957315 397 148579986039868160 398 157896013818938990 399 167784039084534001 400 178278456061053605 401 189415683893247840 402 201234284623482654 403 213775085451192046 404 227081310348380871 405 241198716566720442 406 256175741437831585 407 272063654749327433 408 288916722447528297 409 306792376684707418 410 325751398332428624 411 345858106701570033 412 367180562986254305 413 389790781880104631 414 413764958303928623 415 439183703388119503 416 466132297096765892 417 494700951317654187 418 524985091283418527 419 557085648812563122 420 591109375745705873 421 627169170716030966 422 665384428171269913 423 705881402421334046 424 748793596207778745 425 794262166186472393 426 842436355437353692 427 893473944994671066 428 947541735168344879 429 1004816048235607978 430 1065483263975356670 431 1129740379191161867 432 1197795603444586863 433 1269868981695496641 434 1346193056868311526 435 1427013562574845235 436 1512590159865012367 437 1603197207750171398 438 1699124582280911136 439 1800678533422083676 440 1908182595476669276 441 2021978539782431200 442 2142427386470301372 443 2269910463469884885 444 2404830530659882296 445 2547612956794763466 446 2698706968287710172 447 2858586956911393159 448 3027753866761942612 449 3206736646959155794 450 3396093791781930273 451 3596414954110173339 452 3808322655316755618 453 4032474076865648817 454 4269562958307149218 455 4520321586295390591 456 4785522900975606809 457 5065982703726014869 458 5362561994371600579 459 5676169421205925336 460 6007763873835348137 461 6358357201522253293 462 6729017089074552984 463 7120870072296113428 464 7535104727219570440 465 7972975014473515322 466 8435803815338132972 467 8924986640176674029 468 9441995548298593092 469 9988383259285303551 470 10565787497513197833 471 11175935549260163114 472 11820649077006709260 473 12501849169684608265 474 13221561676572261990 475 13981922802980961374 476 14785185018741682692 477 15633723257057698819 478 16530041458290727207 479 17476779435698831694 480 18476720121517333203 481 19532797169902047723 482 20648102979229865293 483 21825897109833850311 484 23069615164082728677 485 24382878104500842722 486 25769502081587571384 487 27233508746733669255 488 28779136126996614899 489 30410850036928418463 490 32133356109713349693 491 33951612422708293521 492 35870842805560539314 493 37896550806025244097 494 40034534408023321858 495 42290901477239928621 496 44672086035666105842 497 47184865340723637667 498 49836377877771977664 499 52634142242174632292 500 55586077027689856544 501 58700521698122801164 502 61986258567598836514 503 65452535867398958467 504 69109092033990384253 505 72966181197486349820 506 77034600015167150291 507 81325715830914393535 508 85851496315988739722 509 90624540573977117636 510 95658111877001733373 511 100966172018406495803 512 106563417461600923425 513 112465317273130594635 514 118688153033260649751 515 125249060715504327877 516 132166074743091328988 517 139458174217757093103 518 147145331544739843153 519 155248563453968391228 520 163789984658520328116 521 172792864155651860741 522 182281684430080384496 523 192282203570956374920 524 202821520582323226391 525 213928143905543419215 526 225632063455271600647 527 237964826195490389619 528 250959615580775259993 529 264651334898467719067 530 279076694862453996738 531 294274305504639193356 532 310284772742477928745 533 327150799680430872698 534 344917293053685879375 535 363631474885332125714 536 383342999797802067867 537 404104078064789783900 538 425969604879674482812 539 448997295943545089371 540 473247829887040269682 541 498784997648076079107 542 525675859361074502547 543 553990908901046745026 544 583804246683061648456 545 615193760884263033162 546 648241317737704705886 547 683032961091795317280 548 719659121937496356786 549 758214838126798618746 550 798799985042021128339 551 841519517472595667794 552 886483723521199478094 553 933808490832818640481 554 983615586036252099429 555 1036032947732719863233 556 1091194993994559916689 557 1149242944754318623626 558 1210325160127028325722 559 1274597495096670491225 560 1342223671696296074399 561 1413375669169047404933 562 1488234133333739020671 563 1566988805704570355177 564 1649838973690976970940 565 1736993942496243545276 566 1828673530152093012468 567 1925108586384306244901 568 2026541536867471550857 569 2133226953648429818308 570 2245432153427925080254 571 2363437824573450587997 572 2487538684695637785243 573 2618044169764378610451 574 2755279156752344502246 575 2899584720895991758664 576 3051318929730606764206 577 3210857675115158977862 578 3378595545587149224148 579 3554946740401810037233 580 3740346027795572433715 581 3935249748980865387723 582 4140136870629398177027 583 4355510087519225935392 584 4581896978339007816242 585 4819851216509992923605 586 5069953839276159257821 587 5332814577126862834572 588 5609073247082022025020 589 5899401212128422306632 590 6204502910641310856235 591 6525117458326426420786 592 6862020326847548305269 593 7216025101945672750619 594 7587985325574943412180 595 7978796425159168205616 596 8389397734885754248229 597 8820774612467882523557 598 9273960656717980747716 599 9750040029722271360913 600 10250149889423241499219 601 10775482936793783770754 602 11327290083914477846205 603 11906883247570005110186 604 12515638275225296310110 605 13154998008471429798421 606 13826475491399434798575 607 14531657329511771536726 608 15272207207279843840137 609 16049869570527017889138 610 16866473482453067115799 611 17723936660103726175887 612 18624269700871245006672 613 19569580506513438505239 614 20562078915114943986832 615 21604081549227063059127 616 22698016891521625329312 617 23846430597015107062925 618 25051991054190561812143 619 26317495204971006607576 620 27645874636951343811704 621 29040201958824490340499 622 30503697473583491345796 623 32039736161509581384157 624 33651854988806184365241 625 35343760555063847601406 626 37119337096806852228773 627 38982654861591392249779 628 40937978871419318492010 629 42989778091341975716555 630 45142735023664606490706 631 47401755745161145911945 632 49771980409501174660504 633 52258794233976572353891 634 54867838994678528370850 635 57605025051045333744638 636 60476543926051857520613 637 63488881464963223216086 638 66648831601230082665924 639 69963510754634457423008 640 73440372892772660567067 641 77087225283371497795944 642 80912244971253651058994 643 84923996010054503384489 644 89131447485475080236298 645 93543992363017744558935 646 98171467200218445558291 647 103024172759425975035191 648 108112895564654133921706 649 113448930441943698679440 650 119044104090579668859716 651 124910799728294783599121 652 131061982861958681023579 653 137511228230912584075414 654 144272747978966072101909 655 151361421106609254196259 656 158792824264368761169547 657 166583263943650978560415 658 174749810131341795067351 659 183310331489727902034146 660 192283532133815858392710 661 201688990073305183146419 662 211547197397604875600752 663 221879602277351670768853 664 232708652867682735477507 665 244057843193478630000983 666 255951761109290084650047 667 268416138421526197277041 668 281477903273727340915641 669 295165234890519199459920 670 309507620789885895830520 671 324535916568091662915953 672 340282408376469216003289 673 356780878203913933593088 674 374066672094713338943839 675 392176771425904784080501 676 411149867385104824292659 677 431026438784274274610233 678 451848833362656439732077 679 473661352726620644703003 680 496510341093006337759192 681 520444277997051358610439 682 545513875146012422452754 683 571772177594089706264636 684 599274669435530026530099 685 628079384207327430992887 686 658247020215522644803514 687 689841060993715950082489 688 722927901126398659439113 689 757576977664421699836207 690 793860907385412711961226 691 831855630146802179935754 692 871640558606214943835505 693 913298734579008209202434 694 956916992331544112409553 695 1002586129104029399840111 696 1050401083187388901640800 697 1100461119874153165527824 698 1152870025635925884788631 699 1207736310875834773299578 700 1265173421639039212955379 701 1325299960660591079499893 702 1388239918166842313385314 703 1454122912843268628298505 704 1523084443420856364552088 705 1595266151330403156828400 706 1670816094915905642210171 707 1749889035696021404524503 708 1832646737207136532638114 709 1919258276960085902125063 710 2009900372090028170073775 711 2104757719278296017904893 712 2204023349575611116767229 713 2307898998756285384030511 714 2416595493886931635505566 715 2530333156794474691375498 716 2649342225175722176414010 717 2773863292093192761370719 718 2904147764663186233060714 719 3040458342745836174367878 720 3183069518512261825018900 721 3332268097769172174899881 722 3488353743991030421237671 723 3651639546016781626836284 724 3822452610442593004964283 725 4001134679750803731326819 726 4188042777294755031790380 727 4383549880269985138080375 728 4588045621887134921278858 729 4801937023975024270275945 730 5025649261332995475185819 731 5259626459167289804475459 732 5504332525043051561485722 733 5760252016802059124229290 734 6027891047999749936967980 735 6307778232436752721930454 736 6600465669470728715513461 737 6906529971819444218120981 738 7226573337684224648090274 739 7561224669051899153658780 740 7911140738159768639951299 741 8277007404141324923129341 742 8659540882005667661533076 743 9059489066141429233121881 744 9477632910680676680432665 745 9914787869101264291542182 746 10371805395600902155076319 747 10849574510824866261029025 748 11349023434694946343213490 749 11871121289142103399167153 750 12416879873722661337950259 751 12987355517159558512973979 752 13583651008040082349128442 753 14206917607970701379680253 754 14858357150692980878046254 755 15539224230741970676127072 756 16250828485446300683363447 757 16994536974155618717550088 758 17771776658814403039091295 759 18584036990097431948296959 760 19432872603572300139062320 761 20319906130461399441238964 762 21246831127843846047359666 763 22215415133256650304797087 764 23227502848941788419779481 765 24285019461117530721940762 766 25389974099960488361426503 767 26544463446130604868765899 768 27750675490001726334737963 769 29010893449921508187261530 770 30327499856178797917906402 771 31702980807534517770296463 772 33139930407552229934768205 773 34641055388160730193865358 774 36209179928288893403127827 775 37847250675629084137253017 776 39558341980023131314029770 777 41345661347202669398412573 778 43212555122085392714531476 779 45162514411090223125793500 780 47199181253438617240448154 781 49326355051696442519955612 782 51547999272352167452612395 783 53868248427542339291334679 784 56291415349616537732335847 785 58821998770579710067422654 786 61464691219073932733958775 787 64224387247940519922697926 788 67106192006073719777549281 789 70115430168692164768599775 790 73257655240874250416355186 791 76538659249657722016094804 792 79964482840777221497245443 793 83541425796610220014727439 794 87276057992732764625169668 795 91175230811029376925991875 796 95246089028194353498716855 797 99496083199054830834250093 798 103932982555105514489526622 799 108564888439292581975553599 800 113400248299115507058231361 801 118447870260822304951328537 802 123716938308582104434544715 803 129217028093289868499440554 804 134958123396849547791595115 805 140950633278622462232655153 806 147205409932008562517002135 807 153733767280044203278995725 808 160547500340277135248978854 809 167658905390177219678630047 810 175080800965822013214353361 811 182826549727682844812287815 812 190910081228929132243503806 813 199345915622851252515763801 814 208149188347714407860218779 815 217335675828642599508670551 816 226921822237973124702461393 817 236924767356921442635976785 818 247362375583376609419189903 819 258253266132169023026004070 820 269616844476282258719965306 821 281473335079134523635859224 822 293843815470346433481422859 823 306750251719208675163506094 824 320215535362527751824042374 825 334263521845479756271623233 826 348919070536753479032007563 827 364208086381383505910914630 828 380157563257526333338637348 829 396795629105733200328700275 830 414151592902342097674044241 831 432255993551108219860667751 832 451140650770493828478554695 833 470838718056747417306856415 834 491384737806454533346077023 835 512814698685180894190889091 836 535166095332650844161338092 837 558477990498090453203127641 838 582791079703477546319828463 839 608147758535895262231327522 840 634592192674611525810743699 841 662170390762250834882014380 842 690930280234187261536959497 843 720921786224344647405613185 844 752196913670714922705242010 845 784809832748300807785796405 846 818816967762704256460664453 847 854277089642342740433613778 848 891251412173210529568324209 849 929803692125257560588139989 850 970000333425845572953503863 851 1011910495541322895518442044 852 1055606206234632901397182219 853 1101162478872913153686648166 854 1148657434466439582690125084 855 1198172428626809025111229121 856 1249792183640214418636792985 857 1303604925858742451248591479 858 1359702528621191068694001482 859 1418180660922558868973477864 860 1479138942060578911718130864 861 1542681102495949122749786198 862 1608915151172834632382853690 863 1677953549555171521803418962 864 1749913392644980806197570729 865 1824916597258583385470221679 866 1903090097848099829658358120 867 1984566050166085932880710088 868 2069482043083523835041065922 869 2157981318882702559906424082 870 2250213002359833046219755868 871 2346332339084470362090760643 872 2446500943177141047151353208 873 2550887054979786407725003439 874 2659665809009048950020603150 875 2773019512596704487926995155 876 2891137935638132825147901522 877 3014218611885140862589435873 878 3142467152237305491776143174 879 3276097570502659684069055211 880 3415332622117757706973170826 881 3560404156335142884326889123 882 3711553482406915936062257758 883 3869031750312524559102906652 884 4033100346601142463231996232 885 4204031305939975461689552318 886 4382107738983771876213525725 887 4567624277203450782494927130 888 4760887535337521520148847603 889 4962216592154400306983602909 890 5171943490241447676837581037 891 5390413755562918125409904065 892 5617986937558837290949491322 893 5855037170585274567529902801 894 6101953757528568238649289201 895 6359141776456758708504479302 896 6627022711206010946631167246 897 6906035106832924884174351679 898 7196635250900778299285173216 899 7499297881603469798791984309 900 7814516923770893233145754349 901 8142806253838003800803621714 902 8484700494902830192195183658 903 8840755843040237427443412858 904 9211550926084497802142336633 905 9597687696138530825348581694 906 9999792357117429799283942321 907 10418516328682198572421496612 908 10854537247973146389161338961 909 11308560010604465057168563815 910 11781317852439087936601459622 911 12273573473719065105927882775 912 12786120207188619586832489310 913 13319783231907552689139248009 914 13875420834519279288614015045 915 14453925719802978366182316828 916 15056226372410990398606489516 917 15683288471762856988655930517 918 16336116362144455266955214716 919 17015754580136387414675462827 920 17723289441578659044307231452 921 18459850690360245509929373868 922 19226613211411270269692124887 923 20024798810363386636767220893 924 20855678062439798644882850359 925 21720572233231003361023236403 926 22620855274115402983811703926 927 23557955895185874161356599793 928 24533359718654209013497512815 929 25548611515815125200961920877 930 26605317530770709771575080704 931 27705147894234380403083229846 932 28849839130861577433549736096 933 30041196763681691254843683795 934 31281098019343489742627379300 935 32571494638023357334848522973 936 33914415791993764973408042432 937 35311971116996926941589400444 938 36766353860727825718957301995 939 38279844152889601159102951385 940 39854812401455469520001060844 941 41493722819942278221038455747 942 43199137090684802990680885002 943 44973718169283868949394922960 944 46820234235599162135012989065 945 48741562796855583902375153863 946 50740694948644592302035402060 947 52820739799815020014361071393 948 54984929067476354331629497309 949 57236621848566695453886612871 950 59579309574683187464450159709 951 62016621157119341035024908036 952 64552328329317591387945847223 953 67190351194210751090051214712 954 69934763984209644786005797558 955 72789801041879613147983357657 956 75759863029653359730880034443 957 78849523377234593673233308060 958 82063534975674428628636739416 959 85406837127432661174478764583 960 88884562762087956568412255988 961 92502045927716038240581298732 962 96264829568333077543316444726 963 100178673598183302490015578535 964 104249563284056069202233068495 965 108483717947228198777441158281 966 112887599997063801905357652952 967 117467924308745237245690806008 968 122231667958077684097520461306 969 127186080326784381410144369183 970 132338693592213216219015165024 971 137697333615885513460997748094 972 143270131245858861198352549027 973 149065534048424199380740623597 974 155092318485238473195715479269 975 161359602552583590424651504661 976 167876858900066524379818477025 977 174653928446708910509597328384 978 181701034513044767339328262703 979 189028797488525790505864422281 980 196648250054253510809719019425 981 204570852981789215580022732116 982 212808511529565557868944929445 983 221373592459209907410122782332 984 230278941694919590761822277921 985 239537902649873819403320428736 986 249164335244558431888993980040 987 259172635642787039720743462767 988 269577756732159193768685165194 989 280395229376671064118963074120 990 291641184470221640993368001060 991 303332375820804685354961103973 992 315486203896279792577502075057 993 328120740463740786659688116294 994 341254754155683918809053542042 995 354907736997386500731944086599 996 369099931931177877864871444567 997 383852361374582184171214964435 998 399186856850676933969917524266 999 415126089730404937170722447058 1000 431693603128041750949348258637