0 7 1 8 2 15 3 34 4 71 5 132 6 223 7 350 8 519 9 736 10 1007 11 1338 12 1735 13 2204 14 2751 15 3382 16 4103 17 4920 18 5839 19 6866 20 8007 21 9268 22 10655 23 12174 24 13831 25 15632 26 17583 27 19690 28 21959 29 24396 30 27007 31 29798 32 32775 33 35944 34 39311 35 42882 36 46663 37 50660 38 54879 39 59326 40 64007 41 68928 42 74095 43 79514 44 85191 45 91132 46 97343 47 103830 48 110599 49 117656 50 125007 51 132658 52 140615 53 148884 54 157471 55 166382 56 175623 57 185200 58 195119 59 205386 60 216007 61 226988 62 238335 63 250054 64 262151 65 274632 66 287503 67 300770 68 314439 69 328516 70 343007 71 357918 72 373255 73 389024 74 405231 75 421882 76 438983 77 456540 78 474559 79 493046 80 512007 81 531448 82 551375 83 571794 84 592711 85 614132 86 636063 87 658510 88 681479 89 704976 90 729007 91 753578 92 778695 93 804364 94 830591 95 857382 96 884743 97 912680 98 941199 99 970306 100 1000007 101 1030308 102 1061215 103 1092734 104 1124871 105 1157632 106 1191023 107 1225050 108 1259719 109 1295036 110 1331007 111 1367638 112 1404935 113 1442904 114 1481551 115 1520882 116 1560903 117 1601620 118 1643039 119 1685166 120 1728007 121 1771568 122 1815855 123 1860874 124 1906631 125 1953132 126 2000383 127 2048390 128 2097159 129 2146696 130 2197007 131 2248098 132 2299975 133 2352644 134 2406111 135 2460382 136 2515463 137 2571360 138 2628079 139 2685626 140 2744007 141 2803228 142 2863295 143 2924214 144 2985991 145 3048632 146 3112143 147 3176530 148 3241799 149 3307956 150 3375007 151 3442958 152 3511815 153 3581584 154 3652271 155 3723882 156 3796423 157 3869900 158 3944319 159 4019686 160 4096007 161 4173288 162 4251535 163 4330754 164 4410951 165 4492132 166 4574303 167 4657470 168 4741639 169 4826816 170 4913007 171 5000218 172 5088455 173 5177724 174 5268031 175 5359382 176 5451783 177 5545240 178 5639759 179 5735346 180 5832007 181 5929748 182 6028575 183 6128494 184 6229511 185 6331632 186 6434863 187 6539210 188 6644679 189 6751276 190 6859007 191 6967878 192 7077895 193 7189064 194 7301391 195 7414882 196 7529543 197 7645380 198 7762399 199 7880606 200 8000007 201 8120608 202 8242415 203 8365434 204 8489671 205 8615132 206 8741823 207 8869750 208 8998919 209 9129336 210 9261007 211 9393938 212 9528135 213 9663604 214 9800351 215 9938382 216 10077703 217 10218320 218 10360239 219 10503466 220 10648007 221 10793868 222 10941055 223 11089574 224 11239431 225 11390632 226 11543183 227 11697090 228 11852359 229 12008996 230 12167007 231 12326398 232 12487175 233 12649344 234 12812911 235 12977882 236 13144263 237 13312060 238 13481279 239 13651926 240 13824007 241 13997528 242 14172495 243 14348914 244 14526791 245 14706132 246 14886943 247 15069230 248 15252999 249 15438256 250 15625007 251 15813258 252 16003015 253 16194284 254 16387071 255 16581382 256 16777223 257 16974600 258 17173519 259 17373986 260 17576007 261 17779588 262 17984735 263 18191454 264 18399751 265 18609632 266 18821103 267 19034170 268 19248839 269 19465116 270 19683007 271 19902518 272 20123655 273 20346424 274 20570831 275 20796882 276 21024583 277 21253940 278 21484959 279 21717646 280 21952007 281 22188048 282 22425775 283 22665194 284 22906311 285 23149132 286 23393663 287 23639910 288 23887879 289 24137576 290 24389007 291 24642178 292 24897095 293 25153764 294 25412191 295 25672382 296 25934343 297 26198080 298 26463599 299 26730906 300 27000007 301 27270908 302 27543615 303 27818134 304 28094471 305 28372632 306 28652623 307 28934450 308 29218119 309 29503636 310 29791007 311 30080238 312 30371335 313 30664304 314 30959151 315 31255882 316 31554503 317 31855020 318 32157439 319 32461766 320 32768007 321 33076168 322 33386255 323 33698274 324 34012231 325 34328132 326 34645983 327 34965790 328 35287559 329 35611296 330 35937007 331 36264698 332 36594375 333 36926044 334 37259711 335 37595382 336 37933063 337 38272760 338 38614479 339 38958226 340 39304007 341 39651828 342 40001695 343 40353614 344 40707591 345 41063632 346 41421743 347 41781930 348 42144199 349 42508556 350 42875007 351 43243558 352 43614215 353 43986984 354 44361871 355 44738882 356 45118023 357 45499300 358 45882719 359 46268286 360 46656007 361 47045888 362 47437935 363 47832154 364 48228551 365 48627132 366 49027903 367 49430870 368 49836039 369 50243416 370 50653007 371 51064818 372 51478855 373 51895124 374 52313631 375 52734382 376 53157383 377 53582640 378 54010159 379 54439946 380 54872007 381 55306348 382 55742975 383 56181894 384 56623111 385 57066632 386 57512463 387 57960610 388 58411079 389 58863876 390 59319007 391 59776478 392 60236295 393 60698464 394 61162991 395 61629882 396 62099143 397 62570780 398 63044799 399 63521206 400 64000007 401 64481208 402 64964815 403 65450834 404 65939271 405 66430132 406 66923423 407 67419150 408 67917319 409 68417936 410 68921007 411 69426538 412 69934535 413 70445004 414 70957951 415 71473382 416 71991303 417 72511720 418 73034639 419 73560066 420 74088007 421 74618468 422 75151455 423 75686974 424 76225031 425 76765632 426 77308783 427 77854490 428 78402759 429 78953596 430 79507007 431 80062998 432 80621575 433 81182744 434 81746511 435 82312882 436 82881863 437 83453460 438 84027679 439 84604526 440 85184007 441 85766128 442 86350895 443 86938314 444 87528391 445 88121132 446 88716543 447 89314630 448 89915399 449 90518856 450 91125007 451 91733858 452 92345415 453 92959684 454 93576671 455 94196382 456 94818823 457 95444000 458 96071919 459 96702586 460 97336007 461 97972188 462 98611135 463 99252854 464 99897351 465 100544632 466 101194703 467 101847570 468 102503239 469 103161716 470 103823007 471 104487118 472 105154055 473 105823824 474 106496431 475 107171882 476 107850183 477 108531340 478 109215359 479 109902246 480 110592007 481 111284648 482 111980175 483 112678594 484 113379911 485 114084132 486 114791263 487 115501310 488 116214279 489 116930176 490 117649007 491 118370778 492 119095495 493 119823164 494 120553791 495 121287382 496 122023943 497 122763480 498 123505999 499 124251506 500 125000007 501 125751508 502 126506015 503 127263534 504 128024071 505 128787632 506 129554223 507 130323850 508 131096519 509 131872236 510 132651007 511 133432838 512 134217735 513 135005704 514 135796751 515 136590882 516 137388103 517 138188420 518 138991839 519 139798366 520 140608007 521 141420768 522 142236655 523 143055674 524 143877831 525 144703132 526 145531583 527 146363190 528 147197959 529 148035896 530 148877007 531 149721298 532 150568775 533 151419444 534 152273311 535 153130382 536 153990663 537 154854160 538 155720879 539 156590826 540 157464007 541 158340428 542 159220095 543 160103014 544 160989191 545 161878632 546 162771343 547 163667330 548 164566599 549 165469156 550 166375007 551 167284158 552 168196615 553 169112384 554 170031471 555 170953882 556 171879623 557 172808700 558 173741119 559 174676886 560 175616007 561 176558488 562 177504335 563 178453554 564 179406151 565 180362132 566 181321503 567 182284270 568 183250439 569 184220016 570 185193007 571 186169418 572 187149255 573 188132524 574 189119231 575 190109382 576 191102983 577 192100040 578 193100559 579 194104546 580 195112007 581 196122948 582 197137375 583 198155294 584 199176711 585 200201632 586 201230063 587 202262010 588 203297479 589 204336476 590 205379007 591 206425078 592 207474695 593 208527864 594 209584591 595 210644882 596 211708743 597 212776180 598 213847199 599 214921806 600 216000007 601 217081808 602 218167215 603 219256234 604 220348871 605 221445132 606 222545023 607 223648550 608 224755719 609 225866536 610 226981007 611 228099138 612 229220935 613 230346404 614 231475551 615 232608382 616 233744903 617 234885120 618 236029039 619 237176666 620 238328007 621 239483068 622 240641855 623 241804374 624 242970631 625 244140632 626 245314383 627 246491890 628 247673159 629 248858196 630 250047007 631 251239598 632 252435975 633 253636144 634 254840111 635 256047882 636 257259463 637 258474860 638 259694079 639 260917126 640 262144007 641 263374728 642 264609295 643 265847714 644 267089991 645 268336132 646 269586143 647 270840030 648 272097799 649 273359456 650 274625007 651 275894458 652 277167815 653 278445084 654 279726271 655 281011382 656 282300423 657 283593400 658 284890319 659 286191186 660 287496007 661 288804788 662 290117535 663 291434254 664 292754951 665 294079632 666 295408303 667 296740970 668 298077639 669 299418316 670 300763007 671 302111718 672 303464455 673 304821224 674 306182031 675 307546882 676 308915783 677 310288740 678 311665759 679 313046846 680 314432007 681 315821248 682 317214575 683 318611994 684 320013511 685 321419132 686 322828863 687 324242710 688 325660679 689 327082776 690 328509007 691 329939378 692 331373895 693 332812564 694 334255391 695 335702382 696 337153543 697 338608880 698 340068399 699 341532106 700 343000007 701 344472108 702 345948415 703 347428934 704 348913671 705 350402632 706 351895823 707 353393250 708 354894919 709 356400836 710 357911007 711 359425438 712 360944135 713 362467104 714 363994351 715 365525882 716 367061703 717 368601820 718 370146239 719 371694966 720 373248007 721 374805368 722 376367055 723 377933074 724 379503431 725 381078132 726 382657183 727 384240590 728 385828359 729 387420496 730 389017007 731 390617898 732 392223175 733 393832844 734 395446911 735 397065382 736 398688263 737 400315560 738 401947279 739 403583426 740 405224007 741 406869028 742 408518495 743 410172414 744 411830791 745 413493632 746 415160943 747 416832730 748 418508999 749 420189756 750 421875007 751 423564758 752 425259015 753 426957784 754 428661071 755 430368882 756 432081223 757 433798100 758 435519519 759 437245486 760 438976007 761 440711088 762 442450735 763 444194954 764 445943751 765 447697132 766 449455103 767 451217670 768 452984839 769 454756616 770 456533007 771 458314018 772 460099655 773 461889924 774 463684831 775 465484382 776 467288583 777 469097440 778 470910959 779 472729146 780 474552007 781 476379548 782 478211775 783 480048694 784 481890311 785 483736632 786 485587663 787 487443410 788 489303879 789 491169076 790 493039007 791 494913678 792 496793095 793 498677264 794 500566191 795 502459882 796 504358343 797 506261580 798 508169599 799 510082406 800 512000007 801 513922408 802 515849615 803 517781634 804 519718471 805 521660132 806 523606623 807 525557950 808 527514119 809 529475136 810 531441007 811 533411738 812 535387335 813 537367804 814 539353151 815 541343382 816 543338503 817 545338520 818 547343439 819 549353266 820 551368007 821 553387668 822 555412255 823 557441774 824 559476231 825 561515632 826 563559983 827 565609290 828 567663559 829 569722796 830 571787007 831 573856198 832 575930375 833 578009544 834 580093711 835 582182882 836 584277063 837 586376260 838 588480479 839 590589726 840 592704007 841 594823328 842 596947695 843 599077114 844 601211591 845 603351132 846 605495743 847 607645430 848 609800199 849 611960056 850 614125007 851 616295058 852 618470215 853 620650484 854 622835871 855 625026382 856 627222023 857 629422800 858 631628719 859 633839786 860 636056007 861 638277388 862 640503935 863 642735654 864 644972551 865 647214632 866 649461903 867 651714370 868 653972039 869 656234916 870 658503007 871 660776318 872 663054855 873 665338624 874 667627631 875 669921882 876 672221383 877 674526140 878 676836159 879 679151446 880 681472007 881 683797848 882 686128975 883 688465394 884 690807111 885 693154132 886 695506463 887 697864110 888 700227079 889 702595376 890 704969007 891 707347978 892 709732295 893 712121964 894 714516991 895 716917382 896 719323143 897 721734280 898 724150799 899 726572706 900 729000007 901 731432708 902 733870815 903 736314334 904 738763271 905 741217632 906 743677423 907 746142650 908 748613319 909 751089436 910 753571007 911 756058038 912 758550535 913 761048504 914 763551951 915 766060882 916 768575303 917 771095220 918 773620639 919 776151566 920 778688007 921 781229968 922 783777455 923 786330474 924 788889031 925 791453132 926 794022783 927 796597990 928 799178759 929 801765096 930 804357007 931 806954498 932 809557575 933 812166244 934 814780511 935 817400382 936 820025863 937 822656960 938 825293679 939 827936026 940 830584007 941 833237628 942 835896895 943 838561814 944 841232391 945 843908632 946 846590543 947 849278130 948 851971399 949 854670356 950 857375007 951 860085358 952 862801415 953 865523184 954 868250671 955 870983882 956 873722823 957 876467500 958 879217919 959 881974086 960 884736007 961 887503688 962 890277135 963 893056354 964 895841351 965 898632132 966 901428703 967 904231070 968 907039239 969 909853216 970 912673007 971 915498618 972 918330055 973 921167324 974 924010431 975 926859382 976 929714183 977 932574840 978 935441359 979 938313746 980 941192007 981 944076148 982 946966175 983 949862094 984 952763911 985 955671632 986 958585263 987 961504810 988 964430279 989 967361676 990 970299007 991 973242278 992 976191495 993 979146664 994 982107791 995 985074882 996 988047943 997 991026980 998 994011999 999 997003006 1000 1000000007