# Computed using the Mathematica program that I contributed to this sequence 1 3 2 19 3 86 4 263 5 636 6 1309 7 2418 8 4115 9 6584 10 10029 11 14672 12 20773 13 28602 14 38459 15 50672 16 65589 17 83580 18 105037 19 130388 20 160071 21 194554 22 234335 23 279924 24 331865 25 390722 26 457077 27 531544 28 614763 29 707390 30 810113 31 923648 32 1048707 33 1186058 34 1336475 35 1500774 36 1679767 37 1874318 38 2085299 39 2313608 40 2560173 41 2825940 42 3111877 43 3418992 44 3748289 45 4100822 46 4477655 47 4879892 48 5308639 49 5765028 50 6250229 51 6765434 52 7311855 53 7890722 54 8503307 55 9150882 56 9834759 57 10556270 58 11316767 59 12117638 60 12960281 61 13846124 62 14776629 63 15753268 64 16777527 65 17850938 66 18975053 67 20151452 68 21381713 69 22667468 70 24010349 71 25412034 72 26874215 73 28398608 74 29986949 75 31641004 76 33362559 77 35153430 78 37015453 79 38950482 80 40960409 81 43047140 82 45212597 83 47458752 84 49787569 85 52201064 86 54701259 87 57290210 88 59969993 89 62742702 90 65610463 91 68575428 92 71639775 93 74805688 94 78075387 95 81451124 96 84935159 97 88529790 98 92237337 99 96060124 100 100000541 101 104060948 102 108243773 103 112551444 104 116986425 105 121551196 106 126248273 107 131080188 108 136049489 109 141158760 110 146410601 111 151807648 112 157352549 113 163047978 114 168896635 115 174901256 116 181064577 117 187389364 118 193878423 119 200534574 120 207360659 121 214359542 122 221534129 123 228887318 124 236422059 125 244141316 126 252048077 127 260145350 128 268436175 129 276923608 130 285610733 131 294500660 132 303596519 133 312901472 134 322418693 135 332151386 136 342102785 137 352276134 138 362674723 139 373301838 140 384160809 141 395254972 142 406587717 143 418162424 144 429982523 145 442051454 146 454372695 147 466949734 148 479786073 149 492885260 150 506250863 151 519886478 152 533795697 153 547982164 154 562449543 155 577201532 156 592241807 157 607574120 158 623202225 159 639129898 160 655360941 161 671899188 162 688748489 163 705912728 164 723395787 165 741201602 166 759334119 167 777797312 168 796595173 169 815731730 170 835211013 171 855037100 172 875214077 173 895746072 174 916637209 175 937891664 176 959513625 177 981507292 178 1003876917 179 1026626744 180 1049761069 181 1073284208 182 1097200467 183 1121514214 184 1146229833 185 1171351728 186 1196884325 187 1222832078 188 1249199459 189 1275990970 190 1303211151 191 1330864514 192 1358955659 193 1387489172 194 1416469677 195 1445901812 196 1475790249 197 1506139682 198 1536954829 199 1568240418 200 1600001223 201 1632242030 202 1664967647 203 1698182918 204 1731892705 205 1766101884 206 1800815373 207 1836038080 208 1871774979 209 1908031050 210 1944811291 211 1982120738 212 2019964437 213 2058347464 214 2097274923 215 2136751944 216 2176783657 217 2217375248 218 2258531937 219 2300258888 220 2342561373 221 2385444662 222 2428914055 223 2472974850 224 2517632399 225 2562892052 226 2608759205 227 2655239274 228 2702337695 229 2750059928 230 2798411451 231 2847397774 232 2897024435 233 2947296992 234 2998221017 235 3049802108 236 3102045903 237 3154958050 238 3208544229 239 3262810140 240 3317761511 241 3373404084 242 3429743627 243 3486785944 244 3544536845 245 3603002178 246 3662187815 247 3722099648 248 3782743587 249 3844125580 250 3906251583 251 3969127598 252 4032759617 253 4097153688 254 4162315865 255 4228252238 256 4294968915 257 4362472022 258 4430767723 259 4499862198 260 4569761657 261 4640472304 262 4712000403 263 4784352230 264 4857534109 265 4931552322 266 5006413235 267 5082123230 268 5158688697 269 5236116044 270 5314411733 271 5393582222 272 5473634003 273 5554573594 274 5636407535 275 5719142402 276 5802784759 277 5887341228 278 5972818445 279 6059223082 280 6146561811 281 6234841344 282 6324068407 283 6414249768 284 6505392197 285 6597502492 286 6690587487 287 6784654034 288 6879709013 289 6975759320 290 7072811889 291 7170873662 292 7269951603 293 7370052714 294 7471184027 295 7573352558 296 7676565405 297 7780829632 298 7886152389 299 7992540780 300 8100001987 301 8208543194 302 8318171613 303 8428894480 304 8540719059 305 8653652636 306 8767702513 307 8882876028 308 8999180525 309 9116623400 310 9235212053 311 9354953904 312 9475856405 313 9597927042 314 9721173299 315 9845602712 316 9971222825 317 10098041220 318 10226065487 319 10355303234 320 10485762129 321 10617449812 322 10750373993 323 10884542382 324 11019962719 325 11156642778 326 11294590337 327 11433813220 328 11574319259 329 11716116288 330 11859212213 331 12003614942 332 12149332413 333 12296372560 334 12444743379 335 12594452876 336 12745509083 337 12897920030 338 13051693809 339 13206838522 340 13363362287 341 13521273254 342 13680579593 343 13841289510 344 14003411207 345 14166952958 346 14331922995 347 14498329622 348 14666181163 349 14835485952 350 15006252357 351 15178488772 352 15352203593 353 15527405262 354 15704102239 355 15882303014 356 16062016089 357 16243250000 358 16426013307 359 16610314578 360 16796162423 361 16983565478 362 17172532377 363 17363071808 364 17555192475 365 17748903092 366 17944212409 367 18141129198 368 18339662279 369 18539820442 370 18741612531 371 18945047420 372 19150133999 373 19356881190 374 19565297927 375 19775393182 376 19987175955 377 20200655232 378 20415840049 379 20632739490 380 20851362617 381 21071718542 382 21293816409 383 21517665368 384 21743274593 385 21970653284 386 22199810679 387 22430756032 388 22663498613 389 22898047724 390 23134412687 391 23372602850 392 23612627589 393 23854496300 394 24098218403 395 24343803336 396 24591260569 397 24840599600 398 25091829945 399 25344961132 400 25600002741 401 25856964350 402 26115855569 403 26376686048 404 26639465433 405 26904203414 406 27170909687 407 27439593998 408 27710266097 409 27982935764 410 28257612819 411 28534307074 412 28813028373 413 29093786604 414 29376591667 415 29661453482 416 29948381997 417 30237387200 418 30528479063 419 30821667618 420 31116962903 421 31414374990 422 31713913973 423 32015589968 424 32319413115 425 32625393578 426 32933541533 427 33243867204 428 33556380825 429 33871092652 430 34188012999 431 34507152122 432 34828520387 433 35152128140 434 35477985759 435 35806103662 436 36136492257 437 36469162010 438 36804123397 439 37141386908 440 37480963079 441 37822862444 442 38167095585 443 38513673110 444 38862605615 445 39213903746 446 39567578193 447 39923639644 448 40282098783 449 40642966370 450 41006253181 451 41371969988 452 41740127607 453 42110736884 454 42483808665 455 42859353842 456 43237383317 457 43617908030 458 44000938947 459 44386487014 460 44774563257 461 45165178700 462 45558344407 463 45954071460 464 46352370917 465 46753253932 466 47156731649 467 47562815240 468 47971515899 469 48382844850 470 48796813331 471 49213432624 472 49632714003 473 50054668800 474 50479308337 475 50906643996 476 51336687149 477 51769449230 478 52204941647 479 52643175888 480 53084163413 481 53527915754 482 53974444425 483 54423760978 484 54875876997 485 55330804088 486 55788553883 487 56249138030 488 56712568227 489 57178856140 490 57648013511 491 58120052078 492 58594983623 493 59072819930 494 59553572829 495 60037254164 496 60523875797 497 61013449628 498 61505987573 499 62001501560 500 62500003571 501 63001505582 502 63506019599 503 64013557674 504 64524131863 505 65037754238 506 65554436913 507 66074192024 508 66597031727 509 67122968198 510 67652013643 511 68184180300 512 68719480407 513 69257926234 514 69799530093 515 70344304316 516 70892261233 517 71443413222 518 71997772685 519 72555352040 520 73116163727 521 73680220214 522 74247533995 523 74818117602 524 75391983543 525 75969144394 526 76549612755 527 77133401234 528 77720522453 529 78310989084 530 78904813821 531 79502009344 532 80102588409 533 80706563768 534 81313948187 535 81924754478 536 82538995479 537 83156684038 538 83777833017 539 84402455330 540 85030563907 541 85662171672 542 86297291613 543 86935936720 544 87578120019 545 88223854554 546 88873153387 547 89526029624 548 90182496363 549 90842566768 550 91506253989 551 92173571202 552 92844531619 553 93519148488 554 94197435069 555 94879404644 556 95565070517 557 96254446028 558 96947544545 559 97644379412 560 98344964057 561 99049311914 562 99757436415 563 100469351052 564 101185069309 565 101904604724 566 102627970847 567 103355181248 568 104086249505 569 104821189254 570 105560014139 571 106302737834 572 107049374013 573 107799936400 574 108554438753 575 109312894826 576 110075318387 577 110841723258 578 111612123275 579 112386532310 580 113164964231 581 113947432962 582 114733952419 583 115524536574 584 116319199395 585 117117954886 586 117920817087 587 118727800034 588 119538917819 589 120354184530 590 121173614297 591 121997221288 592 122825019633 593 123657023540 594 124493247245 595 125333704982 596 126178411019 597 127027379654 598 127880625207 599 128738161998 600 129600004409 601 130466166822 602 131336663639 603 132211509322 604 133090718303 605 133974305076 606 134862284153 607 135754670064 608 136651477377 609 137552720644 610 138458414493 611 139368573548 612 140283212449 613 141202345878 614 142125988535 615 143054155148 616 143986860483 617 144924119270 618 145865946337 619 146812356488 620 147763364583 621 148718985472 622 149679234053 623 150644125244 624 151613673997 625 152587895262 626 153566804015 627 154550415284 628 155538744105 629 156531805532 630 157529614657 631 158532186584 632 159539536449 633 160551679400 634 161568630627 635 162590405328 636 163617018737 637 164648486084 638 165684822665 639 166726043774 640 167772164751 641 168823200920 642 169879167679 643 170940080388 644 172005954485 645 173076805418 646 174152648655 647 175233499682 648 176319374029 649 177410287218 650 178506254831 651 179607292462 652 180713415687 653 181824640158 654 182940981545 655 184062455528 656 185189077805 657 186320864120 658 187457830227 659 188599991894 660 189747364937 661 190899965184 662 192057808487 663 193220910718 664 194389287783 665 195562955594 666 196741930109 667 197926227308 668 199115863169 669 200310853720 670 201511215003 671 202716963090 672 203928114067 673 205144684062 674 206366689199 675 207594145664 676 208827069627 677 210065477300 678 211309384933 679 212558808762 680 213813765087 681 215074270220 682 216340340477 683 217611992228 684 218889241849 685 220172105744 686 221460600363 687 222754742114 688 224054547503 689 225360033012 690 226671215179 691 227988110550 692 229310735693 693 230639107210 694 231973241723 695 233313155856 696 234658866289 697 236010389718 698 237367742877 699 238730942474 700 240100005279 701 241474948082 702 242855787713 703 244242540984 704 245635224765 705 247033855948 706 248438451429 707 249849028148 708 251265603047 709 252688193142 710 254116815387 711 255551486834 712 256992224535 713 258439045568 714 259891967029 715 261351006042 716 262816179755 717 264287505352 718 265765000013 719 267248680962 720 268738565443 721 270234670730 722 271737014127 723 273245612918 724 274760484455 725 276281646108 726 277809115277 727 279342909344 728 280883045763 729 282429542000 730 283982415521 731 285541683848 732 287107364507 733 288679475078 734 290258033099 735 291843056194 736 293434561989 737 295032568142 738 296637092327 739 298248152264 740 299865765639 741 301489950202 742 303120723743 743 304758104052 744 306402108949 745 308052756282 746 309710063915 747 311374049750 748 313044731699 749 314722127690 750 316406255693 751 318097133702 752 319794779727 753 321499211798 754 323210447993 755 324928506366 756 326653405039 757 328385162150 758 330123795875 759 331869324344 760 333621765791 761 335381138442 762 337147460543 763 338920750374 764 340701026237 765 342488306452 766 344282609375 767 346083953364 768 347892356825 769 349707838172 770 351530415857 771 353360108342 772 355196934123 773 357040911710 774 358892059655 775 360750396506 776 362615940873 777 364488711344 778 366368726579 779 368256005208 780 370150565939 781 372052427474 782 373961608557 783 375878127908 784 377802004343 785 379733256636 786 381671903645 787 383617964198 788 385571457179 789 387532401488 790 389500816053 791 391476719828 792 393460131769 793 395451070880 794 397449556185 795 399455606716 796 401469241557 797 403490479794 798 405519340537 799 407555842932 800 409600006133 801 411651849344 802 413711391767 803 415778652644 804 417853651229 805 419936406822 806 422026938695 807 424125266204 808 426231408707 809 428345385578 810 430467216221 811 432596920070 812 434734516583 813 436880025218 814 439033465479 815 441194856894 816 443364219007 817 445541571398 818 447726933663 819 449920325420 820 452121766301 821 454331275992 822 456548874173 823 458774580564 824 461008414905 825 463250396962 826 465500546519 827 467758883394 828 470025427415 829 472300198442 830 474583216367 831 476874501094 832 479174072555 833 481481950710 834 483798155533 835 486122707046 836 488455625243 837 490796930210 838 493146641987 839 495504780710 840 497871366473 841 500246419442 842 502629959787 843 505022007722 844 507422583425 845 509831707172 846 512249399207 847 514675679834 848 517110569379 849 519554088170 850 522006256571 851 524467094978 852 526936623797 853 529414863480 854 531901834463 855 534397557244 856 536902052333 857 539415340254 858 541937441555 859 544468376822 860 547008166673 861 549556831720 862 552114392625 863 554680870052 864 557256284717 865 559840657328 866 562434008645 867 565036359440 868 567647730509 869 570268142658 870 572897616761 871 575536173644 872 578183834235 873 580840619422 874 583506550167 875 586181647418 876 588865932179 877 591559425464 878 594262148283 879 596974121710 880 599695366833 881 602425904762 882 605165756633 883 607914943584 884 610673486805 885 613441407496 886 616218726899 887 619005466260 888 621801646843 889 624607289952 890 627422416917 891 630247049108 892 633081207845 893 635924914560 894 638778190657 895 641641057592 896 644513536827 897 647395649858 898 650287418199 899 653188863392 900 656100006997 901 659020870602 902 661951475829 903 664891844300 904 667841997683 905 670801957664 906 673771745939 907 676751384258 908 679740894365 909 682740298040 910 685749617103 911 688768873350 912 691798088657 913 694837284888 914 697886483945 915 700945707776 916 704014978295 917 707094317498 918 710183747363 919 713283289914 920 716392967207 921 719512801292 922 722642814269 923 725783028260 924 728933465405 925 732094147862 926 735265097819 927 738446337488 928 741637889109 929 744839774964 930 748052017297 931 751274638428 932 754507660685 933 757751106442 934 761004998067 935 764269357958 936 767544208565 937 770829572312 938 774125471705 939 777431929234 940 780748967411 941 784076608778 942 787414875929 943 790763791452 944 794123377953 945 797493658084 946 800874654533 947 804266389962 948 807668887103 949 811082168690 950 814506257499 951 817941176308 952 821386947933 953 824843595204 954 828311140985 955 831789608162 956 835279019637 957 838779398348 958 842290767245 959 845813149320 960 849346567561 961 852891045014 962 856446604713 963 860013269744 964 863591063205 965 867180008216 966 870780127939 967 874391445528 968 878013984197 969 881647767160 970 885292817643 971 888949158930 972 892616814325 973 896295807114 974 899986160657 975 903687898312 976 907401043467 977 911125619540 978 914861649959 979 918609158198 980 922368167723 981 926138702048 982 929920784717 983 933714439274 984 937519689293 985 941336558384 986 945165070205 987 949005248354 988 952857116553 989 956720698464 990 960596017829 991 964483098402 992 968381963949 993 972292638268 994 976215145169 995 980149508502 996 984095752135 997 988053899964 998 992023975917 999 996006003908 1000 1000000007919