0 1 1 12 2 132 3 847 4 3921 5 14506 6 45402 7 124707 8 308407 9 699766 10 1477686 11 2936517 12 5540107 13 9993192 14 17333536 15 29048541 16 47220357 17 74703832 18 115341952 19 174223731 20 257989821 21 375191422 22 536708382 23 756232687 24 1050823851 25 1441543026 26 1954172962 27 2620031257 28 3476884647 29 4569972396 30 5953147156 31 7690141977 32 9855972457 33 12538483332 34 15840049116 35 19879438711 36 24793854217 37 30741154482 38 37902274242 39 46483850011 40 56721064191 41 68880719182 42 83264553582 43 100212812877 44 120108087331 45 143379430096 46 170506768872 47 202025624757 48 238532152237 49 280688514576 50 329228609176 51 384964157787 52 448791176757 53 521696842822 54 604766770246 55 699192715431 56 806280725427 57 927459747082 58 1064290713882 59 1218476127841 60 1391870154111 61 1586489246292 62 1804523320732 63 2048347498417 64 2320534433361 65 2623867246716 66 2961353086132 67 3336237330207 68 3752018458177 69 4212463605306 70 4721624824746 71 5283856076947 72 5903830968007 73 6586561258662 74 7337416165926 75 8162142479701 76 9066885516987 77 10058210936632 78 11143127437872 79 12329110366221 80 13624126250581 81 15036658295752 82 16575732854832 83 18250946906307 84 20072496560941 85 22051206623886 86 24198561237742 87 26526735632607 88 29048629009467 89 31777898583586 90 34728994814866 91 37917197852457 92 41358655221207 93 45070420777852 94 49070494965156 95 53377866392521 96 58012554771897 97 62995655238132 98 68349384083212 99 74097125934151 100 80263482404601 101 86874322250562 102 93956833060882 103 101539574513547 104 109652533229071 105 118327179252606 106 127596524196702 107 137495181076957 108 148059425873107 109 159327260848416 110 171338479660536 111 184134734297317 112 197759603871357 113 212258665307392 114 227679565956936 115 244072098174891 116 261488275893157 117 279982413226582 118 299611205146902 119 320433810260631 120 342511935727171 121 365909924353722 122 390694843903882 123 416936578657137 124 444707923256751 125 474084678883876 126 505145751796012 127 537973254268257 128 572652607976097 129 609272649858796 130 647925740502756 131 688707875084527 132 731718796913457 133 777062113614282 134 824845415990266 135 875180399607811 136 928182989143767 137 983973465536982 138 1042676595985942 139 1104421766834661 140 1169343119389291 141 1237579688708232 142 1309275545408832 143 1384579940534077 144 1463647453522981 145 1546638143328696 146 1633717702728672 147 1725057615871507 148 1820835319105437 149 1921234365133726 150 2026444590542526 151 2136662286747087 152 2252090374402507 153 2372938581325522 154 2499423623974146 155 2631769392532281 156 2770207139646727 157 2914975672864332 158 3066321550817332 159 3224499283205241 160 3389771534621961 161 3562409332277092 162 3742692277660732 163 3930908762201367 164 4127356186966761 165 4332341186458066 166 4546179856547682 167 4769197986611707 168 5001731295908127 169 5244125674252206 170 5496737427040846 171 5759933524677997 172 6034091856453507 173 6319601488928112 174 6616862928877576 175 6926288390849301 176 7248302069385037 177 7583340415963632 178 7931852420718072 179 8294299898981371 180 8671157782716181 181 9062914416883302 182 9470071860804582 183 9893146194576007 184 10332667830587091 185 10789181830202986 186 11263248225666042 187 11755442347273857 188 12266355155891167 189 12796593580853236 190 13346780863318716 191 13917556905130257 192 14509578623241457 193 15123520309769052 194 15760073997729556 195 16419949832519871 196 17103876449201697 197 17812601355649882 198 18546891321625162 199 19307532773832051 200 20095332197022951 201 20911116541209862 202 21755733635045382 203 22630052605434997 204 23534964303442971 205 24471381736554456 206 25440240507356752 207 26442499258702957 208 27479140125421557 209 28551169192635816 210 29659616960757136 211 30805538817216867 212 31990015515001357 213 33214153658055342 214 34479086193619086 215 35785972911564991 216 37136000950799707 217 38530385312798082 218 39970369382335602 219 41457225455486281 220 42992255274953271 221 44576790572799772 222 46212193620648132 223 47899857787415337 224 49641208104653401 225 51437701839563476 226 53290829075752812 227 55202113301804007 228 57173112007726297 229 59205417289358946 230 61300656460797106 231 63460492674910827 232 65686625552028207 233 67980791816853982 234 70344765943695166 235 72780360810065661 236 75289428358742067 237 77873860268343232 238 80535588632506392 239 83276586647733061 240 86098869309978141 241 89004494120056032 242 91995561797937832 243 95074217006014027 244 98242649081397381 245 101503092777341046 246 104857829013847222 247 108309185637542007 248 111859538190892387 249 115511310690841626 250 119266976416939626 251 123129058709045137 252 127100131774677007 253 131182821506091972 254 135379806307166796 255 139693817930162881 256 144127642322451777 257 148684120483280332 258 153366149330654532 259 158176682578421391 260 163118731623628561 261 168195366444241642 262 173409716507299482 263 178764971687588067 264 184264383196913911 265 189911264524058166 266 195708992385492982 267 201661007686941957 268 207770816495866827 269 214041991024962856 270 220478170626745696 271 227083062799312797 272 233860444203362757 273 240814161690556312 274 247948133343302976 275 255266349526057651 276 262772873948211837 277 270471844738664382 278 278367475532157022 279 286464056567460271 280 294765955797495531 281 303277620011479602 282 312003575969178082 283 320948431547354457 284 330116876898501991 285 339513685621945836 286 349143715947403092 287 359011911931088857 288 369123304664456617 289 379483013495661636 290 390096247263836316 291 400968305546266807 292 412104579918560457 293 423510555227894002 294 435191810879432706 295 447154022136010971 296 459402961431165247 297 471944499695610382 298 484784607697250862 299 497929357394818701 300 511384923305230051 301 525157583884752912 302 539253722924078632 303 553679830957390197 304 568442506685520621 305 583548458413295056 306 599004505501150552 307 614817579831127707 308 630994727287328757 309 647543109250936966 310 664470004109892486 311 681782808783320167 312 699489040260805107 313 717596337156612042 314 736112461278944986 315 755045299214343841 316 774402863927315007 317 794193296375293332 318 814424867139033052 319 835105978068525681 320 856245163944543121 321 877851094155904572 322 899932574392566132 323 922498548354632287 324 945558099477388801 325 969120452672456826 326 993194976085168362 327 1017791182868263507 328 1042918732972010247 329 1068587434950847846 330 1094807247786655206 331 1121588282728745877 332 1148940805150691707 333 1176875236424077432 334 1205402155809288816 335 1234532302363437261 336 1264276576865524117 337 1294646043758948232 338 1325651933111460592 339 1357305642592670211 340 1389618739469205741 341 1422602962617637582 342 1456270224555265582 343 1490632613488877727 344 1525702395381585531 345 1561492016037842146 346 1598014103206749522 347 1635281468703761257 348 1673307110550888087 349 1712104215135513276 350 1751686159387925476 351 1792066512977676937 352 1833259040528875257 353 1875277703854517172 354 1918136664209973196 355 1961850284565732231 356 2006433131899515577 357 2051899979507870082 358 2098265809337350482 359 2145545814335401291 360 2193755400821048911 361 2242910190875514942 362 2293026024752861982 363 2344118963310783517 364 2396205290461649811 365 2449301515643922016 366 2503424376314047032 367 2558590840458945957 368 2614818109129209277 369 2672123618993112256 370 2730525044911564296 371 2790040302534106347 372 2850687550916070757 373 2912485195157018262 374 2975451889060567126 375 3039606537815729751 376 3104968300699872387 377 3171556593803413882 378 3239391092776379722 379 3308491735596927921 380 3378878725361963631 381 3450572533099959652 382 3523593900606100332 383 3597963843299866657 384 3673703653105180641 385 3750834901353227436 386 3829379441708073892 387 3909359413115202607 388 3990797242773080817 389 4073715649127883786 390 4158137644891492666 391 4244086540082887107 392 4331585945093053207 393 4420659773773527702 394 4511332246548699606 395 4603627893551990821 396 4697571557786037547 397 4793188398306994632 398 4890503893433085312 399 4989543843977519101 400 5090334376505900901 401 5192901946618254712 402 5297273342255785632 403 5403475687032504147 404 5511536443591837021 405 5621483416988349406 406 5733344758094703102 407 5847148967033976207 408 5962924896637469707 409 6080701755928126866 410 6200509113629691586 411 6322376901701732217 412 6446335418900657607 413 6572415334366852492 414 6700647691238059636 415 6831063910289136441 416 6963695793598314057 417 7098575528240087332 418 7235735690004864252 419 7375209247145503831 420 7517029564150871721 421 7661230405546543122 422 7807845939722782882 423 7956910742789932987 424 8108459802461337951 425 8262528521963938926 426 8419152723976667662 427 8578368654596771757 428 8740212987334202947 429 8904722827134200496 430 9071935714428202056 431 9241889629213214677 432 9414622995159778957 433 9590174683748659632 434 9768584018436396216 435 9949890778849847611 436 10134135205009864917 437 10321358001584226982 438 10511600342169973542 439 10704903873605271111 440 10901310720310947091 441 11100863488661827882 442 11303605271388017082 443 11509579652006250177 444 11718830709281462431 445 11931403021718706996 446 12147341672085560572 447 12366692251965154257 448 12589500866339967537 449 12815814138206523676 450 13045679213221125076 451 13279143764376767487 452 13516255996711372257 453 13757064652047476122 454 14001619013763518346 455 14249968911596865331 456 14502164726478713127 457 14758257395401008582 458 15018298416315530182 459 15282339853065269941 460 15550434340348258011 461 15822635088713971992 462 16098995889592473232 463 16379571120356412717 464 16664415749416049461 465 16953585341347424616 466 17247136062053834832 467 17545124683960748707 468 17847608591244310477 469 18154645785093575406 470 18466294889006621646 471 18782615154120683647 472 19103666464576452507 473 19429509342916688962 474 19760204955519295026 475 20095815118064990601 476 20436402301039741687 477 20782029635272087132 478 21132760917505511172 479 21488660616006009321 480 21849793876204995481 481 22216226526377698452 482 22588025083357196332 483 22965256758284237607 484 23347989462392998041 485 23736291812832922786 486 24130233138526803442 487 24529883486065240107 488 24935313625637638767 489 25346595056999894686 490 25763800015478912766 491 26187001478014116157 492 26616273169236094707 493 27051689567582545152 494 27493325911451655256 495 27941258205393084421 496 28395563226336693597 497 28856318529859177632 498 29323602456488753512 499 29797494138048058251 500 30278073504035410501 501 30765421288044590262 502 31259619034223291382 503 31760749103770401847 504 32268894681472267171 505 32784139782278092506 506 33306569257914639402 507 33836268803540373457 508 34373324964439219407 509 34917825142754080516 510 35469857604260279436 511 36029511485179078017 512 36596876799031433857 513 37172044443532151692 514 37755106207524588036 515 38346154777956067791 516 38945283746894171857 517 39552587618584055082 518 40168161816546954202 519 40792102690720045731 520 41424507524637814071 521 42065474542655090422 522 42715102917211923382 523 43373492776140442437 524 44040745210013875851 525 44716962279537884776 526 45402247022984375712 527 46096703463667953757 528 46800436617465179397 529 47513552500376791896 530 48236158136133062656 531 48968361563842442227 532 49710271845683664957 533 50461999074641475582 534 51223654382286142366 535 51995349946596921711 536 52777198999829639467 537 53569315836428554482 538 54371815820982670242 539 55184815396226660761 540 56008432091086577191 541 56842784528770501932 542 57687992434904317332 543 58544176645712756377 544 59411459116245903081 545 60289962928651310596 546 61179812300491905372 547 62081132593109846007 548 62994050320036505737 549 63918693155448747826 550 64855189942671663426 551 65803670702727941787 552 66764266642934043007 553 67737110165543343822 554 68722334876436427246 555 69720075593858687181 556 70730468357205419427 557 71753650435854570832 558 72789760338047318632 559 73838937819816652341 560 74901323893964130861 561 75977060839084987792 562 77066292208641758232 563 78169162840086600667 564 79285818864032487861 565 80416407713473440966 566 81561078133053981382 567 82719980188387975207 568 83893265275427045427 569 85081086129878727306 570 86283596836674542746 571 87500952839488169697 572 88733310950303883007 573 89980829359035443412 574 91243667643195611676 575 92521986777616465201 576 93815949144220694737 577 95125718541844059132 578 96451460196109176372 579 97793340769350829471 580 99151528370592966081 581 100526192565577571002 582 101917504386845591082 583 103325636343870092307 584 104750762433241829191 585 106193058148907406886 586 107652700492460216742 587 109129867983484326357 588 110624740669951505467 589 112137500138671569336 590 113668329525796221616 591 115217413527376578957 592 116784938409974559957 593 118371092021328321352 594 119976063801071924656 595 121600044791509416771 596 123243227648443508397 597 124905806652059034382 598 126587977717861380462 599 128289938407670061151 600 130011887940667633851 601 131754027204504134562 602 133516558766457220882 603 135299686884648208297 604 137103617519314186071 605 138928558344136399356 606 140774718757625084452 607 142642309894560944457 608 144531544637493452857 609 146442637628296172916 610 148375805279779281036 611 150331265787359482567 612 152309239140787508857 613 154309947135933384642 614 156333613386629655186 615 158380463336572762891 616 160450724271282763407 617 162544625330121571582 618 164662397518369927902 619 166804273719363276381 620 168970488706686745171 621 171161279156429421472 622 173376883659498112632 623 175617542733990785637 624 177883498837629877501 625 180174996380255669376 626 182492281736379917512 627 184835603257799934507 628 187205211286273314597 629 189601358166253497046 630 192024298257686362006 631 194474287948868053527 632 196951585669364224707 633 199456451902990900282 634 201989149200857152266 635 204549942194469784561 636 207139097608900222767 637 209756884276013805732 638 212403573147761675692 639 215079437309535464161 640 217784751993584971041 641 220519794592499034732 642 223284844672749791332 643 226080183988300521327 644 228906096494277282481 645 231762868360704527946 646 234650787986304908922 647 237570146012363461507 648 240521235336656377687 649 243504351127444560726 650 246519790837532165526 651 249567854218390324837 652 252648843334346262507 653 255763062576837995272 654 258910818678734824896 655 262092420728723822781 656 265308180185762509477 657 268558410893597931832 658 271843429095352340832 659 275163553448175673491 660 278519105037965042461 661 281910407394151437342 662 285337786504553841982 663 288801570830300972367 664 292302091320820840011 665 295839681428898346066 666 299414677125801111682 667 303027416916473750457 668 306678241854800789127 669 310367495558938442956 670 314095524226715452596 671 317862676651103189497 672 321669304235755237257 673 325515761010616656612 674 329402403647603142076 675 333329591476350278551 676 337297686500033106537 677 341307053411256204882 678 345358059608014500322 679 349451075209725013371 680 353586473073329750431 681 357764628809469952302 682 361985920798731909582 683 366250730207964555757 684 370559441006669049091 685 374912439983460554736 686 379310116762602438792 687 383752863820613086357 688 388241076502945555917 689 392775153040740282736 690 397355494567651044216 691 401982505136744400507 692 406656591737472823957 693 411378164312721731302 694 416147635775930632806 695 420965422028288612871 696 425831941976004356947 697 430747617547650939882 698 435712873711585591162 699 440728138493444652801 700 445793842993713945951 701 450910421405374762612 702 456078311031625699132 703 461297952303680548497 704 466569788798642468721 705 471894267257454644956 706 477271837602927663252 707 482702952957843814207 708 488188069663138545057 709 493727647296159279066 710 499322148689001821386 711 504972039946924570867 712 510677790466840757607 713 516439872955888926342 714 522258763450081886086 715 528134941333034346741 716 534068889354769463707 717 540061093650604511832 718 546112043760115910352 719 552222232646183820781 720 558392156714116540021 721 564622315830854911272 722 570913213344256975632 723 577265356102463087587 724 583679254473341717901 725 590155422364016167726 726 596694377240472418062 727 603296640147248339007 728 609962735727204483547 729 616693192241376690946 730 623488541588910725106 731 630349319327079173577 732 637276064691380833207 733 644269320615722808732 734 651329633752685550916 735 658457554493871061161 736 665653636990334489817 737 672918439173099355732 738 680252522773756614892 739 687656453345147806311 740 695130800282132503641 741 702676136842440301282 742 710293040167607564082 743 717982091303999170027 744 725743875223915475631 745 733578980846784734046 746 741488001060441196222 747 749471532742489125757 748 757530176781752958387 749 765664538099813837376 750 773875225672632756376 751 782162852552260541637 752 790528035888634905757 753 798971396951464805472 754 807493561152202336296 755 816095158066102397131 756 824776821454370358277 757 833539189286397966582 758 842382903762087721782 759 851308611334265958391 760 860316962731184867811 761 869408612979113695642 762 878584221425019349482 763 887844451759336652817 764 897189972038828480911 765 906621454709536014916 766 916139576629819350732 767 925745019093488699457 768 935438467853026416577 769 945220613142900097356 770 955092149702966976196 771 965053776801969868047 772 975106198261124890257 773 985250122477801203562 774 995486262449293011226 775 1005815335796684055651 776 1016238064788804852087 777 1026755176366282899382 778 1037367402165686108022 779 1048075478543759686021 780 1058880146601756723531 781 1069782152209862717352 782 1080782246031714276832 783 1091881183549012252957 784 1103079725086229532741 785 1114378635835413741336 786 1125778685881085094592 787 1137280650225229645107 788 1148885308812388165117 789 1160593446554840909886 790 1172405853357888505566 791 1184323324145229205807 792 1196346658884432761707 793 1208476662612511150002 794 1220714145461586404706 795 1233059922684655797721 796 1245514814681454614247 797 1258079647024416769132 798 1270755250484733510612 799 1283542461058510458201 800 1296442119993023221801 801 1309455073813071849412 802 1322582174347434351132 803 1335824278755419547447 804 1349182249553519490121 805 1362656954642161704306 806 1376249267332561500802 807 1389960066373674607707 808 1403790235979250371007 809 1417740665854985773966 810 1431812251225780525486 811 1446005892863093467917 812 1460322497112400555107 813 1474762975920754651792 814 1489328246864447405736 815 1504019233176773444341 816 1518836863775897147757 817 1533782073292822250832 818 1548855802099464526552 819 1564058996336827803931 820 1579392607943283573621 821 1594857594682954434822 822 1610454920174201637382 823 1626185553918216973287 824 1642050471327719272051 825 1658050653755755754826 826 1674187088524608502362 827 1690460768954806292257 828 1706872694394242061247 829 1723423870247396248596 830 1740115308004666276956 831 1756948025271802427377 832 1773923045799450365457 833 1791041399512800575932 834 1808304122541344963316 835 1825712257248740876511 836 1843266852262782815617 837 1860968962505482079482 838 1878819649223254612842 839 1896819980017217312211 840 1914971028873593049991 841 1933273876194224676582 842 1951729608827198260582 843 1970339320097575827477 844 1989104109838237857531 845 2008025084420835803896 846 2027103356786854892272 847 2046340046478787463757 848 2065736279671417122837 849 2085293189203213952776 850 2105011914607841060976 851 2124893602145772717187 852 2144939404836024347757 853 2165150482487994649422 854 2185528001733420086446 855 2206073136058442035231 856 2226787065835786840827 857 2247670978357059050082 858 2268726067865148086482 859 2289953535586748632041 860 2311354589764994981911 861 2332930445692209637692 862 2354682325742766405732 863 2376611459406068267017 864 2398719083319640285561 865 2421006441302337822516 866 2443474784387670323532 867 2466125370857240947207 868 2488959466274302302777 869 2511978343517428565506 870 2535183282814304238546 871 2558575571775629830347 872 2582156505429144717007 873 2605927386253767459262 874 2629889524213853844126 875 2654044236793572921501 876 2678392849031401306387 877 2702936693554736017632 878 2727677110614626124472 879 2752615448120623472421 880 2777753061675752760381 881 2803091314611601241152 882 2828631578023528317832 883 2854375230805995308907 884 2880323659688015655141 885 2906478259268725841686 886 2932840432053077309142 887 2959411588487649627607 888 2986193146996585208067 889 3013186534017645825786 890 3040393184038391230666 891 3067814539632480119857 892 3095452051496093748207 893 3123307178484482452452 894 3151381387648635365356 895 3179676154272073596321 896 3208192961907767155297 897 3236933302415175897132 898 3265898675997414763812 899 3295090591238543602351 900 3324510565140981836401 901 3354160123163048269962 902 3384040799256626301882 903 3414154135904954830147 904 3444501684160545125271 905 3475085003683223952406 906 3505905662778303222102 907 3536965238434876449957 908 3568265316364242305707 909 3599807491038455532616 910 3631593365729005518336 911 3663624552545622798717 912 3695902672475213776357 913 3728429355420923935992 914 3761206240241329839136 915 3794234974789760180691 916 3827517215953746190557 917 3861054629694601663582 918 3894848891087132901502 919 3928901684359478850831 920 3963214702933081720971 921 3997789649462788367122 922 4032628235877082722882 923 4067732183418449567737 924 4103103222683869914951 925 4138743093665448305676 926 4174653545791172295412 927 4210836337965804419257 928 4247293238611906922697 929 4284026025710999544996 930 4321036486844850642556 931 4358326419236901939927 932 4395897629793827196457 933 4433751935147225076882 934 4471891161695446514466 935 4510317145645556855611 936 4549031733055433075167 937 4588036779875996351982 938 4627334151993580294542 939 4666925725272435106861 940 4706813385597367985091 941 4746999028916520035632 942 4787484561284280005832 943 4828271898904335118677 944 4869362968172859303181 945 4910759705721839112496 946 4952464058462537622072 947 4994477983629096600507 948 5036803448822277246037 949 5079442432053339781926 950 5122396921788062204326 951 5165668916990898476487 952 5209260427169276463507 953 5253173472418035902122 954 5297410083464006700346 955 5341972301710727862081 956 5386862179283307332127 957 5432081779073423057332 958 5477633174784465559932 959 5523518450976822319441 960 5569739703113304259761 961 5616299037604714638492 962 5663198571855560635732 963 5710440434309907939967 964 5758026764497378628961 965 5805959713079292643866 966 5854241441894953155082 967 5902874124008076118707 968 5951859943753364322727 969 6001201096783226222406 970 6050899790114639864646 971 6100958242176162201397 972 6151378682855084092507 973 6202163353544731298712 974 6253314507191911765776 975 6304834408344509501101 976 6356725333199225344437 977 6408989569649464934632 978 6461629417333374174672 979 6514647187682022497571 980 6568045203967734235981 981 6621825801352568398702 982 6675991326936947157582 983 6730544139808433348607 984 6785486611090657291291 985 6840821123992393230786 986 6896550073856785707442 987 6952675868210726158857 988 7009200926814380059767 989 7066127681710864905436 990 7123458577276079344516 991 7181196070268683767657 992 7239342629880232658457 993 7297900737785459013652 994 7356872888192711139756 995 7416261587894542133671 996 7476069356318452355097 997 7536298725577785198882 998 7596952240522776475762 999 7658032458791757710251 1000 7719541950862513664751