0 1 1 0 2 64 3 665 4 3431 5 12194 6 34462 7 83187 8 178957 9 352484 10 647516 11 1124045 12 1861939 13 2964870 14 4564666 15 6825959 16 9951257 17 14186312 18 19825912 19 27219969 20 36780031 21 48986090 22 64393814 23 83642075 24 107460901 25 136679724 26 172236052 27 215184437 28 266705867 29 328117454 30 400882546 31 486621135 32 587120689 33 704347280 34 840457136 35 997808489 36 1178973847 37 1386752562 38 1624183822 39 1894559939 40 2201440061 41 2548664180 42 2940367564 43 3380995485 44 3875318371 45 4428447254 46 5045849642 47 5733365687 48 6497224777 49 7344062424 50 8280937576 51 9315350225 52 10455259439 53 11709101690 54 13085809606 55 14594831019 56 16246148437 57 18050298812 58 20018393732 59 22162139909 60 24493860091 61 27026514270 62 29773721314 63 32749780895 64 35969695841 65 39449194784 66 43204755232 67 47253626937 68 51613855687 69 56304307394 70 61344692606 71 66755591315 72 72558478189 73 78775748100 74 85430742076 75 92547773549 76 100152155027 77 108270225062 78 116929375642 79 126158079879 80 135985920121 81 146443616360 82 157563055064 83 169377318305 84 181920713311 85 195228802314 86 209338432822 87 224287768187 88 240116318597 89 256864972364 90 274576027636 91 293293224405 92 313061776939 93 333928406510 94 355941374546 95 379150516079 96 403607273617 97 429364731312 98 456477649552 99 485002499849 100 514997500151 101 546522650450 102 579639768814 103 614412527715 104 650906490781 105 689189149844 106 729329962412 107 771400389437 108 815473933507 109 861626177334 110 909934822666 111 960479729495 112 1013342955689 113 1068608796920 114 1126363827016 115 1186696938609 116 1249699384207 117 1315464817562 118 1384089335462 119 1455671519819 120 1530312480181 121 1608115896540 122 1689188062564 123 1773637929125 124 1861577148251 125 1953120117374 126 2048384024002 127 2147488890687 128 2250557620417 129 2357716042304 130 2469092957696 131 2584820186585 132 2705032614439 133 2829868239330 134 2959468219486 135 3093976921139 136 3233541966797 137 3378314283812 138 3528448153372 139 3684101259789 140 3845434740211 141 4012613234630 142 4185804936314 143 4365181642535 144 4550918805721 145 4743195584904 146 4942194897592 147 5148103471937 148 5361111899327 149 5581414687274 150 5809210312726 151 6044701275675 152 6288094153189 153 6539599653740 154 6799432671956 155 7067812343669 156 7344962101387 157 7631109730062 158 7926487423282 159 8231331839759 160 8545884160241 161 8870390144720 162 9205100190064 163 9550269387945 164 9906157583191 165 10273029432434 166 10651154463182 167 11040807133187 168 11442266890237 169 11855818232244 170 12281750767756 171 12720359276765 172 13171943771939 173 13636809560150 174 14115267304426 175 14607633086199 176 15114228467977 177 15635380556312 178 16171422065192 179 16722691379729 180 17289532620271 181 17872295706810 182 18471336423814 183 19087016485355 184 19719703600661 185 20369771539964 186 21037600200772 187 21723575674437 188 22428090313147 189 23151542797214 190 23894338202786 191 24656888069855 192 25439610470689 193 26242930078560 194 27067278236896 195 27913093028729 196 28780819346567 197 29670908962562 198 30583820599102 199 31520019999699 200 32479980000301 201 33464180600900 202 34473109037564 203 35507259854765 204 36567134978131 205 37653243787494 206 38766103190362 207 39906237695687 208 41074179488057 209 42270468502184 210 43495652497816 211 44750287134945 212 46034936049439 213 47350170928970 214 48696571589366 215 50074726051259 216 51485230617157 217 52928689948812 218 54405717145012 219 55916933819669 220 57462970180331 221 59044465106990 222 60662066231314 223 62316430016175 224 64008221835601 225 65738116055024 226 67506796111952 227 69314954596937 228 71163293334967 229 73052523467154 230 74983365532846 231 76956549552035 232 78972815108189 233 81032911431380 234 83137597481836 235 85287642033789 236 87483823759747 237 89726931315062 238 92017763422922 239 94357128959639 240 96745847040361 241 99184747105080 242 101674669005064 243 104216463089585 244 106810990293071 245 109459122222554 246 112161741245542 247 114919740578187 248 117734024373877 249 120605507812124 250 123535117187876 251 126523790001125 252 129572475046939 253 132682132505790 254 135853734034306 255 139088262856319 256 142386713854337 257 145750093661312 258 149179420752832 259 152675725539609 260 156240050460391 261 159873450075170 262 163576991158814 263 167351752794995 264 171198826470541 265 175119316170084 266 179114338471132 267 183185022639437 268 187332510724787 269 191557957657094 270 195862531342906 271 200247412762215 272 204713796065689 273 209262888672200 274 213895911366776 275 218614098398849 276 223418697580927 277 228310970387562 278 233292192054742 279 238363651679579 280 243526652320421 281 248782511097260 282 254132559292564 283 259578142452405 284 265120620488011 285 270761367777614 286 276501773268722 287 282343240580687 288 288287188107697 289 294335049122064 290 300488271877936 291 306748319715305 292 313116671164439 293 319594820050610 294 326184275599246 295 332886562541379 296 339703221219517 297 346635807693812 298 353685893848652 299 360855067499549 300 368144932500451 301 375557108851350 302 383093232806314 303 390754956981815 304 398543950465481 305 406461898925144 306 414510504718312 307 422691487001937 308 431006581842607 309 439457542327034 310 448046138672966 311 456774158340395 312 465643406143189 313 474655704361020 314 483812892851716 315 493116829163909 316 502569388650107 317 512172464580062 318 521927968254562 319 531837829119519 320 541903994880481 321 552128431617440 322 562513123900064 323 573060074903225 324 583771306522951 325 594648859492674 326 605694793499902 327 616911187303187 328 628300138849517 329 639863765392004 330 651604203607996 331 663523609717485 332 675624159601939 333 687908048923430 334 700377493244186 335 713034728146439 336 725882009352697 337 738921612846312 338 752155834992472 339 765586992659489 340 779217423340511 341 793049485275530 342 807085557573814 343 821328040336635 344 835779354780421 345 850441943360204 346 865318269893492 347 880410819684437 348 895722099648427 349 911254638436974 350 927010986563026 351 942993716526575 352 959205422940689 353 975648722657840 354 992326254896656 355 1009240681368969 356 1026394686407287 357 1043790977092562 358 1061432283382382 359 1079321358239459 360 1097460977760541 361 1115853941305620 362 1134503071627564 363 1153411215002045 364 1172581241357891 365 1192016044407734 366 1211718541779082 367 1231691675145687 368 1251938410359337 369 1272461737581944 370 1293264671418056 371 1314350251047665 372 1335721540359439 373 1357381628084250 374 1379333627929126 375 1401580678711499 376 1424125944493877 377 1446972614718812 378 1470123904344292 379 1493583053979429 380 1517353330020571 381 1541438024787710 382 1565840456661314 383 1590563970219455 384 1615611936375361 385 1640987752515264 386 1666694842636672 387 1692736657486937 388 1719116674702247 389 1745838398946914 390 1772905362053086 391 1800321123160755 392 1828089268858189 393 1856213413322660 394 1884697198461596 395 1913544294054029 396 1942758397892467 397 1972343235925062 398 2002302562398202 399 2032640159999399 400 2063359840000601 401 2094465442401800 402 2125960836075064 403 2157849918908865 404 2190136617952831 405 2222824889562794 406 2255918719546262 407 2289422123308187 408 2323339145997157 409 2357673862651884 410 2392430378348116 411 2427612828345845 412 2463225378236939 413 2499272224093070 414 2535757592614066 415 2572685741276559 416 2610060958483057 417 2647887563711312 418 2686169907664112 419 2724912372419369 420 2764119371580631 421 2803795350427890 422 2843944786068814 423 2884572187590275 424 2925682096210301 425 2967279085430324 426 3009367761187852 427 3051952762009437 428 3095038759164067 429 3138630456816854 430 3182732592183146 431 3227349935682935 432 3272487291095689 433 3318149495715480 434 3364341420506536 435 3411067970259089 436 3458334083745647 437 3506144733877562 438 3554504927862022 439 3603419707359339 440 3652894148640661 441 3702933362745980 442 3753542495642564 443 3804726728383685 444 3856491277267771 445 3908841393997854 446 3961782365841442 447 4015319515790687 448 4069458202722977 449 4124203821561824 450 4179561803438176 451 4235537615852025 452 4292136762834439 453 4349364785109890 454 4407227260259006 455 4465729802881619 456 4524878064760237 457 4584677735023812 458 4645134540311932 459 4706254244939309 460 4768042651060691 461 4830505598836070 462 4893648966596314 463 4957478671009095 464 5022000667245241 465 5087220949145384 466 5153145549387032 467 5219780539651937 468 5287132030793887 469 5355206173006794 470 5424009155993206 471 5493547209133115 472 5563826601653189 473 5634853642796300 474 5706634681991476 475 5779176109024149 476 5852484354206827 477 5926565888550062 478 6001427223933842 479 6077074913279279 480 6153515550720721 481 6230755771778160 482 6308802253530064 483 6387661714786505 484 6467340916262711 485 6547846660752914 486 6629185793304622 487 6711365201393187 488 6794391815096797 489 6878272607271764 490 6963014593728236 491 7048624833406205 492 7135110428551939 493 7222478524894710 494 7310736311823946 495 7399891022566679 496 7489949934365417 497 7580920368656312 498 7672809691247752 499 7765625312499249 500 7859374687500751 501 7954065316252250 502 8049704743843814 503 8146300560635915 504 8243860402440181 505 8342391950700444 506 8441902932674212 507 8542401121614437 508 8643894336951707 509 8746390444476734 510 8849897356523266 511 8954423032151295 512 9059975477330689 513 9166562745125120 514 9274192935876416 515 9382874197389209 516 9492614725116007 517 9603422762342562 518 9715306600373662 519 9828274578719219 520 9942335085280781 521 10057496556538340 522 10173767477737564 523 10291156383077325 524 10409671855897651 525 10529322528867974 526 10650117084175802 527 10772064253715687 528 10895172819278617 529 11019451612741704 530 11144909516258296 531 11271555462448385 532 11399398434589439 533 11528447466807530 534 11658711644268886 535 11790200103371739 536 11922922031938597 537 12056886669408812 538 12192103307031572 539 12328581288059189 540 12466330007940811 541 12605358914516430 542 12745677508211314 543 12887295342230735 544 13030222022755121 545 13174467209135504 546 13320040614089392 547 13466952003896937 548 13615211198597527 549 13764828072186674 550 13915812552813326 551 14068174622977475 552 14221924319728189 553 14377071734861940 554 14533627015121356 555 14691600362394269 556 14851002033913187 557 15011842342455062 558 15174131656541482 559 15337880400639159 560 15503099055360841 561 15669798157666520 562 15837988301065064 563 16007680135816145 564 16178884369132591 565 16351611765383034 566 16525873146294982 567 16701679391158187 568 16879041437028437 569 17057970278931644 570 17238476970068356 571 17420572622018565 572 17604268404946939 573 17789575547808350 574 17976505338553826 575 18165069124336799 576 18355278311719777 577 18547144366881312 578 18740678815823392 579 18935893244579129 580 19132799299420871 581 19331408687068610 582 19531733174898814 583 19733784591153555 584 19937574825150061 585 20143115827490564 586 20350419610272572 587 20559498247299437 588 20770363874291347 589 20983028689096614 590 21197504951903386 591 21413804985451655 592 21631941175245689 593 21851925969766760 594 22073771880686296 595 22297491483079329 596 22523097415638367 597 22750602380887562 598 22980019145397302 599 23211360539999099 600 23444639460000901 601 23679868865402700 602 23917061781112564 603 24156231297162965 604 24397390568927531 605 24640552817338094 606 24885731329102162 607 25132939456920687 608 25382190619706257 609 25633498302801584 610 25886876058198416 611 26142337504756745 612 26399896328424439 613 26659566282457170 614 26921361187638766 615 27185294932501859 616 27451381473548957 617 27719634835473812 618 27990069111383212 619 28262698463019069 620 28537537120980931 621 28814599384948790 622 29093899623906314 623 29375452276364375 624 29659271850585001 625 29945372924805624 626 30233770147463752 627 30524478237421937 628 30817511984193167 629 31112886248166554 630 31410615960833446 631 31710716125013835 632 32013201815083189 633 32318088177199580 634 32625390429531236 635 32935123862484389 636 33247303838931547 637 33561945794440062 638 33879065237501122 639 34198677749759039 640 34520798986240961 641 34845444675586880 642 35172630620280064 643 35502372696877785 644 35834686856242471 645 36169589123773154 646 36507095599637342 647 36847222459003187 648 37189985952272077 649 37535402405311524 650 37883488219688476 651 38234259872902925 652 38587733918621939 653 38943926986913990 654 39302855784483706 655 39664537094906919 656 40028987778866137 657 40396224774386312 658 40766265097071032 659 41139125840339009 660 41514824175660991 661 41893377352796970 662 42274802700033814 663 42659117624423195 664 43046339612019941 665 43436486228120684 666 43829575117502932 667 44225624004664437 668 44624650694062987 669 45026673070356494 670 45431709098643506 671 45839776824704015 672 46250894375240689 673 46665079958120400 674 47082351862616176 675 47502728459649449 676 47926228202032727 677 48352869624712562 678 48782671345012942 679 49215652062878979 680 49651830561121021 681 50091225705659060 682 50533856445767564 683 50979741814320605 684 51428900928037411 685 51881352987728214 686 52337117278540522 687 52796213170205687 688 53258660117285897 689 53724477659421464 690 54193685421578536 691 54666303114297105 692 55142350533939439 693 55621847562938810 694 56104814170048646 695 56591270410591979 696 57081236426711317 697 57574732447618812 698 58071778789846852 699 58572395857498949 700 59076604142501051 701 59584424224853150 702 60095876772881314 703 60610982543490015 704 61129762382414881 705 61652237224475744 706 62178428093830112 707 62708356104226937 708 63242042459260807 709 63779508452626434 710 64320775468373566 711 64865864981162195 712 65414798556518189 713 65967597851089220 714 66524284612901116 715 67084880681614509 716 67649407988781907 717 68217888558105062 718 68790344505692762 719 69366798040318919 720 69947271463681081 721 70531787170659240 722 71120367649575064 723 71713035482451425 724 72309813345272351 725 72910724008243274 726 73515790336051702 727 74125035288128187 728 74738481918907717 729 75356153378091404 730 75978072910908596 731 76604263858379285 732 77234749657576939 733 77869553841891630 734 78508700041293586 735 79152211982597039 736 79800113489724497 737 80452428483971312 738 81109180984270672 739 81770395107458889 740 82436095068541111 741 83106305180957330 742 83781049856848814 743 84460353607324835 744 85144241042729821 745 85832736872910804 746 86525865907485292 747 87223653056109437 748 87926123328746627 749 88633301835936374 750 89345213789063626 751 90061884500628375 752 90783339384515689 753 91509603956266040 754 92240703833346056 755 92976664735419569 756 93717512484619087 757 94463273005817562 758 95213972326900582 759 95969636579038859 760 96730291996961141 761 97495964919227420 762 98266681788502564 763 99042469151830245 764 99823353660907291 765 100609362072358334 766 101400521248010882 767 102196858155170687 768 102998399866897537 769 103805173562281344 770 104617206526718656 771 105434526152189465 772 106257159937534439 773 107085135488732450 774 107918480519178526 775 108757222849962099 776 109601390410145677 777 110451011237043812 778 111306113476502492 779 112166725383178829 780 113032875320821171 781 113904591762549510 782 114781903291136314 783 115664838599287655 784 116553426489924761 785 117447695876465864 786 118347675783108472 787 119253395345111937 788 120164883809080447 789 121082170533246314 790 122005284987753686 791 122934256754942555 792 123869115529633189 793 124809891119410860 794 125756613444910996 795 126709312540104629 796 127668018552584267 797 128632761743850062 798 129603572489596402 799 130580481279998799 800 131563518720001201 801 132552715529603600 802 133548102544150064 803 134549710714617065 804 135557571107902231 805 136571714907113394 806 137592173411858062 807 138618978038533187 808 139652160320615357 809 140691751908951284 810 141737784572048716 811 142790290196367645 812 143849300786611939 813 144914848466021270 814 145986965476663466 815 147065684179727159 816 148151037055814857 817 149243056705236312 818 150341775848302312 819 151447227325618769 820 152559444098381231 821 153678459248669690 822 154804305979743814 823 155937017616338475 824 157076627604959701 825 158223169514180924 826 159376677034939652 827 160537183980834437 828 161704724288422267 829 162879332017516254 830 164061041351483746 831 165249886597544735 832 166445902187070689 833 167649122675883680 834 168859582744555936 835 170077317198709689 836 171302360969317447 837 172534749113002562 838 173774516812340222 839 175021699376158739 840 176276332239841261 841 177538450965627780 842 178808091242917564 843 180085288888571885 844 181370079847217171 845 182662500191548454 846 183962586122633242 847 185270373970215687 848 186585900193021177 849 187909201379061224 850 189240314245938776 851 190579275641153825 852 191926122542409439 853 193280892057918090 854 194643621426708406 855 196014348018932219 856 197393109336172037 857 198779943011748812 858 200174886811030132 859 201577978631738709 860 202989256504261291 861 204408758591957870 862 205836523191471314 863 207272588733037295 864 208716993780794641 865 210169777033095984 866 211630977322818832 867 213100633617676937 868 214578785020532087 869 216065470769706194 870 217560730239293806 871 219064602939474915 872 220577128516828189 873 222098346754644500 874 223628297573240876 875 225167021030274749 876 226714557321058627 877 228270946778875062 878 229836229875292042 879 231410447220478679 880 232993639563521321 881 234585847792739960 882 236187112936005064 883 237797476161054705 884 239416978775812111 885 241045662228703514 886 242683568108976422 887 244330738147018187 888 245987214214674997 889 247653038325571164 890 249328252635428836 891 251012899442388005 892 252707021187326939 893 254410660454182910 894 256123859970273346 895 257846662606617279 896 259579111378257217 897 261321249444581312 898 263073120109645952 899 264834766822498649 900 266606233177501351 901 268387562914654050 902 270178799919918814 903 271979988225544115 904 273791172010389581 905 275612395600251044 906 277443703468186012 907 279285140234839437 908 281136750668769907 909 282998579686776134 910 284870672354223866 911 286753073885373095 912 288645829643705689 913 290548985142253320 914 292462586043925816 915 294386678161839809 916 296321307459647807 917 298266520051867562 918 300222362204211862 919 302188880333918619 920 304166121010081381 921 306154130953980140 922 308152957039412564 923 310162646293025525 924 312183245894647051 925 314214803177618574 926 316257365629127602 927 318310980890540687 928 320375696757736817 929 322451561181441104 930 324538622267558896 931 326636928277510185 932 328746527628564439 933 330867468894175730 934 332999800804318286 935 335143572245822339 936 337298832262710397 937 339465630056533812 938 341644014986709772 939 343834036570858589 940 346035744485141411 941 348249188564598230 942 350474418803486314 943 352711485355618935 944 354960438534704521 945 357221328814686104 946 359494206830081192 947 361779123376321937 948 364076129410095727 949 366385276049686074 950 368706614575313926 951 371040196429479275 952 373386073217303189 953 375744296706870140 954 378114918829570756 955 380497991680444869 956 382893567518524987 957 385301698767180062 958 387722438014459682 959 390155838013438559 960 392601951682561441 961 395060832105988320 962 397532532533940064 963 400017106383044345 964 402514607236681991 965 405025088845333634 966 407548605126926782 967 410085210167183187 968 412634958219966637 969 415197903707631044 970 417774101221368956 971 420363605521560365 972 422966471538121939 973 425582754370856550 974 428212509289803226 975 430855791735587399 976 433512657319771577 977 436183161825206312 978 438867361206381592 979 441565311589778529 980 444277069274221471 981 447002690731230410 982 449742232605373814 983 452495751714621755 984 455263305050699461 985 458044949779441164 986 460840743241144372 987 463650742950924437 988 466475006599069547 989 469313592051396014 990 472166557349603986 991 475033960711633455 992 477915860532020689 993 480812315382254960 994 483723384011135696 995 486649125345129929 996 489589598488730167 997 492544862724812562 998 495514977514995502 999 498500002499998499 1000 501499997500001501