1 1 2 1 3 1 4 2 5 3 6 3 7 3 8 4 9 6 10 8 11 11 12 15 13 19 14 22 15 25 16 30 17 37 18 47 19 62 20 83 21 108 22 136 23 168 24 205 25 247 26 295 27 354 28 429 29 524 30 642 31 789 32 972 33 1196 34 1466 35 1789 36 2173 37 2625 38 3155 39 3778 40 4515 41 5391 42 6437 43 7692 44 9201 45 11014 46 13186 47 15780 48 18865 49 22516 50 26818 51 31871 52 37791 53 44714 54 52805 55 62264 56 73332 57 86295 58 101495 59 119338 60 140299 61 164927 62 193854 63 227805 64 267603 65 314177 66 368576 67 431990 68 505768 69 591445 70 690779 71 805796 72 938841 73 1092634 74 1270341 75 1475652 76 1712865 77 1986975 78 2303775 79 2669965 80 3093265 81 3582537 82 4147920 83 4800982 84 5554883 85 6424566 86 7426977 87 8581322 88 9909364 89 11435773 90 13188543 91 15199477 92 17504751 93 20145565 94 23168899 95 26628373 96 30585221 97 35109388 98 40280767 99 46190581 100 52942912 101 60656400 102 69466124 103 79525686 104 91009512 105 104115406 106 119067399 107 136118933 108 155556432 109 177703323 110 202924591 111 231631943 112 264289677 113 301421355 114 343617404 115 391543764 116 445951712 117 507689014 118 577712556 119 657102621 120 747078977 121 849018970 122 964477818 123 1095211320 124 1243201209 125 1410683413 126 1600179517 127 1814531747 128 2056941854 129 2331014324 130 2640804420 131 2990871618 132 3386339093 133 3832960017 134 4337191535 135 4906277402 136 5548340388 137 6272485718 138 7088916956 139 8009065908 140 9045738283 141 10213277055 142 11527745661 143 13007133371 144 14671585389 145 16543660475 146 18648619146 147 21014745764 148 23673708126 149 26660958502 150 30016180440 151 33783786063 152 38013469057 153 42760819095 154 48088004051 155 54064527064 156 60768066309 157 68285406265 158 76713470303 159 86160465599 160 96747152702 161 108608253582 162 121894013654 163 136771935106 164 153428700915 165 172072311191 166 192934455969 167 216273151263 168 242375668159 169 271561787939 170 304187419714 171 340648620812 172 381386064250 173 426890002065 174 477705778069 175 534439948810 176 597767077183 177 668437269345 178 747284532366 179 835236037478 180 933322381979 181 1042688951907 182 1164608497623 183 1300495045551 184 1451919281698 185 1620625556338 186 1808550674583 187 2017844654630 188 2250893654491 189 2510345289188 190 2799136583924 191 3120524834878 192 3478121678245 193 3875930700244 194 4318388956278 195 4810412806557 196 5357448518582 197 5965528134268 198 6641331151458 199 7392252626518 200 8226478367013 201 9153067951532 202 10182046388050 203 11324505303243 204 12592714643541 205 14000245965008 206 15562108494102 207 17294899255781 208 19216968690213 209 21348603315556 210 23712227143020 211 26332623713034 212 29237180799270 213 32456160022204 214 36022993827582 215 39974612519677 216 44351804296812 217 49199611519755 218 54567766754994 219 60511172477510 220 67090428694792 221 74372413168973 222 82430919370970 223 91347357803501 224 101211526883337 225 112122460181940 226 124189357492906 227 137532607929946 228 152284914066446 229 168592527013393 230 186616603303429 231 206534695512441 232 228542389714302 233 252855104137737 234 279710064786013 235 309368475300248 236 342117900006508 237 378274880897312 238 418187811272638 239 462240090918113 240 510853590044340 241 564492451768258 242 623667265703813 243 688939648265664 244 760927268598944 245 840309362655364 246 927832781868795 247 1024318627172460 248 1130669523778578 249 1247877597246761 250 1377033216940291 251 1519334579054279 252 1676098208045642 253 1848770462555470 254 2038940139848393 255 2248352281465046 256 2478923292262615 257 2732757495380750 258 3012165256998613 259 3319682827133226 260 3658094056267002 261 4030454162388826 262 4440115739202363 263 4890757213920808 264 5386413982362322 265 5931512470128949 266 6530907391649310 267 7189922503959776 268 7914395179471475 269 8710725151817364 270 9585927821406501 271 10547692542760707 272 11604446354320080 273 12765423653446977 274 14040742365124522 275 15441487202651584 276 16979800672825060 277 18668982537045611 278 20523598503891042 279 22559598998414734 280 24794448929226952 281 27247269456829959 282 29938992856276632 283 32892531664631851 284 36132963409618295 285 39687732330967620 286 43586869631186160 287 47863233928566977 288 52552773733303195 289 57694813928534068 290 63332368413232626 291 69512481254271677 292 76286598902143817 293 83710976250140675 294 91847119561925632 295 100762269559110396 296 110529928250566537 297 121230433400827006 298 132951584878291829 299 145789327497465287 300 159848495375738378 301 175243623267125638 302 192099830815937217 303 210553786195933441 304 230754756168657305 305 252865750212248180 306 277064767043298344 307 303546152583751561 308 332522079217353800 309 364224157041038860 310 398905188751581818 311 436841080823058962 312 478332924732793609 313 523709263189765847 314 573328557617733619 315 627581874554006016 316 686895810153076261 317 751735673642066771 318 822608952372888622 319 900069083065792732 320 984719555953180983 321 1077218380824798567 322 1178282946460537102 323 1288695307631080625 324 1409307936766915851 325 1541049980561665653 326 1684934065206746351 327 1842063697673179855 328 2013641314487069835 329 2200977033813865739 330 2405498171401376252 331 2628759586063218942 332 2872454925946240523 333 3138428852853425518 334 3428690328426943351 335 3745427053076516551 336 4091021156211970806 337 4468066244655163333 338 4879385925119052392 339 5328053926408416507 340 5817415957580319568 341 6351113449770586931 342 6933109341818514549 343 7567716083284871839 344 8259626043043412271 345 9013944527425832382 346 9836225629014030033 347 10732511145709133821 348 11709372829780164876 349 12773958248331597760 350 13934040560163662625 351 15198072539477809317 352 16575245204459685572 353 18075551438623038974 354 19709855025103314300 355 21489965549047031677 356 23428719661065565402 357 25540069235639836987 358 27839177002624049760 359 30342520277869973911 360 33068003470767760655 361 36035080102487131925 362 39264885129241214014 363 42780378430348271270 364 46606500391627187159 365 50770340591155144491 366 55301320677098888905 367 60231392616699172232 368 65595253592076003185 369 71430578922907482879 370 77778274508840758459 371 84682750406393346792 372 92192217286823955137 373 100359007663779251789 374 109239923933304798558 375 118896615434960145204 376 129395986922288408913 377 140810641024826619351 378 153219357493356500615 379 166707612246429237094 380 181368139480693469762 381 197301540371660469267 382 214616942176815250578 383 233432711861111089283 384 253877228697683208185 385 276089720656043063704 386 300221169778178181861 387 326435292162158710456 388 354909598625492356058 389 385836542609215849359 390 419424762411409664491 391 455900425408539414116 392 495508682538064623171 393 538515241979670233441 394 585208071689098511741 395 635899241212013523868 396 690926914040057945386 397 750657502672044082934 398 815487999515205191465 399 885848497810161161953 400 962204917894690105795 401 1045061955341966262959 402 1134966268825538086526 403 1232509926983419955561 404 1338334135085267353163 405 1453133263958321608959 406 1577659205408928899372 407 1712726080296951442548 408 1859215327491053290345 409 2018081204165238204046 410 2190356730303608080219 411 2377160112874516295575 412 2579701687931556976379 413 2799291421912709735867 414 3037347016657190888763 415 3295402666160168292974 416 3575118516857877923259 417 3878290887300719538827 418 4206863307452085969211 419 4562938442570192443627 420 4948790971715063148460 421 5366881496401132845500 422 5819871560817799721885 423 6310639871398187064574 424 6842299810365271390167 425 7418218345262004090432 426 8042036444418537039086 427 8717691116868671240759 428 9449439204445987874800 429 10241883063718139354862 430 11099998286109623211847 431 12029163616077266764401 432 13035193239601234769455 433 14124371628604964447680 434 15303491141292418329941 435 16579892593868240424733 436 17961509035769448983812 437 19456912978476100187189 438 21075367347279528110995 439 22826880446174133081403 440 24722265248413816294459 441 26773203349356911612297 442 28992313944142627495937 443 31393228220635931608963 444 33990669588095104000436 445 36800540194316488427719 446 39840014218765749651822 447 43127638466598356628666 448 46683440828701842219142 449 50529047216171048921651 450 54687807624183164258400 451 59184932030316835024643 452 64047636886222068359448 453 69305303019477434073797 454 74989645824771569160089 455 81134898690542811474903 456 87778010679253623894091 457 94958859556940752688878 458 102720481350970896756645 459 111109317704477841720803 460 120175482392225198086126 461 129973048466127944212785 462 140560357609911492718161 463 152000353401963951916613 464 164360940313962902380975 465 177715370410994985110076 466 192142659867346220291032 467 207728037571686800186584 468 224563428266825727051137 469 242747972853447822773556 470 262388588685212543270937 471 283600572895304089936089 472 306508252023063122913354 473 331245681454869119094049 474 357957398457231582179791 475 386799232863431896065189 476 417939179779477702298417 477 451558339002135524146794 478 487851926193054927709870 479 527030361230269606471333 480 569320439563567701607965 481 614966592835414511506786 482 664232245496483305917047 483 717401274646761405840458 484 774779580872176925287833 485 836696778425447430741784 486 903508013721292068189884 487 975595921783390182535668 488 1053372730996853739156012 489 1137282527289090461667305 490 1227803689687610037383037 491 1325451510089683861233922 492 1430781011030222395787482 493 1544389976255513087112561 494 1666922210006635109082643 495 1799071042092867747238274 496 1941583097098059001506440 497 2095262347417958885637707 498 2260974471280633242095645 499 2439651538462422016120325 500 2632297048086166063536479 501 2839991344684822044055675 502 3063897440640926030194128 503 3305267275180091843093102 504 3565448442314951419921034 505 3845891422515493835495468 506 4148157355434240506770169 507 4473926393752536152978454 508 4825006681150752175814498 509 5203344000554652008118946 510 5611032142187831102087397 511 6050324044582377293647866 512 6523643765584221826079813 513 7033599344554832651224482 514 7582996621437036498178452 515 8174854083141366588554300 516 8812418812843466339811846 517 9499183623287416397495276 518 10238905461090821050835437 519 11035625175373389192322774 520 11893688750811874972272154 521 12817770112493046897833467 522 13812895617727566431517025 523 14884470358338466160622581 524 16038306405888135863197637 525 17280653141899972801138582 526 18618229825410754932551934 527 20058260561206190761733903 528 21608511843897263273152747 529 23277332865644871011128259 530 25073698788894763058786083 531 27007257200007959035553030 532 29088377975232331418694408 533 31328206807132207345765247 534 33738722657453266624585996 535 36332799421533718548564163 536 39124272109869660079157408 537 42128007874398867700997963 538 45359982230585992822884734 539 48837360851583340511747554 540 52578587337722920401124698 541 56603477393493285495732958 542 60933319875103615616608671 543 65590985204881735665689495 544 70601041684246490473708372 545 75989880275003050460322263 546 81785848459408671912118740 547 88019393833034798804758061 548 94723218131110866689130753 549 101932442438991428190596713 550 109684784390871875796723666 551 118020748218135663139133348 552 126983828570011147518453371 553 136620729094830842988493649 554 146981596840421303904483415 555 158120273607330174894545294 556 170094565469062491700345816 557 182966531759619190564554037 558 196802794920800442583589412 559 211674872700375436270483654 560 227659534297778101921570447 561 244839182166945450212905435 562 263302261306785169979796935 563 283143697999090675618760740 564 304465370092101392783709083 565 327376611075960471721056256 566 351994750354721083494494234 567 378445692289011690008394336 568 406864536764754956838118766 569 437396244237261476729848609 570 470196348407461337703643245 571 505431719908926720158868783 572 543281384621673888701990772 573 583937400482578063903102499 574 627605796933727407668793612 575 674507581440398140808432530 576 724879817820850020674112206 577 778976781462207025910488622 578 837071196851783700226578388 579 899455563232925757981448766 580 966443574600444617409472924 581 1038371640684844951615484950 582 1115600516038700427920797882 583 1198517044834784963850851069 584 1287536029516114442638418356 585 1383102232005245661057749707 586 1485692516786523512239340377 587 1595818145823142361651735930 588 1714027235963753149970617184 589 1840907390233957600880402155 590 1977088515199645422969216648 591 2123245837435230576547279918 592 2280103133034144913024806804 593 2448436185065419305750564275 594 2629076484913059228100464651 595 2822915194538724888954254043 596 3030907387887781733615296797 597 3254076590919246876285761324 598 3493519641087019357165540788 599 3750411888538915649660869715 600 4026012762837700009106849396 601 4321671730651186565389488806 602 4638834671613730140293593032 603 4979050701436628225982356107 604 5343979473348250837601951332 605 5735398991084766275259148858 606 6155213968938388387953644225 607 6605464776812003446584107727 608 7088337010837371567868684490 609 7606171732900072604426915304 610 8161476425389964500707138148 611 8756936710673929206729438833 612 9395428888181737206822528987 613 10080033345620516922793771882 614 10814048904704090798976990409 615 11601008165916891826202098252 616 12444693921245962033636573313 617 13349156708527493764693634470 618 14318733586086595010656835980 619 15358068211721868102726153386 620 16472132315822838010669423023 621 17666248664532622649869607655 622 18946115615406492313737851704 623 20317833374996833735537433599 624 21787932075246070867623338724 625 23363401793522814272527355585 626 25051724649626518567755519224 627 26860909122148054075891732179 628 28799526736246049398308861134 629 30876751285222369932315337511 630 33102400759298092512645016786 631 35486982166750119622303028748 632 38041739445117509722753566085 633 40778704673578306050836222527 634 43710752811888222334913488726 635 46851660206521790192236076401 636 50216167120928233936765832777 637 53820044564176361141653406290 638 57680165710787565780655203325 639 61814582224320829035720699493 640 66242605818360645915146839140 641 70984895411055791307849253582 642 76063550253357220196640704848 643 81502209436706767954369818612 644 87326158213240813712054164391 645 93562441590707795523831440105 646 100239985695375943524538069887 647 107389727429356252212050847902 648 115044752984122387245548343906 649 123240445809719720216187701379 650 132014644679375355470699389204 651 141407812532115368298425325802 652 151463216821740847763186229639 653 162227122149298587487491401577 654 173748996008205520357881907691 655 186081728526661438206316241125 656 199281867151139272882119614245 657 213409867277818145662943882616 658 228530359906079186195983851677 659 244712437459892230112914583251 660 262029958999375240567088813108 661 280561876126318994347520143287 662 300392580974368801732134106735 663 321612277767195911621610044461 664 344317379526749845138184105538 665 368610931618959668086075728220 666 394603063936473603209036931458 667 422411473637646497025923967719 668 452161940488487022733164740323 669 483988876990175970054170541023 670 518035915619611726276313763294 671 554456535664812742138855344634 672 593414732301530800207096205420 673 635085730732764827219016485112 674 679656748399717122258558303476 675 727327808471851995648598223833 676 778312608035899107125334129428 677 832839444629739923268477193841 678 891152205008030133669240845003 679 953511420283106309716818874401 680 1020195391858226307920373102737 681 1091501392861590633846414743092 682 1167746950100047102212326116733 683 1249271211882129229163980822877 684 1336436407412434880140227359058 685 1429629403834715272070616403104 686 1529263367400904873779735791896 687 1635779535669265051958518685254 688 1749649108088525155127686101042 689 1871375262808178964906647418577 690 2001495308069841970841299551170 691 2140582977082828003322298401040 692 2289250875871024789410666044889 693 2448153094200037785119228733691 694 2617987990355878184125436445180 695 2799501161251798839247527975247 696 2993488610091001952319568812317 697 3200800124612802796195198919743 698 3422342879801570663328833541101 699 3659085279844718070116636438992 700 3912061055091721181667386744172 701 4182373630794403932553787445203 702 4471200785503521464608317850958 703 4779799618162307130116993427262 704 5109511844178645208445416285136 705 5461769442078731557241496646139 706 5838100673751626918426035229651 707 6240136502791459510024951266856 708 6669617437038009169867087312463 709 7128400823113188194898749492985 710 7618468622557100111186977110031 711 8141935701089900034337643095786 712 8701058664572035543932150965510 713 9298245277413522863832021339921 714 9936064501501118247334088879086 715 10617257196179519770594462821494 716 11344747522448586934674059210282 717 12121655097333102490205106432925 718 12951307947355569582238794788699 719 13837256313207363492493475863026 720 14783287361081388263793549586768 721 15793440859713138339217550119056 722 16872025885990462708912426976306 723 18023638626049968221371417488900 724 19253181343095393711316409278546 725 20565882587766928664096431972018 726 21967318731777868768633100662767 727 23463436910734828470514278594789 728 25060579467589771992986381327532 729 26765509994057428717834556564371 730 28585441073592598404163915814373 731 30528063836182203607933357980295 732 32601579442291980546458125379397 733 34814732620844270714749466273429 734 37176847394120023143566499200686 735 39697865131005169546003825228027 736 42388385079071220125096871070964 737 45259707535626493134543055416877 738 48323879828134226626137258027848 739 51593745285305593112392290789084 740 55082995391780432058504908702958 741 58806225331649984143160092567160 742 62778993139200435293193177054190 743 67017882689212934094531105794432 744 71540570773997285530645728940642 745 76365898530118365515889073743040 746 81513947494555531160000351846812 747 87006120587878690868073801404408 748 92865228340996926720519553642717 749 99115580702207462033097096466605 750 105783084782719581551613218207289 751 112895348921629763713967311645593 752 120481793475565667465805119695731 753 128573768763987900910594017603650 754 137204680628535458750756703858352 755 146410124093925071024597688946354 756 156228025648874492404660055788924 757 166698794698429717889609834765795 758 177865484774058091603209175842439 759 189773965125052688902323902093867 760 202473103354315624758635286918448 761 216014959803595011396577303202027 762 230454994437897127734495254402759 763 245852287026246533763642490746510 764 262269771466397103949733570068635 765 279774485154691806779726144323271 766 298437834359225529346717376388990 767 318335876614992510768515250425791 768 339549621224020093998447135165783 769 362165349011839324149712637259988 770 386274952564270747895044262512028 771 411976298245676370902747054853348 772 439373611381828253582473579796759 773 468577886077670192592463217287160 774 499707321232819309383973364195896 775 532887784416006676314218316592130 776 568253305364148644740403617911006 777 605946600982753614340201766446486 778 646119633842306285536089249881446 779 688934206290561449363371293747036 780 734562592433776879439351335864128 781 783188210381302595012501581104941 782 835006337298133965594375668775337 783 890224869969572538179515484154054 784 949065133751598118170929261762281 785 1011762742960550899880811325210218 786 1078568515946903189010027567196189 787 1149749448300956124276453559154538 788 1225589747853959608550965894307168 789 1306391935367199965270366343757183 790 1392478015044853664949601372700272 791 1484190719264741175717504684220917 792 1581894832195460322820208214833063 793 1685978597259717856237750339552773 794 1796855213713055631936981873687565 795 1914964427935692001908990042998898 796 2040774225384045306802830902120954 797 2174782629518922017137498868460315 798 2317519614420660266956202102676652 799 2469549138219123996089806300436174 800 2631471304909832793070226159641694 801 2803924662598267495264214896458638 802 2987588646714187361397060432771097 803 3183186177268408701717215135015557 804 3391486419787812700432827975993708 805 3613307720162371717689968795581786 806 3849520724272829889264693047898783 807 4101051693941595284519453125338970 808 4368886031464783572343148264209559 809 4654072025742728024701492283125313 810 4957724833832322007253119009866483 811 5281030712600134636368937938290988 812 5625251516063357078489603435930778 813 5991729474969497722266089083217039 814 6381892276188744456986358033793674 815 6797258460578652050762593146018802 816 7239443159133110175254440764850252 817 7710164188450451578049578458812140 818 8211248527853363257705746262145599 819 8744639201870518280689896731533159 820 9312402593251378669291342162330797 821 9916736213236548138825694959795847 822 10559976957451803313797375706615210 823 11244609877540256182046450327334025 824 11973277500500098101387995156638117 825 12748789729661512873486746945851315 826 13574134363322478459613794751456644 827 14452488269276571269207723519650794 828 15387229255814247864949572126735662 829 16381948682270573539648435447148261 830 17440464854835653156454613437112005 831 18566837256148274248833693682578939 832 19765381660168223676523973424457628 833 21040686186978698631206043907299497 834 22397628355518130192978209859545027 835 23841393195792157661738872145177985 836 25377492485883713181984358853536595 837 27011785183075212606642444149973098 838 28750499122635492861710942106190884 839 30600254062320006195900345849005654 840 32568086155401369699399578296717462 841 34661473940105092458239806298642065 842 36888365938689561749484734270273605 843 39257209965098601990002585366536849 844 41776984246148664671147774461199282 845 44457230467611669132970741035532297 846 47308088863340632640704105795711800 847 50340335472781751814207606126895543 848 53565421699848159527104077772714422 849 56995516314223282893252588042597398 850 60643550044743224067840371032387725 851 64523262923607177550281258172480697 852 68649254549813630033571299934852883 853 73037037450450852392017830211830160 854 77703093729317834145779224567024437 855 82664935203853245269399185370548180 856 87941167243544347790670057898357626 857 93551556535916451468941012034876711 858 99517103019910403930107122502610846 859 105860116240987219545614781913208229 860 112604296397704533540711786399417998 861 119774820365841287911455829399628097 862 127398433003460174204951029722118921 863 135503544058650408194916557023342936 864 144120331021148391097494752559208856 865 153280848279656387961630679119243691 866 163019142968539077059442689887945746 867 173371377910748357441997749606856342 868 184375962088386161714233964511443965 869 196073689098345832761598392538977023 870 208507884078062390979689328035698706 871 221724559615643411971995298392572989 872 235772581189643390892751655611761466 873 250703842716589313820130274769959375 874 266573452819173740811890848370147479 875 283439932464920567114307151379043468 876 301365424664221170689362022236152201 877 320415916958065544384938504607289731 878 340661477469692609296299556093361289 879 362176505340902712152495659739309791 880 385039996423068439767305331415516301 881 409335825145111572472998793765541446 882 435153043536058131842750438643178502 883 462586198438424155851132274769742191 884 491735668010816966617202862528659207 885 522708018683966631586970747569751863 886 555616383804148514466601068154238308 887 590580865271851535050423901264213586 888 627728959561832832472758296421160499 889 667196009593637126107380855232169802 890 709125684009522545320559865251613337 891 753670485509814470592914098635865900 892 800992289994312409077361400693972237 893 851262918362827517950171574874885757 894 904664742938574519697148069873444151 895 961391330595345990701411739543329934 896 1021648124793545217907944309859353625 897 1085653168861654417426323000759122720 898 1153637872999000350072002755201223193 899 1225847827623206737683110140541676091 900 1302543665841976557443272707159847881