1 1 2 3 3 4 4 8 5 8 6 17 7 16 8 30 9 34 10 52 11 57 12 99 13 102 14 153 15 187 16 261 17 298 18 432 19 491 20 684 21 811 22 1061 23 1256 24 1696 25 1966 26 2540 27 3044 28 3876 29 4566 30 5846 31 6843 32 8610 33 10203 34 12610 35 14906 36 18491 37 21638 38 26508 39 31290 40 38044 41 44584 42 54133 43 63262 44 76241 45 89351 46 106816 47 124755 48 149200 49 173541 50 206236 51 240244 52 284134 53 329932 54 389597 55 451340 56 530721 57 614648 58 719788 59 831821 60 973022 61 1121506 62 1307001 63 1506340 64 1750240 65 2012667 66 2334738 67 2679690 68 3100350 69 3555604 70 4103053 71 4697206 72 5412871 73 6185690 74 7111140 75 8120409 76 9315604 77 10619935 78 12165903 79 13848651 80 15834751 81 18007371 82 20550841 83 23338470 84 26601593 85 30167662 86 34326226 87 38892242 88 44184372 89 49995926 90 56729568 91 64112476 92 72640628 93 82017023 94 92794477 95 104651917 96 118271853 97 133230931 98 150371814 99 169240108 100 190776160 101 214481127 102 241517946 103 271248951 104 305085521 105 342341586 106 384606270 107 431149390 108 483910500 109 541946241 110 607616132 111 679924844 112 761533108 113 851376629 114 952691341 115 1064145714 116 1189628041 117 1327741396 118 1482905966 119 1653668978 120 1845361517 121 2056148108 122 2292442420 123 2552382828 124 2843247506 125 3163129318 126 3520782739 127 3913864296 128 4352828840 129 4835335135 130 5373330547 131 5964539505 132 6623240884 133 7346630018 134 8151720387 135 9035928437 136 10018682052 137 11097645017 138 12296003006 139 13610949896 140 15069985538 141 16670813966 142 18444990528 143 20390982915 144 22546214820 145 24908862582 146 27523238291 147 30388846314 148 33556530642 149 37027355201 150 40861565607 151 45060624583 152 49695604047 153 54770576598 154 60367294354 155 66493188947 156 73244691333 157 80630964770 158 88765627455 159 97663058490 160 107454002566 161 118159069698 162 129932298561 163 142798995931 164 156940026141 165 172390261917 166 189358161051 167 207890420103 168 228231862764 169 250438925217 170 274798797146 171 301385416726 172 330529825844 173 362326859896 174 397164682225 175 435157714694 176 476760041893 177 522116663019 178 571751601583 179 625846753121 180 685015105657 181 749474411782 182 819941023372 183 896685939036 184 980535521080 185 1071823795982 186 1171516009565 187 1280011042622 188 1398434540053 189 1527275108975 190 1667832082069 191 1820701100653 192 1987396869846 193 2168627105470 194 2366155972778 195 2580842257004 196 2814721363128 197 3068829878531 198 3345537548726 199 3646072432126 200 3973189842908 201 4328366338340 202 4714781367212 203 5134205292554 204 5590332923258 205 6085253903851 206 6623258956993 207 7206845262124 208 7840961311889 209 8528581302922 210 9275449063877 211 10085065885768 212 10964091811534 213 11916685933487 214 12950527075287 215 14070545762556 216 15285640553361 217 16601598114772 218 18028724462914 219 19573862346838 220 21248886701306 221 23061871174248 222 25026560774468 223 27152408925616 224 29455311483207 225 31946398905730 226 34643977699150 227 37561133582571 228 40719025607876 229 44132934884256 230 47827303997236 231 51820062469585 232 56139338299010 233 60806135438330 234 65852925846669 235 71304185639681 236 77197375569483 237 83561117774525 238 90438493350242 239 97862933703586 240 105884108028230 241 114540884553039 242 123890499226371 243 133978277352259 244 144869984938870 245 156618412716377 246 169299295280650 247 182973889854618 248 197729359929200 249 213636943159098 250 230796717698269 251 249291451168560 252 269236248600755 253 290726957917424 254 313895905170963 255 338854294656464 256 365753919699622 257 394723676655358 258 425937954007466 259 459545750470328 260 495747308373614 261 534715101800881 262 576678639486675 263 621837416509616 264 670454790410760 265 722760954020311 266 779057976218337 267 839611780362743 268 904768260036752 269 974834369944626 270 1050206582885926 271 1131238503938607 272 1218384368526616 273 1312051864960671 274 1412760662818469 275 1520980493304473 276 1637306337874066 277 1762278433057270 278 1896577714541482 279 2040825934592128 280 2195801382232237 281 2362219145337712 282 2540969353529397 283 2732873183547536 284 2938948238920088 285 3160137972415247 286 3397604402973128 287 3652430836115652 288 3925944825826895 289 4219388528587393 290 4534278036478732 291 4872038189703018 292 5234398592991968 293 5622992691950606 294 6039794421193287 295 6486674127910916 296 6965883700726495 297 7479565247753702 298 8030285412298243 299 8620496275466382 300 9253123989825677 301 9930972392466778 302 10657376293173424 303 11435542292303234 304 12269267714833743 305 13162217896179217 306 14118717677134690 307 15142952738857195 308 16239846903202915 309 17414180404396249 310 18671554794089511 311 20017426762576946 312 21458169586847186 313 23000006655487338 314 24650186781795262 315 26415807977502575 316 28305109106623463 317 30326181989842965 318 32488391398801493 319 34800954869445452 320 37274513232492273 321 39919565958149384 322 42748196195130089 323 45772358543578816 324 49005774051057339 325 52462044230843266 326 56156744911870222 327 60105350381612788 328 64325531549140713 329 68834885946198620 330 73653460861606183 331 78801255302666616 332 84301004994386175 333 90175435660474497 334 96450318082622865 335 103151466324415022 336 110308089418305196 337 117949491546113973 338 126108768272724010 339 134819181474678152 340 144118211329759345 341 154043597379582929 342 164637781503254848 343 175943559810596294 344 188008977582118846 345 200882557355383397 346 214618662070146197 347 229272286871217151 348 244904935808972961 349 261578907351144126 350 279363763645709219 351 298330064390502482 352 318556450548379326 353 340122810048577429 354 363118035646847180 355 387632532923726436 356 413766752684943950 357 441622983583268153 358 471314690115151903 359 502957566506000021 360 536679757175578056 361 572612058898038050 362 610899153226295885 363 651688882053365213 364 695144533400254724 365 741433159890267381 366 790739018626671280 367 843250788562528428 368 899176328931609660 369 958728700464720903 370 1022142300198230888 371 1089657644424729729 372 1161539009207912997 373 1238057794119125086 374 1319511879738529436 375 1406207449732731815 376 1498480142025121156 377 1596675274490761458 378 1701170958770585054 379 1812356499739472951 380 1930657740191837604 381 2056513479250498104 382 2190403153124865786 383 2332821198543892337 384 2484307286013366626 385 2645418340699849802 386 2816761671845048264 387 2998964452571787359 388 3192709884589505609 389 3398704041358160276 390 3617715350093317086 391 3850538434667430739 392 4098037350348484764 393 4361106176726823622 394 4640716193529502048 395 4937873096802040313 396 5253668476575448012 397 5589233202595404489 398 5945793760780306725 399 6324621489851539292 400 6727094024946681541 401 7154640222653942322 402 7608807179855258317 403 8091200276484472525 404 8603556474130022277 405 9147679077913050366 406 9725517647948029640 407 10339097267123968935 408 10990605664124433529 409 11682316277192317781 410 12416683488425600532 411 13196258978023080722 412 14023795506777804342 413 14902156290310780804 414 15834428103625897681 415 16823822787162574021 416 17873800810651196242 417 18987964280942614456 418 20170191547387263600 419 21424521360255636321 420 22755299507122481825 421 24167053021441363962 422 25664650298903600616 423 27253164562901235735 424 28938048221176609706 425 30724985147125220719 426 32620080552536459009 427 34629700713904697455 428 36760680192358602601 429 39020148020628283911 430 41415753277682383940 431 43955477170518116535 432 46647878592410623301 433 49501890409405150716 434 52527087330707655670 435 55733465169584037090 436 59131732337894081564 437 62733071376043080961 438 66549456168345696817 439 70593393646562135511 440 74878269668401733008 441 79418069376833754083 442 84227753469600688777 443 89322956321353645668 444 94720395318003665867 445 100437544171802843537 446 106493079057648044199 447 112906525236223458558 448 119698742238033430791 449 126891542690981418001 450 134508219988881909326 451 142573136155347448869 452 151112296715895012833 453 160152905289614340171 454 169723988607591623538 455 179855916454024407522 456 190581081211363828928 457 201933379285114688630 458 213948951165667953390 459 226665621490601925173 460 240123703441301723756 461 254365395758574199976 462 269435657093376515180 463 285381555241961986288 464 302253219011914935846 465 320103136219568489847 466 338987188055660870881 467 358963893768162876614 468 380095534689278988553 469 402447339861714154865 470 426088709319930722862 471 451092336435727064637 472 477535536905539685098 473 505499305314204692876 474 535069759001476815465 475 566337121865910253550 476 599397295220798294626 477 634350763751450087103 478 671304301759665510820 479 710369798236628238006 480 751666110186657435940 481 795317798414758253919 482 841457143283708202496 483 890222785070090713132 484 941761913005496999606 485 996228806608706641950 486 1053787212970646989962 487 1114608778936426484249 488 1178875636025720741538 489 1246778716144071915599 490 1318520558230837235883 491 1394313503224447816940 492 1474382741496578709159 493 1558964374994977811036 494 1648308730040062321831 495 1742678277920320562143 496 1842351231232519820897 497 1947619317987662761228 498 2058791685869162883253 499 2176192515439287461626 500 2300165263371232263220 501 2431070104517177747982 502 2569288537668549457843 503 2715220650772245313221 504 2869290120266859916754 505 3031941282464627613876 506 3203644565823160093998 507 3384893356494788800746 508 3576209893894059824639 509 3778141924035171537111 510 3991269098087468675242 511 4216199393504646284187 512 4453576065324860647000 513 4704073821303561261798 514 4968406365211802975135 515 5247322318924150042934 516 5541613408281563443294 517 5852110108921301785851 518 6179690537783842367965 519 6525275806911979648014 520 6889839671157155597987 521 7274403582551733377347 522 7680047158828321923802 523 8107902911527474124147 524 8559167615116356222830 525 9035096691264514074839 526 9537016543827656531156 527 10066318591787500113726 528 10624472652443581436285 529 11213020592521695112836 530 11833590860767638713101 531 12487891737889638466701 532 13177727102532510123459 533 13904989273245567379697 534 14671676113024265200886 535 15479883428971192218356 536 16331823543497961530577 537 17229817231243057473723 538 18176313865225231379662 539 19173882885687465277570 540 20225235655301176031080 541 21333216422211708570599 542 22500826046815860104102 543 23731212438095844550140 544 25027696291205647681385 545 26393760995005924914402 546 27833080551751603442603 547 29349508915133986374842 548 30947110297978137920350 549 32630147921059919999966 550 34403116888186151616651 551 36270732348871285133808 552 38237965159229977993647 553 40310029416409258435788 554 42492421166676153929872 555 44790905294979521708495 556 47211557510738112581825 557 49760750604354432757377 558 52445199989743682212462 559 55271949286085137779318 560 58248419748554027081107 561 61382395165441786611207 562 64682075473762088718168 563 68156060996536236172175 564 71813410599207291478620 565 75663625229609906820273 566 79716711036216314069137 567 83983162212168173115623 568 88474029456444056901363 569 93200902166643654187581 570 98175982697840623214067 571 103412067875563710992447 572 108922629586671796285934 573 114721795632681109759147 574 120824437142751420859169 575 127246148840553030709973 576 134003343859657258022361 577 141113233412529912746559 578 148593929687508418797320 579 156464424968251444553533 580 164744703241619612971852 581 173455718882380119433733 582 182619517713461036364763 583 192259215272078129856265 584 202399128185027688572165 585 213064752107466377216373 586 224282904222039522985239 587 236081701023305130945922 588 248490712887195280142196 589 261540941761240642273043 590 275264988901609783191745 591 289697032621895952853506 592 304873010235859066758509 593 320830596120295386610808 594 337609399072975786009410 595 355250940815004386409412 596 373798870158722265007678 597 393298942191529323589173 598 413799250587224108552405 599 435350207840317348270001 600 458004797265243141797182 601 481818554503286362923740 602 506849840984707288211749 603 533159827075008232617357 604 560812788710852831522849 605 589876092712504389063255 606 620420518567316573496682 607 652520246268116112057165 608 686253205502287541722569 609 721701066558364001560502 610 758949619117189896605894 611 798088766967999186131623 612 839212938922534179618774 613 882421087896683264554176 614 927817136822676460706992 615 975509982879844603167775 616 1025613981221981938291163 617 1078248955392080004474790 618 1133540722086783011010964 619 1191621108583631746910146 620 1252628522202353142471552 621 1316707975861024815185695 622 1384011705848853721135827 623 1454699206941558165137617 624 1528937902601178518284202 625 1606903190858357852257689 626 1688779171601196265004069 627 1774758704792405948585211 628 1865044199481389464571803 629 1959847686321528964691430 630 2059391673565613888611595 631 2163909235608484556362425 632 2273644941902946436704621 633 2388854963710017448621753 634 2509808081878213597925502 635 2636785814481966565083378 636 2770083510183773216401955 637 2910010499193691907589015 638 3056891279780187102024150 639 3211065695557896963182257 640 3372890222762999993255892 641 3542738177508596708707875 642 3721001112412057505583689 643 3908089057205582486668935 644 4104432034354209968124729 645 4310480337138946843111553 646 4526706174026532324661441 647 4753603989138067267826946 648 4991692246340279580090744 649 5241513796775816320515577 650 5503637814961776753672467 651 5778660218978160683849324 652 6067205771076229218213768 653 6369928557132709817142930 654 6687514265784818736683122 655 7020680733548755429493389 656 7370180418136957096803083 657 7736801016810462897479152 658 8121368149893398927375534 659 8524746061205131302394951 660 8947840529675048580162487 661 9391599660555044587641518 662 9857017045091656735926210 663 10345132652700429391502055 664 10857036259196943650969492 665 11393868451739007745749266 666 11956824348486907058953991 667 12547154728067493595507876 668 13166170066097573565603253 669 13815241802810601352131779 670 14495806722687851478835179 671 15209368375944215484363550 672 15957501830471175390600372 673 16741855262985451980947172 674 17564155115705141809735475 675 18426207875356165876739952 676 19329905668158279696204940 677 20277228247502764885900785 678 21270249064542589707878709 679 22311137485682880699526726 680 23402165380093113720332687 681 24545709591200646257829075 682 25744259084077728914147481 683 27000417698448800353553866 684 28316911903558330939814780 685 29696593860867288969250345 686 31142449839063620207814962 687 32657603618493051868288917 688 34245325621228706301892497 689 35909036693513349076054728 690 37652318011656158488347548 691 39478915279883795756623332 692 41392749479165528931039618 693 43397921522806763405797784 694 45498723918401989934866603 695 47699645928878041327089172 696 50005386225110934703707668 697 52420858601901549459703411 698 54951205706758515632863200 699 57601805366561616626657333 700 60378285482198253513189655 701 63286531028521032840985511 702 66332700213758640108974604 703 69523232218023552371174448 704 72864864726411791770090781 705 76364642479318727829861422 706 80029936293784466622701005 707 83868452507581852589303740 708 87888253614957115714640957 709 92097768690318501305952846 710 96505815777102249241069734 711 101121613387065856005354225 712 105954804788522884008383169 713 111015470688345108146858388 714 116314155580409945104451786 715 121861881722882959048406898 716 127670177723523971897892429 717 133751093937798847063784874 718 140117233477683043612760275 719 146781769170263852819573506 720 153758477195031543573305807 721 161061755750279477906783728 722 168706661543776689020503184 723 176708930330780812744434609 724 185085016496154900106921765 725 193852115645795777893053921 726 203028207541382756696418322 727 212632080937520072186590493 728 222683380155330558557160335 729 233202632378654621878227404 730 244211298170039894117245541 731 255731801462210865865065084 732 267787584349094210239543684 733 280403140023083872114273885 734 293604072205276074406091100 735 307417131305820868097731462 736 321870278880208951514211582 737 336992727319136467574818841 738 352815009754353954340834762 739 369369023603738655757458076 740 386688106389892274968302392 741 404807083500215824542234019 742 423762350411051796727934683 743 443591925059596733749014863 744 464335537012535219358734546 745 486034684872448308811681504 746 508732732979895901732727843 747 532474974320336009467866759 748 557308735387079515547086989 749 583283445101886813967389280 750 610450748524405200332313503 751 638864582333908382360557377 752 668581298133774421336515287 753 699659745097027578345491350 754 732161403664346095065884346 755 766150476015982172244081963 756 801694031035051054550656865 757 838862103313805798709299374 758 877727850333306824898715611 759 918367660782163926449616850 760 960861324968218604362036465 761 1005292153304074193879898921 762 1051747161058785061451393669 763 1100317197924192834465616009 764 1151097148314516879703593151 765 1204186073016713931284598944 766 1259687426329199585655121489 767 1317709210896221493178875474 768 1378364213093252032946835793 769 1441770172223648126550509166 770 1508050035684170892406087703 771 1577332143815468772566254383 772 1649750506488413407651652163 773 1725445005022910006140645613 774 1804561691982346550183404725 775 1887253011677361676322013285 776 1973678125114242170997455631 777 2064003150744172390299103962 778 2158401516649294006089520771 779 2257054223353982965849687079 780 2360150225516898347426348422 781 2467886718753771981906418932 782 2580469553303543368261469471 783 2698113546994699195276560264 784 2821042933530349567576689221 785 2949491703928193468905415069 786 3083704092302023542424535306 787 3223934948277725160271634799 788 3370450263400189713956616162 789 3523527577259410945580296719 790 3683456547878216589916903759 791 3850539394533563995194790431 792 4025091515773368295169441704 793 4207441972141088280735179477 794 4397934155786710030509164341 795 4596926316596309511444223231 796 4804792287651591275842866473 797 5021922058584382849328869243 798 5248722561508014230917619283 799 5485618295704258477070109102 800 5733052179048516636841761335 801 5991486228508842038596082310 802 6261402482456341555734451811 803 6543303741858946450911471284 804 6837714569332675318418669144 805 7145182096283052105930332644 806 7466277105054806327699579615 807 7801594907744935535318945072 808 8151756518279160986652495866 809 8517409609130970421571757566 810 8899229780737557867343830454 811 9297921602834531195851268719 812 9714219989255477426999709876 813 10148891331188376454051932474 814 10602734986002288488354653594 815 11076584510377034498190138002 816 11571309272535611358535818045 817 12087815793808125625662227459 818 12627049494443006155254062484 819 13189996152920271249173046306 820 13777683796276335431921292141 821 14391184287298069419105856950 822 15031615371220796362182346909 823 15700142401714084441377203064 824 16397980556811386605774626114 825 17126396715551879570485500335 826 17886711856967567062827605063 827 18680303100276877491522988121 828 19508606301917626757979224392 829 20373118273183778133458320226 830 21275399591548588426480756647 831 22217077010840022910612468586 832 23199846504324970154646088994 833 24225475883821531496351625425 834 25295808093476693658147252478 835 26412764055483014305069177799 836 27578346235060160351633799357 837 28794641731963800548285967121 838 30063826138735503732342112403 839 31388166898835484452139885751 840 32770027482061354079834611010 841 34211871031752548278772289019 842 35716264883261030709088677379 843 37285884524592941968006732285 844 38923518485780638105752273891 845 40632072639400674002570238106 846 42414575491002799852764743650 847 44274182847997609944377346584 848 46214183543787348815372803669 849 48238004505934679762708968539 850 50349216949126197599442534104 851 52551541876147039010384585880 852 54848856777702937121725207469 853 57245201602333536237114022806 854 59744786004243665231735277609 855 62351995821334610427823398171 856 65071400915334511735968559890 857 67907762200418949875852866532 858 70866040123563652697353072915 859 73951402289532005957331751321 860 77169232633293428198346427462 861 80525139690991670712144339893 862 84024966520233456403374450986 863 87674799670795146675673859588 864 91480979913143150163948993471 865 95450111966823518577210781513 866 99589076102492455580091810135 867 103905038690760190408013124915 868 108405464748002723701488973488 869 113098129373644577851418322242 870 117991131315736858990654692444 871 123092905369958432777078475843 872 128412237047108262207966771861 873 133958276013174811707720722364 874 139740551947179275855374623536 875 145768989108216487500555614897 876 152053923479245787709905606494 877 158606118553696417431847045997 878 165436783868525325580857355850 879 172557592110607841625783494449 880 179980699150294319701191749845 881 187718762576041099642814429721 882 195784963348667492725334905294 883 204193025881123335512830178822 884 212957241443318631705786792551 885 222092489913504268047471345676 886 231614265073495779141426654927 887 241538698168481624527315178362 888 251882585243691879933608347969 889 262663412660090356158418859406 890 273899386635645574318539010573 891 285609460876386059460333409952 892 297813368497928794220970575535 893 310531651944349233813920638074 894 323785697479675809933171368286 895 337597767580427106126904670434 896 351991038201927403031836627801 897 366989633845444222220033742750 898 382618667819868929517242611202 899 398904280200653395819254529308 900 415873681324976528541081943739 901 433555192876539531087229585706 902 451978294871281661369390957853 903 471173670120995519349278537442 904 491173254986332743148757103655 905 512010287492584845895958824097 906 533719362148694698945242048478 907 556336482009740068071399064009 908 579899117884342230886639540843 909 604446264662067809732281138019 910 630018505256289528909656475635 911 656658071540248718776792346786 912 684408913399880625979727280910 913 713316764648893234122644964277 914 743429217595648592328090306197 915 774795794337254092049397281822 916 807468027275478788681460356070 917 841499536221802614343196586988 918 876946115331639670547347226991 919 913865816485680423486405066751 920 952319043148626666333352889354 921 992368640529244880294363269122 922 1034079996908474728190337111820 923 1077521141120571341397408083839 924 1122762851938254041963170496142 925 1169878763459173896805256535468 926 1218945483181863866621698984693 927 1270042705928129978390244823175 928 1323253341291907200288315130001 929 1378663636778122744608506419571 930 1436363315359967705778660416432 931 1496445708567209282043925291346 932 1559007904944883446897682333360 933 1624150893881962993671583470204 934 1691979725824894397172373976276 935 1762603667699924361410234264499 936 1836136375801497001454483254721 937 1912696063727159213943851080856 938 1992405688932517489838276957293 939 2075393134169977709492371534496 940 2161791408777413023049184991512 941 2251738844689892053427982289845 942 2345379313612207360978292446698 943 2442862438754801545567295138736 944 2544343829129626263684995545764 945 2649985308251747187611420380597 946 2759955166892172780717338746251 947 2874428410083806869907819978393 948 2993587029768271305190597526282 949 3117620271547411926979133239041 950 3246724928772384229474610747434 951 3381105630594498938192277970831 952 3520975159162285192847291813697 953 3666554760646647127956344306191 954 3818074487340337095339813642526 955 3975773533460423036666376136079 956 4139900604083076189575375876740 957 4310714277666672015491053270600 958 4488483403901182921452268145310 959 4673487495046245204252727096142 960 4866017154934614741273977988423 961 5066374501379277964399166426406 962 5274873628742707896400917589562 963 5491841063841886420018854202996 964 5717616264677431242539275936251 965 5952552112453464581021635415271 966 6197015449259885475002523817433 967 6451387609023188709970129910798 968 6716064997149377050002234182039 969 6991459663439431941794404211826 970 7277999926927332695182405889268 971 7576130994027952290703815097178 972 7886315632052265449863498785159 973 8209034836103596418072139705249 974 8544788555018338239677953199001 975 8894096410797199752580793960949 976 9257498481002112452344498562185 977 9635556074800288403768986034254 978 10028852576155630291570912131647 979 10437994280872373856676112875717 980 10863611305250025526653126950837 981 11306358488849984892717049378225 982 11766916373634077465026012806958 983 12245992177539511607834487453053 984 12744320849503075531117247452996 985 13262666119314202554265572700546 986 13801821634337485306074416258120 987 14362612091531931902022885290851 988 14945894462120615071193145784533 989 15552559212113915719970799423417 990 16183531621649227231415439149692 991 16839773100833956878604913215478 992 17522282610987675938868485906268 993 18232098083140176519108015012734 994 18970297948950072782666774210675 995 19738002669751617845743064664569 996 20536376385511847687452392702475 997 21366628562913781584556907794730 998 22230015771346057592265029367183 999 23127843459154989640316105109757 1000 24061467866332787741036381057959