0 1 1 89 2 814 3 4179 4 15659 5 47775 6 125853 7 296703 8 641058 9 1290718 10 2451449 11 4432792 12 7686042 13 12851762 14 20818302 15 32792898 16 50387031 17 75717831 18 111527416 19 161322161 20 229533997 21 321705945 22 444704195 23 606959145 24 818737920 25 1092450996 26 1442995659 27 1888139134 28 2448944324 29 3150241204 30 4021147020 31 5095638548 32 6413179773 33 8019408453 34 9966885138 35 12315908319 36 15135399487 37 18503861987 38 22510417657 39 27255925347 40 32854185518 41 39433235226 42 47136737901 43 56125472436 44 66578926206 45 78696996742 46 92701806890 47 108839638390 48 127382988915 49 148632757715 50 172920565116 51 200611211229 52 232105279329 53 267841889469 54 308301607999 55 354009518765 56 405538461868 57 463512445968 58 528610240223 59 601569152058 60 683188997064 61 774336267432 62 875948505432 63 989038888552 64 1114701033017 65 1254114022513 66 1408547669046 67 1579368012971 68 1768043069331 69 1976148827751 70 2205375513237 71 2457534115335 72 2734563193210 73 3038535964310 74 3371667684385 75 3736323326736 76 4135025568674 77 4570463093274 78 5045499214614 79 5563180834794 80 6126747741135 81 6739642252063 82 7405519220288 83 8128256401993 84 8911965200853 85 9761001795809 86 10679978661627 87 11673776491377 88 12747556530072 89 13906773328812 90 15157187928883 91 16504881485366 92 17956269339916 93 19518115552476 94 21197547901796 95 23002073364732 96 24939594084405 97 27018423837405 98 29247305010330 99 31635426096055 100 34192439720231 101 36928481208619 102 39854187705969 103 42980717857259 104 46319772062214 105 49883613314130 106 53685088634133 107 57737651112108 108 62055382565638 109 66653016828398 110 71545963679554 111 76750333425822 112 82282962147947 113 88161437623467 114 94404125937732 115 101030198795253 116 108059661543561 117 115513381921861 118 123413119546871 119 131781556148341 120 140642326566852 121 150020050526600 122 159940365195975 123 170429958548850 124 181516603539600 125 193229193104976 126 205597776006064 127 218653593523664 128 232429117020529 129 246958086384009 130 262275549362750 131 278417901811203 132 295422928855803 133 313329846996783 134 332179347159693 135 352013638710799 136 372876494450642 137 394813296600142 138 417871083793737 139 442098599094152 140 467546339043498 141 494266603765506 142 522313548133806 143 551743234021266 144 582613683645511 145 614984934025847 146 648919092566920 147 684480393784545 148 721735257189245 149 760752346343145 150 801602629105971 151 844359439086009 152 889098538311984 153 935898181141924 154 984839179425179 155 1036004968933870 156 1089481677080148 157 1145358191935748 158 1203726232570428 159 1264680420725988 160 1328318353842669 161 1394740679454837 162 1464051170972962 163 1536356804869007 164 1611767839282447 165 1690397894064243 166 1772364032276201 167 1857786843163251 168 1946790526616286 169 2039502979143306 170 2136055881366717 171 2236584787064740 172 2341229213774990 173 2450132734978390 174 2563443073881690 175 2681312198816966 176 2803896420276579 177 2931356489602179 178 3063857699346444 179 3201569985326349 180 3344668030386865 181 3493331369894093 182 3647744498976943 183 3808096981536573 184 3974583561042908 185 4147404273137664 186 4326764560063407 187 4512875386938282 188 4705953359896152 189 4906220846111992 190 5113906095732488 191 5329243365731896 192 5552473045713321 193 5783841785675681 194 6023602625766726 195 6272015128042587 196 6529345510254435 197 6795866781682935 198 7071858881041285 199 7357608816467735 200 7653410807628586 201 7959566429952774 202 8276384761019249 203 8604182529118464 204 8943284264009394 205 9294022449893610 206 9656737680628038 207 10031778817198138 208 10419503147473343 209 10820276548266703 210 11234473649720784 211 11662478002041977 212 12104682244605477 213 12561488277453297 214 13033307435207787 215 13520560663423233 216 14023678697398216 217 14543102243471516 218 15079282162824451 219 15632679657812646 220 16203766460850332 221 16793025025870380 222 17400948722383380 223 18028042032159180 224 18674820748554405 225 19341812178509581 226 20029555347239594 227 20738601205641319 228 21469512840442359 229 22222865687114939 230 22999247745579105 231 23799259798719483 232 24623515633739958 233 25472642266380738 234 26347280168022373 235 27248083495701404 236 28175720325062422 237 29130872886271422 238 30114237802915442 239 31126526333913582 240 32168464618464603 241 33240793924056411 242 34344270897562836 243 35479667819453221 244 36647772861140441 245 37849390345493077 246 39085341010537575 247 40356462276376325 248 41663608515347700 249 43007651325454200 250 44389479807084951 251 45810000843058914 252 47270139382015264 253 48770838725177504 254 50313060816517984 255 51897786536349600 256 53526015998371553 257 55198768850196153 258 56917084577383758 259 58682022811013043 260 60494663638813899 261 62356107919890367 262 64267477603061117 263 66229916048845087 264 68244588355120002 265 70312681686481598 266 72435405607331481 267 74613992418721656 268 76849697498983866 269 79143799648171986 270 81497601436345822 271 83912429555724770 272 86389635176739895 273 88930594308013095 274 91536708160292120 275 94209403514370321 276 96950133093020109 277 99760375936969209 278 102641637784948899 279 105595451457843529 280 108623377246970720 281 111727003306521748 282 114907946050191723 283 118167850552029278 284 121508390951535588 285 124931270863042644 286 128438223789400812 287 132031013540005812 288 135711434653195357 289 139481312823045797 290 143342505330599218 291 147296901479551551 292 151346423036432351 293 155493024675307011 294 159738694427032281 295 164085454133096067 296 168535359904072590 297 173090502582724090 298 177753008211780365 299 182525038506427540 300 187408791331537566 301 192406501183670054 302 197520439677878154 303 202752916039350294 304 208106277599919699 305 213582910299473715 306 219185239192295068 307 224915728958367293 308 230776884419676673 309 236771251061543133 310 242901415559012639 311 249170006308343757 312 255579693963621132 313 262133191978528752 314 268833257153315967 315 275682690186989338 316 282684336234763496 317 289841085470804296 318 297155873656297656 319 304631682712877576 320 312271541301446937 321 320078525406424785 322 328055758925453910 323 336206414264602635 324 344533712939094835 325 353040926179602311 326 361731375544133749 327 370608433535554599 328 379675524224772314 329 388936123879621494 330 398393761599483585 331 408052019955675888 332 417914535637644738 333 427985000104997818 334 438267160245410678 335 448764819038442634 336 459481836225297327 337 470422128984563327 338 481589672613970272 339 492988501218196137 340 504622708402761333 341 516496447974045441 342 528613934645462491 343 540979444749830801 344 553597316957973496 345 566471953003585932 346 579607818414406355 347 593009443249726230 348 606681422844276780 349 620628418558528380 350 634855158535439556 351 649366438463692444 352 664167122347451669 353 679262143282683709 354 694656504240073914 355 710355278854578455 356 726363612221648583 357 742686721700164683 358 759329897722117713 359 776298504609075723 360 793597981395473254 361 811233842658761522 362 829211679356457397 363 847537159670129292 364 866216029856358182 365 885254115104712078 366 904657320402772386 367 924431631408250686 368 944583115328234571 369 965117921805601291 370 986042283812638052 371 1007362518551907925 372 1029085028364400425 373 1051216301645005925 374 1073762913765353175 375 1096731528004049301 376 1120128896484361764 377 1143961861119381864 378 1168237354564709479 379 1192962401178698834 380 1218144117990305200 381 1243789715674572528 382 1269906499535802128 383 1296501870498442608 384 1323583326105741393 385 1351158461526198249 386 1379234970567861342 387 1407820646700506467 388 1436923384085740187 389 1466551178615067727 390 1496712128955966573 391 1527414437606006831 392 1558666411955059506 393 1590476465355633966 394 1622853118201385961 395 1655804999013837672 396 1689340845537351370 397 1723469505842398370 398 1758199939437165070 399 1793541218387537970 400 1829502528445509671 401 1866093170186047959 402 1903322560152470184 403 1941200232010365249 404 1979735837710105629 405 2018939148657991945 406 2058820056896072723 407 2099388576290682073 408 2140654843729738128 409 2182629120328845188 410 2225321792646242619 411 2268743373906643662 412 2312904505234007412 413 2357815956893287332 414 2403488629541199772 415 2449933555486056068 416 2497161899956701901 417 2545184962380607701 418 2594014177671153986 419 2643661117524155631 420 2694137491723669167 421 2745455149457127315 422 2797626080639845065 423 2850662417248941715 424 2904576434666723390 425 2959380553033570666 426 3015087338610376029 427 3071709505150576004 428 3129259915281822894 429 3187751581897341174 430 3247197669557013690 431 3307611495898242918 432 3369006533056632643 433 3431396409096535523 434 3494794909451512108 435 3559215978374746989 436 3624673720399467857 437 3691182401809413357 438 3758756452119395727 439 3827410465566004317 440 3897159202608496188 441 3968017591439920096 442 4040000729508520271 443 4113123885049466506 444 4187402498626957176 445 4262852184686741912 446 4339488733119110760 447 4417328110832396760 448 4496386463337038985 449 4576680116340253185 450 4658225577351357286 451 4741039537297799099 452 4825138872151933699 453 4910540644568598039 454 4997262105533530469 455 5085320696022682935 456 5174734048672473738 457 5265519989461028838 458 5357696539400459793 459 5451281916240226528 460 5546294536181633234 461 5642753015603505802 462 5740676172799099302 463 5840083029724284122 464 5940992813757059487 465 6043424959468443183 466 6147399110404786416 467 6252935120881562841 468 6360053057788680901 469 6468773202407368721 470 6579116052238680907 471 6691102322843676705 472 6804752949695319080 473 6920089090042144380 474 7037132124783752355 475 7155903660358166406 476 7276425530641114044 477 7398719798857277644 478 7522808759503565684 479 7648714940284454764 480 7776461104059452805 481 7906070250802733933 482 8037565619574995658 483 8170970690507589063 484 8306309186798972823 485 8443605076723541979 486 8582882575652882497 487 8724166148089502747 488 8867480509713093142 489 9012850629439365282 490 9160301731491522053 491 9309859297484410236 492 9461549068521407286 493 9615397047304094046 494 9771429500254765266 495 9929672959651829902 496 10090154225778153275 497 10252900369082393275 498 10417938732353382900 499 10585296932907611525 500 10755002864789857401 501 10927084700987023989 502 11101570895655232839 503 11278490186360225829 504 11457871596331129684 505 11639744436727635800 506 11824138308920648503 507 12011083106786454978 508 12200609019014470208 509 12392746531428610368 510 12587526429322348224 511 12784979799807504192 512 12985138034176826817 513 13188032830280416537 514 13393696194916046702 515 13602160446233435923 516 13813458216152525931 517 14027622452795819231 518 14244686422934830941 519 14464683714450709311 520 14687648238809079522 521 14913614233549165470 522 15142616264787244345 523 15374689229734488920 524 15609868359229252570 525 15848189220283852146 526 16089687718645903934 527 16334400101374268034 528 16582362959429656599 529 16833613230279961479 530 17088188200520356920 531 17346125508508233073 532 17607463147013016173 533 17872239465880931353 534 18140493174714764163 535 18412263345568676969 536 18687589415658136512 537 18966511190085009012 538 19249068844577879307 539 19535302928247650622 540 19825254366358481668 541 20118964463114117876 542 20416474904459673676 543 20717827760898922836 544 21023065490327153981 545 21332230940879648517 546 21645367353795838290 547 21962518366299200415 548 22283728014492946815 549 22609040736271566115 550 22938501374248275641 551 23272155178698441379 552 23610047810519023854 553 23952225344204107994 554 24298734270836575149 555 24649621501095975540 556 25004934368282659518 557 25364720631358226118 558 25729028478002347498 559 26097906527686027958 560 26471403834761356339 561 26849569891567810707 562 27232454631555174332 563 27620108432423122077 564 28012582119277536417 565 28409926967803612413 566 28812194707455811071 567 29219437524664720621 568 29631708066060885356 569 30049059441715661776 570 30471545228399161887 571 30899219472855343610 572 31332136695094308360 573 31770351891701865960 574 32213920539166427160 575 32662898597223284136 576 33117342512216339449 577 33577309220477344049 578 34042856151722705014 579 34514041232467923819 580 34990922889459726035 581 35473560053125943463 582 35962012161043209813 583 36456339161422531143 584 36956601516612792378 585 37462860206622261334 586 37975176732658151777 587 38493613120684307152 588 39018231924997066722 589 39549096231819375962 590 40086269662913203158 591 40629816379210324266 592 41179801084461538191 593 41736289028904374751 594 42299346012949357696 595 42869038390884885257 596 43445433074600790805 597 44028597537330646305 598 44618599817412871355 599 45215508522070710705 600 45819392831211143256 601 46430322501242785644 602 47048367868912853619 603 47673599855163244534 604 48306089969005804364 605 48945910311416842780 606 49593133579250959908 607 50247833069174248508 608 50910082681616935413 609 51579956924745526173 610 52257530918454516954 611 52942880398377737847 612 53636081719919391847 613 54337211862304853867 614 55046348432651294257 615 55763569670058191403 616 56488954449717798086 617 57222582287045626386 618 57964533341831016021 619 58714888422407851116 620 59473728989845490502 621 60241137162159976750 622 61017195718545589250 623 61801988103626806750 624 62595598431730744875 625 63398111491180134251 626 64209612748606904964 627 65030188353286443189 628 65859925141492585929 629 66698910640873419909 630 67547233074847950775 631 68404981367023708853 632 69272245145635357828 633 70149114748004372808 634 71035681225019854343 635 71932036345640545074 636 72838272601418115792 637 73754483211041787792 638 74680762124904358512 639 75617204029689697552 640 76563904352981780273 641 77520959267895326281 642 78488465697728110206 643 79466521320635012291 644 80455224574323876411 645 81454674660773243247 646 82464971550972026445 647 83486215989681199695 648 84518509500217562770 649 85561954389259654670 650 86616653751675882121 651 87682711475374931784 652 88760232246178534634 653 89849321552716651074 654 90950085691345145454 655 92062631771086018770 656 93187067718590268423 657 94323502283123444023 658 95472045041573968328 659 96632806403484292513 660 97805897616104955069 661 98991430769471613737 662 100189518801505119987 663 101400275503134705657 664 102623815523444351472 665 103860254374842407268 666 105109708438254533851 667 106372294968340036526 668 107648132098731660436 669 108937338847298917956 670 110240035121435018492 671 111556341723367471140 672 112886380355492430765 673 114230273625732858165 674 115588145052920565090 675 116960119072202214991 676 118346321040469350479 677 119746877241812518579 678 121161914892999564969 679 122591562148978168499 680 124035948108402687390 681 125495202819185388618 682 126969457284072132093 683 128458843466242581348 684 129963494294935012558 685 131483543671095793814 686 133019126473053606682 687 134570378562218482182 688 136137436788805723427 689 137720438997584787267 690 139319524033653197388 691 140934831748235561421 692 142566503004507764721 693 144214679683446413581 694 145879504689703600751 695 147561121957507066237 696 149259676456585826460 697 150975314198121344960 698 152708182240724317935 699 154458428696437148010 700 156226202736762179736 701 158011654598715770424 702 159814935590908270024 703 161636198099649983864 704 163475595595083192169 705 165333282637340300385 706 167209414882728194438 707 169104149089938875163 708 171017643126286446243 709 172950055973970530103 710 174901547736366186309 711 176872279644340407127 712 178862414062595265002 713 180872114496037786822 714 182901545596176629937 715 184950873167545635008 716 187020264174154330866 717 189109886745965466666 718 191219910185399646726 719 193350504973867143546 720 195501842778326964607 721 197674096457873248655 722 199867440070349067280 723 202082048878987707705 724 204318099359081512805 725 206575769204678354481 726 208855237335305816619 727 211156683902723163969 728 213480290297701173384 729 215826239156829903964 730 218194714369354482755 731 220585901084038982758 732 222999985716058470108 733 225437155953919297388 734 227897600766407720148 735 230381510409566913804 736 232889076433702468197 737 235420491690416437197 738 237975950339670020842 739 240555647856874957607 740 243159781040013704503 741 245788548016788482811 742 248442148251799267361 743 251120782553750797371 744 253824653082688686966 745 256553963357264713602 746 259308918262031362725 747 262089724054765707100 748 264896588373822699350 749 267729720245517956350 750 270589330091540114226 751 273475629736392832814 752 276388832414866528539 753 279329152779539914779 754 282296806908311428884 755 285292012311960625125 756 288314987941739612953 757 291365954196994620053 758 294445132932817759783 759 297552747467729082693 760 300689022591388991924 761 303854184572341102392 762 307048461165785623767 763 310272081621383347362 764 313525276691090317152 765 316808278637023265248 766 320121321239355892256 767 323464639804246073056 768 326838471171794068641 769 330243053724031824761 770 333678627392943438222 771 337145433668516871795 772 340643715606826998795 773 344173717838150058495 774 347735686575109603645 775 351329869620854021471 776 354956516377265709634 777 358615877853201988734 778 362308206672767833049 779 366033757083620501304 780 369792784965306149370 781 373585547837628506898 782 377412304869049699998 783 381273316885123302178 784 385168846376959695863 785 389099157509723826919 786 393064516131165434712 787 397065189780181840337 788 401101447695413375757 789 405173560823871536697 790 409281801829599942243 791 413426445102368184201 792 417607766766398649376 793 421826044689126398036 794 426081558489992181931 795 430374589549268685342 796 434705421016920072740 797 439074337821494926740 798 443481626679052660140 799 447927576102123485940 800 452412476408702029341 801 456936619731274665829 802 461500300025880669554 803 466103813081207256319 804 470747456527718605599 805 475431529846818946115 806 480156334380049789593 807 484922173338321397443 808 489729351811178565198 809 494578176776100809658 810 499468957107837043789 811 504402003587774824532 812 509377628913344258782 813 514396147707456652902 814 519457876527977991242 815 524563133877237329238 816 529712240211570186771 817 534905517950897027571 818 540143291488336910556 819 545425887199856399101 820 550753633453953814337 821 556126860621378918685 822 561545901084888115935 823 567011089249035254285 824 572522761549998118860 825 578081256465440700336 826 583686914524411326399 827 589340078317276742874 828 595041092505692231464 829 600790303832607851144 830 606588061132310890360 831 612434715340504617288 832 618330619504423415513 833 624276128792984392593 834 630271600506975549078 835 636317394089280595659 836 642413871135140506227 837 648561395402451894727 838 654760332822102303797 839 661011051508342493287 840 667313921769195816858 841 673669316116904774966 842 680077609278414832641 843 686539178205895590576 844 693054402087299398146 845 699623662356957497082 846 706247342706213784630 847 712925829094096285130 848 719659509758026419055 849 726448775224566158655 850 733294018320203159456 851 740195634182173956969 852 747154020269325318069 853 754169576373013836609 854 761242704628043862939 855 768373809523643857105 856 775563297914481255608 857 782811579031715941708 858 790119064494092409363 859 797486168319070710998 860 804913306933996279404 861 812400899187308714172 862 819949366359789623172 863 827559132175849609692 864 835230622814854495957 865 842964266922490873853 866 850760495622171073786 867 858619742526477642711 868 866542443748647422471 869 874529037914095319691 870 882579966171977858577 871 890695672206796608075 872 898876602250041574950 873 907123205091874654450 874 915435932092853230325 875 923815237195694016076 876 932261576937077229414 877 940775410459491192014 878 949357199523117446754 879 958007408517756484734 880 966726504474794174475 881 975514957079208985803 882 984373238681620101028 883 993301824310376506133 884 1002301191683687154793 885 1011371821221792298149 886 1020514196059176073367 887 1029728802056820444117 888 1039016127814500586212 889 1048376664683121811752 890 1057810906777098125223 891 1067319350986772505106 892 1076902496990879004656 893 1086560847269046765616 894 1096294907114346038736 895 1106105184645876305072 896 1115992190821396592145 897 1125956439449998079145 898 1135998447204819085470 899 1146118733635802536995 900 1156317821182496004571 901 1166596235186894409359 902 1176954503906325489709 903 1187393158526378124399 904 1197912733173873607154 905 1208513764929879967470 906 1219196793842769432873 907 1229962362941319127848 908 1240811018247855104778 909 1251743308791439802338 910 1262759786621103026894 911 1273861006819116552562 912 1285047527514312435687 913 1296319909895445139607 914 1307678718224597565672 915 1319124519850631086593 916 1330657885222679678301 917 1342279387903688246601 918 1353989604583995245011 919 1365789115094959680281 920 1377678502422632602192 921 1389658352721473174340 922 1401729255328109422715 923 1413891802775143758990 924 1426146590805003375540 925 1438494218383835609316 926 1450935287715448371804 927 1463470404255295742404 928 1476100176724508822669 929 1488825217123971948949 930 1501646140748444361090 931 1514563566200727424943 932 1527578115405877506543 933 1540690413625464595923 934 1553901089471876778633 935 1567210774922670653139 936 1580620105334967792382 937 1594129719459897347882 938 1607740259457084894877 939 1621452370909187617092 940 1635266702836475929838 941 1649183907711461640246 942 1663204641473572743546 943 1677329563543874954406 944 1691559336839840072451 945 1705894627790161281187 946 1720336106349615479660 947 1734884446013972746285 948 1749540323834953034385 949 1764304420435230199085 950 1779177420023483455311 951 1794160010409496366749 952 1809252883019303465724 953 1824456732910384604064 954 1839772258786907135119 955 1855200163015016027210 956 1870741151638172008888 957 1886395934392537846488 958 1902165224722412854568 959 1918049739795715739928 960 1934050200519515880009 961 1950167331555613136577 962 1966401861336166305702 963 1982754522079370305147 964 1999226049805182200387 965 2015817184351096170583 966 2032528669387967515941 967 2049361252435885807991 968 2066315684880097284426 969 2083392721986976590246 970 2100593122920047967057 971 2117917650756055992480 972 2135367072501085971730 973 2152942159106734083530 974 2170643685486327382630 975 2188472430531193761306 976 2206429177126981972319 977 2224514712170031815919 978 2242729826583794593584 979 2261075315335303931289 980 2279551977451697075205 981 2298160616036786762833 982 2316902038287683772683 983 2335777055511470255713 984 2354786483141923951848 985 2373931140756293395004 986 2393211852092124210147 987 2412629445064136606022 988 2432184751781154167292 989 2451878608563084049932 990 2471711855957948683828 991 2491685338758969086636 992 2511799906021699893061 993 2532056411081216203821 994 2552455711569352358666 995 2572998669431992737927 996 2593686150946414697175 997 2614519026738683739675 998 2635498171801101031425 999 2656624465509703363675 1000 2677898791641815667926