0 1 1 0 2 1 3 1 4 1 5 1 6 2 7 3 8 5 9 7 10 10 11 13 12 18 13 23 14 31 15 40 16 53 17 68 18 89 19 113 20 146 21 184 22 234 23 293 24 369 25 458 26 572 27 706 28 874 29 1073 30 1320 31 1611 32 1970 33 2393 34 2909 35 3518 36 4255 37 5122 38 6167 39 7394 40 8862 41 10585 42 12637 43 15038 44 17886 45 21213 46 25141 47 29723 48 35112 49 41383 50 48737 51 57278 52 67258 53 78830 54 92313 55 107913 56 126042 57 146980 58 171246 59 199224 60 231571 61 268796 62 311742 63 361079 64 417869 65 483007 66 557835 67 643516 68 741757 69 854070 70 982605 71 1129331 72 1296956 73 1488011 74 1705921 75 1953931 76 2236338 77 2557311 78 2922241 79 3336429 80 3806652 81 4339640 82 4943867 83 5627872 84 6402240 85 7277743 86 8267613 87 9385404 88 10647587 89 12071210 90 13676759 91 15485570 92 17523115 93 19816050 94 22395948 95 25296073 96 28555511 97 32215629 98 36324785 99 40934322 100 46103918 101 51897226 102 58387800 103 65654325 104 73787374 105 82884059 106 93055675 107 104421912 108 117119346 109 131295160 110 147116790 111 164764933 112 184444475 113 206376977 114 230812833 115 258023171 116 288313663 117 322015615 118 359501578 119 401175863 120 447491967 121 498942462 122 556078768 123 619500151 124 689876115 125 767934845 126 854488243 127 950419794 128 1056712994 129 1174438384 130 1304785742 131 1449050720 132 1608670979 133 1785212487 134 1980410562 135 2196155598 136 2434539616 137 2697842076 138 2988582253 139 3309505298 140 3663641822 141 4054294077 142 4485103629 143 4960038586 144 5483470025 145 6060160696 146 6695352043 147 7394754457 148 8164646314 149 9011867186 150 9943929989 151 10969017945 152 12096112540 153 13334994728 154 14696390807 155 16191979971 156 17834560022 157 19638062785 158 21617743437 159 23790204962 160 26173614432 161 28787739733 162 31654195896 163 34796496694 164 38240336595 165 42013659654 166 46146982105 167 50673483501 168 55629375050 169 61054017455 170 66990343067 171 73485004775 172 80588859838 173 88357157521 174 96850092621 175 106133039167 176 116277185659 177 127359822470 178 139465070739 179 152684235315 180 167116640101 181 182870058438 182 200061672667 183 218818594678 184 239278968139 185 261592597567 186 285922213044 187 312444226834 188 341350187259 189 372847683706 190 407162017737 191 444537284685 192 485238292952 193 529551852339 194 577788981318 195 630286435445 196 687409245568 197 749552529788 198 817144410126 199 890648155149 200 970565534960 201 1057439347242 202 1151857275761 203 1254454866304 204 1365919961733 205 1486996201061 206 1618488120603 207 1761265258555 208 1916268021296 209 2084512494985 210 2267097188146 211 2465208662977 212 2680129288764 213 2913243820400 214 3166048312073 215 3440157797198 216 3737316531159 217 4059406945249 218 4408461419664 219 4786672706963 220 5196407460678 221 5640218361729 222 6120859657314 223 6641301252617 224 7204746560973 225 7814648858846 226 8474731785177 227 9189008311395 228 9961804273147 229 10797780352196 230 11701959089100 231 12679750327824 232 13736982215205 233 14879930636420 234 16115354774664 235 17450531134364 236 18893294328640 237 20452076368955 238 22135953433976 239 23954691215087 240 25918798522256 241 28039579579086 242 30329195455727 243 32800724329357 244 35468231864002 245 38346840612176 246 41452810612296 247 44803619263218 248 48418053604168 249 52316302175889 250 56520060640532 251 61052637373183 252 65939074303133 253 71206268212084 254 76883108956913 255 83000618719465 256 89592110056609 257 96693345678900 258 104342719102286 259 112581437876023 260 121453730012919 261 131007053982124 262 141292334514008 263 152364203152433 264 164281267512473 265 177106386691423 266 190906978635940 267 205755335288924 268 221728973337422 269 238910994663099 270 257390486444016 271 277262933213564 272 298630673122579 273 321603368754012 274 346298527246066 275 372842038003243 276 401368765401544 277 432023162609855 278 464959946794325 279 500344799485594 280 538355135498190 281 579180901706853 282 623025452371833 283 670106459742370 284 720656910195811 285 774926141852732 286 833180977812997 287 895706908014002 288 962809377975354 289 1034815134376617 290 1112073690179176 291 1194958855943389 292 1283870404898275 293 1379235814948414 294 1481512160319223 295 1591188092432187 296 1708785988265880 297 1834864201930428 298 1970019503760482 299 2114889638603861 300 2270156094044387 301 2436547006047808 302 2614840299718881 303 2805866988173659 304 3010514734781832 305 3229731597097194 306 3464530065792511 307 3715991312092177 308 3985269765732074 309 4273597931795263 310 4582291577937582 311 4912755195002782 312 5266487872667027 313 5645089487630124 314 6050267356944008 315 6483843248183782 316 6947760910973147 317 7444094015560983 318 7975054675711667 319 8543002435491795 320 9150453911017386 321 9800092960303451 322 10494781587307183 323 11237571446702983 324 12031716171587192 325 12880684383992027 326 13788173627854640 327 14758125077372006 328 15794739279392132 329 16902492775725176 330 18086155884435371 331 19350811478991510 332 20701875066471277 333 22145115996475204 334 23686680126065056 335 25333113765183929 336 27091389253831213 337 28968931988445849 338 30973649276950434 339 33113960832834968 340 35398831318459542 341 37837804741096738 342 40441041145030000 343 43219355396812515 344 46184258543018427 345 49348001531339360 346 52723621813654789 347 56324992616206753 348 60166875437974331 349 64264975557467838 350 68636001155247962 351 73297725828024758 352 78269055152103291 353 83570097068660132 354 89222236803257945 355 95248216090083538 356 101672217472846868 357 108519953451947711 358 115818761314906551 359 123597703420483981 360 131887673844070958 361 140721511157774289 362 150134118329775296 363 160162589521370027 364 170846344850490725 365 182227272907812785 366 194349882185790554 367 207261461217787399 368 221012248687621238 369 235655613320990821 370 251248244928558029 371 267850356430637201 372 285525898352449111 373 304342785643419602 374 324373138439792471 375 345693536652624108 376 368385290143217223 377 392534724402926818 378 418233483655126227 379 445578851338565621 380 474674090060374039 381 505628801027876650 382 538559305234414285 383 573589046467521699 384 610849018618843671 385 650478217434111752 386 692624119406296016 387 737443188031522136 388 785101410376416762 389 835774864271136059 390 889650319345321640 391 946925872331374588 392 1007811620146860207 393 1072530371306986259 394 1141318399502484224 395 1214426240039586935 396 1292119533331733760 397 1374679916307421144 398 1462405966312736467 399 1555614198564274064 400 1654640122158377524 401 1759839355910914145 402 1871588809502109560 403 1990287931450131807 404 2116360029902692727 405 2250253668053267225 406 2392444140737211816 407 2543435034335616321 408 2703759877163304435 409 2873983882833403265 410 3054705794457651589 411 3246559832586502335 412 3450217755499325753 413 3666391035213951297 414 3895833158650802349 415 4139342057846385387 416 4397762679558673183 417 4671989698750392504 418 4962970387291313301 419 5271707643031208317 420 5599263191682007703 421 5946760967410007735 422 6315390685784158903 423 6706411615821757192 424 7121156566106978610 425 7561036092666893199 426 8027542945042243616 427 8522256759296079152 428 9046849016006575905 429 9603088273171652672 430 10192845693843652582 431 10818100879747761726 432 11480948032651747419 433 12183602456224791316 434 12928407422299170925 435 13717841415930008165 436 14554525785530701602 437 15441232814330697705 438 16380894242034564448 439 17376610254996632116 440 18431658976654761913 441 19549506478842456967 442 20733817348878375264 443 21988465835622361299 444 23317547612870402728 445 24725392186142207073 446 26216575985059074006 447 27795936170554161856 448 29468585203326745906 449 31239926206331630798 450 33115669172354397806 451 35101848053413222391 452 37204838788147310015 453 39431378308322590662 454 41788584586243129969 455 44283977769078318869 456 46925502468091063013 457 49721551254199261162 458 52680989434680646820 459 55813181168472518371 460 59128017002394123550 461 62635942892425010073 462 66347990800644000836 463 70275810939377688139 464 74431705762278320758 465 78828665782102731228 466 83480407324951622999 467 88401412309858140218 468 93606970174537806229 469 99113222046295590841 470 104937207291073031868 471 111096912550826599566 472 117611323415623105215 473 124500478853043574551 474 131785528556035558624 475 139488793345537044537 476 147633828805256080255 477 156245492300125643484 478 165350013573703017366 479 174975069092848738311 480 185149860354639859082 481 195905196342455883188 482 207273580367861385835 483 219289301505793220927 484 231988530883529458414 485 245409423053688934780 486 259592222737987893885 487 274579377197139145839 488 290415654542508364579 489 307148268272683650686 490 324827008382364681755 491 343504379357404651378 492 363235745438389095988 493 384079483500465681985 494 406097143970293454170 495 429353620165228550826 496 453917326517955985464 497 479860386112970111377 498 507258828044686294092 499 536192795069148979927 500 566746762110346701412 501 599009766143362191016 502 633075648071713662773 503 669043307176556092231 504 707016968817058875376 505 747106466020768893274 506 789427535711408838828 507 834102130280321940263 508 881258745323929822192 509 931032764327709396094 510 983566821201413942368 511 1039011181527921617316 512 1097524143520972467792 513 1159272459644382387312 514 1224431779987512994679 515 1293187118448951633727 516 1365733342932550024944 517 1442275690717212886998 518 1523030310324775336354 519 1608224831167854884069 520 1698098962434087331924 521 1792905122621282096951 522 1892909101325004423618 523 1998390754839125869292 524 2109644737330251190118 525 2226981269307227169889 526 2350726945321738465767 527 2481225582797964250589 528 2618839114119605791140 529 2763948524066712360190 530 2916954834941804144324 531 3078280141691575554802 532 3248368699595581217796 533 3427688067063347956438 534 3616730306365922863623 535 3816013245101844272244 536 4026081801503057199953 537 4247509376664947502000 538 4480899317112835798412 539 4726886451101434828196 540 4986138702396352453639 541 5259358785277346903893 542 5547285984881963728854 543 5850698027006308904151 544 6170413041887093706003 545 6507291626495876193667 546 6862239010314529672668 547 7236207329577739385779 548 7630198015439619984705 549 8045264301549737783749 550 8482513857030989598363 551 8943111550893006862677 552 9428282354460688098309 553 9939314388453510213691 554 10477562121939110183295 555 11044449730457479350812 556 11641474621245290908716 557 12270211133581727399228 558 12932314422959381945765 559 13629524537897102089778 560 14363670698946892053019 561 15136675789584414964285 562 15950561069465303952393 563 16807451120694018854831 564 17709579038606793601779 565 18659291878765160499548 566 19659056372778617943377 567 20711464925803982476378 568 21819241909563918493759 569 22985250264994147730417 570 24212498429702708304585 571 25504147605734119664439 572 26863519384290662326280 573 28294103744419802593027 574 29799567443928797140601 575 31383762821197026134639 576 33050737027909003534938 577 34804741713199151769592 578 36650243181160642019659 579 38591933044203848378539 580 40634739396329173245519 581 42783838530984496128523 582 45044667229884630639836 583 47422935649855802860377 584 49924640836614015937064 585 52556080895160544336607 586 55323869848474140830254 587 58234953217052141449843 588 61296624354012218762807 589 64516541571447801537461 590 67902746096066820100989 591 71463680893244776574023 592 75208210401151950911132 593 79145641217848489446179 594 83285743786978452950070 595 87638775129074212484307 596 92215502668446207116615 597 97027229207174811843593 598 102085819100930352621088 599 107403725693066964504614 600 112994020066911927873122 601 118870421178087829692219 602 125047327432470307979674 603 131539849777515691945974 604 138363846378772589837930 605 145535958955760551939022 606 153073650855819952220064 607 160995246947167611743800 608 169319975417184281316117 609 178068011564877737652353 610 187260523681659324953546 611 196919721117805071730033 612 207068904637603676241924 613 217732519169773736289869 614 228936209065838471099200 615 240706875983107000364432 616 253072739515532779377142 617 266063400700098465997333 618 279709908533558119775563 619 294044829639204805403014 620 309102321231121689763119 621 324918207528714698501470 622 341530059782775771846347 623 358977280080216955430055 624 377301189103784529070070 625 396545118029557734091365 626 416754504754985622385954 627 437976994657372777247637 628 460262546093521069343823 629 483663540859116715230998 630 508234899838168975378021 631 534034204081482651192705 632 561121821565863834353669 633 589561039895302911544457 634 619418205219182889618920 635 650762867653056227736095 636 683667933502518122416402 637 718209824602239235948862 638 754468645098488393713810 639 792528356016148063254570 640 832476957968886737516293 641 874406682385067997828941 642 918414191641151592322650 643 964600788509616658900062 644 1013072635349257939292102 645 1063940983482465816176212 646 1117322413226709190054144 647 1173339085065822765958871 648 1232119002471250432284645 649 1293796286903551305921063 650 1358511465551134861758378 651 1426411772385281800920576 652 1497651463139459262138127 653 1572392144845142115595004 654 1650803120587794072579100 655 1733061750173171834963515 656 1819353827428262544079006 657 1909873974890191110688352 658 2004826056673519690801849 659 2104423610338133871368327 660 2208890298620187983509687 661 2318460381923349765625981 662 2433379212511329942923735 663 2553903751380716982267679 664 2680303108840649188428738 665 2812859109867453201561047 666 2951866885353980965570296 667 3097635490418857745519515 668 3250488550996900254549830 669 3410764939981677513067264 670 3578819484252059689263098 671 3755023703968926868581436 672 3939766585594323677416991 673 4133455390144698990081198 674 4336516498261675994037726 675 4549396293748627163376630 676 4772562087299316154607984 677 5006503082215662446360518 678 5251731383996384308304953 679 5508783055755565254423907 680 5778219221522177356436097 681 6060627219555957278212192 682 6356621807914932951575652 683 6666846424601961450952717 684 6991974504726132874337449 685 7332710857215339542208472 686 7689793103734132305694657 687 8063993182570552526189807 688 8456118920383577715846057 689 8867015674822312197543022 690 9297568051166996738172412 691 9748701696272204901940514 692 10221385173243469302523824 693 10716631920420623883672121 694 11235502298404976053280599 695 11779105729022244869858820 696 12348602930291086816875541 697 12945208251635751328601503 698 13570192113774550034333273 699 14224883557899656921059771 700 14910672908973455130369516 701 15629014558166910168486070 702 16381429869693114136759232 703 17169510217507271480065794 704 17994920157591556296789611 705 18859400741780811644547459 706 19764772979353372822621981 707 20712941452869936395115431 708 21705898095034656565957520 709 22745726133634218050405981 710 23834604211926789966944013 711 24974810692159243759916639 712 26168728150234179959575820 713 27418848069881849370762336 714 28727775745064509965050207 715 30098235399703697535116359 716 31533075534225116815616316 717 33035274508810723123577161 718 34607946373686252918593645 719 36254346957201995800214072 720 37977880222940659376832421 721 39782104907553359116743279 722 41670741451541348704311398 723 43647679235709159506340113 724 45716984136575342911484952 725 47882906414579431843380169 726 50149888949531906150247444 727 52522575838354529480107720 728 55005821370818246495012509 729 57604699399638680794170594 730 60324513122005091262819673 731 63170805290328216917214092 732 66149368870768957241606275 733 69266258168880953001613833 734 72527800442542442755114541 735 75940608023190661049359956 736 79511590967285664057183845 737 83247970260840795023740566 738 87157291600847903536457512 739 91247439778414330146088651 740 95526653689503317691588600 741 100003542000243623834883937 742 104687099494939508190069612 743 109586724136078792952748510 744 114712234866900421887405018 745 120073890188349674557867324 746 125682407543619448484838941 747 131548983544851399728003232 748 137685315078056396696609882 749 144103621323806903245063299 750 150816666732864588306057912 751 157837784997527297234199834 752 165180904061225616102815003 753 172860572210658483912290257 754 180891985296650070555436235 755 189291015131819339890664346 756 198074239115205320852729679 757 207258971136062835679799370 758 216863293811267049701579812 759 226906092113013035790743803 760 237407088445906422997876417 761 248386879234979823130974307 762 259866973088781279677481172 763 271869830604326302130225737 764 284418905883534945315974283 765 297538689833644607037237745 766 311254755327155491730086049 767 325593804299977404825141139 768 340583716869768694994391664 769 356253602559832511366854725 770 372633853717534660769994139 771 389756201219866104894972887 772 407653772562672023073255735 773 426361152434036073426112913 774 445914445876531792028986189 775 466351344147353194580975055 776 487711193389911026419571651 777 510035066235142185356756509 778 533365836455734111611643578 779 557748256801517744820927425 780 583229040149647951941649719 781 609856944108665052676381739 782 637682859221341071243802017 783 666759900917146781431404392 784 697143505371466696861166821 785 728891529435116927375875950 786 762064354804532309673549253 787 796724996609952978274674073 788 832939216606314921389256020 789 870775641159092754274475148 790 910305884225326123575654486 791 951604675538232260586969835 792 994749994212448787712380526 793 1039823207995800717191401598 794 1086909218402839161834051498 795 1136096611974983285868685252 796 1187477817922220490203612745 797 1241149272411697909506138487 798 1297211589779494182050422341 799 1355769740953097323925825913 800 1416933239383970380761235858 801 1480816334801752091116860487 802 1547538215114468541025791688 803 1617223216792301544823446572 804 1690001044086339911427500383 805 1766006997447995254177494762 806 1845382211529781169957186982 807 1928273903163583922665183485 808 2014835629728798528078182448 809 2105227558339402357324573027 810 2199616746296611900312043469 811 2298177433271838149330051823 812 2401091345703664410452478494 813 2508548013912122636905389390 814 2620745102454103123969096697 815 2737888754264886853068277475 816 2860193949153023669086111482 817 2987884877238665296243700709 818 3121195327949505896908885906 819 3260369095213239544404242690 820 3405660399511442808136723512 821 3557334327486568698776488209 822 3715667289821849007380594109 823 3880947498142863972711194542 824 4053475461719930191836154518 825 4233564504781778768100584453 826 4421541305283851475257317184 827 4617746456008412166260957694 828 4822535048909187265040705776 829 5036277283649871137700071569 830 5259359101324222131396155124 831 5492182844385069778957975115 832 5735167943851046342449893565 833 5988751634902660933479459937 834 6253389702024177149284559270 835 6529557254894026895419239511 836 6817749536274952579186891045 837 7118482763205084726633332446 838 7432295002843526138660036202 839 7759747084378069898923002528 840 8101423548459257465346224784 841 8457933635683402199103167853 842 8829912315708332085164317562 843 9218021358648734253193175220 844 9622950450464022611407872620 845 10045418354119862462787221232 846 10486174118375824018826922829 847 10945998336125336213791858577 848 11425704454291169042775064431 849 11926140137359293805804699517 850 12448188686717198404482498317 851 12992770518048746349169547025 852 13560844699127554263747165206 853 14153410550443769774850177595 854 14771509311196201551449331926 855 15416225873282100544219437468 856 16088690586021711369642950329 857 16790081134463087231367502492 858 17521624494225841962967653974 859 18284598965959547006137497538 860 19080336292614679295038586463 861 19910223862850401778444458734 862 20775707004035383121483096085 863 21678291368434315064337131238 864 22619545416315200984041667201 865 23601102999859808901258107455 866 24624666051913410222937522286 867 25692007383768965840292672074 868 26804973596346848583519165449 869 27965488109302870836814059354 870 29175554312776467663128644193 871 30437258846676194904757289587 872 31752775012592965965365717592 873 33124366323631455653792941850 874 34554390197658654242958754688 875 36045301799684403593785334913 876 37599658039313785674949058278 877 39220121729444163464226356422 878 40909465912622481401000506903 879 42670578361729775294875075779 880 44506466261921801267686458439 881 46420261081025883655399127535 882 48415223635876684016580514050 883 50494749362366176066335248681 884 52662373797287960508874742287 885 54921778280371691957764628098 886 57276795885232213587152123733 887 59731417588298479618333536756 888 62289798685142003134802790562 889 64956265463991825243795710721 890 67735322146605494822021015210 891 70631658107061655952314841109 892 73650155379452324101982665442 893 76795896465880123175772567039 894 80074172456610549659163786690 895 83490491474690008772804459294 896 87050587457819968108696962286 897 90760429290774328327333215033 898 94626230302164204065125193850 899 98654458139889922659996787542 900 102851845040177525959548207608 901 107225398505674532213135891675 902 111782412408680687731160207818 903 116530478536211991823077139577 904 121477498594244093540254488843 905 126631696689152264460273013735 906 132001632305063410475702374010 907 137596213796558976267418190838 908 143424712416920173058819063564 909 149496776902886652127491734971 910 155822448637710809663183471656 911 162412177415130221961566892761 912 169276837827754742709318171454 913 176427746304270376321684632959 914 183876678820803866177992727230 915 191635889312767786210694878819 916 199718128814520728064204889794 917 208136665355228669167984799914 918 216905304640406967890205241171 919 226038411549755350335089502069 920 235550932483076169986203542781 921 245458418587286782625156711941 922 255777049898805802020414901945 923 266523660436907891718892573501 924 277715764285008613786950665584 925 289371582698257262575353607002 926 301510072277287877021529784577 927 314150954249504278711162599355 928 327314744900860665889526114215 929 341022787202742503268102002781 930 355297283680260167191617269166 931 370161330570037504162269529795 932 385638953317416482567962900643 933 401755143464904906977243186216 934 418535896985674447670533423430 935 436008254117968439963044760673 936 454200340758411157170430389225 937 473141411474419968693798439916 938 492861894198217514738979082558 939 513393436667320164961480509345 940 534768954678850583103875449534 941 557022682227583596198356231382 942 580190223600295242948181479622 943 604308607501742261450096675723 944 629416343290463350707270806778 945 655553479405561729331739693279 946 682761664068711327648257267142 947 711084208348823837606627524422 948 740566151680131877935973631772 949 771254329927882197652894293442 950 803197446099403801171141678480 951 836446143802016668801106417759 952 871053083553089655639296320253 953 907073022051538776825893394585 954 944562894524192378818130111957 955 983581900264735327294646971933 956 1024191591487393964565846543128 957 1066455965622134966820125672847 958 1110441561182938758064532839615 959 1156217557345669685724597543751 960 1203855877377215911657116611744 961 1253431296062909921907583283855 962 1305021551284781719257612945918 963 1358707459908939282963743333836 964 1414573038146331650593098152600 965 1472705626557327317141147552058 966 1533196019876952379307865948460 967 1596138601844277493513623475739 968 1661631485226339074924935087859 969 1729776657234126980128606830215 970 1800680130535588044153224436684 971 1874452100078281274618600816545 972 1951207105942297206353465765172 973 2031064202452320165037480607430 974 2114147133786290117512049383090 975 2200584516327009995450191055170 976 2290510028012268252605625048316 977 2384062604948604907965836142681 978 2481386645563767142670471249653 979 2582632222583178011065541636602 980 2687955303126405100693960187706 981 2797517977230665830366268606597 982 2911488695119870099634538108107 983 3030042513549580488260438812987 984 3153361351570594315817974351015 985 3281634256066622446897103985031 986 3415057677434787602979834376729 987 3553835755791392559103824428375 988 3698180618099648571964743024888 989 3848312686630809813134554018286 990 4004460999185464958993660926666 991 4166863541517596257992439053456 992 4335767592420465846492290801710 993 4511430081950433462992139246407 994 4694117963282487628931293877599 995 4884108598709589353695928601569 996 5081690160316924346463743569058 997 5287162045881843079502993747919 998 5500835310570681103302010786412 999 5723033115024802327163862198822 1000 5954091190450141347516381740043