0 1 1 0 2 0 3 0 4 0 5 1 6 1 7 1 8 0 9 0 10 1 11 2 12 3 13 2 14 1 15 1 16 3 17 6 18 7 19 6 20 4 21 5 22 10 23 16 24 19 25 17 26 15 27 19 28 31 29 45 30 52 31 51 32 51 33 65 34 95 35 128 36 148 37 154 38 167 39 211 40 288 41 371 42 430 43 469 44 532 45 666 46 870 47 1089 48 1270 49 1431 50 1667 51 2068 52 2625 53 3229 54 3790 55 4368 56 5166 57 6360 58 7922 59 9644 60 11387 61 13324 62 15894 63 19448 64 23926 65 28953 66 34355 67 40605 68 48666 69 59268 70 72327 71 87234 72 103913 73 123626 74 148539 75 180261 76 218829 77 263474 78 314773 79 376078 80 452426 81 547629 82 662564 83 797076 84 954325 85 1143277 86 1376133 87 1662619 88 2007269 89 2413965 90 2894678 91 3473735 92 4182029 93 5046021 94 6083853 95 7315912 96 8782378 97 10550442 98 12701785 99 15311903 100 18445786 101 22182143 102 26648732 103 32034605 104 38564130 105 46459474 106 55939832 107 67276661 108 80865480 109 97247467 110 117058209 111 140963436 112 169675967 113 204081973 114 245389608 115 295171156 116 355269112 117 427697612 118 514721376 119 619147548 120 744642737 121 895829876 122 1078137880 123 1297688100 124 1561566536 125 1878511661 126 2259620161 127 2718610493 128 3271655856 129 3937392516 130 4737766297 131 5699698358 132 6856742315 133 8249886510 134 9927658865 135 11946814669 136 14374857171 137 17294206970 138 20806327183 139 25034287690 140 30124360044 141 36249330705 142 43615878810 143 52475391324 144 63134821843 145 75964974917 146 91407978439 147 109989569559 148 132340600839 149 159226091977 150 191575188084 151 230507775199 152 277362522915 153 333738148837 154 401556262375 155 483141880900 156 581309055260 157 699445486198 158 841608446951 159 1012656934127 160 1218436292112 161 1466007198535 162 1763896422358 163 2122362988409 164 2553710867276 165 3072701673190 166 3697100424774 167 4448339913005 168 5352266609302 169 6439970278043 170 7748775528875 171 9323512965240 172 11218142010969 173 13497706947081 174 16240576800350 175 19541012416220 176 23512258772158 177 28290430505084 178 34039361923290 179 40956425758400 180 49279296163651 181 59293847988728 182 71343701693462 183 85842051200532 184 103286218186774 185 124275083845341 186 149529569910779 187 179916845845841 188 216479600882722 189 260471971080768 190 313403353232647 191 377090871942894 192 453721499601961 193 545926016639342 194 656868417809331 195 790354925196137 196 950966196256309 197 1144215724777502 198 1376738388184197 199 1656515934050634 200 1993149359644810 201 2398189539261777 202 2885536846229948 203 3471920309218008 204 4177470047012333 205 5026403681879641 206 6047854832957221 207 7276875745136535 208 8755646694709733 209 10534927202460289 210 12675794038109982 211 15251728561849195 212 18351134259973397 213 22080377272803489 214 26567449642306557 215 31966367935280004 216 38462449802419466 217 46278656859932574 218 55683240094626081 219 66998961175083443 220 80614194850390050 221 96996267380006027 222 116707474597632044 223 140424346756978121 224 168960858129642098 225 203296396120099574 226 244609423405479520 227 294317936828028121 228 354128088734616192 229 426092679484252263 230 512681601006719793 231 616866677655221192 232 742223756353607215 233 893055448968123833 234 1074538705046896576 235 1292902369225588248 236 1555640958146193248 237 1871772035015548200 238 2252145882976952240 239 2709817910368627624 240 3260496523240608657 241 3923082032418678072 242 4720315362387329696 243 5679558876138693688 244 6833735828361128064 245 8222460316586188521 246 9893396466027914353 247 11903893918046616425 248 14322956270944701456 249 17233610066887151448 250 20735755021086010273 251 24949592610975230938 252 30019750700660719299 253 36120246655019232234 254 43460460255878469329 255 52292321358917863177 256 62918957698948392659 257 75705098332721960510 258 91089589966655182471 259 109600457611558420862 260 131873028269815564740 261 158671739313744725165 262 190916377390588216346 263 229713645998325535640 264 276395145910935563843 265 332563075848029168073 266 400145225195118710767 267 481461144974148506251 268 579301762702658477151 269 697025169299849315829 270 838671867757290267556 271 1009103446954083442683 272 1214169446017296385091 273 1460908132871925694169 274 1757788076976656299231 275 2114998799759798060536 276 2544800484011223026068 277 3061944760728670095330 278 3684181025843305521943 279 4432865655865878378491 280 5333695009608380053936 281 6417587360747677385835 282 7721744044499691181934 283 9290926270583198643341 284 11178991442437853995764 285 13450741691317563954370 286 16184148026221935818262 287 19473026414855748621705 288 23430257675830567211110 289 28191661757520743821039 290 33920659404338616593475 291 40813881159977353768396 292 49107916132395248394337 293 59087432116908251651077 294 71094945848207059653854 295 85542578837689927625624 296 102926202321836714182910 297 123842456696711218756208 298 149009229409280853813810 299 179290294097510559699268 300 215724956802805238930555 301 259563727007733701462388 302 312311237856237860564742 303 375777888427828786752928 304 452141980203502632269286 305 544024480309596652443633 306 654578977908049500092211 307 787599921666776800957685 308 947652853291800348780058 309 1140231106487569279586956 310 1371944348940928071465847 311 1650745438421148784805130 312 1986203379884422953493529 313 2389831752866626649829954 314 2875483881446146429324699 315 3459828308720297699832861 316 4162920893849646135857933 317 5008893167246499809764506 318 6026780571172198388128613 319 7251519014197196032648182 320 8725143943033070778987514 321 10498233084016090265015493 322 12631642369816443645455300 323 15198594632268344333751052 324 18287192752615894230541301 325 22003443528402465199764309 326 26474896041246357076651189 327 31855019396865604689458307 328 38328470086100878244221845 329 46117429754700682209747653 330 55489230913286703764056662 331 66765532322264716506956799 332 80333358966514426965873805 333 96658385524212840010331341 334 116300919237667165143427805 335 139935130754088264218026160 336 168372192990252102480761114 337 202588122202065847236887266 338 243757276812991983483161945 339 293292663728394432119632951 340 352894435515968269371785306 341 424608242982007531842215079 342 510895445946406213935674540 343 614717592005309933200810325 344 739638062743452262839682162 345 889944376057354684974580202 346 1070795342226370233333633336 347 1288398124444382015149674925 348 1550221280933723678978699944 349 1865251100695168409976167027 350 2244300030806116881015072689 351 2700377781027177181147895700 352 3249137842728106933457888463 353 3909414747604475927462008205 354 4703870506073274104104541896 355 5659772412435008969969939660 356 6809928912528462472139135416 357 8193815654561400995620856852 358 9858930371359760042067792368 359 11862423096405856965024438564 360 14273057666112759001536489761 361 17173571831036745546213616972 362 20663516979524872437729931928 363 24862674938449623509827784636 364 29915169122327018002713087784 365 35994411133878376008628720693 366 43309052593555361512774545297 367 52110146476674376985480038661 368 62699763749011241493771333536 369 75441361040301513950270804348 370 90772255194655017521169593113 371 109218632849760755524116353774 372 131413610204108114506883304651 373 158118962819240979992025917494 374 190251271265987132429522176545 375 228913379983967772965211730997 376 275432249084717286995556751235 377 331404498248523887552169251538 378 398751205873109850023025575919 379 479783844289336226928431398690 380 577283614069195885386759825036 381 694596900334672192390290658777 382 835750127317208947512937733770 383 1005587953206351024570751578692 384 1209939548410969964503626226147 385 1455818664231641962338216799645 386 1751664358693204304705481882503 387 2107630641721077025289988217583 388 2535934980858232164473979971239 389 3051277628934529936587315538609 390 3671346165848962951412594604484 391 4417422571335816231547324908295 392 5315113664645923292333686899731 393 6395229981272513494469450071325 394 7694843251513839126351283727431 395 9258558775641725052473890114332 396 11140046366119309119547235051388 397 13403882401830702475293606412510 398 16127766217254253018350461879351 399 19405186897432275913154420698487 400 23348632008428077673294623913088 401 28093448393274873298372408893151 402 33802487543591736647314731578230 403 40671694985204264613191303343249 404 48936835516517231406798488990348 405 58881585123114606604799506490926 406 70847267299135226884821453504726 407 85244567945294687618981764384469 408 102567630922070874558878443814630 409 123411018045313232667304523911827 410 148490115624836102624789298824523 411 178665687938767064896419448986000 412 214973420367544521108602724380121 413 258659466166500789062681661703825 414 311223216912678794845164732110926 415 374468764592220209850972266550980 416 450566821608916400188513271722350 417 542129223931147688629811472190644 418 652298574472812375067703835069946 419 784856103446724105016449118194872 420 944351447671399793758818660365731 421 1136258803113815404884650270384256 422 1367164810132284298669297010463974 423 1644994620012876463886028578982940 424 1979283901850684168713964425455462 425 2381506125590936273842971613630549 426 2865466354231939303659918048944859 427 3447775060917499497312765941213961 428 4148418233258976167439975859831170 429 4991443331995844931269290014902376 430 6005784647454496906442964618068951 431 7226256381673559746216854088030870 432 8694747540740375074815655603789369 433 10461659648408414968412659849989990 434 12587636626172320596022031815947507 435 15145646212709318005152230492802497 436 18223484361123901583929108721002197 437 21926788569868431727475474309889190 438 26382663570822349789445169541810229 439 31744043815321110639250347269726866 440 38194942487290053569586922158739994 441 45956767200005540185103371029752201 442 55295919143701651316556813523693884 443 66532936501814683100849752572701616 444 80053495956011892156170991121426285 445 96321649873433513998282438970277089 446 115895753502616704393940640458219061 447 139447628830997245071247106712186079 448 167785622845521874602509937126147701 449 201882351601528226573577557217821785 450 242908082331260089255303182664404990 451 292270899332062110548394070549922435 452 351665032207047463463470186140682229 453 423129005179135824067697684296552841 454 509115603278047346247334601056155565 455 612576056778310190431390677008374476 456 737061333264850426377274810432149210 457 886844013870369663267167439355009654 458 1067064936718245398079561940987157505 459 1283909640664230633778502471493390635 460 1544820665235493360746422962361082882 461 1858752993321207963056000088496679251 462 2236481403913530280075832926795533340 463 2690970283853465487724004190774316369 464 3237818591252845695125231851835557794 465 3895795242617969392604487374841631022 466 4687483299220931957580925522351152768 467 5640055062470231603878255977653295473 468 6786204681088203730855837206066528960 469 8165270279019841462925068969405407503 470 9824584117724280575453723417451505185 471 11821097133091747045310644749028341584 472 14223333604309132954063668874846079263 473 17113743042779367292315018706070977201 474 20591530022578276797659162153125231936 475 24776059077832325769234629592923441648 476 29810951529835869083689437135885254272 477 35869014855125160574828037041325926032 478 43158173780180247291689332329945398048 479 51928606669666777044037849734042288400 480 62481332143189969859208810452119650785 481 75178540630246471650583228881933927856 482 90456025462793355427752103770134621952 483 108838140165141276950206806507156578352 484 130955795304972184910555219105313612480 485 157568112593036994194935992516107337233 486 189588479443103218553829889068095867041 487 228115898236229796937544143104188200593 488 274472706258181104028542139159225128160 489 330249960932906817288514129382604812784 490 397362048063150456055698018128577528065 491 478112387341112397659321100689516816754 492 575272490272370009686310024688391404867 493 692177083937514119519916171331509195794 494 832838565427317718254600411646018141537 495 1002084715254238377372754286670407469009 496 1205724396337169671003533248200699157603 497 1450746925676632863401329143506485749686 498 1745561961550996526865547296709417417415 499 2100288139637201847460826607665918742198 500 2527100364619070215147270869647934806340 501 3040647677018725766630887946517124768149 502 3658556037268040911777616678377592376298 503 4402033283564799061270409688416602324704 504 5296597026864831237727703047881821909299 505 6372950465807268589473644774023270965953 506 7668036181274997829238985423830978316687 507 9226304078905836893555775494542651950787 508 11101236997851565739678914313311319469151 509 13357186347697671210775729414676016610301 510 16071580776236898888471757510321695199956 511 19337583673947097656440333245736071191939 512 23267290725988103312268405692396901233427 513 27995577258032400462473675231684949736625 514 33684727424455073844010419222529988030239 515 40530004121786135838926401238309031279408 516 48766350797881667755687820170733783002196 517 58676455176172099857180496448454667625322 518 70600451657967601431182414169817922161991 519 84947595408475577618752500146611839000291 520 102210308804273610145410495692523969046272 521 122981082344122877438624640631572802311843 522 147972810095839903451794717857497481906926 523 178043257632021369044050730789006372789509 524 214224502242615278907115410764884428787604 525 257758355870716789195345410008953730208554 526 310138986556872065202787636470708610358406 527 373164201244236391035829854181594253265041 528 448997150071984149934470089278076657008278 529 540240569970476551402960859411388283484039 530 650026115745353437146511551562844531785667 531 782121844670204133305248457244546769354564 532 941061543671825245433962900661256593832001 533 1132300337873092606173087579930379520631725 534 1362401921286697092373260802871059193757358 535 1639263835787814138483942500252309472277984 536 1972388530386034121854720868218779584624270 537 2373209504087382815885722909468647894972232 538 2855483726215121984912298937836182883818290 539 3435763802831614943980311283462695308221084 540 4133966094947603837030290883053748186667067 541 4974054287460545352711924171342148250659612 542 5984861870261231076224386277939736951874486 543 7201081760688538922652742715523610363414792 544 8664457033134119744778333130767526087011606 545 10425213623994340765922901104352626378706441 546 12543784185239764133722526337858591745547763 547 15092882252669380265966601332335633389201165 548 18159997918410315351589053164805495565948890 549 21850400664083889743655462124230873402300884 550 26290752417816999433353976950643762829132839 551 31633454842368224644423760572978744211265810 552 38061880061903485165612028774546851513455369 553 45796664356319459751278180834999720700697818 554 55103280835163585361211116621372002357450939 555 66301151000311204528598492239680131797382613 556 79774607924269113821433199647853380442699533 557 95986087322088709243389766298169358553854018 558 115491999260591169561313970182525316425418997 559 138961825253386530278101326230918574571604126 560 167201096191794249641087789696051854855531370 561 201179039759743903711242808508905514597533085 562 242061846246669027593421458185702870793936164 563 291252694506948992626136936128548055421972548 564 350439911836066409082805062711613249550877141 565 421654920705771949480503086109495745852554493 566 507341961204924683630431924435875944024668581 567 610441982198207180945752056390660240247000619 568 734493580513361923930801202823156440813441797 569 883754452589684429302363457025864175766785853 570 1063347527048787351189445084949657050825404182 571 1279436793746763042193740073256984939428100215 572 1539438864108903814056687066936031930124223693 573 1852277523916493788506985183649692625085110997 574 2228690015301253534178916716239680856827228269 575 2681595560151833704422609744798677667405631832 576 3226538773385234822685548615232506166020290250 577 3882223184904454207439872225142673920377728090 578 4671153181772160644757412323842709494637434905 579 5620406403326651136742588966825405412036562959 580 6762563099369581027108511644688051149317971098 581 8136824348838322061287075076270864690253150351 582 9790357518441522734548030585173857753803650172 583 11779915140061849674882833164217889581035453245 584 14173782770003265988939873515810788827051725954 585 17054122684468392808608512935356166055991968962 586 20519793851534554225138175687784321251607684408 587 24689744966649425822943617306132773593374771621 588 29707097007341694470717938825662612025092253768 589 35744055428506638398370737265202536161890829371 590 43007820594533508472431219615384844464079148161 591 51747699306006213022686562138951276134651379324 592 62263661502652372856690305929273260900974424991 593 74916635825525674518799731819579706870074709797 594 90140897402497758692032293396997921780357854760 595 108458973030381841341519895706249992651062231300 596 130499575329046359893488519019538656760621356856 597 157019181403192094351808087683609381499704952476 598 188927996634184260398176599887804243905700514112 599 227321194730675806067522331145850889551406989548 600 273516506258405274552351920922827621301494795857 601 329099445761925959927040708122786571192041442916 602 395977729762620295586816502409398030911388540632 603 476446753366422714643473206590952282166026823444 604 573268372768052160817507018717264514956812456136 605 689765697623265341018050851956482754758602299517 606 829937146751007040546914960191465082044943228321 607 998593681782951530066209131455012223404924779405 608 1201523928890968970157330417123136884269456806992 609 1445692855897095171047796727717614828034227820212 610 1739480823757740216479031077264699551881441579097 611 2092971217142324542382472830865212351760357983974 612 2518296526157223911631174943602960060208470307243 613 3030054757424927540770454508769614189719324814718 614 3645810466571015671271336276295763935708609406609 615 4386697608545804357684158222105451264185126206301 616 5278144896797159929909300635847526731676027383283 617 6350748567057288670492678851732871963850269870314 618 7641322500724475994784102283237786601688153105935 619 9194161750153167123672965728668338185636404528570 620 11062562832541747569725949007170829389613060427628 621 13310652971913979958864795134248741931569762996193 622 16015591072400252958086137709685849959711423459898 623 19270215964578924595186081770818185297214450359532 624 23186232817934931788949746863638996751174827504819 625 27898047083419390688183017019076954176937618062133 626 33567377554608894652263709870087909506819227952391 627 40388806876855980486676881851105421280894246883719 628 48596460008893157512137014614752777188495636815623 629 58472039854914109342221966344143032008100701324249 630 70354495865933247072318845653534136225326895926484 631 84651657455963217129396473752803860434931673519343 632 101854231514884265827123608740270284964651092898243 633 122552644440358032651077606335946107976209111651733 634 147457306740663247341035862810001230477490585023591 635 177422995729740513926677826612429945421923234066356 636 213478193176810573543937285750481028668359270770076 637 256860384836780730028838928146608281624909662344070 638 309058533411205515607597688829020253375791878069319 639 371864182695905545819237077886217623418350789573567 640 447432946910761793918791295758377283875622930741680 641 538358495647214334811650975172912204567773089860023 642 647761573743331817499454040509519255715192167180502 643 779397111424796819180373902726109563669060811183465 644 937783100943891791455673694861846158419052329986956 645 1128355663017872855345626062473615160669765598384566 646 1357655625253881674549679348817507111861746810175270 647 1633553016301307946229896311440808744158588187782205 648 1965517180815342971491478918408541023952026068223990 649 2364941786112020428135501638097474977803305308350923 650 2845535875386561465981673660061570882757878739554987 651 3423794389215646321350979106152968430950564738546792 652 4119564304573062476125201722731931016690100596342041 653 4956725822370532592271054578666856879972361066181465 654 5964011983228671345856876867946824745913919564357118 655 7175994842313924865608654216567586884513210116129900 656 8634272050714228215468154404312014291511748786452702 657 10388894569175270263457854488946470330398544074443820 658 12500084516159241389747235407551756327613026401070298 659 15040302110172266414253133169345612642576381226880624 660 18096732647913128803736585663181268510399490746668483 661 21774278876256824426933685488826425921938878466939720 662 26199161462203423344534663109826071506423502977026422 663 31523251136048739868673244300810240949523319261966820 664 37929281195506778067458223065843839300587951702394742 665 45637119274244636607736954240078637480588898374619405 666 54911313634342219644923404321353307074914750440488827 667 66070172986373376575204934261833765938761872190634625 668 79496691474508987640141592899462738377885700705932962 669 95651693793758941280666130476480151756534773941387984 670 115089651605800154543868421606732717730700169338980967 671 138477714104093634320118581627275783856091600517502974 672 166618605894960232827865292823265710494265521005742857 673 200478178095224583860269931482649811391562323337056414 674 241218558254641305496012657637776656073182346837955571 675 290238036874068083464676144982675607865120643986301913 676 349219059503652730144653133710488653343326543797871925 677 420185971604854021691852296057274212081057290862226798 678 505574498094278451008253805933191305741919444860302245 679 608315342244826122184147881943692177959010191180754842 680 731934773223933972820958734103102075329865314161313898 681 880675654632362119105341936330940917281629534622129409 682 1059643067982574835301181574750438473289504478646400636 683 1274979529202785202844759235700954171166303279520400968 684 1534075811943958594884253983934157695781986926903283885 685 1845824613563038546013360421979985559030794950202370985 686 2220925770101122214110448552377735170570505039964198149 687 2672253495838870927227482245184481465900999327429843943 688 3215298251817722157251282746782333561737437292788931013 689 3868698409129318633030194794385550340237794685070085489 690 4654879954709782343742373641615097425979085156626055838 691 5600826195608119355008062958291878425383286917069853019 692 6739003879503031687351291219542202195502299317596413077 693 8108477517757715298589213544344550198208941660182973105 694 9756250156785911717508959786352365367876231305288860445 695 11738876615656823134023851182782981327954317134485072340 696 14124404559447220331780631394292526191600166758765994346 697 16994710029820933386101727819449178046864671391292321934 698 20448307592868866340948567722178630819094527894849239201 699 24603731554046658703449464550239117761587472283068246627 700 29603604290200450150122024513479896894039490099956905890