16 1 17 1 18 2 19 3 20 5 21 7 22 11 23 15 24 22 25 25 26 36 27 46 28 60 29 76 30 97 31 121 32 152 33 189 34 232 35 286 36 364 37 446 38 544 39 679 40 819 41 1017 42 1231 43 1516 44 1822 45 2244 46 2691 47 3288 48 3936 49 4750 50 5661 51 6848 52 8092 53 9736 54 11496 55 13724 56 16154 57 19233 58 22558 59 26684 60 31247 61 36820 62 43014 63 50460 64 58867 65 68861 66 80129 67 93438 68 108491 69 126189 70 146305 71 169641 72 196332 73 227182 74 262579 75 303011 76 349614 77 402643 78 463961 79 533254 80 613364 81 703567 82 808062 83 925260 84 1060774 85 1212782 86 1388324 87 1584375 88 1810709 89 2063429 90 2354651 91 2678918 92 3052371 93 3467893 94 3945309 95 4475867 96 5084400 97 5760809 98 6534749 99 7394291 100 8375990 101 9466309 102 10708266 103 12087893 104 13655414 105 15397786 106 17372406 107 19566804 108 22048944 109 24807814 110 27921662 111 31383392 112 35281011 113 39615410 114 44486967 115 49903612 116 55979316 117 62736671 118 70301166 119 78714687 120 88117416 121 98574078 122 110240608 123 123216407 124 137666433 125 153736930 126 171610364 127 191481211 128 213550767 129 238083112 130 265289833 131 295525130 132 329021231 133 366224669 134 407395897 135 453110395 136 503642071 137 559722846 138 621659672 139 690357817 140 766162821 141 850199717 142 942846539 143 1045498326 144 1158590721 145 1283805205 146 1421656281 147 1574200181 148 1742018018 149 1927592945 150 2131638034 151 2357118996 152 2604898361 153 2878516921 154 3179030498 155 3510656297 156 3874707593 157 4276141126 158 4716625198 159 5202016921 160 5734371435 161 6320573473 162 6963236767 163 7670401689 164 8445364517 165 9297498719 166 10230962039 167 11256686291 168 12379879701 169 13613211324 170 14963246620 171 16444700396 172 18065731824 173 19843344308 174 21787765456 175 23918637218 176 26248641122 177 28800419886 178 31589688665 179 34642567945 180 37978416005 181 41627274698 182 45612965885 183 49970087519 184 54727770663 185 59925777241 186 65599690947 187 71795270199 188 78555736741 189 85933675680 190 93981487723 191 102759752783 192 112331637031 193 122766863828 194 134141504611 195 146535893241 196 160041312009 197 174750255334 198 190771955198 199 208213269086 200 227204364993 201 247868612258 202 270360978633 203 294824066845 204 321441709610 205 350378947867 206 381853427922 207 416056336842 208 453244753589 209 493640297549 210 537545932341 211 585219090505 212 637015902862 213 693235415564 214 754295795206 215 820544842476 216 892472275503 217 970483055311 218 1055149784388 219 1146944272759 220 1246534993777 221 1354471892972 222 1471534045811 223 1598363079542 224 1735865524615 225 1884790188980 226 2046190613369 227 2220940949786 228 2410263787931 229 2615180115189 230 2837106889000 231 3077236555641 232 3337209750959 233 3618419149806 234 3922762031204 235 4251865019854 236 4607920176073 237 4992827084152 238 5409115740875 239 5859003916324 240 6345409382087 241 6870920712285 242 7438899890523 243 8052366984042 244 8715193299011 245 9430900998349 246 10203944375067 247 11038428518380 248 11939476170897 249 12911869917899 250 13961496337344 251 15093923641481 252 16315914131521 253 17633946411828 254 19055784137709 255 20588959990431 256 22242383809193 257 24024808442286 258 25946454648483 259 28017483638358 260 30249617450721 261 32654645961705 262 35246005218510 263 38037362925375 264 41044119131133 265 44282105757227 266 47768966914245 267 51523027847936 268 55564499039496 269 59914576249443 270 64596404556142 271 69634476001148 272 75055293949271 273 80887142591822 274 87160358278708 275 93907576294764 276 101163521145702 277 108965818841717 278 117354206427663 279 126372030969772 280 136064758353864 281 146482292293209 282 157676645153537 283 169705217168519 284 182627506240321 285 196509496588859 286 211419226207529 287 227432487924154 288 244627086760257 289 263090017947513 290 282910235412586 291 304187525657229 292 327023571728134 293 351532760571174 294 377831306387451 295 406050231605476 296 436322344181948 297 468797639057601 298 503627842602997 299 540984554021659 300 581041099413611 301 623993671066900 302 670040220118556 303 719404926677748 304 772313818294126 305 829022914775007 306 889790246642492 307 954908009633182 308 1024670715832646 309 1099411687654791 310 1179466970514916 311 1265216590077786 312 1357043916745008 313 1455381996787538 314 1560668063448526 315 1673395338620963 316 1794062354173003 317 1923230608578295 318 2061468370798743 319 2209414538928248 320 2367716708437582 321 2537101543337562 322 2718306790881750 323 2912158561275493 324 3119497084408152 325 3341261120266179 326 3578407307720975 327 3832001977953247 328 4103133967245048 329 4393014039043345 330 4702881096601283 331 5034109331202104 332 5388107952039078 333 5766436082068270 334 6170696077753427 335 6602656211718063 336 7064137882931475 337 7557145854736718 338 8083749785053644 339 8646221761858724 340 9246912731655969 341 9888396900654976 342 10573343794663940 343 11304668919866271 344 12085402501720993 345 12918845566857360 346 13808436526557244 347 14757911718326513 348 15771171358562734 349 16852443213182494 350 18006149725367809 351 19237073286024611 352 20550226696405239 353 21951018159224853 354 23445127590226129 355 25038669122708284 356 26738076255381701 357 28550259269260169 358 30482502596688507 359 32542614155311757 360 34738838903486062 361 37079996611756613 362 39575416066821404 363 42235057340137688 364 45069471749759664 365 48089904132158044 366 51308284300244654 367 54737304266279389 368 58390447655207295 369 62282036198735214 370 66427304373772426 371 70842408771711711 372 75544556016816968 373 80551968057441302 374 85884072231022263 375 91561414698317148 376 97605922575299027 377 104040756909976230 378 110890657798781100 379 118181727595113015 380 125941870735392508 381 134200497118072812 382 142989069809061818 383 152340717296990771 384 162290903213712376 385 172876935764178142 386 184138774751319217 387 196118425255300184 388 208860898615194999 389 222413476627864231 390 236826844491456959 391 252154210892088309 392 268452631832487186 393 285781971311287553 394 304206436915522765 395 323793364329213428 396 344614986450901817 397 366747025048624544 398 390270716622376495 399 415271193073198975 400 441839788995388925 401 470072192837131706 402 500071061862803874 403 531943924642948112 404 565806130400530430 405 601778483767248818 406 639990557586310716 407 680578039429964120 408 723686437282108806 409 769468118769811925 410 818086440492328896 411 869712459860446968 412 924529519667096382 413 982729613591517078 414 1044518458966662564 415 1110111497144361525 416 1179739486782908245 417 1253644122467989329 418 1332084182820405871 419 1415330750486746272 420 1503673948151816143 421 1597417747223897521 422 1696887325472394211 423 1802423452301708233 424 1914390500687777397 425 2033170401410392857 426 2159171342235686054 427 2292821285922053894 428 2434577386403571963 429 2584919072035025784 430 2744358208746252214 431 2913431752655087060 432 3092712686164226994 433 3282802253151471381 434 3484341692704229660 435 3698004074704077257 436 3924506850649466274 437 4164603318509175605 438 4419096007853393395 439 4688827809803112129 440 4974696206217404835 441 5277644114788177610 442 5598674968670833808 443 5938843335834003656 444 6299270846197025150 445 6681136661828413666 446 7085694243959189511 447 7514261762763257692 448 7968239684265742685 449 8449101230777025476 450 8958410761135822200 451 9497814407449898917 452 10069059208288825038 453 10673984074392920955 454 11314539624653743536 455 11992779653482686624 456 12710881602537489342 457 13471138732996513225 458 14275981155986805995 459 15127968938200480932 460 16029813591058528778 461 16984372377477256615 462 17994670147626279739 463 19063895141592958940 464 20195421037293217717 465 21392804590001661070 466 22659807738952342730 467 24000397462517950798 468 25418767763869091794 469 26919342169763891779 470 28506795399553703938 471 30186058980085179330 472 31962342366852013602 473 33841142211565607192 474 35828262685961078891 475 37929828983363287870 476 40152306564730323805 477 42502519549187022133 478 44987668572470991395 479 47615354784701992627 480 50393595977057489316 481 53330856978150586228 482 56436063685746720625 483 59718640725024391602 484 63188522974205317911 485 66856201444895776694 486 70732731869892328497 487 74829789834616236886 488 79159675960892691521 489 83735381427047155281 490 88570589246154438651 491 93679751408115592530 492 99078085716741308913 493 104781665890185389200 494 110807413407531540173 495 117173202010686186474 496 123897843960027484770 497 131001210517845457862 498 138504212002171270211 499 146428935929615454698 500 154798620234798602791 501 163637810898357332226 502 172972327673694151685 503 182829443162060084244 504 193237840374689254073 505 204227815351159583360 506 215831225899845528214 507 228081720003840440234 508 241014675053429740263 509 254667454463222449856 510 269079336740360396665 511 284291802864723529745 512 300348454563043871859 513 317295335193567506433 514 335180836615343030008 515 354056056497233424056 516 373974693223005520857 517 394993442708389886127 518 417171880873179797156 519 440572903239941576833 520 465262594551388434227 521 491310714641747298687 522 518790554907023699062 523 547779474098019441827 524 578358741493728386051 525 610614126488056550525 526 644635728452138883965 527 680518624206890943937 528 718362684758805129965 529 758273284933381192016 530 800361107423313496874 531 844742919085058450171 532 891541362962997521808 533 940885805994770285742 534 992912120009128695024 535 1047763605767576618785 536 1105590764313323356121 537 1166552302520779452299 538 1230814896550071621227 539 1298554284331583959796 540 1369955023373149202522 541 1445211675790149791875 542 1524528563282555521868 543 1608121050580658912003 544 1696215300982431072505 545 1789049664337759059352 546 1886874437252245484218 547 1989953361936735923603 548 2098563396002486059286 549 2212996328750244734509 550 2333558566312482191590 551 2460572872244048010089 552 2594378174790913446310 553 2735331438820436770975 554 2883807503121460625463 555 3040201091010517636821 556 3204926686770553025717 557 3378420692519924367030 558 3561141354280434700198 559 3753571072943348827372 560 3956216392029854937532 561 4169610470840633556546 562 4394313147594862631211 563 4630913583196723002621 564 4880030415359447015809 565 5142314581616890065959 566 5418449582098208292194 567 5709154490797031868550 568 6015184346925493793270 569 6337333363743692219071 570 6676435470904009557226 571 7033367730518217163000 572 7409051055719949270359 573 7804453843971771074446 574 8220592899990572269247 575 8658537296823010136064 576 9119409534651169004169 577 9604389640496244987626 578 10114716597980067465925 579 10651692697157052480525 580 11216685274277023688774 581 11811131323730843871642 582 12436539591089806923619 583 13094495459905443059909 584 13786663446068261217313 585 14514792372836481649711 586 15280718319522968865503 587 16086370099142711673407 588 16933772720072806992393 589 17825053181521468328045 590 18762444512695769778567 591 19748291902611236934485 592 20785057387910922448327 593 21875326334665024661721 594 23021812852899847981417 595 24227366649743441111615 596 25494979256485124456190 597 26827791273949389412678 598 28229099506010190145355 599 29702364620299353140424 600 31251219291167479059680 601 32879476300927006030050 602 34591137804669712880733 603 36390403900163835464316 604 38281683137539335862281 605 40269601588713015534651 606 42359014735923852255181 607 44555017075425507260380 608 46862955531090268190220 609 49288439630803217818346 610 51837356604157616192378 611 54515882174900527166959 612 57330497515942448862602 613 60288000706192454564394 614 63395525730794652399426 615 66660554657083243118915 616 70090938884484221169443 617 73694912100704987360856 618 77481114002750428910675 619 81458604102811107193375 620 85636888160731721366527 621 90025932917416495734552 622 94636195498872484890626 623 99478639165407939119503 624 104564765969153463353051 625 109906633618334796674109 626 115516891692719202450693 627 121408799735570494053174 628 127596267356770031143628 629 134093873678854818151605 630 140916911683552785161933 631 148081409155436032661984 632 155604177656344710622242 633 163502835127823077722022 634 171795859908084072274268 635 180502615175543347170483 636 189643408456061182647065 637 199239518112509945812203 638 209313258824325993135261 639 219888010354572762096490 640 230988289522165954606310 641 242639781505882615990229 642 254869418869119238769832 643 267705415693701490524423 644 281177354260572414719680 645 295316222341316015271359 646 310154508184016860250538 647 325726241331245472512063 648 342067096610432193792020 649 359214438891095386896944 650 377207436831262476418364 651 396087112037168370196503 652 415896463375352672810056 653 436680521051878138224871 654 458486482359917365261207 655 481363771258038860871532 656 505364186489299559761581 657 530541967304484769810181 658 556953954958703926595141 659 584659665301153287080751 660 613721464731633683583727 661 644204650460281760272690 662 676177642086502255539875 663 709712070424468514402799 664 744882985955715687850741 665 781768957215363740783275 666 820452297462407706954132 667 861019173734289831712608 668 903559853180814698293689 669 948168824015303733354822 670 994945063066229160983501 671 1043992169988730646811952 672 1095418657706188384970070 673 1149338101392599824698722 674 1205869453601143185108278 675 1265137209691454366306550 676 1327271749580041178578958 677 1392409521462724114112145 678 1460693412267233600805613 679 1532272951718284618127733 680 1607304713732229717718829 681 1685952543084402649120053 682 1768387990155981049592944 683 1854790562698858982031782 684 1945348196531090242372654 685 2040257535149541182673024 686 2139724439168707478981169 687 2243964296813196426630780 688 2353202575112871336337635 689 2467675164611511951809493 690 2587628975563946651848081 691 2713322320533693515568171 692 2845025559092750392604878 693 2983021522344120981287821 694 3127606209898573932439071 695 3279089260757729414947797 696 3437794706641679265374379 697 3604061494100622157210333 698 3778244298588937352056280 699 3960714103147900012277570 700 4151859077974502709832718 701 4352085221530754186877216 702 4561817310735035026165404 703 4781499610915654320308024 704 5011596902168141742093287 705 5252595265178535732198285 706 5505003189738256340739074 707 5769352444127213471310778 708 6046199272268973853868060 709 6336125355081963762649661 710 6639739103288364746326601 711 6957676719926107149697121 712 7290603596405170313880466 713 7639215486221282361432273 714 8004240012482284243927431 715 8386437963787690271725409 716 8786604922136098654918938 717 9205572692934034864542541 718 9644211062940566007682635 719 10103429377456043841555753 720 10584178438776465606608624 721 11087452244786848315317432 722 11614290039284380481130263 723 12165778227478168293942745 724 12743052590507696349807946 725 13347300394731787545374912 726 13979762783822578671445394 727 14641737100222508344820549 728 15334579469345905184550758 729 16059707353202835813196382 730 16818602342491040564008309 731 17612812964141286025442145 732 18443957698451671541010892 733 19313728064204398616787497 734 20223891879485833771631154 735 21176296650079648423906675 736 22172873094240977291474158 737 23215638862293339278857148 738 24306702347399859495899161 739 25448266766690425045867025 740 26642634282010723775577048 741 27892210475504629067606202 742 29199508806429086027032557 743 30567155516925430444845951 744 31997894453292875518214376 745 33494592440713361575742541 746 35060244499890425362899348 747 36697979732770951396522756 748 38411066968191667011841163 749 40202921204186964305916815 750 42077109719275784147638173 751 44037359120763746519938179 752 46087561961564161917284686 753 48231784448039454311782524 754 50474273605799032462136200 755 52819465705087738803565360 756 55271994022879329248108764 757 57836698048635307816612421 758 60518631894241953038292295 759 63323074348164151828635886 760 66255537989369888213810166 761 69321780163528445561627584 762 72527812862090167084120311 763 75879914700228620025493242 764 79384641627714041715787597 765 83048839994852084489944842 766 86879658167743163440163073 767 90884560775531966048420446 768 95071341309136343429735611 769 99448137650742871449153267 770 104023445742168596531176243 771 108806136505760716504369269 772 113805470676239464955817658 773 119031117231052323049205713 774 124493169487939169944894067 775 130202165172351375480825063 776 136169103892105808533724385 777 142405468979832736407707645 778 148923246466011984014142719 779 155734948845563906394854685 780 162853635681365626015127342 781 170292939456137092182895869 782 178067087950306963185032443 783 186190932353326253102369322 784 194679971572518334550627978 785 203550382791991033684994386 786 212819047883026022587090023 787 222503586613852969897722308 788 232622385347248392244453798 789 243194633120778813800978728 790 254240352833707153455457102 791 265780440434911208994226966 792 277836698819046275669672148 793 290431880378351964793055330 794 303589723847443440826609780 795 317335000495710508681676567 796 331693554181150578770361961 797 346692351482226836461105879 798 362359525244065236540912425 799 378724428972475375541474704 800 395817684180673948445528179 801 413671239393980479769927940 802 432318421632200616996423422 803 451794000401305524429797610 804 472134243675868172940312163 805 493376987284066421932655848 806 515561695786358465018167986 807 538729537692527203712105560 808 562923451667187859008939815 809 588188228052613300611780585 810 614570580869066208540198135 811 642119236154834697769114193 812 670885010269882407925894455 813 700920905605324877710213731 814 732282195742816689757797309 815 765026529129659179266360676 816 799214021693927089334996273 817 834907369128908433532235311 818 872171947615602884635325244 819 911075935411425545021905908 820 951690422387533671702418449 821 994089541672143036302213198 822 1038350588770720207142944093 823 1084554164073939802185173655 824 1132784302394308558447967139 825 1183128627213385208862727770 826 1235678491539392685009348492 827 1290529144837947047624111610 828 1347779886192014666087338258 829 1407534244935661883179613532 830 1469900147180931543344331991 831 1534990111255303726726206031 832 1602921428749970295190643265 833 1673816375949505238344798468 834 1747802410653431945867036512 835 1825012400881225566817588916 836 1905584838824331885485599897 837 1989664088212015996622462654 838 2077400616864903881861898440 839 2168951264217602287529545773 840 2264479494067929448350343455 841 2364155683871599680175698170 842 2468157399414521306912342442 843 2576669707623616014831633943 844 2689885475033368967970142644 845 2808005705996128375446648201 846 2931239866969700090336391737 847 3059806252160641788309233690 848 3193932335827687724608021585 849 3333855167553997721310947788 850 3479821754942807359912772613 851 3632089490889816842181304889 852 3790926569243518535065096052 853 3956612446638347049398606598 854 4129438293904063488746041334 855 4309707495224687623285411522 856 4497736138309945044729590256 857 4693853553866017789163715281 858 4898402847789151950014555651 859 5111741484172655828348258891 860 5334241863049316166945841424 861 5566291950416862104607157690 862 5808295905343727001065933020 863 6060674760773319994808164817 864 6323867104118201413243530362 865 6598329812904136425703865932 866 6884538793313080364484361591 867 7182989775052389073899074676 868 7494199112668549609435992366 869 7818704644377579579817022066 870 8157066561361767864075913011 871 8509868335675605217342361047 872 8877717663158592777549134615 873 9261247465939960263099249312 874 9661116915054700498561987533 875 10078012513511532546400473082 876 10512649205188794092466034898 877 10965771544906875563764174534 878 11438154900708705084052633973 879 11930606717892316653688218882 880 12443967822349747225458129674 881 12979113786071251542236845940 882 13536956339830293248346885651 883 14118444848270631461867878855 884 14724567840886488330699029415 885 15356354605451644642336114760 886 16014876846957100637285338506 887 16701250408840342138909988557 888 17416637070311167015868115144 889 18162246405594355665686356824 890 18939337730902713949020394883 891 19749222112720983616648031391 892 20593264476577417182532273557 893 21472885776276523450331358984 894 22389565277582244691331411532 895 23344842901256213526323878676 896 24340321695801354749576069345 897 25377670368187143616659873944 898 26458625960918678446388508377 899 27584996585435877990848792706 900 28758664319974996105103737133 901 29981588161822199947672645443 902 31255807163729505650855641273 903 32583443622490453044945694235 904 33966706473066782282179995250 905 35407894732343417426053176339 906 36909401171624210870498300051 907 38473716035922081868981710700 908 40103431017099096103835317107 909 41801243270664899600107780955 910 43569959713578028482936116023 911 45412501362269812893491044895 912 47331907980998440283190049501 913 49331342766697433810102219174 914 51414097375792733705020271013 915 53583596983503962932575058876 916 55843405719207641556177774685 917 58197232130008446021233546033 918 60648935057071113646701222602 919 63202529535639015094511224783 920 65862193147274936163619020767 921 68632272391049765337903794265 922 71517289549342850269350634580 923 74521949567667539998638604898 924 77651147474598378034820787931 925 80909975810659400801724708117 926 84303732646084799171240608755 927 87837929602385183674688696076 928 91518300515026383274036821356 929 95350810094727448013274693588 930 99341663285777727559625694318 931 103497314617826205701628753813 932 107824478314468263409510680551 933 112330138390280428669694888222 934 117021559568517442298479565005 935 121906298182450553467952383879 936 126992213965543458225279452488 937 132287481820791110154288956018 938 137800604551615099180719281322 939 143540425567897323804325789742 940 149516142631076351915845710844 941 155737321570954991746131933593 942 162213911124117518037428073238 943 168956257741390674286763374269 944 175975121604766162399578121667 945 183281692611643195352265694809 946 190887607661964811752580881994 947 198804967912099746527238329467 948 207046357430917609925188650300 949 215624861823416544708593289505 950 224554088362009386389859563510 951 233848186087808787458992810623 952 243521867531513086165719594867 953 253590430408665705330155240670 954 264069781053258668727533841677 955 274976457832332730795138948512 956 286327656424803228630449324477 957 298141255090510415440502833077 958 310435841936867286285484357116 959 323230742187957468585550283705 960 336546047592458873319930658054 961 350402645849676540026560858450 962 364822252323867429004768830043 963 379827441796246445302706114995 964 395441682663386844984055180330 965 411689371197314784900378525549 966 428595868419152187742516113961 967 446187537063487836640587491413 968 464491781332934848268116922217 969 483537086778108582483771263148 970 503353063154365845098152959604 971 523970487445011560957413978136 972 545421350058250890788192933787 973 567738901238774202064232071513 974 590957700860974400609498519491 975 615113668492914259455305166620 976 640244137061232790286528443136 977 666387906851779478101766053704 978 693585303342455255997690233142 979 721878235446611404927958720634 980 751310257832450269305339413046 981 781926633738744848765457133382 982 813774402123478171859883743274 983 846902445406665890309454049080 984 881361561816764139003663849159 985 917204538442502397230633285079 986 954486229173371198943563762647 987 993263633471536646420937504155 988 1033595980332575084371249949156 989 1075544813219893635541344804132 990 1119174080503961025705274671856 991 1164550227035364040139923228978 992 1211742291555257483748152484674 993 1260822005419415063845851242731 994 1311863897509663523070162534232 995 1364945400660226468039523055491 996 1420146964639707405794197715449 997 1477552170872873937150845336619 998 1537247854105514476547203758616 999 1599324226059783574600164114631 1000 1663875006440197444440001601910