0 2 1 2 2 11 3 29 4 67 5 127 6 223 7 347 8 521 9 733 10 1009 11 1361 12 1733 13 2203 14 2749 15 3389 16 4099 17 4919 18 5839 19 6863 20 8009 21 9277 22 10651 23 12197 24 13829 25 15629 26 17579 27 19687 28 21961 29 24391 30 27011 31 29803 32 32771 33 35951 34 39313 35 42899 36 46663 37 50671 38 54877 39 59333 40 64007 41 68927 42 74093 43 79531 44 85193 45 91127 46 97367 47 103837 48 110597 49 117659 50 125003 51 132661 52 140611 53 148891 54 157477 55 166393 56 175621 57 185221 58 195121 59 205391 60 216023 61 226991 62 238331 63 250049 64 262147 65 274627 66 287501 67 300779 68 314441 69 328511 70 343019 71 357913 72 373273 73 389023 74 405227 75 421891 76 438979 77 456539 78 474557 79 493043 80 512009 81 531457 82 551381 83 571789 84 592723 85 614129 86 636059 87 658507 88 681481 89 704983 90 729019 91 753583 92 778693 93 804367 94 830587 95 857407 96 884743 97 912727 98 941201 99 970303 100 1000003 101 1030307 102 1061227 103 1092731 104 1124867 105 1157627 106 1191019 107 1225061 108 1259737 109 1295033 110 1331023 111 1367647 112 1404937 113 1442899 114 1481551 115 1520879 116 1560901 117 1601617 118 1643039 119 1685171 120 1728017 121 1771607 122 1815859 123 1860869 124 1906627 125 1953151 126 2000381 127 2048413 128 2097169 129 2146691 130 2197021 131 2248117 132 2300003 133 2352641 134 2406121 135 2460397 136 2515477 137 2571409 138 2628077 139 2685629 140 2744003 141 2803253 142 2863291 143 2924209 144 2985991 145 3048629 146 3112141 147 3176533 148 3241801 149 3307973 150 3375007 151 3442963 152 3511817 153 3581579 154 3652279 155 3723893 156 3796451 157 3869917 158 3944329 159 4019689 160 4096013 161 4173287 162 4251553 163 4330757 164 4410947 165 4492157 166 4574299 167 4657493 168 4741643 169 4826813 170 4913009 171 5000213 172 5088467 173 5177719 174 5268031 175 5359379 176 5451779 177 5545273 178 5639759 179 5735357 180 5832007 181 5929747 182 6028571 183 6128491 184 6229507 185 6331669 186 6434861 187 6539209 188 6644681 189 6751271 190 6859003 191 6967897 192 7077893 193 7189081 194 7301389 195 7414879 196 7529573 197 7645387 198 7762397 199 7880627 200 8000009 201 8120617 202 8242411 203 8365447 204 8489729 205 8615137 206 8741839 207 8869747 208 8998919 209 9129331 210 9261013 211 9393949 212 9528131 213 9663629 214 9800363 215 9938377 216 10077721 217 10218323 218 10360241 219 10503461 220 10648021 221 10793941 222 10941059 223 11089577 224 11239427 225 11390641 226 11543227 227 11697097 228 11852359 229 12008999 230 12167009 231 12326393 232 12487177 233 12649349 234 12812963 235 12977879 236 13144259 237 13312067 238 13481287 239 13651943 240 13824017 241 13997537 242 14172493 243 14348909 244 14526793 245 14706127 246 14886943 247 15069233 248 15253009 249 15438251 250 15625007 251 15813257 252 16003021 253 16194287 254 16387081 255 16581391 256 16777259 257 16974611 258 17173523 259 17373989 260 17576017 261 17779613 262 17984749 263 18191449 264 18399749 265 18609637 266 18821111 267 19034173 268 19248847 269 19465129 270 19683007 271 19902517 272 20123659 273 20346427 274 20570839 275 20796901 276 21024581 277 21253937 278 21484973 279 21717643 280 21952003 281 22188053 282 22425779 283 22665191 284 22906307 285 23149153 286 23393659 287 23639923 288 23887933 289 24137573 290 24389003 291 24642173 292 24897097 293 25153763 294 25412201 295 25672379 296 25934341 297 26198083 298 26463607 299 26730901 300 27000011 301 27270911 302 27543611 303 27818149 304 28094503 305 28372627 306 28652623 307 28934453 308 29218187 309 29503657 310 29791007 311 30080233 312 30371377 313 30664303 314 30959167 315 31255897 316 31554511 317 31855027 318 32157451 319 32461777 320 32768011 321 33076171 322 33386273 323 33698279 324 34012229 325 34328131 326 34645991 327 34965817 328 35287561 329 35611307 330 35937047 331 36264707 332 36594373 333 36926047 334 37259713 335 37595387 336 37933067 337 38272757 338 38614483 339 38958229 340 39304037 341 39651823 342 40001711 343 40353611 344 40707613 345 41063629 346 41421761 347 41781941 348 42144217 349 42508559 350 42875033 351 43243583 352 43614227 353 43986991 354 44361913 355 44738879 356 45118033 357 45499297 358 45882737 359 46268293 360 46656011 361 47045897 362 47437961 363 47832149 364 48228553 365 48627143 366 49027919 367 49430879 368 49836043 369 50243411 370 50653003 371 51064831 372 51478859 373 51895141 374 52313627 375 52734389 376 53157427 377 53582651 378 54010163 379 54439943 380 54872011 381 55306369 382 55742993 383 56181899 384 56623153 385 57066643 386 57512461 387 57960619 388 58411097 389 58863901 390 59319019 391 59776477 392 60236303 393 60698471 394 61162987 395 61629877 396 62099161 397 62570789 398 63044803 399 63521219 400 64000031 401 64481251 402 64964831 403 65450849 404 65939273 405 66430163 406 66923447 407 67419167 408 67917331 409 68417941 410 68921003 411 69426547 412 69934537 413 70445017 414 70957961 415 71473399 416 71991329 417 72511723 418 73034657 419 73560061 420 74088013 421 74618473 422 75151457 423 75686983 424 76225031 425 76765627 426 77308783 427 77854493 428 78402761 429 78953599 430 79507003 431 80062993 432 80621609 433 81182767 434 81746507 435 82312877 436 82881889 437 83453479 438 84027677 439 84604537 440 85184017 441 85766147 442 86350921 443 86938333 444 87528391 445 88121141 446 88716569 447 89314637 448 89915437 449 90518861 450 91125017 451 91733861 452 92345417 453 92959687 454 93576667 455 94196407 456 94818833 457 95444003 458 96071929 459 96702601 460 97336021 461 97972187 462 98611147 463 99252859 464 99897353 465 100544683 466 101194699 467 101847601 468 102503243 469 103161713 470 103823003 471 104487179 472 105154051 473 105823819 474 106496459 475 107171887 476 107850187 477 108531343 478 109215383 479 109902253 480 110592029 481 111284681 482 111980177 483 112678589 484 113379941 485 114084193 486 114791263 487 115501307 488 116214277 489 116930221 490 117649031 491 118370773 492 119095499 493 119823167 494 120553789 495 121287377 496 122023939 497 122763479 498 123505997 499 124251509 500 125000003 501 125751503 502 126506011 503 127263529 504 128024081 505 128787641 506 129554237 507 130323847 508 131096531 509 131872231 510 132651011 511 133432837 512 134217757 513 135005723 514 135796751 515 136590877 516 137388103 517 138188429 518 138991837 519 139798363 520 140608021 521 141420779 522 142236697 523 143055673 524 143877829 525 144703129 526 145531597 527 146363197 528 147197977 529 148035893 530 148877009 531 149721301 532 150568807 533 151419439 534 152273351 535 153130379 536 153990689 537 154854157 538 155720881 539 156590851 540 157464017 541 158340439 542 159220091 543 160103017 544 160989193 545 161878637 546 162771361 547 163667353 548 164566603 549 165469151 550 166375021 551 167284177 552 168196649 553 169112429 554 170031481 555 170953877 556 171879671 557 172808737 558 173741119 559 174676883 560 175616009 561 176558483 562 177504407 563 178453591 564 179406167 565 180362137 566 181321501 567 182284279 568 183250439 569 184220027 570 185193013 571 186169447 572 187149257 573 188132537 574 189119239 575 190109377 576 191102981 577 192100057 578 193100627 579 194104541 580 195112061 581 196122947 582 197137373 583 198155311 584 199176707 585 200201669 586 201230063 587 202262029 588 203297477 589 204336493 590 205379011 591 206425097 592 207474733 593 208527863 594 209584589 595 210644881 596 211708741 597 212776189 598 213847217 599 214921823 600 216000007 601 217081811 602 218167211 603 219256243 604 220348867 605 221445181 606 222545051 607 223648559 608 224755763 609 225866561 610 226981003 611 228099197 612 229220941 613 230346407 614 231475547 615 232608421 616 233744899 617 234885149 618 236029051 619 237176671 620 238328017 621 239483077 622 240641861 623 241804399 624 242970649 625 244140683 626 245314397 627 246491899 628 247673183 629 248858201 630 250047029 631 251239601 632 252435973 633 253636153 634 254840107 635 256047899 636 257259473 637 258474877 638 259694087 639 260917121 640 262144009 641 263374739 642 264609341 643 265847749 644 267089987 645 268336129 646 269586173 647 270840029 648 272097811 649 273359459 650 274625077 651 275894473 652 277167817 653 278445121 654 279726301 655 281011399 656 282300439 657 283593397 658 284890321 659 286191203 660 287496043 661 288804799 662 290117557 663 291434251 664 292754953 665 294079627 666 295408307 667 296740987 668 298077641 669 299418337 670 300763007 671 302111717 672 303464489 673 304821227 674 306182039 675 307546891 676 308915797 677 310288757 678 311665769 679 313046843 680 314432009 681 315821251 682 317214571 683 318611989 684 320013509 685 321419149 686 322828859 687 324242749 688 325660693 689 327082781 690 328509019 691 329939381 692 331373891 693 332812567 694 334255387 695 335702387 696 337153541 697 338608889 698 340068397 699 341532119 700 343000003 701 344472103 702 345948431 703 347428931 704 348913673 705 350402639 706 351895853 707 353393317 708 354894923 709 356400839 710 357911033 711 359425447 712 360944131 713 362467109 714 363994349 715 365525879 716 367061701 717 368601817 718 370146241 719 371695003 720 373248011 721 374805391 722 376367053 723 377933093 724 379503431 725 381078127 726 382657183 727 384240607 728 385828357 729 387420499 730 389017007 731 390617923 732 392223197 733 393832843 734 395446907 735 397065433 736 398688271 737 400315567 738 401947277 739 403583431 740 405224041 741 406869031 742 408518531 743 410172419 744 411830803 745 413493631 746 415160951 747 416832737 748 418508999 749 420189761 750 421875007 751 423564763 752 425259041 753 426957779 754 428661067 755 430368899 756 432081229 757 433798103 758 435519517 759 437245493 760 438976003 761 440711083 762 442450733 763 444194969 764 445943747 765 447697147 766 449455099 767 451217729 768 452984849 769 454756619 770 456533009 771 458314027 772 460099681 773 461889919 774 463684861 775 465484421 776 467288593 777 469097437 778 470910971 779 472729193 780 474552007 781 476379557 782 478211771 783 480048691 784 481890307 785 483736639 786 485587679 787 487443413 788 489303883 789 491169079 790 493039031 791 494913697 792 496793119 793 498677297 794 500566193 795 502459897 796 504358399 797 506261597 798 508169609 799 510082403 800 512000009 801 513922403 802 515849669 803 517781633 804 519718471 805 521660131 806 523606621 807 525557947 808 527514149 809 529475159 810 531441007 811 533411741 812 535387331 813 537367829 814 539353163 815 541343381 816 543338507 817 545338517 818 547343449 819 549353261 820 551368007 821 553387693 822 555412261 823 557441789 824 559476227 825 561515651 826 563559989 827 565609339 828 567663557 829 569722823 830 571787057 831 573856193 832 575930387 833 578009543 834 580093721 835 582182879 836 584277107 837 586376281 838 588480479 839 590589721 840 592704053 841 594823337 842 596947691 843 599077121 844 601211629 845 603351163 846 605495767 847 607645429 848 609800239 849 611960123 850 614125021 851 616295063 852 618470213 853 620650483 854 622835881 855 625026443 856 627222047 857 629422819 858 631628717 859 633839797 860 636056017 861 638277397 862 640503943 863 642735659 864 644972563 865 647214649 866 649461899 867 651714367 868 653972047 869 656234921 870 658503047 871 660776321 872 663054853 873 665338631 874 667627637 875 669921881 876 672221411 877 674526217 878 676836163 879 679151443 880 681472003 881 683797867 882 686128979 883 688465397 884 690807113 885 693154127 886 695506459 887 697864147 888 700227091 889 702595381 890 704969053 891 707347997 892 709732291 893 712122031 894 714516991 895 716917393 896 719323139 897 721734313 898 724150811 899 726572729 900 729000007 901 731432711 902 733870829 903 736314329 904 738763273 905 741217651 906 743677433 907 746142659 908 748613317 909 751089431 910 753571037 911 756058033 912 758550577 913 761048507 914 763551947 915 766060879 916 768575347 917 771095243 918 773620651 919 776151641 920 778688011 921 781229963 922 783777451 923 786330511 924 788889071 925 791453129 926 794022781 927 796597993 928 799178759 929 801765109 930 804357053 931 806954503 932 809557589 933 812166269 934 814780517 935 817400399 936 820025879 937 822656963 938 825293717 939 827936029 940 830584021 941 833237627 942 835896917 943 838561847 944 841232389 945 843908647 946 846590557 947 849278147 948 851971411 949 854670371 950 857375021 951 860085377 952 862801421 953 865523179 954 868250671 955 870983879 956 873722819 957 876467497 958 879217919 959 881974081 960 884736011 961 887503693 962 890277161 963 893056387 964 895841357 965 898632131 966 901428733 967 904231067 968 907039253 969 909853223 970 912673087 971 915498631 972 918330053 973 921167323 974 924010447 975 926859377 976 929714221 977 932574869 978 935441359 979 938313743 980 941192011 981 944076167 982 946966171 983 949862159 984 952763921 985 955671653 986 958585319 987 961504807 988 964430287 989 967361701 990 970299047 991 973242287 992 976191497 993 979146659 994 982107787 995 985074919 996 988047979 997 991026979 998 994012009 999 997003043 1000 1000000007