0 1 1 12 2 78 3 364 4 1365 5 4368 6 12376 7 31824 8 75582 9 167960 10 352716 11 705431 12 1352066 13 2496066 14 4457036 15 7724795 16 13033527 17 21461804 18 34565466 19 54551718 20 84504355 21 128671764 22 192831288 23 284745682 24 414729756 25 596347896 26 847265992 27 1190284393 28 1654581864 29 2277204150 30 3104834668 31 4195889061 32 5622979869 33 7475802412 34 9864498150 35 12923557296 36 16816328321 37 21740208216 38 27932593976 39 35677682756 40 45314215530 41 57244266872 42 71943191684 43 89970848331 44 111984226718 45 138751619370 46 171168483564 47 210275153023 48 257276568627 49 313564209036 50 380740414066 51 460645306122 52 555386527983 53 667372028764 54 799346143960 55 954429230118 56 1136161129896 57 1348548759064 58 1596118123392 59 1883971090365 60 2217847258276 61 2604191283486 62 3050226045516 63 3564032049161 64 4154633483001 65 4832091374540 66 5607604303742 67 6493617158964 68 7503938442221 69 8653866654368 70 9960326315160 71 11442014198264 72 13119556387158 73 15015676784472 74 17155377734716 75 19566133448511 76 22278096945402 77 25324321262098 78 28740995703564 79 32567697945795 80 36847662831343 81 41628068731756 82 46960342385034 83 52900483151022 84 59509407663355 85 66853315893156 86 75004079677176 87 84039654801466 88 94044517770996 89 105110128435896 90 117335419686200 91 130827315469137 92 145701278426144 93 162081888490886 94 180103453834668 95 199910655591725 96 221659227843989 97 245516674393068 98 271663023896342 99 300291624994296 100 331609983107481 101 365840640633832 102 403222102330488 103 444009807718764 104 488477152406530 105 536916560278968 106 589640608566516 107 646983207857779 108 709300839185302 109 776973850373370 110 850407813899436 111 930034948584391 112 1016315607491691 113 1109739834481356 114 1210828991932066 115 1320137462213010 116 1438254425556807 117 1565805717055724 118 1703455765575576 119 1851909617455118 120 2011915047933440 121 2184264763323864 122 2369798697030128 123 2569406402579237 124 2784029546925276 125 3014664507359726 126 3262365075446412 127 3528245271483153 128 3813482273077489 129 4119319461510540 130 4447069589651118 131 4798118075271676 132 5173926423708549 133 5576035783901232 134 6006070641939160 135 6465742656339616 136 6956854639377006 137 7481304688881816 138 8041090475027116 139 8638313686721511 140 9275184642329970 141 9954027069548002 142 10677283059360204 143 11447518199121291 144 12267426889906343 145 13139837853387180 146 14067719833603514 147 15054187499110838 148 16102507551101907 149 17216105043215156 150 18398569918861496 151 19653663772020642 152 20985326837579468 153 22397685217407864 154 23895058348492200 155 25481966719572793 156 27163139842859736 157 28943524487531094 158 30828293181848812 159 32822852990860725 160 34932854576791821 161 37164201549364396 162 39523060113424966 163 42015869021395776 164 44649349838210481 165 47430517526537080 166 50366691360236472 167 53465506174152084 168 56734923958474906 169 60183245806078968 170 63819124221374820 171 67651575799382939 172 71689994283885198 173 75944164013670602 174 80424273766051436 175 85140931006987791 176 90105176557322147 177 95328499684791308 178 100822853631650514 179 106600671587914010 180 112674883120387743 181 119058931067843196 182 125766788912856664 183 132812978641015542 184 140212589098372440 185 147981294858209176 186 156135375608355936 187 164691736070496141 188 173667926463074836 189 183082163519617726 190 192953352074459340 191 203301107228072217 192 214145777104384489 193 225508466212670796 194 237411059426801118 195 249876246594833860 196 262927547792143389 197 276589339231478208 198 290886879843554072 199 305846338541996616 200 321494822186660486 201 337860404259566552 202 354972154267915548 203 372860167888855439 204 391555597870900970 205 411090685707127218 206 431498794095484556 207 452814440201810259 208 475073329741342047 209 498312391894771180 210 522569815075107306 211 547885083561864126 212 574299015019314091 213 601853798915801796 214 630593035861349496 215 660561777881034250 216 691806569641864612 217 724375490651135544 218 758318198444493336 219 793685972782197793 220 830531760872326800 221 868910223639928614 222 908877783061389868 223 950492670583552317 224 993814976647378821 225 1038906701336238956 226 1085831806169156982 227 1134656267059639688 228 1185448128460978889 229 1238277558719203080 230 1293216906655134968 231 1350340759397296316 232 1409726001487688754 233 1471451875282768952 234 1535600042672228820 235 1602254648138486211 236 1671502383180088966 237 1743432552122535066 238 1818137139340314156 239 1895710877914280791 240 1976251319748777435 241 2059858907173235532 242 2146637046053295874 243 2236692180436805026 244 2330133868760362743 245 2427074861642416140 246 2527631181289219864 247 2631922202540307678 248 2740070735580449712 249 2852203110345401176 250 2968449262649082576 251 3088942822060168437 252 3213821201556401228 253 3343225688985289614 254 3477301540360195340 255 3616198075021160993 256 3760068772690181601 257 3909071372450976524 258 4063367973683674382 259 4223125138985182860 260 4388513999106377141 261 4559710359937605456 262 4736894811574377816 263 4920252839495474416 264 5109974937886083486 265 5306256725138954520 266 5509299061566931852 267 5719308169360615479 268 5936495754825280866 269 6161079132931577218 270 6393281354214914380 271 6633331334058842139 272 6881463984398122263 273 7137920347877593132 274 7402947734503329306 275 7676799860823003846 276 7959736991672769667 277 8252026084528387668 278 8553940936498743864 279 8865762334000315250 280 9187778205151564668 281 9520283774926668536 282 9863581723108407944 283 10217982345080483337 284 10583803715499945800 285 10961371854890873846 286 11351020899200863596 287 11753093272362342341 288 12167939861901160701 289 12595920197635366956 290 13037402633507518630 291 13492764532594341072 292 13962392455338000609 293 14446682351043720856 294 14946039752688934968 295 15460879975089634020 296 15991628316470042314 297 16538720263482224248 298 17102601699722704452 299 17683729117793663211 300 18282569834956752766 301 18899602212428066922 302 19535315878363286508 303 20190211954582516639 304 20864803287084828435 305 21559614680403017868 306 22275183135849597746 307 23012058093705545514 308 23770801679403839567 309 24551988953760330140 310 25356208167305007576 311 26184061018767250886 312 27036162917769163016 313 27913143251781626136 314 28815645657398240576 315 29744328295982844765 316 30699864133746850692 317 31682941226313170014 318 32694263007824049996 319 33734548584650685993 320 34804533033763028185 321 35904967705818754764 322 37036620533030941758 323 38200276341874521172 324 39396737170692184141 325 40626822592260954336 326 41891370041381228952 327 43191235147550660248 328 44527292072785829814 329 45900433854655250520 330 47311572754587817468 331 48761640611521419231 332 50251589200957014234 333 51782390599484074322 334 53355037554843898380 335 54970543861597903331 336 56629944742468607951 337 58334297235421636716 338 60084680586557686346 339 61882196648884016846 340 63727970287035651675 341 65623149788017098212 342 67568907278036029944 343 69566439145501005786 344 71616966470255939668 345 73721735459124675000 346 75882017887839663864 347 78099111549429399793 348 80374340709139905792 349 82709056565966235846 350 85104637720870608556 351 87562490651764455757 352 90084050195332337013 353 92670780035776342764 354 95324173200560284630 355 98045752563233650968 356 100837071353415989241 357 103699713674023064104 358 106635295025816831352 359 109645462839361963020 360 112731897014472357986 361 115896310467231775416 362 119140449684673435316 363 122466095287204141331 364 125875062598859195766 365 129369202225475095610 366 132950400640867721132 367 136620580781104455399 368 140381702646959403851 369 144235763914641617868 370 148184800554886965090 371 152230887460505032114 372 156376139082473192103 373 160622710074670720812 374 164972795947346599576 375 169428633729415402926 376 173992502639676431712 377 178666724767052019928 378 183453665759941714864 379 188355735524789805765 380 193375388933964455868 381 198515126543047476526 382 203777495317634570124 383 209165089369746660657 384 214680550703953727185 385 220326569973313355916 386 226105887245227031406 387 232021292777317996316 388 238075627803435322341 389 244271785329889652336 390 250612710942026895320 391 257101403621246981952 392 263740916572575618254 393 270534358062897809816 394 277484892269962767468 395 284595740142270648455 396 291870180269952434514 397 299311549766755099938 398 306923245163245078732 399 314708723311343900331 400 322671502300310728071 401 330815162384287403692 402 339143346921522474618 403 347659763325391558614 404 356368184027332282675 405 365272447451812919668 406 374376459003454737336 407 383684192066428969794 408 393199689016250221612 409 402927062244089019000 410 412870495193727131496 411 423034243411280200921 412 433422635607813132216 413 444040074734974623126 414 454891039073778136556 415 465980083336657550805 416 477311839782926658797 417 488891019347772627884 418 500722412784914476806 419 512810891823058575968 420 525161410336284131345 421 537779005528492571064 422 550668799132055717048 423 563835998620798592052 424 577285898437453684986 425 591023881235724474616 426 605055419137096993572 427 619386075002539201083 428 634021503719228924014 429 648967453502452121610 430 664229767212814229868 431 679814383688908346671 432 695727339095585028739 433 711974768287969486092 434 728562906191372979090 435 745498089197246247226 436 762786756575323827711 437 780435451902109155516 438 798450824505851374936 439 816839630928165835926 440 835608736402451296440 441 854765116349257904792 442 874315857888761093664 443 894268161370497579821 444 914629341920520730868 445 935406831006133632510 446 956608178018359266764 447 978241051872308293433 448 1000313242625606013897 449 1022832663115041187916 450 1045807350611600470686 451 1069245468494053338852 452 1093155307941253480573 453 1117545289643323736064 454 1142423965531892791320 455 1167800020529552948968 456 1193682274318709426406 457 1220079683129992762584 458 1247001341550407050972 459 1274456484351387857455 460 1302454488336944828106 461 1331004874212065143026 462 1360117308471555128716 463 1389801605309498502771 464 1420067728549510891071 465 1450925793595971429100 466 1482386069406413435562 467 1514458980485257328094 468 1547155108899070137611 469 1580485196313537169668 470 1614460146052332558200 471 1649091025178076659114 472 1684389066595569438468 473 1720365671177490222392 474 1757032409912755393496 475 1794401026077726841281 476 1832483437430465202032 477 1871291738428223156838 478 1910838202468375294764 479 1951135284152982291805 480 1992195621577188405093 481 2034032038641652535916 482 2076657547389214374454 483 2120085350365998403752 484 2164328843007159810345 485 2209401616047477624136 486 2255317457957001690616 487 2302090357401961364316 488 2349734505731145103506 489 2398264299487961442616 490 2447694342948393120660 491 2498039450685057451107 492 2549314650157587331174 493 2601535184329548606426 494 2654716514312110829868 495 2708874322034689783415 496 2764024512942781463739 497 2820183218723208574028 498 2877366800057001908162 499 2935591849400140364226 500 2994875193792374680151 501 3055233897694361345612 502 3116685265853334511128 503 3179246846197545087614 504 3242936432759697607440 505 3307772068629616801368 506 3373772048936377234576 507 3440954923860130739349 508 3509339501673867781932 509 3578944851815350306510 510 3649790307989455010316 511 3721895471301167420481 512 3795280213419468565441 513 3869964679772357461516 514 3945969292773254068686 515 4023314755079028808620 516 4102022052879906182677 517 4182112459221491477904 518 4263607537359171005016 519 4346529144145137773968 520 4430899433448295980030 521 4516740859607299146264 522 4604076180916978246988 523 4692928463148417621207 524 4783321083102937975106 525 4875277732200247268546 526 4968822420101021782092 527 5063979478364181168443 528 5160773564139122805239 529 5259229663893182285100 530 5359373097174588403418 531 5461229520411182534886 532 5564824930745173826019 533 5670185669904203173012 534 5777338428108990502200 535 5886310248017841424146 536 5997128528708290891996 537 6109821029696163060216 538 6224415874992328111176 539 6340941557197438394281 540 6459426941634927805480 541 6579901270522559924022 542 6702394167182812018284 543 6826935640292383633381 544 6953556088171120080093 545 7082286303110642757420 546 7213157475742979859814 547 7346201199449492644848 548 7481449474810394067777 549 7618934714095158226136 550 7758689745794120700216 551 7900747819191571523972 552 8045142608980644175658 553 8191908219920305638264 554 8341079191534754246660 555 8492690502855533711243 556 8646777577206673386846 557 8803376287033166540714 558 8962522958773100064492 559 9124254377773750772415 560 9288607793251965131251 561 9455620923299140977036 562 9625331959931131489266 563 9797779574183393414986 564 9973002921251703263151 565 10151041645678766923740 566 10331935886587049906392 567 10515726282958157139814 568 10702453978959093025896 569 10892160629315734201368 570 11084888404733849224960 571 11280679997368001179389 572 11479578626338670955108 573 11681628043297940766622 574 11886872538044079242316 575 12095356944185371225161 576 12307126644853537224377 577 12522227578467089267148 578 12740706244544971714814 579 12962609709570837429620 580 13187985612908311506093 581 13416882172767596615456 582 13649348192223775852184 583 13885433065287170818872 584 14125186783026114539030 585 14368659939742500647256 586 14615903739200472172476 587 14866970000908615102591 588 15121911166456023797946 589 15380780305902607206546 590 15643631124224006725900 591 15910517967811498454787 592 16181495831027254483119 593 16456620362815339779436 594 16735947873368823153418 595 17019535340853382695150 596 17307440418187788023739 597 17599721439881643615268 598 17896437428930779423992 599 18197648103770676961146 600 18503413885288320952756 601 18813795903892868661432 602 19128856006645530927288 603 19448656764449060959889 604 19773261479297248896480 605 20102734191584822131718 606 20437139687478153420716 607 20776543506347180760429 608 21121011948258945064277 609 21470612081533153661420 610 21825411750360179675286 611 22185479582481909365816 612 22550884996935851556441 613 22921698211862925310056 614 23297990252379344068216 615 23679832958513016524460 616 24067298993204886566082 617 24460461850375636688824 618 24859395863058181365876 619 25264176211596378936243 620 25674878931910392667990 621 26091580923829133749114 622 26514359959490221062828 623 26943294691807894714887 624 27378464663009322398251 625 27819950313239739804876 626 28267832989236868425762 627 28722194953075056218578 628 29183119390979588767239 629 29650690422211620709740 630 30124993108024179369368 631 30606113460689694690126 632 31094138452599511749824 633 31589156025435844303832 634 32091255099416629998960 635 32600525582613750090341 636 33117058380345078694556 637 33640945404640828819566 638 34172279583784664626316 639 34711154871930051598161 640 35257666258792318522545 641 35811909779416907424652 642 36373982524024289835054 643 36943982647932030022716 644 37522009381554478081093 645 38108163040480578018480 646 38702545035630278274264 647 39305257883490034360288 648 39916405216427895611182 649 40536091793088670319256 650 41164423508869665828396 651 41801507406477502467367 652 42447451686566502516018 653 43102365718459157718114 654 43766360050949181181900 655 44439546423187651844043 656 45122037775652762014311 657 45813948261203680867244 658 46515393256219049103162 659 47226489371820622364150 660 47947354465182583361171 661 48678107650927045046196 662 49418869312606269548216 663 50169761114272129984226 664 50930906012133344655756 665 51702428266301015548280 666 52484453452623005464872 667 53277108474607690546809 668 54080521575437627362456 669 54894822350073676181718 670 55720141757450124496620 671 56556612132761357299189 672 57404367199840623085773 673 58263542083631447022252 674 59134273322752245177286 675 60016698882154696210816 676 60910958165876429392497 677 61817192029888590319608 678 62735542795038848206264 679 63666154260090411125460 680 64609171714857618102618 681 65564741953438679483896 682 66533013287546139534564 683 67514135559935637762267 684 68508260157933548006990 685 69515540027064076894026 686 70536129684776405808236 687 71570185234272463117391 688 72617864378435915949411 689 73679326433862973412876 690 74754732344995595742290 691 75844244698357706449242 692 76948027736895007167839 693 78066247374418997497596 694 79199071210155804769368 695 80346668543400431289910 696 81509210388277029258264 697 82686869488605816192408 698 83879820332877246357472 699 85088239169334056347341 700 86312304021161805639636 701 87552194701788535619902 702 88808092830294173254348 703 90080181846930308281689 704 91368647028750975493545 705 92673675505355076379468 706 93995456274741077127006 707 95334180219274622689284 708 96690040121769709362397 709 98063230681684061052480 710 99453948531429357157656 711 100862392252796962743176 712 102288762393499814448966 713 103733261483831118337496 714 105196094053440518666396 715 106677466648228399354575 716 108177587847358982702762 717 109696668280392892729394 718 111234920644539853290636 719 112792559722032193969043 720 114369802397619839538975 721 115966867676187461648364 722 117583976700494474195818 723 119221352769038556729342 724 120879221354043393048171 725 122557810119571315052356 726 124257348939761544755832 727 125978069917194730257738 728 127720207401384474353764 729 129483998007396557364280 730 131269680634596558658968 731 133077496485526584268641 732 134907689084911810893904 733 136760504298797559547302 734 138636190353817615000620 735 140534997856594510152061 736 142457179813272497379141 737 144402991649183931902316 738 146372691228649795151606 739 148366538874915089103816 740 150384797390219835541385 741 152427732076006417175432 742 154495610753264000575224 743 156588703783010783854076 744 158707284086914815077618 745 160851627168054130384440 746 163022011131816963841364 747 165218716706942784096003 748 167442027266704915937862 749 169692228850235507936026 750 171969610183993610386476 751 174274462703377130875287 752 176607080574479437845403 753 178967760715991385644364 754 181356802821249537628290 755 183774509380431367003618 756 186221185702898218202551 757 188697139939686814710924 758 191202683106150102398232 759 193738129104748220538910 760 196303794747990395861616 761 198899999781528558119256 762 201527066907403478836816 763 204185321807444238066741 764 206875093166821827162636 765 209596712697757698771470 766 212350515163388078442252 767 215136838401784855455329 768 217956023350133873691041 769 220808414069071446579468 770 223694357767179923404430 771 226614204825643137474764 772 229568308823062569924213 773 232557026560435066158032 774 235580718086292945229656 775 238639746722007345704496 776 241734479087255654850142 777 244865285125653871282968 778 248032538130554754500364 779 251236614771012618035575 780 254477895117915626288418 781 257756762670286458409986 782 261073604381752205952844 783 264428810687184374340187 784 267822775529509861557975 785 271255896386693790833196 786 274728574298895077429146 787 278241213895795613064966 788 281794223424103954851651 789 285388014775234409030356 790 289023003513162403201080 791 292699608902457044140722 792 296418253936491761729084 793 300179365365833942929656 794 303983373726814463208968 795 307830713370278026223945 796 311721822490515226061064 797 315657143154377249774198 798 319637121330574141439852 799 323662206919157552429061 800 327732853781188906084541 801 331849519768593908489772 802 336012666754204340523558 803 340222760661988069909264 804 344480271497468225492385 805 348785673378332479513368 806 353139444565233387184696 807 357542067492780736432164 808 361994028800726864220042 809 366495819365345899448440 810 371047934331007895988676 811 375650873141948823008811 812 380305139574237383336766 813 385011241767939634212586 814 389769692259482388394476 815 394581008014216377205215 816 399445710459180160736467 817 404364325516065774068364 818 409337383634387102010546 819 414365419824851978528618 820 419448973692939010686735 821 424588589472680130612764 822 429784816060649882677208 823 435038207050162456770822 824 440349320765677482268616 825 445718720297415600979736 826 451146973536184841103552 827 456634653208418817942173 828 462182336911427790858564 829 467790607148863609717470 830 473460051366399587803468 831 479191261987626341976681 832 484984836450164644602009 833 490841377241996335572172 834 496761491938014346538430 835 502745793236792893265556 836 508794898997578895839501 837 514909432277505690277216 838 521090021369030098918296 839 527337299837593930817496 840 533651906559510987205750 841 540034485760080650945112 842 546485687051929142770044 843 553006165473579530983711 844 559596581528251585163418 845 566257601222892568324050 846 572989896107440065892364 847 579794143314317953758243 848 586671025598166611591567 849 593621231375808491545196 850 600645454766450156405706 851 607744395632121905203982 852 614918759618356108257563 853 622169258195105377585764 854 629496608697901702617080 855 636901534369257685096218 856 644384764400311011095316 857 651947033972713302040504 858 659589084300764490680952 859 667311662673793871952945 860 675115522498788982726336 861 683001423343273468464966 862 690970130978435098886316 863 699022417422505098768781 864 707159060984389964127541 865 715380846307556938062060 866 723688564414174324669782 867 732083012749507823521624 868 740564995226574071305401 869 749135322271052581363368 870 757794810866457275979640 871 766544284599568810412364 872 775384573706128891814178 873 784316515116797800342712 874 793340952503376323930676 875 802458736325293322362451 876 811670723876360140491062 877 820977779331793094625978 878 830380773795505260328364 879 839880585347668794066215 880 849478099092549025407243 881 859174207206611560662476 882 868969808986903643138274 883 878865810899711019408882 884 888863126629491565285735 885 898962677128086929433516 886 909165390664213456866456 887 919472202873233658851566 888 929884056807209500048416 889 940401902985238778027736 890 951026699444075874633520 891 961759411789038162985477 892 972601013245199358260604 893 983552484708871104744366 894 994614814799374096003468 895 1005788999911100029403505 896 1017076044265865700575889 897 1028476959965560547829388 898 1039992767045088960902382 899 1051624493525608672862556 900 1063373175468066558381221 901 1075239857027033166039792 902 1087225590504837316766168 903 1099331436406002104948864 904 1111558463491983643236750 905 1123907748836213896502168 906 1136380377879448954925036 907 1148977444485424100645319 908 1161700050996817026930962 909 1174549308291520573318050 910 1187526335839226344699596 911 1200632261758320586868971 912 1213868222873093695563591 913 1227235364771264740604076 914 1240734841861822391283706 915 1254367817433183633732630 916 1268135463711671675560947 917 1282038961920314437674484 918 1296079502337965037756856 919 1310258284358745674521218 920 1324576516551816326455020 921 1339035416721469683411064 922 1353636211967553734038248 923 1368380138746223436695577 924 1383268442931022906153336 925 1398302379874299553055766 926 1413483214468951617800172 927 1428812221210510545178133 928 1444290684259559650825389 929 1459919897504490535238060 930 1475701164624598705834118 931 1491635799153519872270496 932 1507725124543008384967889 933 1523970474227059291547192 934 1540373191686375490643640 935 1556934630513181467337076 936 1573656154476385099219386 937 1590539137587089026913016 938 1607584964164453087657636 939 1624795028901909315395451 940 1642170736933731015609390 941 1659713503901957428002442 942 1677424756023675494950764 943 1695305930158660258517871 944 1713358473877375413682243 945 1731583845529335550306060 946 1749983514311831621258514 947 1768558960339021179003258 948 1787311674711384927866047 949 1806243159585551144115516 950 1825354928244489520917336 951 1844648505168076000159702 952 1864125426104030158096248 953 1883787238139226716711064 954 1903635499771382757679520 955 1923671780981122220778093 956 1943897663304419273586356 957 1964314739905422144324734 958 1984924615649659014682572 959 2005728907177627574512505 960 2026729242978769845299081 961 2047927263465833884352076 962 2069324621049623986727966 963 2090922980214141006946596 964 2112724017592114427644221 965 2134729422040927807388800 966 2156940894718939244978712 967 2179360149162198502651944 968 2201988911361562435749286 969 2224828919840210381502168 970 2247881925731561164753500 971 2271149692857593383568239 972 2294633997807570642849418 973 2318336630017173409245042 974 2342259391848039165811596 975 2366404098667712550090931 976 2390772578930007164459007 977 2415366674255780752817388 978 2440188239514125442921514 979 2465239142903974758873630 980 2490521266036129113552843 981 2516036504015701496010116 982 2541786765524985074122104 983 2567773972906744438074602 984 2594000062247932215534020 985 2620466983463832794663736 986 2647176700382634896451416 987 2674131190830434743133441 988 2701332446716671574833456 989 2728782474119997271873766 990 2756483293374581845570860 991 2784436939156856565689757 992 2812645460572696498106149 993 2841110921245044231610476 994 2869835399401976578184118 995 2898820987965216036484840 996 2928069794639088813696489 997 2957583941999931206326728 998 2987365567585946145976312 999 3017416823987511721554076 1000 3047739878937943494873426