0 1 1 19 2 181 3 1159 4 5641 5 22363 6 75517 7 224143 8 598417 9 1462563 10 3317445 11 7059735 12 14218905 13 27298155 14 50250765 15 89129247 16 152951073 17 254831667 18 413442773 19 654862247 20 1014889769 21 1541911931 22 2300409629 23 3375210671 24 4876601009 25 6946419011 26 9765268709 27 13560999991 28 18618616249 29 25291783051 30 34016124973 31 45324511807 32 59864549953 33 78418509907 34 101925936373 35 131509203655 36 168502295625 37 214483106715 38 271309578045 39 341160000975 40 426577839057 41 530521438563 42 656419017477 43 808229343063 44 990508528857 45 1208483403179 46 1468131923021 47 1776271129439 48 2140653163361 49 2570069884019 50 3074466656021 51 3665065895399 52 4354500989801 53 5156961233339 54 6088348442461 55 7166445945583 56 8411100666097 57 9844419045763 58 11490977583397 59 13378048792183 60 15535843407865 61 17997769709515 62 20800710844525 63 23985321079935 64 27596341933185 65 31682939166867 66 36299061664053 67 41503823233287 68 47361908425353 69 53944003477467 70 61327253534589 71 69595747332111 72 78841030559249 73 89162649158051 74 100668723849029 75 113476557211031 76 127713274680089 77 143516500869611 78 161035072652429 79 180429790483871 80 201874209484193 81 225555471838387 82 251675182111573 83 280450327118887 84 312114242029993 85 346917624430075 86 385129598101405 87 427038828332335 88 472954690603825 89 523208494547395 90 578154765112677 91 638172582927543 92 703666985879097 93 775070433989643 94 852844339708077 95 937480665783999 96 1029503592939201 97 1129471259599059 98 1237977575994741 99 1355654114996039 100 1483172082084041 101 1621244366922779 102 1770627679039421 103 1932124770173519 104 2106586745907281 105 2294915469240803 106 2498066058828677 107 2717049484647383 108 2952935263916377 109 3206854260149803 110 3480001588270285 111 3773639628771295 112 4089101153970145 113 4427792569449715 114 4791197273843605 115 5180879140176487 116 5598486122029033 117 6045753987854907 118 6524510186835933 119 7036677849720687 120 7584279928151409 121 8169443476044291 122 8794404076648869 123 9461510418973431 124 10173229027325049 125 10932149147775051 126 11740987795423469 127 12602594966399231 128 13519959018596609 129 14496212225212691 130 15534636505215413 131 16638669334936967 132 17811909845053193 133 19058125107275867 134 20381256615151613 135 21785426963428495 136 23274946730519185 137 24854321568657955 138 26528259506417605 139 28301678468321815 140 30179714016358297 141 32167727318268523 142 34271313347560717 143 36496309320264223 144 38848803373515297 145 41335143491136819 146 43961946681447381 147 46736108412608679 148 49664812310894121 149 52755540127336059 150 56016081978284061 151 59454546865482159 152 63079373481349041 153 66899341305221699 154 70923581996400101 155 75161591089908023 156 79623240000963257 157 84318788344229003 158 89258896573997357 159 94454638951535423 160 99917516845904705 161 105659472374645075 162 111692902390795765 163 118030672822807495 164 124686133373982025 165 131673132588158107 166 139006033288446013 167 146699728395896527 168 154769657135074513 169 163231821633591907 170 172102803922740229 171 181399783346448471 172 191140554385878489 173 201343544907056811 174 212027834839029069 175 223213175290111071 176 234920008109898849 177 247169485904788851 178 259983492514848789 179 273384663959969511 180 287396409863318633 181 302042935360207547 182 317349263500574813 183 333341258153380847 184 350045647421301233 185 367490047574198915 186 385702987509948965 187 404713933751283575 188 424553315987419385 189 445252553169324235 190 466844080167575917 191 489361375001861503 192 512838986651262337 193 537312563454566803 194 562818882109950517 195 589395877283461639 196 617082671835847561 197 645919607677358299 198 675948277260261501 199 707211555718904079 200 739753633667256081 201 773620050663973539 202 808857729355118661 203 845515010304777879 204 883641687523920921 205 923289044707947243 206 964509892193469837 207 1007358604644990623 208 1051891159482226337 209 1098165176058949043 210 1146239955604311125 211 1196176521937730855 212 1248037662968521385 213 1301887972991553275 214 1357793895790348445 215 1415823768559111727 216 1476047866655314993 217 1538538449194558147 218 1603369805499541093 219 1670618302415091127 220 1740362432501301049 221 1812682863116944651 222 1887662486405448109 223 1965386470195808191 224 2045942309830961089 225 2129419880936219091 226 2215911493140506229 227 2305511944763238471 228 2398318578479808969 229 2494431337978754331 230 2593952825623793853 231 2696988361134050127 232 2803646041295876433 233 2914036800719833827 234 3028274473656478853 235 3146475856884741335 236 3268760773686790745 237 3395252138923409195 238 3526076025224009165 239 3661361730305554655 240 3801241845434765537 241 3945852325048106483 242 4095332557544183957 243 4249825437263297383 244 4409477437669013737 245 4574438685746758459 246 4744863037634539741 247 4920908155501047919 248 5102735585686496881 249 5290510838121700099 250 5484403467041000101 251 5684587153004796919 252 5891239786247548281 253 6104543551367242059 254 6324685013372469741 255 6551855205103358463 256 6786249716042748417 257 7028068782534132243 258 7277517379423003317 259 7534805313138390663 260 7800147316231489545 261 8073763143388428635 262 8355877668934347005 263 8646720985846087055 264 8946528506290942865 265 9255541063709037347 266 9574005016457035973 267 9902172353031039767 268 10240300798886635673 269 10588653924874218347 270 10947501257307833869 271 11317118389685932831 272 11697787096082557729 273 12089795446227627571 274 12493437922295121109 275 12909015537418099111 276 13336835955949645609 277 13777213615488948091 278 14230469850691877149 279 14696933018885567151 280 15176938627506641073 281 15670829463382864707 282 16178955723878158053 283 16701675149921034807 284 17239353160936684473 285 17792362991703055755 286 18361085831151444525 287 18945910963132234815 288 19547235909166586945 289 20165466573205013075 290 20801017388413927157 291 21454311466011403463 292 22125780746173525577 293 22815866151032855963 294 23525017739790704957 295 24253694865965027279 296 25002366336795923921 297 25771510574830877539 298 26561615781712000261 299 27373180104187724119 300 28206711802371516121 301 29062729420270352299 302 29941761958605837901 303 30844349049951014239 304 31771041136206046561 305 32722399648436141683 306 33698997189095198997 307 34701417716658853863 308 35730256732690728297 309 36786121471365860283 310 37869631091475439965 311 38981416870937138415 312 40122122403835472625 313 41292403800016808835 314 42492929887263765285 315 43724382416073934967 316 44987456267068008953 317 46282859661052541387 318 47611314371762758253 319 48973555941310973567 320 50370333898366338689 321 51802411979091813011 322 53270568350864407349 323 54775595838804914951 324 56318302155143509129 325 57899510131447751131 326 59520057953739716989 327 61180799400529117711 328 62882604083789453329 329 64626357692904407971 330 66412962241611860293 331 68243336317973051287 332 70118415337394619673 333 72039151798731383787 334 74006515543497918093 335 76021494018217142175 336 78085092539934310305 337 80198334564924960435 338 82362261960625552725 339 84577935280815699495 340 86846434044081060777 341 89168857015586152443 342 91546322492186487197 343 93979968590909642543 344 96470953540835024177 345 99020455978402268099 346 101629675246178400101 347 104299831695114047159 348 107032166990319171641 349 109827944420388976139 350 112688449210310804141 351 115614988837983039679 352 118608893354377187521 353 121671515707374494419 354 124804232069308651381 355 128008442168246296903 356 131285569623037221577 357 134637062282166355483 358 138064392566439801277 359 141569057815537357903 360 145152580638464162385 361 148816509267934260195 362 152562417918719098245 363 156391907149994118615 364 160306604231716815705 365 164308163515069804587 366 168398266807002633933 367 172578623748906263007 368 176850972199454308833 369 181217078621645356787 370 185678738474080815509 371 190237776606512985191 372 194896047659698196969 373 199655436469590070331 374 204517858475908125149 375 209485260135117175151 376 214559619337853120369 377 219742945830830947331 378 225037281643270937509 379 230444701517879276791 380 235967313346419451513 381 241607258609911009867 382 247366712823492461293 383 253247885985985280767 384 259253023034196179713 385 265384404301995000595 386 271644345984205788085 387 278035200605348786055 388 284559357493271306505 389 291219243257705613915 390 298017322273792166397 391 304956097170606753423 392 312038109324730268817 393 319265939358900057123 394 326642207645781971397 395 334169574816902480919 396 341850742276780368281 397 349688452722297756779 398 357685490667350411021 399 365844682972817456159 400 374168899381890864161 401 382661053060805259059 402 391324101145008797141 403 400161045290816082599 404 409174932232584284201 405 418368854345453824123 406 427745950213695216157 407 437309405204703837103 408 447062452048684622257 409 457008371424068883523 410 467150492548705656805 411 477492193776870193975 412 488036903202132423865 413 498788099266128416395 414 509749311373278094125 415 520924120511492646207 416 532316159878915310913 417 543929115516739404627 418 555766726948147687413 419 567832787823417368007 420 580131146571235264329 421 592665707056267849371 422 605440429243031126589 423 618459329866105493711 424 631726483106740969169 425 645246021275898371171 426 659022135503772255749 427 673059076435841636951 428 687361154935494729689 429 701932742793274173611 430 716778273442789414733 431 731902242683343140447 432 747309209409318882913 433 763003796346377125747 434 778990690794507469333 435 795274645377984631015 436 811860478802276277865 437 828753076617950911675 438 845957391991634248285 439 863478446484062756335 440 881321330835283244017 441 899491205757047606403 442 917993302732452070437 443 936832924822870499703 444 956015447482231546617 445 975546319378689665739 446 995431063223740228461 447 1015675276608829206399 448 1036284632849508118401 449 1057264881837185164179 450 1078621850898523696181 451 1100361445662539410439 452 1122489650935447866761 453 1145012531583314178779 454 1167936233422556945021 455 1191266984118358723343 456 1215011094091035582737 457 1239174957430418498723 458 1263765052818299591237 459 1288787944458996437143 460 1314250283018087923225 461 1340158806569375339755 462 1366520341550122649485 463 1393341803724630102175 464 1420630199156195600545 465 1448392625187518459827 466 1476636271429600439893 467 1505368420759199166247 468 1534596450324889293993 469 1564327832561787007227 470 1594570136214993685149 471 1625331027371814805551 472 1656618270502810396209 473 1688439729511733585091 474 1720803368794414041189 475 1753717254306643339191 476 1787189554641119523129 477 1821228542113508386571 478 1855842593857679229869 479 1891040192930173098431 480 1926829929423961749953 481 1963220501591555843027 482 2000220716977521084533 483 2037839493560461318727 484 2076085860904527786953 485 2114968961320514033435 486 2154498051036596179645 487 2194682501378778537295 488 2235531799961104778065 489 2277055551885695126755 490 2319263480952670293637 491 2362165430880023111383 492 2405771366533499092057 493 2450091375166547370283 494 2495135667670403749837 495 2540914579834367822559 496 2587438573616336380641 497 2634718238423655596019 498 2682764292404354693781 499 2731587583748824100199 500 2781199092002001300201 501 2831609929386127893819 502 2882831342134141596381 503 2934874711833767182959 504 2987751556782370633841 505 3041473533352640994563 506 3096052437369164721317 507 3151500205495957540343 508 3207828916635019108217 509 3265050793335976018763 510 3323178203216878961645 511 3382223660396220097535 512 3442199826936236975105 513 3503119514297569575955 514 3564995684805337334965 515 3627841453126703245447 516 3691670087759992420873 517 3756495012535432747867 518 3822329808127585528573 519 3889188213579534274447 520 3957084127838900077969 521 4026031611305752253731 522 4096044887392483205829 523 4167138344095716744471 524 4239326535580319341209 525 4312624183775584079211 526 4387046179983657322509 527 4462607586500278396191 528 4539323638247902838049 529 4617209744421280051251 530 4696281490145556457173 531 4776554638146975517607 532 4858045130436246266153 533 4940769090004652259707 534 5024742822532973132573 535 5109982818113291207855 536 5196505752983755893425 537 5284328491276378862915 538 5373468086777933295845 539 5463941784704030725175 540 5555767023486449315257 541 5648961436573787668363 542 5743542854245518533677 543 5839529305439517068863 544 5936939019593138581057 545 6035790428497920951379 546 6136102168167987224821 547 6237893080722224125639 548 6341182216280312537161 549 6445988834872686264219 550 6552332408364495676221 551 6660232622393653109199 552 6769709378323037186001 553 6880782795206933495139 554 6993473211771789350661 555 7107801188411360637783 556 7223787509196329031897 557 7341453183898468161963 558 7460819450029437573197 559 7581907774894283628383 560 7704739857659726772065 561 7829337631437314867315 562 7955723265381522600725 563 8083919166802877237735 564 8213947983296191297385 565 8345832604883983003067 566 8479596166175165653853 567 8615262048539087349487 568 8752853882295002791153 569 8892395548917059169667 570 9033911183254878442789 571 9177425175769818593911 572 9322962174786996755449 573 9470547088763157371851 574 9620205088570468869229 575 9771961609796332591231 576 9925842355059288053889 577 10081873296341098865811 578 10240080677335103954229 579 10400491015810919032071 580 10563131105995573536393 581 10728028020971168564187 582 10895209115089141627773 583 11064702026401224348687 584 11236534679107179506193 585 11410735286019404154275 586 11587332351044485819205 587 11766354671681799088535 588 11947831341539230201625 589 12131791752866117551595 590 12318265599103496308877 591 12507282877451735677343 592 12698873891455657595297 593 12893069253607225995443 594 13089899887965896040277 595 13289397032796713052199 596 13491592243226251161001 597 13696517393916481995259 598 13904204681756664048541 599 14114686628573343656239 600 14327996083858558824241 601 14544166227516337456579 602 14763230572627581835621 603 14985222968233431515319 604 15210177602137197095481 605 15438129003724957653003 606 15669112046804914914477 607 15903161952465597563583 608 16140314291953009386177 609 16380604989566815266003 610 16624070325575659354485 611 16870746939151710049095 612 17120671831324526726345 613 17373882367954343487515 614 17630416282724865487805 615 17890311680155673732687 616 18153607038634334538833 617 18420341213468310171107 618 18690553439956767481733 619 18964283336482381692887 620 19241570907623232779609 621 19522456547284892226091 622 19806981041852798245069 623 20095185573365017867231 624 20387111722705494625249 625 20682801472817880875251 626 20982297211940054117269 627 21285641736859416995431 628 21592878256189080978409 629 21904050393665034040891 630 22219202191464392987613 631 22538378113544841382767 632 22861623049005354369393 633 23188982315468311985667 634 23520501662483102907813 635 23856227274951320872695 636 24196205776573656356985 637 24540484233318586414155 638 24889110156912965895405 639 25242131508354623606015 640 25599596701447067274497 641 25961554606356401538323 642 26328054553190563476917 643 26699146335600980550023 644 27074880214406756127497 645 27455306921241488125019 646 27840477662222826589181 647 28230444121644876404879 648 28625258465693551627921 649 29024973346184988276259 650 29429641904327122744261 651 29839317774504543335959 652 30254055088086722745241 653 30673908477259739643499 654 31098933078881597868301 655 31529184538361252040223 656 31964719013561448769057 657 32405593178725492945203 658 32851864228428048947157 659 33303589881550086931623 660 33760828385278084708905 661 34223638519127596042875 662 34692079598991296551965 663 35166211481211618725295 664 35646094566678087906225 665 36131789804949471434307 666 36623358698400853475813 667 37120863306395748412727 668 37624366249483366000313 669 38133930713621141844107 670 38649620454422647088429 671 39171499801430991550271 672 39699633662417834874689 673 40234087527708120630611 674 40774927474530648609269 675 41322220171394600931271 676 41876032882492137912649 677 42436433472127179985051 678 43003490409170492310589 679 43577272771541189077711 680 44157850250714774810833 681 44745293156257840373347 682 45339672420389531691013 683 45941059602569909570647 684 46549526894115319337433 685 47165147122840889363115 686 47787993757730277906765 687 48418140913632788039775 688 49055663355987970777185 689 49700636505577836888435 690 50353136443306798212117 691 51013239915009459651303 692 51681024336286383378537 693 52356567797367947132603 694 53039949068006418842717 695 53731247602396370169839 696 54430543544123551909361 697 55137917731142354554499 698 55853451700781977675301 699 56577227694781432124279 700 57309328664353499436281 701 58049838275277773147339 702 58798840913022907114861 703 59556421687898196279679 704 60322666440234615669121 705 61097661745595443799443 706 61881494920016596995637 707 62674254025276801506823 708 63476027874197730656137 709 64286906035974234625243 710 65106978841534790835325 711 65936337388932303248655 712 66775073548765379277585 713 67623279969630213351075 714 68481050083603206552645 715 69348478111754452107927 716 70225659069692216864793 717 71112688773138549274347 718 72009663843536144746893 719 72916681713686599623327 720 73833840633420185369249 721 74761239675297274966451 722 75698978740341553844309 723 76647158563805148061991 724 77605880720965802821289 725 78575247632956244759291 726 79555362572625861840029 727 80546329670434835034671 728 81548253920380856350769 729 82561241185958568142531 730 83585398206151859006053 731 84620832601459151935927 732 85667652879951820792633 733 86725968443365871503627 734 87795889593227024795053 735 88877527537009337625535 736 89970994394327500868545 737 91076403203162951165395 738 92193867926123935246965 739 93323503456739665398855 740 94465425625788705121737 741 95619751207661724416283 742 96786597926758764500157 743 97966084463921152143183 744 99158330462898204185937 745 100363456536848863186659 746 101581584274878405521541 747 102812836248610363644119 748 104057336018793804590681 749 105315208141946107200299 750 106586578177031380900301 751 107871572692174669290719 752 109170319271412082144481 753 110482946521476999823859 754 111809584078622494497941 755 113150362615480112930663 756 114505413847955165994217 757 115874870542158670448443 758 117258866521376088913117 759 118657536673073014346863 760 120071016955937945733745 761 121499444406962302066435 762 122942957148557822103205 763 124401694395711497764855 764 125875796463178189427065 765 127365404772711071753547 766 128870661860330059105773 767 130391711383628359955967 768 131928698129117310121473 769 133481768019609635030547 770 135051068121641291622069 771 136636746652932040874631 772 138238952989884902353929 773 139857837675124642561371 774 141493552425075449261309 775 143146250137577944359311 776 144816084899545688299409 777 146503211994661329344291 778 148207787911112551498949 779 149929970349367975235351 780 151669918229993165573273 781 153427791701506902470507 782 155203752148277868874253 783 156997962198461912184607 784 158810585731980035280673 785 160641787888537273659955 786 162491735075682615642325 787 164360594976910122991015 788 166248536559801409704745 789 168155730084209637137275 790 170082347110485184003357 791 172028560507743150233263 792 173994544462172854041777 793 175980474485389481981763 794 177986527422828052157157 795 180012881462179851175479 796 182059716141871505825721 797 184127212359586850873739 798 186215552380831754774061 799 188324919847542065504319 800 190455499786734839136321 801 192607478619203014166099 802 194781044168253695034101 803 196976385668490208676039 804 199193693774638098354761 805 201433160570415219433883 806 203694979577446102164797 807 205979345764220746970063 808 208286455555098018118097 809 210616506839353802096483 810 212969698980274097404165 811 215346232824293202896215 812 217746310710177172228825 813 220170136478252702366635 814 222617915479681624529485 815 225089854585781166371167 816 227586162197390154598753 817 230107048254281327657587 818 232652724244619928524053 819 235223403214468748065767 820 237819299777339789846889 821 240440630123792727674811 822 243087612031080327603549 823 245760464872841006528751 824 248459409628838699929329 825 251184668894750211731331 826 253936466892000219690789 827 256715029477644110113911 828 259520584154298816155129 829 262353360080121834356171 830 265213588078838594512493 831 268101500649818358377087 832 271017331978198823135873 833 273961317945059606013587 834 276933696137644786794293 835 279934705859634685466375 836 282964588141467052628105 837 286023585750707850716635 838 289111943202471804550525 839 292229906769892900103695 840 295377724494645010856977 841 298555646197512831502243 842 301763923489013299203397 843 305002809780067683048343 844 308272560292724522756377 845 311573432070933598136299 846 314905683991371111221901 847 318269576774316263443359 848 321665372994579410625441 849 325093337092481979036339 850 328553735384888326144341 851 332046836076289730173479 852 335572909269940692983721 853 339132226979047741236219 854 342725063138010911239581 855 346351693613718103309103 856 350012396216892491907377 857 353707450713493178271683 858 357437138836169272671077 859 361201744295767593874103 860 365001552792894173846585 861 368836852029529756137995 862 372707931720699476854445 863 376615083606196917556415 864 380558601462362719859905 865 384538781113917951960787 866 388555920445852417743733 867 392610319415368099579207 868 396702280063877926354633 869 400832106529060058728987 870 405000105056967884043709 871 409206584014195913766991 872 413451853900101776793169 873 417736227359084502364131 874 422060019192919286825349 875 426423546373148938875351 876 430827128053532198414169 877 435271085582549124543531 878 439755742515963748719309 879 444281424629444189504991 880 448848459931240425823713 881 453457178674919926055667 882 458107913372161330777493 883 462800998805606387390567 884 467536772041770335335913 885 472315572444010941044795 886 477137741685556382225885 887 482003623762592181542255 888 486913565007407390184305 889 491867914101600222298115 890 496867022089343341682597 891 501911242390709002623223 892 507000930815054247185017 893 512136445574466361742923 894 517318147297268795983597 895 522546399041587748069119 896 527821566308979620110081 897 533144017058119548552979 898 538514121718551214544821 899 543932253204498139796359 900 549398786928736673924361 901 554914100816530879712859 902 560478575319629523193341 903 566092593430325375904399 904 571756540695577037152401 905 577470805231193484556323 906 583235777736081561621957 907 589051851506556611553303 908 594919422450716466972057 909 600838889102879005679723 910 606810652638083483061005 911 612835116886655852191775 912 618912688348838283180065 913 625043776209483093734195 914 631228792352811303418325 915 637468151377236024522407 916 643762270610250902940713 917 650111570123383822920827 918 656516472747216090013213 919 662977404086467307020207 920 669494792535146158212529 921 676069069291767317551171 922 682700668374634697122789 923 689390026637191252467511 924 696137583783435561949369 925 702943782383405397791371 926 709809067888728506869549 927 716733888648240819833151 928 723718695923672307591489 929 730763943905400704681811 930 737870089728273319506933 931 745037593487497151906247 932 752266918254597538999113 933 759558530093445550715547 934 766912898076354356905533 935 774330494300244788395215 936 781811793902880314835665 937 789357275079171662667875 938 796967419097551297006085 939 804642710316417991720535 940 812383636200651712480217 941 820190687338199037996203 942 828064357456729345186637 943 836005143440361984465503 944 844013545346464671838817 945 852090066422523324973939 946 860235213123083570890261 947 868449495126764153402599 948 876733425353342468932201 949 885087519980912459784379 950 893512298463115094476381 951 902008283546441665184239 952 910576001287610132862961 953 919215981071014751080579 954 927928755626249200093221 955 936714861045703463175543 956 945574836802234677708537 957 954509225766912194014923 958 963518574226837075421037 959 972603431903036273513343 960 981764351968431713047425 961 991001891065884521457555 962 1000316609326314638405685 963 1009709070386896041299975 964 1019179841409327823204745 965 1028729493098181360056027 966 1038358599719323804589693 967 1048067739118418144882447 968 1057857492739500065899793 969 1067728445643631852939427 970 1077681186527633576353349 971 1087716307742891797427351 972 1097834405314246035792409 973 1108036078958953239238891 974 1118321932105730497301389 975 1128692571913876240479391 976 1139148609292470167456929 977 1149690658919652143182771 978 1160319339261980311171669 979 1171035272593868663886631 980 1181839085017104315562153 981 1192731406480444722328827 982 1203712870799295095000733 983 1214784115675466250388527 984 1225945782717013147503153 985 1237198517458154355517635 986 1248542969379272700857445 987 1259979791926997341293495 988 1271509642534367515415865 989 1283133182641078216370955 990 1294851077713808039249837 991 1306663997266629452021183 992 1318572614881501740408257 993 1330577608228846877616083 994 1342679659088208570322037 995 1354879453368994732850759 996 1367177681131303641962441 997 1379575036606834025192219 998 1392072218219879336187581 999 1404669928608406471000399 1000 1417368874645219179800401