1 1 2 1 3 2 4 3 5 4 6 6 7 8 8 11 9 14 10 18 11 24 12 30 13 38 14 48 15 60 16 75 17 92 18 114 19 140 20 170 21 208 22 252 23 304 24 366 25 439 26 526 27 626 28 744 29 884 30 1044 31 1232 32 1451 33 1704 34 1998 35 2336 36 2730 37 3182 38 3700 39 4300 40 4986 41 5772 42 6672 43 7700 44 8876 45 10212 46 11736 47 13472 48 15438 49 17673 50 20207 51 23076 52 26322 53 29988 54 34134 55 38808 56 44072 57 50008 58 56682 59 64184 60 72612 61 82070 62 92680 63 104560 64 117867 65 132760 66 149400 67 167996 68 188758 69 211920 70 237744 71 266512 72 298554 73 334202 74 373838 75 417902 76 466836 77 521152 78 581412 79 648224 80 722266 81 804254 82 895014 83 995432 84 1106448 85 1229148 86 1364684 87 1514316 88 1679436 89 1861548 90 2062332 91 2283568 92 2527224 93 2795488 94 3090672 95 3415344 96 3772302 97 4164578 98 4595497 99 5068632 100 5587941 101 6157700 102 6782508 103 7467464 104 8218050 105 9040224 106 9940482 107 10925848 108 12004014 109 13183238 110 14472520 111 15881692 112 17421288 113 19102812 114 20938728 115 22942512 116 25128802 117 27513364 118 30113388 119 32947424 120 36035460 121 39399277 122 43062326 123 47049972 124 51389664 125 56111016 126 61246128 127 66829520 128 72898539 129 79493608 130 86658156 131 94439176 132 102887352 133 112057312 134 122008020 135 132802908 136 144510534 137 157204684 138 170964720 139 185876372 140 202031792 141 219530208 142 238478472 143 258991504 144 281193114 145 305216244 146 331203986 147 359310354 148 389700618 149 422552612 150 458057418 151 496420280 152 537861748 153 582618492 154 630944928 155 683114048 156 739418676 157 800173430 158 865715640 159 936407196 160 1012636314 161 1094819200 162 1183402338 163 1278863996 164 1381716942 165 1492510896 166 1611834372 167 1740318096 168 1878637584 169 2027516127 170 2187728260 171 2360102824 172 2545527372 173 2744951508 174 2959390980 175 3189932984 176 3437740044 177 3704055432 178 3990208662 179 4297620968 180 4627811916 181 4982405054 182 5363135552 183 5771857708 184 6210551736 185 6681333176 186 7186461312 187 7728348456 188 8309570288 189 8932875856 190 9601199928 191 10317674112 192 11085639438 193 11908661186 194 12790541946 195 13735337448 196 14747372955 197 15831260100 198 16991915976 199 18234581288 200 19564842077 201 20988651832 202 22512353202 203 24142704288 204 25886904156 205 27752620428 206 29748019232 207 31881795504 208 34163207682 209 36602111520 210 39208997088 211 41995030124 212 44972091930 213 48152824560 214 51550678044 215 55179959632 216 59055887742 217 63194646016 218 67613444206 219 72330581236 220 77365509480 221 82738907560 222 88472753940 223 94590405680 224 101116682728 225 108077955074 226 115502238702 227 123419292808 228 131860724424 229 140860102094 230 150453070544 231 160677476160 232 171573498738 233 183183789772 234 195553621164 235 208731038112 236 222767025948 237 237715684480 238 253634408784 239 270584087008 240 288629304516 241 307838560850 242 328284500301 243 350044152674 244 373199192898 245 397836209188 246 424046988828 247 451928824264 248 481584828512 249 513124274136 250 546662949876 251 582323535736 252 620236002480 253 660538027296 254 703375439864 255 748902690360 256 797283338475 257 848690578940 258 903307789272 259 961329109360 260 1022960054908 261 1088418160596 262 1157933665908 263 1231750230096 264 1310125689720 265 1393332863652 266 1481660390944 267 1575413622612 268 1674915560196 269 1780507843156 270 1892551794804 271 2011429516352 272 2137545050342 273 2271325603040 274 2413222825734 275 2563714178344 276 2723304356784 277 2892526799198 278 3071945275740 279 3262155557728 280 3463787186352 281 3677505323948 282 3904012708704 283 4144051721924 284 4398406549608 285 4667905470288 286 4953423261672 287 5255883731552 288 5576262389466 289 5915589247315 290 6274951781772 291 6655498047172 292 7058439942126 293 7485056666116 294 7936698343734 295 8414789841720 296 8920834789242 297 9456419799912 298 10023218928162 299 10622998340896 300 11257621238514 301 11929053042976 302 12639366833088 303 13390749077052 304 14185505657652 305 15026068204120 306 15915000759876 307 16855006776716 308 17848936488096 309 18899794653136 310 20010748684032 311 21185137214896 312 22426479089940 313 23738482814858 314 25125056494998 315 26590318268448 316 28138607289168 317 29774495244852 318 31502798467956 319 33328590675768 320 35257216325146 321 37294304663592 322 39445784483904 323 41717899616336 324 44117225212890 325 46650684826922 326 49325568376452 327 52149550996876 328 55130712818814 329 58277559768832 330 61599045382992 331 65104593713684 332 68804123383508 333 72708072820228 334 76827426771240 335 81173744101872 336 85759186982928 337 90596551543346 338 95699299997151 339 101081594385060 340 106758331972020 341 112745182379136 342 119058626558136 343 125715997648528 344 132735523874156 345 140136373526112 346 147938702121018 347 156163701909560 348 164833653766356 349 173971981616246 350 183603309518640 351 193753521506668 352 204449824367244 353 215720813423676 354 227596541520888 355 240108591376656 356 253290151374526 357 267176095053984 358 281803064423076 359 297209557271120 360 313436018703276 361 330524937029877 362 348520944304006 363 367470921657050 364 387424109641584 365 408432223911400 366 430549576378500 367 453833202158144 368 478342992572984 369 504141834457644 370 531295756131132 371 559874080241696 372 589949583880128 373 621598666314206 374 654901524584248 375 689942337448152 376 726809457994992 377 765595615323448 378 806398125747600 379 849319113880004 380 894465744165400 381 941950463253088 382 991891253684160 383 1044411899539712 384 1099642264450062 385 1157718582604224 386 1218783763354306 387 1282987709979928 388 1350487653357030 389 1421448501068036 390 1496043202758264 391 1574453132496720 392 1656868488761571 393 1743488713015224 394 1834522927620498 395 1930190393967488 396 2030720991782760 397 2136355720457798 398 2247347223547488 399 2363960337358016 400 2486472664679517 401 2615175174961628 402 2750372831921736 403 2892385249913824 404 3041547380345354 405 3198210229413060 406 3362741608687344 407 3535526919822928 408 3716969975053308 409 3907493855087978 410 4107541805876052 411 4317578176182708 412 4538089397670216 413 4769585009361600 414 5012598728529360 415 5267689569906408 416 5535443015563842 417 5816472237528424 418 6111419375429136 419 6420956871819016 420 6745788867451104 421 7086652659273806 422 7444320223899492 423 7819599809322912 424 8213337598051818 425 8626419444528580 426 9059772690271440 427 9514368060164272 428 9991221643173644 429 10491396961462512 430 11016007131593736 431 11566217121821728 432 12143246109749598 433 12748369944504530 434 13382923718239264 435 14048304451482600 436 14745973897219506 437 15477461469127232 438 16244367298991580 439 17048365429048376 440 17891207145068328 441 18774724456121982 442 19700833727561940 443 20671539473485304 444 21688938315760740 445 22755223116811692 446 23872687293259064 447 25043729318546460 448 26270857422428136 449 27556694495721660 450 28903983209222910 451 30315591355650120 452 31794517424480438 453 33343896419314480 454 34967005928021268 455 36667272456787648 456 38448278038831368 457 40313767129648826 458 42267653800940310 459 44314029245691396 460 46457169607865232 461 48701544149998612 462 51051823773272640 463 53512889904982784 464 56089843768437970 465 58788016051881792 466 61612976992950054 467 64570546896108776 468 67666807101423228 469 70908111423235168 470 74301098078906656 471 77852702127780844 472 81570168441616572 473 85461065229203680 474 89533298137715040 475 93795124955140628 476 98255170938853200 477 102922444796158980 478 107806355344337904 479 112916728877861120 480 118263827272548420 481 123858366857313364 482 129711538084724810 483 135835026034106496 484 142241031781270599 485 148942294670689160 486 155952115527599142 487 163284380848368680 488 170953588010062578 489 178974871540712248 490 187364030493835170 491 196137556973252632 492 205312665854708748 493 214907325753789036 494 224940291291247480 495 235431136708622928 496 246400290889918368 497 257869073846139008 498 269859734722988136 499 282395491394008652 500 295500571703092708 501 309200256424417776 502 323520924009299436 503 338490097192646128 504 354136491534907056 505 370490065977544452 506 387582075494533984 507 405445125924274110 508 424113231070109760 509 443621872162137780 510 464008059774832104 511 485310398300219344 512 507569153079793387 513 530826320302077592 514 555125699777957118 515 580512970708769312 516 607035770568255480 517 634743777223703232 518 663688794425442592 519 693924840800974956 520 725508242493720156 521 758497729592408396 522 792954536503273164 523 828942506422035188 524 866528200070575684 525 905781008867852464 526 946773272711852424 527 989580402557520064 528 1034281007980508664 529 1080957029925866137 530 1129693878847905500 531 1180580578455080184 532 1233709915283278176 533 1289178594327637192 534 1347087400973949564 535 1407541369479388056 536 1470649958260559204 537 1536527232259502040 538 1605292052666617818 539 1677068274291007704 540 1751984950880444292 541 1830176548703428694 542 1911783168720101224 543 1996950777679077628 544 2085831448491052710 545 2178583610245115416 546 2275372308244838496 547 2376369474458086844 548 2481754208788830126 549 2591713071594326068 550 2706440387888915748 551 2826138563690028144 552 2951018414982034992 553 3081299509790913664 554 3217210523879722342 555 3358989610597723080 556 3506884785433633452 557 3661154325845381716 558 3822067186961226240 559 3989903433767907832 560 4164954690427823280 561 4347524607388690896 562 4537929346975391958 563 4736498088181898024 564 4943573551404657504 565 5159512543889973852 566 5384686526696167180 567 5619482204000877808 568 5864302135617374376 569 6119565373613128364 570 6385708123960974768 571 6663184434187167332 572 6952466908014716680 573 7254047448042294144 574 7568438027534726544 575 7896171492442749264 576 8237802394812564570 577 8593907858787012674 578 8965088480448969035 579 9351969262800774532 580 9755200587223297116 581 10175459222811151424 582 10613449375028091084 583 11069903775184493400 584 11545584812293719678 585 12041285708921348568 586 12557831742704186226 587 13096081515274380504 588 13656928270392868878 589 14241301263162163264 590 14850167182255183208 591 15484531627174298364 592 16145440642625249274 593 16833982312169506844 594 17551288413400006872 595 18298536136965487584 596 19076949871859498618 597 19887803059474902928 598 20732420119018877712 599 21612178446982666032 600 22528510493453833506 601 23482905918166653674 602 24476913829291480672 603 25512145108073446216 604 26590274822548798008 605 27713044733680864692 606 28882265897385952596 607 30099821366045286128 608 31367668993227598004 609 32687844345490594272 610 34062463725265972620 611 35493727308981377984 612 36983922404726244276 613 38535426833922445550 614 40150712441629813188 615 41832348740279930520 616 43583006691808845984 617 45405462633345004364 618 47302602351789210960 619 49277425312824271028 620 51333049050091712064 621 53472713720480440656 622 55699786831692775608 623 58017768148470946144 624 60430294784105849940 625 62941146484088080669 626 65554251109005594730 627 68273690324058679776 628 71103705502823101986 629 74048703853171019656 630 77113264773547258272 631 80302146448090326872 632 83620292689401825872 633 87072840038078388376 634 90665125128451877130 635 94402692330329504832 636 98291301676868876292 637 102336937089095862102 638 106545814907948927144 639 110924392745123186832 640 115479378664398095130 641 120217740705544163644 642 125146716763346834904 643 130273824834732634460 644 135606873647442509888 645 141153973684189871664 646 146923548616731211848 647 152924347164796390544 648 159165455395362363114 649 165656309478301521360 650 172406708915017669938 651 179426830257266140160 652 186727241333971129956 653 194318916004494814740 654 202213249457458003428 655 210422074074901798536 656 218957675882280452510 657 227832811605501650092 658 237060726356990878848 659 246655171973526397992 660 256630426029408972816 661 267001311549362456702 662 277783217446418471868 663 288992119710946281048 664 300644603377903797300 665 312757885300346891136 666 325349837758227753084 667 338439012932530973808 668 352044668275868294856 669 366186792811738915360 670 380886134395801652568 671 396164227973688182288 672 412043424871087063056 673 428546923153097621858 674 445698799091149645898 675 463524039777127523966 676 482048576925737807133 677 501299321907586375620 678 521304202056934024812 679 542092198299635843344 680 563693384148354587476 681 586138966113803630520 682 609461325582467003136 683 633694062213012307160 684 658872038905439993880 685 685031428398890222028 686 712209761555994427872 687 740445977393662649884 688 769780474922290000812 689 800255166857534696792 690 831913535271034105632 691 864800689248749174828 692 898963424628010463922 693 934450285886804538816 694 971311630261403206476 695 1009599694171062536528 696 1049368662031265196084 697 1090674737539797521556 698 1133576217522860808406 699 1178133568431455691828 700 1224409505581382970840 701 1272469075233436841780 702 1322379739613707290372 703 1374211464977346719272 704 1428036812822740437388 705 1483931034366690097728 706 1541972168395037564382 707 1602241142607110615840 708 1664821878576423283224 709 1729801400454294481646 710 1797269947547396996720 711 1867321090904745738688 712 1940051854054300277358 713 2015562838034146964224 714 2093958350868218319648 715 2175346541641640283792 716 2259839539336096483892 717 2347553596591115799072 718 2438609238562844614824 719 2533131417057738461920 720 2631249670124676339180 721 2733098287295253639616 722 2838816480668508772693 723 2948548562043010203556 724 3062444126306156390490 725 3180658241297706590188 726 3303351644371920696462 727 3430690945890345415544 728 3562848839885167685616 729 3700004322141205197998 730 3842342915953046625684 731 3990056905822537425200 732 4143345579370830301332 733 4302415477748509098326 734 4467480654836885070424 735 4638762945543523922460 736 4816492243505293818168 737 5000906788522831485088 738 5192253464061280526100 739 5390788105163452510172 740 5596775817133278472076 741 5810491305359467866896 742 6032219216661778848048 743 6262254492555213979280 744 6500902734840737384256 745 6748480583944896205476 746 7005316110444933034686 747 7271749220230651786536 748 7548132073769487078552 749 7834829519956865244608 750 8132219545050161660232 751 8440693737201268010624 752 8760657767120031869168 753 9092531885418709807176 754 9436751437205969795196 755 9793767394518021739488 756 10164046907194121336208 757 10548073872823975019582 758 10946349526415579113372 759 11359393050453651620928 760 11787742206041196952152 761 12231953985839871682476 762 12692605289548636265664 763 13170293622684855466288 764 13665637819457447722944 765 14179278790547956548360 766 14711880296642582374272 767 15264129748586203452752 768 15836739035058396054030 769 16430445378701339574530 770 17046012221660328855744 771 17684230141529534669316 772 18345917798728522255302 773 19031922916369030834500 774 19743123293706612993672 775 20480427854307933651632 776 21244777730101976009910 777 22037147382521980859744 778 22858545761984835743634 779 23710017506995830378128 780 24592644184209146528472 781 25507545570818378706528 782 26455880980696674540592 783 27438850635752847294444 784 28457697084018131653155 785 29513706666028058599896 786 30608211031115435685576 787 31742588705283529955660 788 32918266712383361037034 789 34136722250375685919536 790 35399484424516649146272 791 36708136039366413450976 792 38064315451582367813160 793 39469718485522752826948 794 40926100413752940607590 795 42435278004615035127624 796 43999131639092159975208 797 45619607499271792724020 798 47298719830787738169792 799 49038553281698104433760 800 50841265320336840787453 801 52709088734759168379468 802 54644334216486711676110 803 56649393031346258996080 804 58726739780287140258600 805 60878935253156105496960 806 63108629378505466936912 807 65418564272610360232044 808 67811577390974136151386 809 70290604785707425696780 810 72858684472276348950300 811 75518959909228716936980 812 78274683594624176021744 813 81129220783014947646784 814 84086053326948452569416 815 87148783647091736106224 816 90321138835210203565500 817 93606974894370135862384 818 97010281120875680618242 819 100535184632596732732064 820 104185955048494526814276 821 107967009324306829696164 822 111882916749514749887196 823 115938404110878289791320 824 120138361027998083197832 825 124487845466536613995032 826 128992089434913465965856 827 133656504870476241976376 828 138486689721341789467536 829 143488434230301399695798 830 148667727427389095894200 831 154030763837923901851708 832 159583950413055549955266 833 165333913690068577222460 834 171287507189932199471640 835 177451819059823304583312 836 183834179968597304078800 837 190442171263436775809248 838 197283633396171129191124 839 204366674628031960036496 840 211699680021888904705248 841 219291320731299627656047 842 227150563596005439212374 843 235286681053811424500820 844 243709261379106786099924 845 252428219258607978621820 846 261453806715244323456288 847 270796624391453375865704 848 280467633203511939006922 849 290478166378898267858632 850 300839941889062345288386 851 311565075290374404076192 852 322666092986427254567952 853 334155945925286246827070 854 346048023745711884318880 855 358356169386824753202096 856 371094694176141033610284 857 384278393411379577435372 858 397922562451929192775056 859 412043013336367466026724 860 426656091942940747255848 861 441778695710449549320480 862 457428291937534604460528 863 473622936678927081650368 864 490381294257812363000478 865 507722657414060754177876 866 525666968108701409274610 867 544234839005657732494502 868 563447575652424556604160 869 583327199382049982809088 870 603896470959488249666232 871 625178914996115525459944 872 647198845156948320956066 873 669981390185875150243420 874 693552520775006931487392 875 717939077305070818357056 876 743168798484616900220748 877 769270350916677841853798 878 796273359622418969101264 879 824208439552241661968316 880 853107228115756475282856 881 883002418763025508579804 882 913927795650486892817154 883 945918269426018655174380 884 979009914168675963472260 885 1013240005519745293533936 886 1048647060042902881701804 887 1085270875852443810530224 888 1123152574549762955794116 889 1162334644509521501018368 890 1202860985558223401574772 891 1244776955089256418970776 892 1288129415659823463786528 893 1332966784116602817846656 894 1379339082298432186156980 895 1427297989365812233825128 896 1476896895808571787007976 897 1528190959184630966815968 898 1581237161644440926866302 899 1636094369297371619723072 900 1692823393478063401949190 901 1751487053972555714813244 902 1812150244265858576456856 903 1874879998874541206406464 904 1939745562829879044288294 905 2006818463379127292391672 906 2076172583974577293901232 907 2147884240622204144217716 908 2222032260663931183758756 909 2298698064069821644448100 910 2377965747318861883168800 911 2459922169949425929152800 912 2544657043863010324144776 913 2632263025467403003001328 914 2722835810748102696444050 915 2816474233359538810122024 916 2913280365830457520636746 917 3013359623980741097958208 918 3116820874649916474843084 919 3223776546840688282891640 920 3334342746384004175790608 921 3448639374235428267664600 922 3566790248515965478487898 923 3688923230413948223694944 924 3815170354068169737130560 925 3945667960556129383184546 926 4080556836115047017165512 927 4219982354727209387770096 928 4364094625205235310520082 929 4513048642916990781631228 930 4667004446294154773332224 931 4826127278272834071184620 932 4990587752819155207117070 933 5160562026697427757834192 934 5336231976643279045296132 935 5517785382109110585405088 936 5705416113754325405396700 937 5899324327858026771137690 938 6099716666837298079826016 939 6306806466059744398582036 940 6520813967144713992146208 941 6741966537953527846830292 942 6970498899475131125018436 943 7206653359819848971955600 944 7450680055540384560773244 945 7702837200505845582945888 946 7963391342561432460392304 947 8232617628213472504786920 948 8510800075586746097895456 949 8798231855908528952979484 950 9095215583781475271779628 951 9402063616515397325989260 952 9719098362796163189996880 953 10046652600978343984881836 954 10385069807296901774115612 955 10734704494302126260529792 956 11095922559831210978221616 957 11469101646839314387416048 958 11854631514422687170880160 959 12252914420376471999168608 960 12664365515640103801568580 961 13089413250993867156988833 962 13528499796381110604466116 963 13982081473241885106103896 964 14450629200255375299098422 965 14934628952900436428179208 966 15434582237255848189848192 967 15951006578474558306467688 968 16484436024379224403808943 969 17035421664639784371896880 970 17604532166007602596392036 971 18192354324094965026915608 972 18799493632203341360792766 973 19426574867718909564480544 974 20074242696609360002241456 975 20743162296571975142544340 976 21434019999399430679133042 977 22147523953146698215892828 978 22884404804699861591462280 979 23645416403365604494667784 980 24431336526118599725548282 981 25242967625163046103150164 982 26081137598484173641725852 983 26946700584085686345484912 984 27840537778629852906939180 985 28763558281218304458330948 986 29716699963073573297865908 987 30700930363904026220487936 988 31717247615758127562389112 989 32766681395197930939349952 990 33850293904646363986298352 991 34969180883788257051616592 992 36124472651931196677451424 993 37317335182259177559485800 994 38548971208939706012212416 995 39820621368073495935689632 996 41133565373505217090843464 997 42489123228543930975403502 998 43888656474672904686517668 999 45333569478360453792627196 1000 46825310757116357802028548