10 1 11 0 12 1 13 1 14 2 15 2 16 4 17 4 18 7 19 8 20 14 21 16 22 23 23 28 24 40 25 49 26 67 27 82 28 110 29 135 30 180 31 220 32 286 33 349 34 448 35 548 36 694 37 846 38 1061 39 1290 40 1608 41 1948 42 2406 43 2909 44 3566 45 4300 46 5242 47 6298 48 7637 49 9149 50 11044 51 13189 52 15847 53 18872 54 22582 55 26817 56 31967 57 37858 58 44970 59 53116 60 62894 61 74096 62 87460 63 102788 64 120977 65 141845 66 166486 67 194756 68 228004 69 266131 70 310812 71 362012 72 421803 73 490287 74 570001 75 661242 76 767132 77 888222 78 1028387 79 1188531 80 1373440 81 1584492 82 1827611 83 2104840 84 2423488 85 2786484 86 3202843 87 3676656 88 4219082 89 4835711 90 5540363 91 6340548 92 7253369 93 8288877 94 9468201 95 10804635 96 12324292 97 14044600 98 15997853 99 18206717 100 20711135 101 23540372 102 26743780 103 30359042 104 34447054 105 39056072 106 44261217 107 50123974 108 56737013 109 64178345 110 72562178 111 81987122 112 92593834 113 104506580 114 117898414 115 132925458 116 149800418 117 168718839 118 189942039 119 213714201 120 240356079 121 270171797 122 303554658 123 340882660 124 382637534 125 429287973 126 481423475 127 539623913 128 604610012 129 677097675 130 757967203 131 848100640 132 948572088 133 1060466430 134 1185092783 135 1323783072 136 1478131279 137 1649769726 138 1840637379 139 2052731367 140 2288407831 141 2550106299 142 2840686924 143 3163125157 144 3520889353 145 3917603231 146 4357468309 147 4844891443 148 5384957355 149 5983017635 150 6645219666 151 7378053526 152 8188943790 153 9085751104 154 10077433590 155 11173499647 156 12384747068 157 13722663067 158 15200250308 159 16831369780 160 18631664102 161 20617838688 162 22808694023 163 25224340813 164 27887353194 165 30821914074 166 34055103301 167 37615968495 168 41536964546 169 45852944913 170 50602770530 171 55828217197 172 61575774056 173 67895462869 174 74842848220 175 82477765287 176 90866566649 177 100080755547 178 110199497933 179 121308157554 180 133501106269 181 146880158618 182 161557716478 183 177655103033 184 195306081525 185 214655089706 186 235861178845 187 259096151061 188 284548970544 189 312423808121 190 342944983802 191 376354925607 192 412919710313 193 452926947622 194 496691992856 195 544555772878 196 596891755107 197 654103735056 198 716633658744 199 784959396917 200 859603530142 201 941131143220 202 1030159696766 203 1127356883666 204 1233451726742 205 1349232550267 206 1475559462134 207 1613362505456 208 1763655706321 209 1927535482396 210 2106196463514 211 2300930251964 212 2513143249264 213 2744355884726 214 2996222712443 215 3270532247203 216 3569229634442 217 3894417259047 218 4248380332394 219 4633588471083 220 5052724593589 221 5508687702487 222 6004625538150 223 6543938842560 224 7130318276069 225 7767750493330 226 8460559901355 227 9213416933798 228 10031385311902 229 10919932969663 230 11884985570498 231 12932940616952 232 14070728080565 233 15305828320107 234 16646340801443 235 18101006555176 236 19679286099432 237 21391387289483 238 23248353714791 239 25262098929168 240 27445506774124 241 29812473141689 242 32378019875984 243 35158345410823 244 38170954130782 245 41434717438771 246 44970020726223 247 48798836671470 248 52944892268456 249 57433756440286 250 62293029920839 251 67552449592050 252 73244104404852 253 79402559224972 254 86065100418983 255 93271882425949 256 101066207143965 257 109494696931276 258 118607612511156 259 128459056666183 260 139107336034562 261 150615200409877 262 163050254549479 263 176485238727045 264 190998497524217 265 206674308127751 266 223603414042366 267 241883408587217 268 261619342572420 269 282924171540221 270 305919447704470 271 330735840738722 272 357513925694203 273 386404788573238 274 417570923554776 275 451186936218831 276 487440565251447 277 526533498041932 278 568682534122077 279 614120529974187 280 663097723829164 281 715882828928591 282 772764541995804 283 834052806940021 284 900080532351518 285 971205050759809 286 1047810073966032 287 1130307376501379 288 1219139021538363 289 1314779301218296 290 1417737270323272 291 1528558980722915 292 1647830365023492 293 1776179807572818 294 1914281426008916 295 2062858027157920 296 2222684840862662 297 2394592915795041 298 2579473367267155 299 2778281275545016 300 2992040517634799 301 3221848239280845 302 3468880350079403 303 3734396650087971 304 4019747078214493 305 4326377585383091 306 4655837238146393 307 5009784942831652 308 5389997519871231 309 5798377397479686 310 6236961787520005 311 6707931483235928 312 7213621284783255 313 7756530053620393 314 8339332555364219 315 8964890943884825 316 9636268211226447 317 10356741297524745 318 11129816362667349 319 11959243744229972 320 12849035293664001 321 13803481433918548 322 14827170834668742 323 15925009854537949 324 17102244865666480 325 18364484402983427 326 19717724488757552 327 21168373853713642 328 22723282657698267 329 24389771195163113 330 26175662459349207 331 28089314798504135 332 30139658828710430 333 32336234567899616 334 34689233267477650 335 37209539619553235 336 39908779150755653 337 42799366175098032 338 45894557475795287 339 49208506762896203 340 52756325461666938 341 56554144531719733 342 60619183284881185 343 64969819532394706 344 69625667472514098 345 74607657255945139 346 79938123115365242 347 85640893578211069 348 91741391158667664 349 98266734603147168 350 105245851631947903 351 112709594778412477 352 120690868854703852 353 129224762142951967 354 138348690469908086 355 148102545730073820 356 158528858690122488 357 169672967072961079 358 181583199477903340 359 194311065534067067 360 207911463619797243 361 222442895907511175 362 237967702899603018 363 254552306538872881 364 272267474952505422 365 291188597197050239 366 311395982021908584 367 332975168260642935 368 356017261896020617 369 380619286605903774 370 406884563939395030 371 434923109082002874 372 464852059543495202 373 496796121830607491 374 530888054709255524 375 567269173171636600 376 606089893076972072 377 647510299582159682 378 691700760795483000 379 738842568715951150 380 789128630463708732 381 842764190753818926 382 899967610307112157 383 960971179981513410 384 1026021997130656590 385 1095382882743642817 386 1169333367820229905 387 1248170726243246046 388 1332211084694626974 389 1421790585520375974 390 1517266635338953793 391 1619019213875626892 392 1727452278233414259 393 1842995235592756533 394 1966104522147610242 395 2097265259710743706 396 2236993030588218131 397 2385835740526290925 398 2544375613333596314 399 2713231285281396616 400 2893060046114803096 401 3084560193005904353 402 3288473547757095459 403 3505588101742171852 404 3736740842633690697 405 3982820725489998183 406 4244771846276517691 407 4523596778410709032 408 4820360134740582738 409 5136192313493861367 410 5472293495277250620 411 5829937847544920383 412 6210478008646553245 413 6615349805693808439 414 7046077283777492671 415 7504277998536105760 416 7991668655453130447 417 8510071045593401556 418 9061418367459055576 419 9647761882339711925 420 10271277999637006149 421 10934275737165338209 422 11639204660246470806 423 12388663242200464722 424 13185407757970907562 425 14032361651073192552 426 14932625494156394920 427 15889487480953571929 428 16906434579149605691 429 17987164279544394635 430 19135597081023485419 431 20355889644353519037 432 21652448765106044228 433 23029946096426071931 434 24493333783618375358 435 26047860939053347380 436 27699091131988614852 437 29452920819710632254 438 31315598908252824171 439 33293747367148710085 440 35394383101264850506 441 37624941002418647094 442 39993298399840741786 443 42507800830672060148 444 45177289366905273497 445 48011129418736395571 446 51019241269539642154 447 54212132261557444392 448 57600930907904600437 449 61197422849522453457 450 65014088954792451858 451 69064145480482841701 452 73361586615727368900 453 77921229328328328636 454 82758760861120397051 455 87890788798984352895 456 93334894082518421305 457 99109686891040606917 458 105234865801637683725 459 111731280149929683120 460 118620996032632014173 461 125927365881629257774 462 133675102085911394590 463 141890354596336759457 464 150600793029009399667 465 159835693208865516784 466 169626028712153205764 467 180004567357605805383 468 191005973251669580350 469 202666914347584833295 470 215026176174487999657 471 228124781708370425022 472 242006118096381905436 473 256716070220661815155 474 272303161873441301825 475 288818704546560986312 476 306316954672798944159 477 324855279342069278419 478 344494331401438534099 479 365298233985268033840 480 387334775462438245354 481 410675614873963132924 482 435396498933023493009 483 461577490691948224215 484 489303211040975285821 485 518663093179284104761 486 549751651324395441388 487 582668763841712964983 488 617519972170830052734 489 654416795777621362962 490 693477064629412389607 491 734825269476167700813 492 778592931566768148102 493 824918992144705679897 494 873950223496208109330 495 925841661964855824648 496 980757064862969618479 497 1038869391772882859306 498 1100361312340242918823 499 1165425741141900942441 500 1234266401918396170765 501 1307098421854628660903 502 1384148958404114712702 503 1465657859454363567277 504 1551878359553366067978 505 1643077813123049780059 506 1739538467625339489337 507 1841558277750982383722 508 1949451763865499103495 509 2063550915944500784713 510 2184206146526749990380 511 2311787294099037211489 512 2446684680762996017964 513 2589310225801695020348 514 2740098619348272732488 515 2899508558002565820062 516 3068024046983468216043 517 3246155770918090533062 518 3434442538277470540086 519 3633452801844968621433 520 3843786260689178452298 521 4066075546345738255256 522 4300987999185886132493 523 4549227538031158321033 524 4811536629546261243545 525 5088698360865236681705 526 5381538622589962576524 527 5690928406056882973202 528 6017786222675948507177 529 6363080649728278474457 530 6727833011154986622000 531 7113120198269422779132 532 7520077639723388817285 533 7949902426266260479944 534 8403856600502074297233 535 8883270617857531500977 536 9389546989924239510063 537 9924164117136555744078 538 10488680322998463339836 539 11084738097651408045076 540 11714068564147351993782 541 12378496176140227530180 542 13079943661621310648466 543 13820437222433037160008 544 14602112005569137260885 545 15427217857127370916668 546 16298125376437870462956 547 17217332282486912924069 548 18187470111819836189720 549 19211311261430736958147 550 20291776397642979072250 551 21431942246023972375928 552 22635049785333549829404 553 23904512862248321670396 554 25243927252048465913052 555 26657080183887932503791 556 28147960358231943304538 557 29720768477159257067956 558 31379928317741023926763 559 33130098371488085619811 560 34976184082959164761465 561 36923350713056049798215 562 38977036863255782719222 563 41142968689104185194038 564 43427174842681824642252 565 45836002175455432185859 566 48376132245019612773743 567 51054598660550034684996 568 53878805314631203215479 569 56856545540039553020791 570 59996022243702669215617 571 63305869060561255585922 572 66795172584550029813013 573 70473495723994741237565 574 74350902244116370106737 575 78437982548977034423671 576 82745880771558864000551 577 87286323229860566449039 578 92071648324278608551590 579 97114837940271364040513 580 102429550438779154427026 581 108030155305131001952708 582 113931769546807422804896 583 120150295918202116706151 584 126702463071404395131178 585 133605867719303357158497 586 140879018919516180160455 587 148541384574418702751221 588 156613440266167868288103 589 165116720531870240062286 590 174073872709166081371878 591 183508713468245569271648 592 193446288173033398746150 593 203912933199502793149933 594 214936341367511718063942 595 226545630627253698041908 596 238771416171674915213537 597 251645886130383091197179 598 265202881032784136330506 599 279477977211832513610780 600 294508574354075607008042 601 310333987384803309082254 602 326995542913634539211208 603 344536680448492433528811 604 363003058624819264296680 605 382442666679003192735524 606 402905941436430954829900 607 424445890066218808344921 608 447118218898834666399263 609 470981468584000737073831 610 496097155913334106330423 611 522529922612923665507370 612 550347691461220372973280 613 579621830067955858975619 614 610427322703311521914282 615 642842950546534661114438 616 676951480780268274421884 617 712839864936518890345950 618 750599446961071849890433 619 790326181442560032476880 620 832120862517363068050417 621 876089363940714517738313 622 922342890883743116558758 623 970998243995254108961358 624 1022178096341096621860536 625 1076011283813009880453565 626 1132633109677909978615028 627 1192185663917693242358268 628 1254818158094093674509155 629 1320687276452428852205471 630 1389957544068314155862844 631 1462801712821035848045955 632 1539401166073724812337874 633 1619946342920546220004063 634 1704637182964231832712222 635 1793683592567986741376629 636 1887305933636063599617648 637 1985735535958824765185380 638 2089215234276051677543569 639 2197999931194825156405525 640 2312357187224485972264923 641 2432567839175027734705169 642 2558926648300320298690441 643 2691742979552953567229035 644 2831341513462060227707607 645 2978062992132719585412546 646 3132265001020350045559827 647 3294322788122931910051334 648 3464630122399715012144376 649 3643600193217067978380067 650 3831666552799778120915172 651 4029284103661102093710236 652 4236930133175257050974590 653 4455105397454490064046429 654 4684335256896960200079267 655 4925170865774092538377034 656 5178190418444914251724634 657 5444000454791861629606758 658 5723237227707283021435730 659 6016568135472034923847210 660 6324693222119411676429141 661 6648346748895723221296681 662 6988298840199105994147809 663 7345357207402911273456091 664 7720368954260139983818195 665 8114222467617703476965479 666 8527849397480810531174606 667 8962226730508598914788684 668 9418378961356713475633345 669 9897380366332913621985038 670 10400357384191241617254400 671 10928491108951390282367619 672 11483019900016170688830834 673 12065242114933095736294601 674 12676518970561278028176159 675 13318277538491375312777506 676 13992013881012698666052925 677 14699296334023105996517589 678 15441768943757349701557017 679 16221155064327734990908096 680 17039261123587322503610584 681 17897980564962653636807711 682 18799297973458569812191425 683 19745293394195060307667782 684 20738146852434003160377690 685 21780143084233908780198252 686 22873676487514420472815113 687 24021256303517936183472417 688 25225512039348730180796578 689 26489199142503651943699748 690 27815204939054819681401596 691 29206554847409498363652420 692 30666418880376299776028105 693 32198118448565959777584000 694 33805133479021137681413228 695 35491109863306728541330566 696 37259867250225628019721133 697 39115407198703786280179118 698 41061921707394526723555830 699 43103802137977146075049146 700 45245648550209522320018450 701 47492279467270338096266445 702 49848742091096174165550609 703 52320322987950585125793836 704 54912559265723746785197531 705 57631250265054713341411713 706 60482469787729093917755980 707 63472578886466133957956931 708 66608239241677334773294053 709 69896427151514351216734690 710 73344448163108183722826811 711 76959952373719039587961889 712 80750950432226120804879902 713 84725830272293699795125438 714 88893374610395596833620013 715 93262779242885747151938327 716 97843672178295283597465805 717 102646133642150125469564780 718 107680716993754825358953990 719 112958470595620366807080203 720 118490960678537427297933587 721 124290295246658264914971849 722 130369149069460388781547570 723 136740789808968869677442310 724 143419105333325621080234339 725 150418632269453191297167363 726 157754585850490115190608359 727 165442891115504268822991622 728 173500215522156149524227772 729 181944003034999566778950743 730 190792509755528106828714490 731 200064841162294875497561003 732 209780991033130339921600267 733 219961882123924770933801779 734 230629408682438330272585098 735 241806480878286711772404322 736 253517071234570693968416983 737 265786263149568483381186412 738 278640301601580810455752447 739 292106646133259377025209096 740 306214026216799918564851443 741 320992499104938510126817361 742 336473510278151340445357553 743 352689956602361226439655270 744 369676252317360617781560369 745 387468397980441063743249119 746 406104052496107240621850418 747 425622608367445283835776063 748 446065270311624759097116082 749 467475137387153914609713698 750 489897288787982027020530224 751 513378873465172105441510388 752 537969203744952658332841373 753 563719853118119824800520771 754 590684758384508438773819623 755 618920326342994154102744051 756 648485545226952595046476049 757 679442101092477975409250355 758 711854499376903309638351199 759 745790191853230181474986600 760 781319709217155737292684800 761 818516799552201086980634453 762 857458572930434503181602997 763 898225652415916583369726671 764 940902331750968481578582744 765 985576740015887650059076284 766 1032341013566775650206617259 767 1081291475567633983541472477 768 1132528823448078356002128550 769 1186158324630566451011423325 770 1242290020887478534788032738 771 1301038941702080638747296399 772 1362525327025197410658292152 773 1426874859834358277622937954 774 1494218908921442838261271355 775 1564694782351142992541070455 776 1638445992053407559818673230 777 1715622530030799924993613565 778 1796381156684264466989659322 779 1880885701780163686977283650 780 1969307378605871922182794164 781 2061825111882318091175332131 782 2158625880028306077521800579 783 2259905072394439084290778455 784 2365866862113088690120063079 785 2476724595235901714226370494 786 2592701196861310310639624687 787 2714029594981794991828232932 788 2840953162814174928603594882 789 2973726180405908210300241214 790 3112614316346672088600104240 791 3257895130446833905472236575 792 3409858598283701030781036568 793 3568807658551636889755865163 794 3735058784194644296758550539 795 3908942578338318769732061991 796 4090804396084091515096786969 797 4281004993270350996912139470 798 4479921203354840040619237148 799 4687946643618049585104207546 800 4905492451941240932123242093 801 5132988055462018537177341345 802 5370881972468725935805326443 803 5619642648948530590746655174 804 5879759331267218418450371403 805 6151742976516979888943931040 806 6436127202136823308917836881 807 6733469276473575187752343669 808 7044351152025406470619297214 809 7369380543178638802052074382 810 7709192050328650154250639111 811 8064448332350468941780676027 812 8435841329471295803151314566 813 8824093538678417999531261104 814 9229959343889755425766844647 815 9654226403202501911424784213 816 10097717095636806368070998830 817 10561290029887249568486813406 818 11045841617704690162820344606 819 11552307714635087265613294334 820 12081665330960742862925617837 821 12634934415802351689793573527 822 13213179717468836531219105096 823 13817512723264546577158271557 824 14449093682102536992268869297 825 15109133713405708396617084772 826 15798897005928135858465331902 827 16519703110273309859545015136 828 17272929329048902563579306939 829 18060013208754340545581798026 830 18882455137673700549854634419 831 19741821054216407173900447277 832 20639745270338876860631190314 833 21577933414864612003848977301 834 22558165501726517473928847381 835 23582299128355160683434308648 836 24652272809659835133846381104 837 25770109453266114765798112238 838 26937919981914964738706874828 839 28157907109163574014345275489 840 29432369274789172014872986935 841 30763704746551970509699934536 842 32154415895255785153616035377 843 33607113650321177858511841856 844 35124522143391416673712451544 845 36709483547791004910127145842 846 38364963121986893026182591422 847 40094054465527012732757144096 848 41899984996288054057117395407 849 43786121658216058949176060747 850 45755976869129779935217159573 851 47813214718537753717094950124 852 49961657425837855948077457297 853 52205292069680853749952095231 854 54548277599731265379300247002 855 56994952142505929011664548270 856 59549840613459189149566121446 857 62217662647967845383690878410 858 65003340864397183643350446361 859 67912009472953815981918633727 860 70949023244602089528203518369 861 74119966854888669162657675719 862 77430664618137236154454804467 863 80887190628090056678558352984 864 84495879321740532322590664755 865 88263336483766435851361743581 866 92196450709694926575581310150 867 96302405346650926182028134285 868 100588690931320190279309017179 869 105063118145538236704498636828 870 109733831310759082726513882206 871 114609322443501706071813894913 872 119698445894783015613520714920 873 125010433597459396593343429084 874 130554910946383287751107331760 875 136341913337269433637324679477 876 142381903391229240982634004078 877 148685788893000794974530288670 878 155264941472051604722352600933 879 162131216056887727674134462007 880 169296971134144998060760833946 881 176775089845289146411941115005 882 184579001955093606587292237324 883 192722706727416933945785994948 884 201220796745251653952146897911 885 210088482713479735661052235050 886 219341619284336243679844107346 887 228996731947165173697160685138 888 239071045025743550021299588104 889 249582510828160915592487638435 890 260549839996069108897727320754 891 271992533101967148788023355705 892 283930913545160261067229565996 893 296386161799031963841826439531 894 309380351064400391056347910793 895 322936484385891825885106741001 896 337078533290567235770577443072 897 351831478010374192805279590998 898 367221349352483426588813222371 899 383275272284094549269072157589 900 400021511300980937762107963426 901 417489517651772740923108449745 902 435709978492876679145137390176 903 454714868051880138876828583027 904 474537500880417912568223193967 905 495212587280666046720521209597 906 516776290993007466194932619661 907 539266289235856217288727531450 908 562721835192276360478296078373 909 587183823041750030043206879212 910 612694855639388499553111412160 911 639299314948896717544452575311 912 667043435339854025278369065336 913 695975379864212058291709341764 914 726145319631500566980786763840 915 757605516406917199817956105942 916 790410408561430975501712153015 917 824616700508088820017250701932 918 860283455764060688225320455289 919 897472193783422222748587146055 920 936246990711443224321995027367 921 976674584217049147986693997011 922 1018824482566348428810223285326 923 1062769078106487067362257620451 924 1108583765335809406824893079003 925 1156347063743179168835004090260 926 1206140745606562622453339438720 927 1258049968948397071432308066988 928 1312163415853087309251177189080 929 1368573436359982905783781626949 930 1427376198153624845063590367636 931 1488671842281695173752321865774 932 1552564645140203125844272901393 933 1619163186974770821582638685714 934 1688580527156697238446190098055 935 1760934386502546656931269696869 936 1836347336916594785276186553039 937 1914946998646328627527233190343 938 1996866245452614434087233809611 939 2082243418007868186256022972035 940 2171222545847877072987183606101 941 2263953578215564427228956880159 942 2360592624148269720206245626806 943 2461302202173754869615760949550 944 2566251499994467071555642801096 945 2675616644554300916731876703069 946 2789580982897541733472749613611 947 2908335374245540696139003128500 948 3032078493733318189841301230337 949 3161017148265406069122825871483 950 3295366604968185312258667982188 951 3435350932734431607411660063224 952 3581203357375127419595917015999 953 3733166630913500693022085026436 954 3891493415577104371034902798054 955 4056446683065209674167432558304 956 4228300129691264187779949079821 957 4407338608023301795277403264980 958 4593858575669418573188694759900 959 4788168561880371177889570192630 960 4990589652667464668138815152751 961 5201455995160784566631562017235 962 5421115321960966265684695967269 963 5649929496266677752307223206233 964 5888275078590313321868127386830 965 6136543915905634734921518819779 966 6395143754103768632112944387031 967 6664498874667636813114505260264 968 6945050756510098935620133356506 969 7237258763957370174327548779716 970 7541600861897203435836167836261 971 7858574359150424163533932743694 972 8188696681165265050989897379554 973 8532506173176077259742819889667 974 8890562935012010067103072656477 975 9263449688786642621395612260346 976 9651772680746963536214611973028 977 10056162618608997376360309000318 978 10477275645758444661860182239604 979 10915794353747384759585194270833 980 11372428834573092382244132330813 981 11847917774281768583705065859840 982 12343029589499221429526976213144 983 12858563608551658767777669160421 984 13395351298903544374282958435089 985 13954257542705305972670237494231 986 14536181962312372777214345167341 987 15142060297707925290305099775047 988 15772865837835701177227145517321 989 16429610907925558682933199034146 990 17113348414974131555097985987719 991 17825173453625133144947567497357 992 18566224974779600607514370324620 993 19337687519354904337039741140231 994 20140793019703643197389755292087 995 20976822671298868487832296756559 996 21847108877391433053698675588919 997 22753037269447885825377748930892 998 23696048806284276440128190813487 999 24677641954921711590917493145305 1000 25699374956304612584775206464044