1 1 2 1 3 2 4 3 5 4 6 7 7 9 8 14 9 18 10 27 11 35 12 49 13 64 14 86 15 113 16 148 17 192 18 247 19 319 20 404 21 517 22 649 23 822 24 1024 25 1285 26 1590 27 1979 28 2436 29 3007 30 3682 31 4515 32 5501 33 6703 34 8131 35 9851 36 11899 37 14344 38 17252 39 20703 40 24804 41 29640 42 35377 43 42115 44 50085 45 59415 46 70420 47 83261 48 98365 49 115947 50 136557 51 160502 52 188485 53 220929 54 258731 55 302485 56 353312 57 412046 58 480088 59 558580 60 649282 61 753749 62 874164 63 1012638 64 1171896 65 1354739 66 1564587 67 1805135 68 2080658 69 2396005 70 2756536 71 3168530 72 3638747 73 4175270 74 4786599 75 5483094 76 6275478 77 7176910 78 8200945 79 9364235 80 10683875 81 12180877 82 13876802 83 15798013 84 17971721 85 20430917 86 23209835 87 26349677 88 29893478 89 33892510 90 38400804 91 43482050 92 49203886 93 55645325 94 62890887 95 71038343 96 80193138 97 90476100 98 102018399 99 114969196 100 129491342 101 145768641 102 164002891 103 184420324 104 207270375 105 232831222 106 261410585 107 293349971 108 329028327 109 368864460 110 413323996 111 462919995 112 518223583 113 579862402 114 648535829 115 725010790 116 810142107 117 904865875 118 1010225266 119 1127361295 120 1257545099 121 1402165858 122 1562769981 123 1741046833 124 1938875067 125 2158306404 126 2401620096 127 2671304965 128 2970122369 129 3301087855 130 3667542636 131 4073135795 132 4521905272 133 5018261608 134 5567078612 135 6173681008 136 6843944695 137 7584290254 138 8401793828 139 9304188523 140 10299986084 141 11398490046 142 12609928023 143 13945479951 144 15417422384 145 17039175365 146 18825459192 147 20792365553 148 22957527068 149 25340217911 150 27961538366 151 30844550379 152 34014478571 153 37498888878 154 41327907472 155 45534450039 156 50154462843 157 55227210674 158 60795543637 159 66906254975 160 73610377647 161 80963622906 162 89026714395 163 97865918912 164 107553425622 165 118167984583 166 129795339854 167 142528990987 168 156470693906 169 171731361803 170 188431648193 171 206703008785 172 226688383384 173 248543440632 174 272437382421 175 298554395145 176 327094602090 177 358275751868 178 392334348147 179 429527606975 180 470134802709 181 514459529447 182 562831305673 183 615608184268 184 673178664640 185 735964698782 186 804423972899 187 879053362548 188 960391652140 189 1049023505518 190 1145582701521 191 1250756692154 192 1365290450469 193 1489991698253 194 1625735473198 195 1773470126655 196 1934222731967 197 2109105963819 198 2299324494933 199 2506182884230 200 2731093125844 201 2975583700740 202 3241308464737 203 3530057036826 204 3843765248051 205 4184527065248 206 4554606849288 207 4956453052582 208 5392712568963 209 5866246474468 210 6380146801052 211 6937754630147 212 7542679662941 213 8198821034530 214 8910390104622 215 9681934409625 216 10518364168409 217 11424979851819 218 12407502960597 219 13472107777063 220 14625457048125 221 15874738561795 222 17227706470278 223 18692723428778 224 20278808387942 225 21995685157216 226 23853837610029 227 25864565653527 228 28040048936725 229 30393411351709 230 32938794477994 231 35691431922737 232 38667733903917 233 41885372918396 234 45363381080502 235 49122248820981 236 53184036811927 237 57572489665489 238 62313164528988 239 67433562024213 240 72963273907177 241 78934133806856 242 85380386665392 243 92338862222072 244 99849169324224 245 107953895506139 246 116698829714867 247 126133191803055 248 136309887691251 249 147285773155219 250 159121946000729 251 171884049122929 252 185642604930363 253 200473363342160 254 216457684406028 255 233682937713360 256 252242939971867 257 272238413194473 258 293777484950422 259 316976213690196 260 341959160441123 261 368859990808385 262 397822128078889 263 428999442719152 264 462556998250308 265 498671840527730 266 537533849279651 267 579346641155527 268 624328541569762 269 672713617369107 270 724752785652486 271 780714994033627 272 840888485339831 273 905582145899320 274 975126947567649 275 1049877487173019 276 1130213630253577 277 1216542267868129 278 1309299189672026 279 1408951087833294 280 1515997690763767 281 1630974047788691 282 1754452959082100 283 1887047579174530 284 2029414183336960 285 2182255133084128 286 2346322024579029 287 2522419064923924 288 2711406654242612 289 2914205227932425 290 3131799330851165 291 3365241987978221 292 3615659336797793 293 3884255596913441 294 4172318335444632 295 4481224115296445 296 4812444478111340 297 5167552361300437 298 5548228894083406 299 5956270684992575 300 6393597539008565 301 6862260730350528 302 7364451762637367 303 7902511756630570 304 8478941391061164 305 9096411551573351 306 9757774607644278 307 10466076487677129 308 11224569467309013 309 12036725856750867 310 12906252498166021 311 13837106274988522 312 14833510541348415 313 15899972689714771 314 17041302763611222 315 18262633349976412 316 19569440658225802 317 20967567037309953 318 22463244840052412 319 24063121902671022 320 25774288553425795 321 27604306434947895 322 29561239061310185 323 31653684411120384 324 33890809487881456 325 36282387165301671 326 38838835262552905 327 41571258183449249 328 44491491081924376 329 47612146904038082 330 50946666290621902 331 54509370706626644 332 58315518807958102 333 62381366427575906 334 66724230223359300 335 71362555385279148 336 76315987481984422 337 81605448859797724 338 87253219718423436 339 93283024291964173 340 99720122310465030 341 106591406186641294 342 113925504161630358 343 121752889870676384 344 130105998629733185 345 139019350921002355 346 148529683454239970 347 158676088300343456 348 169500160559742251 349 181046155081871220 350 193361152794743101 351 206495237182909646 352 220501681580356413 353 235437147841706587 354 251361897178175113 355 268340013749948425 356 286439641934827160 357 305733237897694232 358 326297836527868553 359 348215334407641312 360 371572790041673214 361 396462742055626847 362 422983546773087100 363 451239735932496122 364 481342396149753500 365 513409570951655223 366 547566687201535566 367 583947006816834161 368 622692105836459983 369 663952381825972789 370 707887591936453480 371 754667422709713340 372 804472094227536148 373 857492999820253001 374 913933384240119873 375 974009061659065956 376 1037949176731082645 377 1105997010248258655 378 1178410832995509392 379 1255464809530233831 380 1337449955889486557 381 1424675153180721854 382 1517468221490646262 383 1616177056335490406 384 1721170832557435943 385 1832841278199021757 386 1951604023772442105 387 2077900029811708541 388 2212197098681285742 389 2354991473939420303 390 2506809533836087326 391 2668209582713565988 392 2839783747550584365 393 3022159983955752862 394 3216004199570814648 395 3422022499803649887 396 3640963564636609961 397 3873621162128376117 398 4120836808212439919 399 4383502579203659065 400 4662564087551809621 401 4959023628153171391 402 5273943506782574543 403 5608449558973151575 404 5963734872027159295 405 6341063719632224333 406 6741775722993374445 407 7167290249248104029 408 7619111062420772021 409 8098831239136172258 410 8608138365826987733 411 9148820031285870471 412 9722769632920357150 413 10331992512390080718 414 10978612440770748067 415 11664878470969584006 416 12393172179504540451 417 13166015317657968148 418 13986077896284585399 419 14856186726836788306 420 15779334445278646049 421 16758689044295359944 422 17797603943110994934 423 18899628623488033708 424 20068519864138772746 425 21308253605645506885 426 22623037481345668716 427 24017324050192371284 428 25495824770617373557 429 27063524755751929128 430 28725698352984297622 431 30487925593030109133 432 32356109555872283802 433 34336494704087884815 434 36435686235771620239 435 38660670513489373847 436 41018836626849936506 437 43517999151677428089 438 46166422169337886626 439 48972844616444561672 440 51946507035114163718 441 55097179802005158187 442 58435192913651938984 443 61971467415174131672 444 65717548558022264429 445 69685640783608867709 446 73888644627529661897 447 78340195652009874089 448 83054705511314598359 449 88047405269662599955 450 93334391087519260396 451 98932672408937977295 452 104860222778186626211 453 111136033432809025051 454 117780169815071761586 455 124813831164913442409 456 132259413351563114746 457 140140575124542079982 458 148482307958098071591 459 157311009689179302494 460 166654562141719220786 461 176542412958709543496 462 187005661855594041309 463 198077151539999808673 464 209791563534358177179 465 222185519172360990771 466 235297686031315657659 467 249168890099904083859 468 263842233971678401672 469 279363221395245980395 470 295779888502795343408 471 313142942082544463206 472 331505905251443526690 473 350925270931844794572 474 371460663526868224333 475 393175009240153593511 476 416134715477227409199 477 440409859820391115611 478 466074389061378380327 479 493206328834568500787 480 521888004387013030754 481 552206273084069051322 482 584252769244408606550 483 618124161964849794587 484 653922426592349029439 485 691755130571466484446 486 731735734394893850345 487 773983908460053205141 488 818625866636965087916 489 865794717432612908475 490 915630833642705837019 491 968282241466563967428 492 1023905030070649255905 493 1082663782676062300468 494 1144732030259965741319 495 1210292729055868644214 496 1279538763057960366719 497 1352673472835066421963 498 1429911211986518325307 499 1511477932678265382693 500 1597611801731686176572 501 1688563848849519297864 502 1784598648605887684431 503 1885995037945598865683 504 1993046870989994056890 505 2106063813071415599404 506 2225372175981211034342 507 2351315796547970268671 508 2484256960737607719180 509 2624577375606122010125 510 2772679191524272190553 511 2928986077240576290621 512 3093944350452493345820 513 3268024166711342836306 514 3451720769606683796415 515 3645555805340771876667 516 3850078704942397997130 517 4065868137544260509778 518 4293533538307189702939 519 4533716714760204233138 520 4787093535507123238999 521 5054375705447928708474 522 5336312631869659477013 523 5633693385972008381727 524 5947348764626682854403 525 6278153457394166193747 526 6627028324085329717912 527 6994942788395567524197 528 7382917353435692480347 529 7792026245241321183578 530 8223400190674862317709 531 8678229336410822848657 532 9157766316066623077678 533 9663329472838925486050 534 10196306245419574734326 535 10758156725286613017337 536 11350417393926359839273 537 11974705048890105379795 538 12632720928099998867607 539 13326255042195456624688 540 14057190725277348201936 541 14827509414816463791065 542 15639295672118356887065 543 16494742455182126817496 544 17396156656481039466159 545 18345964918678770541843 546 19346719742055620636161 547 20401105897949990178750 548 21511947163357141432693 549 22682213392408444193474 550 23915027941373584301709 551 25213675464465404827031 552 26581610098735757632950 553 28022464057050347188410 554 29540056649236141574980 555 31138403752264047088185 556 32821727751540035884702 557 34594467976224459453245 558 36461291652823347667759 559 38427105402228160768953 560 40497067306827517719800 561 42676599575342848470145 562 44971401834620104810733 563 47387465078744516358167 564 49931086307569692405580 565 52608883888005369305556 566 55427813673288498010611 567 58395185916846438137214 568 61518683019410410759442 569 64806378149566773610017 570 68266754780166081765195 571 71908727184700281103288 572 75741661940189061854415 573 79775400484984946997219 574 84020282782552179827844 575 88487172144340099745650 576 93187481267749978271054 577 98133199547477673949625 578 103336921721645147883012 579 108811877916657717020961 580 114571965158128279165435 581 120631780417998922969839 582 127006655271691546873756 583 133712692242200813894811 584 140766802912066134827489 585 148186747887563345518175 586 155991178703829767068868 587 164199681763395150230890 588 172832824405343688803472 589 181912203206481446300544 590 191460494621048661110239 591 201501508070094693147836 592 212060241597246614347825 593 223162940212652275884518 594 234837157052979001220247 595 247111817490916582955901 596 260017286334263240777012 597 273585438260808786063391 598 287849731642435290570270 599 302845285918614160541000 600 318608962687311342782378 601 335179450688753798205446 602 352597354866025416430103 603 370905289694649905176407 604 390147976982575899826704 605 410372348350987855180866 606 431627652616432736362514 607 453965568304656992561465 608 477440321537495745427845 609 502108809545040772848866 610 528030730067221136355293 611 555268716920886634701420 612 583888482021437494803581 613 613958964161171154952636 614 645552484860610370892758 615 678744911623483583140443 616 713615828941364780997599 617 750248717409783755315208 618 788731141334309143987884 619 829154945222435101350714 620 871616459575271890306278 621 916216716412032865843496 622 963061674980091666838344 623 1012262458124190479789895 624 1063935599809919747819498 625 1118203304319375731259285 626 1175193717660359816464028 627 1235041211755426843955173 628 1297886682002639539798490 629 1363877858827180735663433 630 1433169633870807540165371 631 1505924401495987948275509 632 1582312416311883362718547 633 1662512167461987253533461 634 1746710770446270332157164 635 1835104377286368343297834 636 1927898605878353214206125 637 2025308989416622816868869 638 2127561446811683626043892 639 2234892775067196960540498 640 2347551164624427113043178 641 2465796738728746427146822 642 2589902117919469432370002 643 2720153010795070945432795 644 2856848832256659448384025 645 3000303350488001375849698 646 3150845363985788921842234 647 3308819410014317728400970 648 3474586505919133872092011 649 3648524924800175530835473 650 3831031007110776699295488 651 4022520009820839391075482 652 4223426994854264803675657 653 4434207758589168452966047 654 4655339804287667498962122 655 4887323359407525496832773 656 5130682439833267240973360 657 5385965963157551634129057 658 5653748913236618886237775 659 5934633558345150667679743 660 6229250725357304274524272 661 6538261132491277225525995 662 6862356783265329686820197 663 7202262424433648872620516 664 7558737070790979785473245 665 7932575599866120966003552 666 8324610419655786249394178 667 8735713212693154735443459 668 9166796759888666955768885 669 9618816847736102436696069 670 10092774262633099122542699 671 10589716876234504141051305 672 11110741825927108422715130 673 11656997794698487926147917 674 12229687394858123492105641 675 12830069660269374185749673 676 13459462651952971177560403 677 14119246182140736803493807 678 14810864662078442952932951 679 15535830079113917135485914 680 16295725108846433609037676 681 17092206368371429886681690 682 17927007816915977752394135 683 18801944310441043192859217 684 19718915317071308570768639 685 20679908800518484535605386 686 21687005278974181365515010 687 22742382067280225373050625 688 23848317710522080592012298 689 25007196617551807135578718 690 26221513903314814806739532 691 27493880449246885674776754 692 28827028191408446640455262 693 30223815646449433049382272 694 31687233685934123334243814 695 33220411570018760879641428 696 34826623251949444485762694 697 36509293965351461552372947 698 38272007106797887828600867 699 40118511426692677766568295 700 42052728542065746951054935 701 44078760785472400163083116 702 46200899404801316052437076 703 48423633129441665282474298 704 50751657118925663689858957 705 53189882310865148247121051 706 55743445185725004884166783 707 58417717966739264140050423 708 61218319274063480426499436 709 64151125253085882827431283 710 67222281197676611045077398 711 70438213690054730657446635 712 73805643279884500484617253 713 77331597726190352504429504 714 81023425826693201751480930 715 84888811860232911306715894 716 88935790669043237997377262 717 93172763408799182796561681 718 97608513995554062446696223 719 102252226279936382933775296 720 107113501980278060574327156 721 112202379407705894952041182 722 117529353017642600634001360 723 123105393823640794586496863 724 128941970711010281072230771 725 135051072689302701931280053 726 141445232124387512929554090 727 148137548992594343626344553 728 155141716201210911853273695 729 162472046021515765034347343 730 170143497682495665208097986 731 178171706175449147534691270 732 186573012321817982565674175 733 195364494158815257428678875 734 204563999699742970414983623 735 214190181128309090633061800 736 224262530488777702217324614 737 234801416936409016595374922 738 245828125615385986727535362 739 257364898234270896818414684 740 269434975412009717684421984 741 282062640870590946256881074 742 295273267553694215899057264 743 309093365754015557323218829 744 323550633335460219602365998 745 338674008140030284109348798 746 354493722673036862745450037 747 371041361164211618960644382 748 388349919106418403431585367 749 406453865377945238332496097 750 425389207058833452220754888 751 445193557056342712712487670 752 465906204659507027705151165 753 487568189147771554106363741 754 510222376583967772160424581 755 533913539927344994615530835 756 558688442608089529320560398 757 584595925710684388851713391 758 611686998919658459879909777 759 640014935387695225664679433 760 669635370692789893273868700 761 700606406058106162877636985 762 732988716015468718634172798 763 766845660700976121816179171 764 802243402979116597903840332 765 839251030599952723526230807 766 877940683602502507450263751 767 918387687186315469612209404 768 960670690282522328401777862 769 1004871810065252598207796862 770 1051076782654372229026947229 771 1099375120270915331162420896 772 1149860275117483808622731218 773 1202629810267183517942853523 774 1257785577856476637456634653 775 1315433904889569695395759645 776 1375685786974754025929321401 777 1438657090326378106142845413 778 1504468762379995840916554868 779 1573247051382604748920550839 780 1645123735334907514432990039 781 1720236360678098575321988340 782 1798728491133946519328639203 783 1880749967123808085132047903 784 1966457176209830601309703452 785 2056013335019868010222038344 786 2149588783136719203253377724 787 2247361289452084072008694409 788 2349516371506298332325398258 789 2456247628356337584980465817 790 2567757087536957961480465396 791 2684255566703047232539894884 792 2805963050565487929341925908 793 2933109083757962894351650471 794 3065933180298362917048567850 795 3204685250335664211053909014 796 3349626044901537181443458590 797 3501027619415404771072343858 798 3659173816722402779111775459 799 3824360770475583230247888001 800 3996897429706966453623081402 801 4177106105466565845911040970 802 4365323040444509631813254948 803 4561899002528745503407735603 804 4767199903289771820582221598 805 4981607442424274581895153137 806 5205519779231704059416055794 807 5439352232241583614322802118 808 5683538008154953309764795807 809 5938528961310701675898765873 810 6204796384936883646584884778 811 6482831835498356000716465589 812 6773147991505442259207410732 813 7076279548203768463616149346 814 7392784149623153204976962099 815 7723243359523399435259582800 816 8068263672837290098799103207 817 8428477569275953892259613000 818 8804544610829313661911794886 819 9197152584964488742131474960 820 9607018695398069642802122002 821 10034890802394062494889833337 822 10481548714618290309396930696 823 10947805534662096699005332853 824 11434509060433606503691540081 825 11942543244703531669897356615 826 12472829715184852964632269441 827 13026329357621652218506393181 828 13604043964462200388504224722 829 14207017951795138151589033577 830 14836340147335503424392202673 831 15493145652359501534766718815 832 16178617780603564464740446389 833 16893990077264468463153951398 834 17640548421363359823330848328 835 18419633214867567522284780512 836 19232641662100343334387116707 837 20081030143110286366249936107 838 20966316684819462980445124839 839 21890083533922279599827956586 840 22853979835666286343543836102 841 23859724422811475006734644832 842 24909108719236564704088949116 843 26003999762839473142541266263 844 27146343352564927428436049401 845 28338167324585248791827098081 846 29581584962861024047411332563 847 30878798549516972280695916793 848 32232103060685098269932806663 849 33643890013692563356688800552 850 35116651471705866497495393820 851 36652984212186335140109991716 852 38255594065764840434322759434 853 39927300432406553280998728017 854 41671040982009706371783987196 855 43489876546866262954041311340 856 45386996213707371729841661631 857 47365722623363114637793468248 858 49429517486384583372045468276 859 51581987323307426592892247638 860 53826889438579943410785556951 861 56168138137536309294885945693 862 58609811196166856714685871160 863 61156156593823322894730086212 864 63811599519397868693168508644 865 66580749661931377954290512099 866 69468408797039313513138576114 867 72479578680993235417777611325 868 75619469264763228193020418945 869 78893507240812032403114991965 870 82307344935935883901054414939 871 85866869563971127035391992063 872 89578212852729843464455211397 873 93447761060093326636028354813 874 97482165394779498753198219149 875 101688352857910724138138953069 876 106073537522142195968524584057 877 110645232265769692006408760531 878 115411260979919298298404665509 879 120379771267632341576351017978 880 125559247654396557474097352029 881 130958525330441237146240013395 882 136586804445910066898062896046 883 142453664980852526200777269980 884 148569082212833392333820427754 885 154943442805852182039308048628 886 161587561545190626494873662744 887 168512698743768745329306625358 888 175730578346589179832787186584 889 183253406760887545093526993870 890 191093892440684130616410957676 891 199265266255551867819307751449 892 207781302674577606630655083899 893 216656341797701128213554909454 894 225905312267869541549929858180 895 235543755098746680399371250583 896 245587848454068476846870270633 897 256054433416139145985229639779 898 266961040782420093862607415888 899 278325918930677070754569569489 900 290168062794722043319844444016 901 302507243994418081042055285482 902 315364042165309154280546704760 903 328759877534995878508713751968 904 342717044795203935174973288330 905 357258748320388147199300534771 906 372409138785683137431215600851 907 388193351239055394399694829202 908 404637544684632705667165223696 909 421768943236389800458922302805 910 439615878903655124428336142216 911 458207836072277731613914307185 912 477575497747756954813547605498 913 497750793629195876787675945289 914 518766950085594502325209979781 915 540658542108755301075239323997 916 563461547319934504635993123606 917 587213402110342895103652255109 918 611953059998682111006362101585 919 637721052292102754075066867823 920 664559551140291370220809362609 921 692512435075841089418817705205 922 721625357137638201524160291319 923 751945815677710981634232104253 924 783523227955840844463582465037 925 816409006630236560104379907455 926 850656639256723345645952445140 927 886321770913207732364953443391 928 923462290070650129998355223451 929 962138417836417981207059220882 930 1002412800700707682149262659523 931 1044350606921721516381499269558 932 1088019626690471537984449162701 933 1133490376221464613673784178298 934 1180836205921107031449487696050 935 1230133412791462691835032607253 936 1281461357233011811010398009546 937 1334902584416297319412507219267 938 1390542950398820232783867392167 939 1448471753170263823702998579693 940 1508781868816096584768030052543 941 1571569892996836985833602694091 942 1636936287947766753706690848712 943 1704985535211665734912274080101 944 1775826294325218979371602631243 945 1849571567688128092731717338199 946 1926338871852653622675670515953 947 2006250415480336597664877288834 948 2089433284222005704924086861496 949 2176019632786886093506435213522 950 2266146884476697775568096954144 951 2359957938471081028640833867108 952 2457601385161525487412828511089 953 2559231729842224603219651465360 954 2665009625077941396393518587634 955 2775102112081071732010332669734 956 2889682871442642495453485420436 957 3008932483575001849220668421154 958 3133038699237463322486372796612 959 3262196720530173725497647413855 960 3396609492756004323267563446587 961 3536488007565335414221075834274 962 3682051617814235504466068989271 963 3833528364582748956532203078798 964 3991155316816821036912769240061 965 4155178924074829328483601794894 966 4325855382877777998246168065516 967 4503451017180970480589651926083 968 4688242673504431141230936805982 969 4880518131279523015437338438261 970 5080576528990133199221469204304 971 5288728806708497137588990631367 972 5505298165648236525098315821256 973 5730620545380521788655503771445 974 5965045119383470137248392308515 975 6208934809619984797987295090156 976 6462666820865263809357773329904 977 6726633195532190491104595324395 978 7001241389770798653244112143228 979 7286914871647018794002427099479 980 7584093742235996058250284926791 981 7893235380496463964456713879642 982 8214815112825002046819448696853 983 8549326908222540484556034487257 984 8897284100040246005025863756672 985 9259220135307973427620719248598 986 9635689352685845211236721530809 987 10027267790118272749634938517058 988 10434554023309910770835840088146 989 10858170036184688620617966760711 990 11298762124532246349079831269729 991 11757001834090871301467338611081 992 12233586934362443581837491401684 993 12729242429503011838775295234375 994 13244721607682500196066801379709 995 13780807130358752218642578270305 996 14338312162964719401635396562324 997 14918081548563163365051097996929 998 15520993026080838860961461053545 999 16147958494793826903928861771970 1000 16799925326797575609320123471970