1 1 2 1 3 3 4 2 5 6 6 6 7 11 8 11 9 22 10 23 11 37 12 42 13 65 14 76 15 111 16 127 17 182 18 217 19 294 20 351 21 471 22 562 23 734 24 881 25 1137 26 1364 27 1733 28 2074 29 2608 30 3127 31 3883 32 4644 33 5732 34 6838 35 8367 36 9963 37 12113 38 14395 39 17396 40 20614 41 24785 42 29314 43 35059 44 41360 45 49270 46 57979 47 68775 48 80753 49 95445 50 111810 51 131693 52 153914 53 180718 54 210770 55 246719 56 287122 57 335191 58 389272 59 453232 60 525319 61 610132 62 705803 63 817849 64 944284 65 1091795 66 1258317 67 1451797 68 1670268 69 1923292 70 2208930 71 2538680 72 2910914 73 3339390 74 3822903 75 4377988 76 5004075 77 5721125 78 6529521 79 7453146 80 8493878 81 9680508 82 11016676 83 12537086 84 14248046 85 16191263 86 18376479 87 20853965 88 23637923 89 26789062 90 30327410 91 34325992 92 38812557 93 43875270 94 49551332 95 55947186 96 63112427 97 71175400 98 80201243 99 90344860 100 101690859 101 114426385 102 128660475 103 144618752 104 162441000 105 182399674 106 204672149 107 229587358 108 257369827 109 288416238 110 323009174 111 361627183 112 404624169 113 452577519 114 505928790 115 565373716 116 631461649 117 705031226 118 786762726 119 877666536 120 978583399 121 1090729599 122 1215140969 123 1353281282 124 1506423126 125 1676327477 126 1864554159 127 2073219534 128 2304231710 129 2560133488 130 2843252695 131 3156642514 132 3503138343 133 3886403125 134 4309883450 135 4777971454 136 5294848606 137 5865778210 138 6495824864 139 7191290008 140 7958298573 141 8804390726 142 9736960243 143 10765022942 144 11897492470 145 13145140209 146 14518696044 147 16031020007 148 17695009704 149 19526007870 150 21539497460 151 23753767563 152 26187381714 153 28862126413 154 31800228384 155 35027620603 156 38570886022 157 42460868431 158 46729322982 159 51412907494 160 56549511630 161 62182670965 162 68357545621 163 75125797669 164 82541196530 165 90665003764 166 99561169278 167 109302283241 168 119964329560 169 131633255590 170 144399253727 171 158364012318 172 173634484485 173 190330894596 174 208579952759 175 228523690340 176 250312087734 177 274112819614 178 300103246113 179 328481171618 180 359456154004 181 393261371146 182 430144209606 183 470379353169 184 514258597314 185 562105292826 186 614263333001 187 671113087122 188 733059521930 189 800549773518 190 874060343126 191 954116492299 192 1041278460874 193 1136162862682 194 1239427886146 195 1351796900615 196 1474042582913 197 1607012976418 198 1751614492379 199 1908840673031 200 2079754040817 201 2265517844830 202 2467376707236 203 2686691690503 204 2924919707540 205 3183652248009 206 3464593543631 207 3769603347615 208 4100673832180 209 4459976872716 210 4849839672465 211 5272797030510 212 5731565732893 213 6229102339198 214 6768576361346 215 7353434201444 216 7987371178234 217 8674402272878 218 9418833115259 219 10225338293984 220 11098931416499 221 12045051846307 222 13069533999222 223 14178703439905 224 15379345663124 225 16678812594357 226 18084991113328 227 19606421174986 228 21252264421231 229 23032435218254 230 24957569814951 231 27039171779018 232 29289582209602 233 31722141259025 234 34351160027148 235 37192100015295 236 40261547508322 237 43577413035233 238 47158909128559 239 51026772181390 240 55203244673146 241 59712322019823 242 64579740597719 243 69833252542836 244 75502621075968 245 81619926606301 246 88219571142331 247 95338619409213 248 103016814503802 249 111296958200791 250 120224940278770 251 129850162790226 252 140225585926801 253 151408201510682 254 163459098791232 255 176443993123476 256 190433315544443 257 205502803397400 258 221733618169190 259 239213005583624 260 258034446970090 261 278298397302449 262 300112476058503 263 323592292850969 264 348861684697826 265 376053639958879 266 405310590057592 267 436785443850702 268 470641942929504 269 507055820139674 270 546215228973740 271 588322041578862 272 633592364409000 273 682257993006127 274 734567027690553 275 790785504717173 276 851198127837288 277 916110097712987 278 985847977552050 279 1060761745507270 280 1141225815023573 281 1227641338151406 282 1320437404200528 283 1420073625274275 284 1527041540281288 285 1641867517962982 286 1765114396876319 287 1897384745803966 288 2039322774644525 289 2191617996870572 290 2355007451202797 291 2530279816506495 292 2718277989386654 293 2919903708358372 294 3136120538697212 295 3367959069668335 296 3616520365105637 297 3882981805514567 298 4168601070460771 299 4474722706584250 300 4802782716840518 301 5154315945292464 302 5530961358422399 303 5934470349065150 304 6366712806061846 305 6829686452626958 306 7325523813403384 307 7856502716685560 308 8425054282522106 309 9033774734371670 310 9685434547746498 311 10382991735264454 312 11129602313648767 313 11928635246094138 314 12783684406148108 315 13698585384279761 316 14677429149923745 317 15724580954936479 318 16844695921103920 319 18042740301597644 320 19324009250724940 321 20694150736759599 322 22159185783095373 323 23725535362313622 324 25400043434898865 325 27190007194438266 326 29103203271728627 327 31147921746603304 328 33332995931343526 329 35667840615764808 330 38162485896121197 331 40827620176710649 332 43674628569397144 333 46715641238914104 334 49963576963287818 335 53432197481986781 336 57136156881376658 337 61091062684329335 338 65313531807777481 339 69821259222269068 340 74633081320732202 341 79769053077092905 342 85250519769184268 343 91100203677277645 344 97342285220706374 345 104002500362778882 346 111108232350076353 347 118688621131177874 348 126774667033415396 349 135399353659043060 350 144597764997616070 351 154407223439006627 352 164867422001195371 353 176020579296053250 354 187911588756367264 355 200588192608771164 356 214101150212403613 357 228504433338224008 358 243855415985676639 359 260215093541678558 360 277648296726732738 361 296223937511097919 362 316015250160533308 363 337100067128224928 364 359561090524875048 365 383486201585719938 366 408968766286707281 367 436107982409370993 368 465009223468612923 369 495784427871607992 370 528552485816052038 371 563439675568000276 372 600580098541474336 373 640116168307472957 374 682199099681950683 375 726989456734832825 376 774657702398611272 377 825384812478164778 378 879362893057673342 379 936795868325872612 380 997900173912909682 381 1062905527253662890 382 1132055705935339260 383 1205609410333758886 384 1283841137111978360 385 1367042144988892337 386 1455521434709723724 387 1549606830060474546 388 1649646076943431217 389 1756008053147242946 390 1869084000623493689 391 1989288879073713286 392 2117062747152263458 393 2252872276659561795 394 2397212300206508674 395 2550607504726503787 396 2713614165152864248 397 2886822038097723390 398 3070856303337146537 399 3266379680882356027 400 3474094604558946156 401 3694745588339046209 402 3929121659073716790 403 4178059000889497742 404 4442443677216216242 405 4723214585314786569 406 5021366501165296309 407 5337953379819937007 408 5674091760522232161 409 6030964452603383678 410 6409824342432159055 411 6811998509045725530 412 7238892479222418363 413 7691994822004719080 414 8172881903400803366 415 8683223014466975358 416 9224785682933223508 417 9799441395630119907 418 10409171530754596084 419 11056073742216455226 420 11742368583389769725 421 12470406628481866649 422 13242675866526238348 423 14061809643230985181 424 14930594912739059166 425 15851981092678247732 426 16829089270944231947 427 17865222076942365685 428 18963873951438825421 429 20128742148370648044 430 21363738187765571454 431 22673000115118584605 432 24060905270636489716 433 25532083947158968451 434 27091433623673746870 435 28744134178253862008 436 30495663750058483807 437 32351815680921036351 438 34318716188076605206 439 36402843227037491570 440 38611046177253440695 441 40950566839955917454 442 43429061361056972769 443 46054623600943998299 444 48835809543394415044 445 51781663300084768484 446 54901744281385831684 447 58206156126888507494 448 61705576943912486592 449 65411291486928914797 450 69335224802779488709 451 73489978016801130722 452 77888865760441286365 453 82545955960524247384 454 87476111465517805606 455 92695034277107622500 456 98219311836239815684 457 104066466183400171438 458 110255005415167053974 459 116804478311811163814 460 123735531529923127292 461 131069970293665561348 462 138830821949645299831 463 147042403381919725142 464 155730391622256334708 465 164921898719458988287 466 174645550172138541824 467 184931568060766989700 468 195811858151812447422 469 207320102186890985728 470 219491854597385175633 471 232364644939999146252 472 245978085260642549418 473 260373983770513023625 474 275596464008067051148 475 291692090965451540081 476 308710003318852979457 477 326702053342804290767 478 345722953613250187169 479 365830432188184131798 480 387085395335693959997 481 409552099614859224752 482 433298332344246738626 483 458395602388522864672 484 484919340262884344996 485 512949109620026334736 486 542568829084543915108 487 573867006643512615634 488 606936985523844409565 489 641877203919766211892 490 678791467467494297514 491 717789236996487820663 492 758985930421903845093 493 802503241485999887079 494 848469474182119315662 495 897019895760651372650 496 948297107121477674615 497 1002451433698314382891 498 1059641335612646069156 499 1120033840424189343243 500 1183804997231629656631 501 1251140355688830801786 502 1322235468669755338188 503 1397296422403675667239 504 1476540392797495934076 505 1560196232042718751583 506 1648505084212332318239 507 1741721034242246922842 508 1840111788996712024638 509 1943959395132343525806 510 2053560992460963127239 511 2169229607870651908771 512 2291294988513694689750 513 2420104479692370280892 514 2556023946168607147548 515 2699438742729050155698 516 2850754732759046251042 517 3010399361089115339766 518 3178822779906553274782 519 3356499034461767795624 520 3543927307414392540807 521 3741633229051715724597 522 3950170252291900506533 523 4170121100247447496364 524 4402099285345893896211 525 4646750708369414610254 526 4904755336514136917062 527 5176828969464055347297 528 5463725092705904004583 529 5766236827764057165710 530 6085198978731881472052 531 6421490185518041446817 532 6776035183361778076810 533 7149807179835096319157 534 7543830349094321204416 535 7959182455463495060426 536 8396997606355121176262 537 8858469147545886764471 538 9344852701094602083321 539 9857469359931892931230 540 10397709039733774992783 541 10967034003203866816769 542 11566982557749482153349 543 12199172942862021209282 544 12865307408613718199806 545 13567176502865147241452 546 14306663569082089918475 547 15085749473746950273481 548 15906517565816356095151 549 16771158888716917236810 550 17681977647957657171244 551 18641396956484027718904 552 19651964861560798450656 553 20716360677078769219626 554 21837401625872284998790 555 23018049817861527020694 556 24261419569506956142366 557 25570785092470982745845 558 26949588557986091145532 559 28401448567081806293520 560 29930169034304997375912 561 31539748517534788415573 562 33234390002798277322819 563 35018511179345672966104 564 36896755215313459331482 565 38874002072118251607274 566 40955380369498899836991 567 43146279842480123963686 568 45452364403947961041214 569 47879585857509280984766 570 50434198276301039434271 571 53122773096112442703194 572 55952214940684637543210 573 58929778231559609982095 574 62063084602788178660790 575 65360141177222996917497 576 68829359727422958759498 577 72479576782625347426642 578 76320074707827385352340 579 80360603821573285986858 580 84611405581832457968022 581 89083236912150366733962 582 93787395701163216374183 583 98735747553728374040082 584 103940753830864860856362 585 109415501063354075526400 586 115173731780735268012036 587 121229876847718867053547 588 127599089354772443666186 589 134297280162700885534552 590 141341155153523260515539 591 148748254295947254685442 592 156536992583870391454009 593 164726702965429545020304 594 173337681327790105475690 595 182391233665223901101504 596 191909725503126736324787 597 201916633716430612000555 598 212436600823285836843820 599 223495491904330463005965 600 235120454237485152674762 601 247339979811494402185141 602 260183970818134533977427 603 273683808300346170503756 604 287872424067201399531142 605 302784376068234070592575 606 318455927350136895462369 607 334925128804967765298594 608 352231905846171437641623 609 370418149239635121507386 610 389527810240710403023653 611 409607000284088063494532 612 430704095393533558719850 613 452869845579770590509654 614 476157489411181980647614 615 500622874048902326661185 616 526324580950368501393833 617 553324057558242911664292 618 581685755200070674407577 619 611477273543161113799190 620 642769511853426115332829 621 675636827432673847437800 622 710157201508731946467736 623 746412412985554790121363 624 784488220355812052915365 625 824474552218651281895764 626 866465706735967254449934 627 910560560508545428310174 628 956862787239211693126250 629 1005481086706444023236138 630 1056529424452615538029356 631 1110127282756127803271398 632 1166399923332178098956578 633 1225478662381265173313086 634 1287501158474613902297180 635 1352611713949868222163247 636 1420961590354886502149681 637 1492709338672020244137729 638 1568021144913967921621614 639 1647071191887824305925930 640 1730042037776699568556517 641 1817125012405434521583525 642 1908520631903551928382140 643 2004439032708041010792180 644 2105100425688863564135428 645 2210735571422555799461454 646 2321586277473089241619330 647 2437905918795437282694855 648 2559959982204403700934967 649 2688026636122167742636560 650 2822397326638257774642946 651 2963377401202047142890142 652 3111286761081103736109983 653 3266460544021513541882185 654 3429249838352355767641536 655 3600022430096685764123630 656 3779163584450106617393662 657 3967076863326623608038265 658 4164184980462726059773889 659 4370930695928801486916836 660 4587777751680632804104342 661 4815211850162621063287558 662 5053741677750302411594685 663 5303899975220611126331552 664 5566244657206449059967584 665 5841359983016339171892691 666 6129857780960152214469826 667 6432378728770877768000961 668 6749593692464668930576884 669 7082205126456660498471890 670 7430948537494335173309370 671 7796594015473395954651437 672 8179947833937392614225365 673 8581854123595179294410062 674 9003196621918617659850425 675 9444900502447261353569382 676 9907934287147213220392745 677 10393311845769130943644608 678 10902094485863043236111788 679 11435393137740988789970734 680 11994370638383568661675085 681 12580244118957662316500480 682 13194287500310243320766518 683 13837834101514595801463050 684 14512279366235800356613700 685 15219083712436487835928210 686 15959775510627651386910766 687 16735954196668933843802807 688 17549293524800241727535428 689 18401544967434581004053946 690 19294541267913586216165108 691 20230200153326796851604408 692 21210528214162047036692743 693 22237624958508790540642649 694 23313687048197927487954728 695 24441012725274595935307634 696 25622006436858376845239043 697 26859183667520514100840954 698 28155175987962912945267968 699 29512736329925170065371482 700 30934744496899301063036384 701 32424212921444024812326239 702 33984292679543353646001082 703 35618279773741810423606971 704 37329621696442355694088402 705 39121924286121061311403054 706 40998958888868783552364057 707 42964669839123780860997597 708 45023182273119677038612644 709 47178810290118340435965312 710 49436065476163954421257658 711 51799665806737347803163404 712 54274544944364864325382044 713 56865861948983054022437766 714 59579011418546710763015052 715 62419634079226053498466703 716 65393627844238944259843147 717 68507159362341143925542089 718 71766676076714704242109875 719 75178918817098649757257784 720 78750934947743704255416066 721 82490092096012518447544144 722 86404092486208851875532545 723 90500987905603840256997403 724 94789195329418188423440636 725 99277513234058792802124614 726 103975138627732499330242816 727 108891684830265092113124210 728 114037200033816592475573341 729 119422186679066586733282860 730 125057621681350911899734293 731 130954977544303286772417272 732 137126244398514160089134278 733 143583953005994205367703229 734 150341198771246757809744774 735 157411666803245802681597818 736 164809658072698999738302450 737 172550116712700009530401946 738 180648658511031881389557860 739 189121600646356956348746196 740 197985992720770315985670772 741 207259649145434076159928537 742 216961182936345881479209945 743 227110040981820775961047562 744 237726540843707566206496762 745 248831909159192555792077694 746 260448321710603862495689951 747 272598945235789145136625150 748 285307981052331998292948804 749 298600710574383291245136375 750 312503542801723263931572654 751 327044063866557928165250416 752 342251088724556388084890817 753 358154715082927357269015578 754 374786379659517708686003584 755 392178916873640742660075391 756 410366620070727542058359363 757 429385305390084278604613276 758 449272378386646593555959379 759 470066903525310144475783480 760 491809676668270666276820652 761 514543300684029720949166898 762 538312264308848122122795855 763 563163024400225839187211237 764 589144091724412435142308852 765 616306120429364996045314866 766 644702001357325599328869368 767 674386959361264642036284592 768 705418654792554410192405170 769 737857289338021635493876338 770 771765716388044912734443134 771 807209556128909724921136225 772 844257315556589326414352898 773 882980513621485521908843990 774 923453811718100045354664131 775 965755149746852642931171896 776 1009965887980226355712549114 777 1056170954979610828076721834 778 1104459001814757235500419679 779 1154922562852963986882079748 780 1207658223391288574319815179 781 1262766794421377401356125875 782 1320353494823374961119515529 783 1380528141302842529030236560 784 1443405346392244463144111256 785 1509104724857288998588422327 786 1577751108856867420521225264 787 1649474772225418662598819668 788 1724411664255909214195372885 789 1802703653383157335591284726 790 1884498781177582608509161465 791 1969951527082566283326536926 792 2059223084340039576463969126 793 2152481647573704565488672065 794 2249902712511901867925263422 795 2351669388358736602964987313 796 2457972723335968038737944090 797 2569012043946711940860103012 798 2684995308527298434166350682 799 2806139475684265050946739228 800 2932670888230283606590471066 801 3064825673265707869325371110 802 3202850159070908947300363258 803 3347001309509875468232210842 804 3497547176665843774459332788 805 3654767372467638774271488883 806 3818953560087661946359431985 807 3990409965933181195482870048 808 4169453913076973643583851221 809 4356416377017106114406433312 810 4551642564682362175191736850 811 4755492517646802770766124823 812 4968341740546202032376919718 813 5190581855739569122970316860 814 5422621285290971466047887648 815 5664885961401100650355121555 816 5917820066453014331657120585 817 6181886803894756023042510674 818 6457569201219791410685833896 819 6745370946368818945943506900 820 7045817258918272223427031182 821 7359455797488132890169389832 822 7686857604847256696119980817 823 8028618092266755701819524725 824 8385358064721713345071479924 825 8757724788619273108189944558 826 9146393103785377319343941302 827 9552066581526034291465848056 828 9975478730638110849936663974 829 10417394253334532387552672432 830 10878610353113186385287959095 831 11359958096695473845022525650 832 11862303832230607113928474658 833 12386550666065681362591156601 834 12933640000457922532765368736 835 13504553134717280148469368766 836 14100312932350650600230960181 837 14721985556899218094870418282 838 15370682279250821387170513686 839 16047561359338537174948793890 840 16753830005235002895535819694 841 17490746412791060262101000175 842 18259621889074199628509104891 843 19061823063011867599255722271 844 19898774186760874449479396802 845 20771959531485049187580825622 846 21682925881349504779008308020 847 22633285129712983154101493867 848 23624716981636831057226626490 849 24658971767015394004756287232 850 25737873368781455835352985081 851 26863322270840721367830801516 852 28037298730550901640449725372 853 29261866080776546651778102482 854 30539174166726093643781301508 855 31871462923009564130923578777 856 33261066096545548962634844927 857 34710415121195718906020401264 858 36222043150211397831711368728 859 37798589252845315912210438396 860 39442802781705359535747816601 861 41157547917716149206485893657 862 42945808399796784895692530194 863 44810692446674110092968062040 864 46755437878513683051409192816 865 48783417446385334952616681689 866 50898144377865000686175926244 867 53103278147434689118813509817 868 55402630480651002805435012330 869 57800171601440236727432604960 870 60300036732212272799257174945 871 62906532856902641905405425129 872 65624145757414012683970647346 873 68457547334377313246932961636 874 71411603223544496682686512835 875 74491380719608128388952881540 876 77702157019667085009919598641 877 81049427799077655117323730400 878 84538916132888326662470668046 879 88176581776616191251320670160 880 91968630820619549870816835735 881 95921525732923619426207494511 882 100041995805893545946912805614 883 104337048022797169421978555811 884 108813978360881168050552470716 885 113480383548281874703224914080 886 118344173292720591777512023594 887 123413583000684088540868418174 888 128697187006470592040462431736 889 134203912331289685847109193528 890 139943052993339283761771340494 891 145924284890652553236875427903 892 152157681279301885442856154971 893 158653728870483009946780120764 894 165423344570860721618577734386 895 172477892891565025327437984962 896 179829204052154059335502916741 897 187489592806944257689792705156 898 195471878022110378452921220886 899 203789403033124719570670115047 900 212456056813187463890168540537 901 221486295984555659665127610376 902 230895167705847705684048912449 903 240698333469751392179664212004 904 250912093846826426121049681996 905 261553414212546424421389107484 906 272639951496089040103556156734 907 284190081990947616285511176265 908 296222930268910094669298644956 909 308758399240634698844198631172 910 321817201407641339709404963505 911 335420891352349567351514515463 912 349591899514509504213143226446 913 364353567304321851993398944433 914 379730183604394638783411925128 915 395747022714782236190831698996 916 412430383797350237354539840340 917 429807631877967062721527217552 918 447907240467179031222636957781 919 466758835862454370257494713544 920 486393243197407499534124227273 921 506842534306028068717316176583 922 528140077472448185357080183738 923 550320589139592742077744210366 924 573420187652763898898254298845 925 597476449117235535974938559856 926 622528465451851990145779985494 927 648616904723879512075469991575 928 675784073853506035443800318441 929 704073983779885614551270916000 930 733532417184017232783084698018 931 764206998867513657354375085969 932 796147268889974408922654606189 933 829404758571728046294838218187 934 864033069472652681081889547712 935 900087955462141364202455286830 936 937627407999529820301628554786 937 976711744748991360910398284196 938 1017403701657485195445854599597 939 1059768528629386086834948721822 940 1103874088936360432914944889030 941 1149790962506476539479130576606 942 1197592553241856810406602660408 943 1247355200520011780119691646254 944 1299158295039727803856106650056 945 1353084399178652612960866963835 946 1409219372035898044447783443502 947 1467652499339724788736970974695 948 1528476628407025930198842470539 949 1591788308348580124555668332939 950 1657687935721210141058475751916 951 1726279905835783112788228113230 952 1797672769937705491679958132076 953 1871979398484953688641312846019 954 1949317150756991507287236690632 955 2029808051036944670748054042592 956 2113578971618351150773026833121 957 2200761822897503481958440927440 958 2291493750822034070353226721646 959 2385917341976820810381609780044 960 2484180836598663273980708407449 961 2586438349822389146045711348591 962 2692850101472217193686759731875 963 2803582654724253844259235631663 964 2918809163978020376880886462186 965 3038709632287862456916693699761 966 3163471178718031054909042925162 967 3293288315999149613603704217134 968 3428363238877705821674342453958 969 3568906123565175366572235864730 970 3715135438708368597151063058213 971 3867278268318680618813975491094 972 4025570647114048294863216757699 973 4190257908744710860878036315042 974 4361595047391218377352019200776 975 4539847093241718270157236595377 976 4725289502374213738833606642992 977 4918208561589462306550544177623 978 5118901808760260497215607321785 979 5327678469284326267251836809982 980 5544859909249588093727472600674 981 5770780105943756595685167216336 982 6005786136363284517982581336463 983 6250238684401607448540903332778 984 6504512567421541680383034968692 985 6768997282943348600205410909260 986 7044097576206843417042857044713 987 7330234029394541557117631029511 988 7627843673331728713251534703644 989 7937380622510084622808596369712 990 8259316734312557603812818698150 991 8594142293350216199612336963494 992 8942366721855206555329602919892 993 9304519317109426762841259329177 994 9681150016924439775139749117018 995 10072830194226262669255496353159 996 10480153481837273861948003444636 997 10903736628588422988742773405706 998 11344220387936424313775441359898 999 11802270440304591965562063611922 1000 12278578350410577124406099033772