1000 1 1 2 4 3 11 4 1431655765 5 128 6 127 7 213 8 204 9 256 10 255 11 341 12 460 13 512 14 511 15 853 16 716 17 1024 18 1023 19 1365 20 1228 21 2048 22 2047 23 3413 24 3276 25 4096 26 4095 27 5461 28 7372 29 8192 30 8191 31 13653 32 11468 33 16384 34 16383 35 21845 36 19660 37 32768 38 32767 39 54613 40 52428 41 65536 42 65535 43 87381 44 117964 45 131072 46 131071 47 218453 48 183500 49 262144 50 262143 51 349525 52 314572 53 524288 54 524287 55 873813 56 838860 57 1048576 58 1048575 59 1398101 60 1887436 61 2097152 62 2097151 63 3495253 64 2936012 65 4194304 66 4194303 67 5592405 68 5033164 69 8388608 70 8388607 71 13981013 72 13421772 73 16777216 74 16777215 75 22369621 76 30198988 77 33554432 78 33554431 79 55924053 80 46976204 81 67108864 82 67108863 83 89478485 84 80530636 85 134217728 86 134217727 87 223696213 88 214748364 89 268435456 90 268435455 91 357913941 92 483183820 93 536870912 94 536870911 95 894784853 96 751619276 97 1073741824 98 1073741823 99 1431655765 100 1288490188 101 181714662 102 324015425 103 762875968 104 1043497826 105 1002173003 106 761149800 107 523754017 108 858348929 109 736987383 110 937763692 111 510991112 112 438887466 113 607259217 114 991623396 115 919736867 116 515799823 117 401606658 118 737135529 119 272094065 120 930186954 121 121204947 122 401208182 123 329842572 124 242581003 125 24500526 126 373072225 127 140469901 128 647767057 129 967196698 130 755291160 131 442547449 132 757335923 133 453899228 134 473457658 135 974568895 136 702487618 137 255634712 138 1026771443 139 72768585 140 977137770 141 623254408 142 662660151 143 608334233 144 190495095 145 148009798 146 174213053 147 493184891 148 1070655127 149 1015310754 150 736966039 151 793661632 152 856478206 153 40920200 154 1007399702 155 32328081 156 155176071 157 670096248 158 767292344 159 185261769 160 1017398969 161 556005643 162 77452271 163 482801515 164 405688843 165 640590862 166 125036467 167 218812186 168 230976898 169 14721828 170 136501221 171 631916717 172 460089499 173 1007021570 174 806027648 175 240158667 176 733524869 177 585202482 178 32001440 179 512989339 180 611436465 181 42801516 182 8671569 183 161195140 184 296220581 185 458925948 186 711370806 187 305736441 188 498688302 189 880961979 190 980390136 191 954630493 192 110634199 193 1066063891 194 495502988 195 297842925 196 3995063 197 1025865624 198 227055939 199 874748353 200 862040201 201 331148976 202 8608433 203 855963101 204 167806233 205 92316357 206 502720349 207 245050188 208 949160188 209 961101461 210 669813060 211 240844881 212 871224993 213 46313470 214 169680429 215 889757865 216 77867941 217 482820206 218 1029919949 219 1016592083 220 661647748 221 69740245 222 816349112 223 200809590 224 701106064 225 598671919 226 641149221 227 356931787 228 888054077 229 15004569 230 917534336 231 223606817 232 874127293 233 444244727 234 684674768 235 744208229 236 161085930 237 645777711 238 227940068 239 651311817 240 1064171905 241 585618155 242 314734175 243 276690540 244 630573230 245 640793333 246 955484288 247 393354270 248 224829158 249 563697435 250 527314896 251 148439341 252 296039442 253 61055653 254 349940621 255 234460994 256 462427402 257 745048415 258 486438384 259 319043413 260 359009379 261 574863918 262 459895360 263 109233575 264 960818819 265 941021241 266 321202613 267 561505748 268 762083348 269 331940252 270 727678508 271 688490992 272 495040954 273 110055091 274 686916007 275 417517497 276 14572574 277 633003248 278 228037025 279 650702546 280 1028166475 281 347600961 282 180857142 283 248490773 284 400483419 285 803895815 286 994185485 287 415806960 288 559190124 289 144934047 290 272114722 291 118137305 292 289011694 293 573333110 294 604341336 295 495638211 296 1010652482 297 526562227 298 573006296 299 843504312 300 416269726 301 305258859 302 865999946 303 923334000 304 4883277 305 454413675 306 550841553 307 729014790 308 486557750 309 170044813 310 407711718 311 685896113 312 901200829 313 821969311 314 167001588 315 911426200 316 88521447 317 366364379 318 141075918 319 374824366 320 276147674 321 926945263 322 507620339 323 1026423459 324 666177958 325 291339407 326 149595551 327 539689186 328 107122016 329 324220836 330 135033519 331 244968606 332 1061130638 333 919338747 334 850454868 335 44847863 336 622363872 337 663054225 338 13430421 339 471829538 340 563626302 341 743555433 342 963401381 343 865468075 344 671338528 345 21712370 346 926704640 347 931080901 348 897214779 349 306486270 350 814770278 351 9135273 352 240495227 353 119683147 354 899449495 355 288787715 356 674631759 357 281652631 358 308466666 359 744889969 360 824692034 361 649169737 362 122604719 363 912685846 364 604739560 365 642707881 366 85646944 367 231961906 368 424673817 369 43789987 370 520895144 371 243803609 372 99023994 373 892645923 374 560004659 375 751953068 376 361990490 377 544353528 378 1024235089 379 434287530 380 331066845 381 303501646 382 943605868 383 557752848 384 273331318 385 388114354 386 343810630 387 789626182 388 840940464 389 290949035 390 418118161 391 807602912 392 635718734 393 1014678240 394 842854734 395 964023980 396 445089204 397 363221458 398 387116420 399 711081936 400 979971998 401 322715935 402 573213120 403 919864315 404 289486897 405 497817177 406 278603751 407 175541155 408 265265491 409 964297584 410 363154653 411 898709077 412 459291732 413 304300969 414 866862709 415 306113040 416 466554607 417 371975458 418 156238388 419 314367162 420 885569679 421 333552105 422 81272808 423 690789020 424 501435116 425 124777384 426 725178115 427 934630639 428 104538359 429 162642134 430 621024727 431 977305470 432 898645781 433 274445954 434 6509971 435 415070293 436 455061417 437 780961192 438 392085014 439 307804287 440 938823406 441 120445720 442 194705561 443 845285587 444 399626533 445 526566638 446 121918487 447 1031674328 448 100722190 449 52400281 450 849320601 451 133121454 452 799787185 453 692488305 454 244133446 455 626108179 456 581170815 457 175519710 458 614100292 459 554063980 460 441588920 461 391429395 462 995969902 463 794431979 464 139816741 465 11838284 466 3545302 467 136505782 468 181341992 469 12491951 470 370394136 471 441536812 472 1066781204 473 340577964 474 957751163 475 137398835 476 613294551 477 379795449 478 661286888 479 482477973 480 882015991 481 749815572 482 1049518249 483 713052015 484 838313694 485 845737054 486 1046816512 487 44368562 488 226069872 489 410429121 490 551203973 491 894315699 492 442249467 493 593951205 494 912360287 495 192860612 496 849778 497 995434745 498 937838401 499 688301035 500 396366836 501 1024388363 502 1024863809 503 141372570 504 669403049 505 1005190636 506 144910458 507 1054609027 508 751232239 509 616965290 510 410158462 511 974424694 512 481953746 513 838407827 514 730976924 515 646730315 516 458163930 517 539973585 518 751697133 519 786271465 520 129712931 521 341727374 522 844670527 523 72758864 524 430773961 525 584320939 526 43497408 527 544378552 528 973016228 529 654264841 530 233527688 531 791610306 532 153580626 533 476975451 534 216396264 535 307044021 536 39846291 537 684490134 538 882022283 539 776466129 540 736220659 541 111226845 542 785749360 543 792951464 544 64076740 545 28515858 546 135489446 547 935568272 548 449355116 549 862215654 550 34189283 551 669391397 552 180638718 553 821979779 554 995537125 555 773571282 556 999063589 557 443250628 558 474671016 559 273492340 560 597159007 561 983118328 562 947964259 563 510025481 564 916321161 565 665888061 566 364317026 567 1039531117 568 812660409 569 365912935 570 122216869 571 1045134635 572 761833833 573 155053938 574 249600339 575 639676762 576 1062720243 577 450850193 578 846238718 579 705338765 580 806299738 581 1022795452 582 916335799 583 1001228244 584 538177896 585 824961759 586 776689648 587 576728262 588 862332951 589 521200781 590 264896299 591 213545895 592 977783115 593 1023210821 594 1043729798 595 178982030 596 123746783 597 936328527 598 939617286 599 557886383 600 592974593 601 231851549 602 454982845 603 651303070 604 210311384 605 155841094 606 755272637 607 413271225 608 881754757 609 205661708 610 420137178 611 424254351 612 707878506 613 499692401 614 313880897 615 133603427 616 552425927 617 667940063 618 226559955 619 555275196 620 78237348 621 365685091 622 966262625 623 398084094 624 189980429 625 85502318 626 894344617 627 400518176 628 854526106 629 899051310 630 607196714 631 571077480 632 478992208 633 734445943 634 443540425 635 800790841 636 885317317 637 867621944 638 226908228 639 279008244 640 417073312 641 885218690 642 977767536 643 829223396 644 684847969 645 112273954 646 788363349 647 985157442 648 918013056 649 935831746 650 730217990 651 976158784 652 44769491 653 859315878 654 100391519 655 52461096 656 875651659 657 968778993 658 70382208 659 970575500 660 9377280 661 434558328 662 444987683 663 909292424 664 759674253 665 444952114 666 1067289280 667 819580938 668 560050870 669 91898404 670 82772862 671 670853944 672 833263722 673 55518961 674 610292215 675 774174171 676 457678855 677 950707694 678 864564681 679 299718878 680 450783738 681 334763973 682 713913599 683 223353825 684 282188968 685 1013258676 686 827363131 687 819261138 688 575638698 689 299124555 690 557547970 691 880053665 692 127472983 693 765791181 694 729027401 695 599769339 696 924182685 697 351854092 698 354152088 699 303406878 700 500778290 701 189642217 702 929790722 703 142944180 704 341338633 705 916823639 706 904040867 707 462816704 708 14493216 709 74692338 710 418096757 711 454337189 712 380665754 713 1061834790 714 1024271411 715 178090285 716 578402604 717 103182569 718 135597580 719 313749419 720 317560018 721 338975996 722 315279910 723 463339563 724 796509924 725 162112201 726 928207856 727 4848049 728 727231591 729 635450308 730 891520326 731 190436741 732 91838398 733 573494886 734 427605349 735 740385685 736 641186467 737 500882610 738 489667755 739 359167203 740 685846643 741 184482381 742 660715565 743 879821573 744 59850695 745 210992420 746 625983512 747 835477425 748 988966498 749 895729572 750 647779303 751 715905888 752 326089320 753 400344961 754 792936288 755 320374266 756 798089198 757 383857674 758 782220142 759 836645015 760 189085136 761 675183383 762 170968512 763 611701579 764 62101728 765 922696568 766 796378685 767 484111882 768 482261087 769 395769856 770 411915589 771 127442833 772 853967558 773 1024656925 774 930639303 775 197740908 776 184015335 777 515681020 778 902021669 779 316029948 780 767537490 781 1055432260 782 959272673 783 175245728 784 20851219 785 58693975 786 488395303 787 250244059 788 256250555 789 237788720 790 294206235 791 777863578 792 677690048 793 115003588 794 246688765 795 895280511 796 333301791 797 108295676 798 229999136 799 877638464 800 1026008673 801 316017470 802 911526566 803 772200217 804 237226463 805 465203583 806 827439899 807 517494344 808 640651871 809 679933677 810 282830031 811 225992604 812 503921665 813 665099813 814 1009978898 815 337498904 816 162864503 817 236120573 818 310477873 819 316542877 820 637476497 821 945795287 822 813944139 823 1000079786 824 603222554 825 1017139848 826 216147186 827 633761326 828 21078528 829 497559506 830 414380708 831 478247014 832 486585553 833 243803756 834 351508742 835 343374280 836 974374787 837 933483666 838 227775741 839 1001193223 840 512204438 841 754414388 842 685629325 843 297016607 844 1063962997 845 76243367 846 1010595216 847 962267511 848 708106043 849 1047583218 850 368201780 851 852608012 852 452573110 853 777242781 854 738684244 855 796084916 856 796236743 857 343806753 858 524498582 859 768457832 860 661442570 861 425190360 862 78712416 863 257302441 864 563880147 865 425814662 866 584792474 867 385014508 868 101001850 869 836880500 870 342358340 871 1710615 872 226700529 873 1055341327 874 2417364 875 527357971 876 354684341 877 977565735 878 359432815 879 1010405226 880 807502597 881 731346610 882 1037182438 883 314042616 884 632723312 885 418725665 886 877663118 887 803205029 888 206398634 889 690432590 890 807654366 891 353514553 892 831591617 893 644169194 894 371509481 895 380073016 896 3153039 897 308930956 898 508633752 899 557143763 900 292205192 901 993716034 902 508354245 903 434537189 904 476676311 905 19097277 906 690958363 907 107077893 908 849920454 909 1038843395 910 875178695 911 778907808 912 954424700 913 1011408572 914 814251517 915 644272942 916 227176452 917 824486657 918 165523789 919 848481389 920 195366572 921 631418060 922 971271361 923 867641008 924 456403885 925 29741799 926 560406229 927 205740609 928 1046931242 929 679329402 930 365873974 931 792676044 932 193663092 933 344571931 934 327431512 935 118296033 936 77975213 937 648874875 938 104807895 939 646614404 940 994090927 941 338692250 942 351300013 943 838716871 944 836149316 945 660284814 946 609277487 947 834197629 948 702416057 949 1069981659 950 1021592808 951 1032895993 952 253348017 953 81508441 954 115967540 955 828631515 956 800046420 957 943929518 958 181732794 959 439069425 960 829337801 961 442302799 962 663858089 963 214235428 964 869336580 965 246216476 966 746848721 967 359437432 968 261573594 969 842614663 970 163282815 971 800734238 972 576150133 973 303412808 974 70137655 975 950484108 976 407601669 977 868772773 978 532323634 979 143414194 980 570295765 981 498317900 982 771474869 983 649237046 984 131913375 985 293693364 986 830181934 987 101962951 988 172068666 989 650841628 990 115307566 991 975581302 992 1051310740 993 922471177 994 35339561 995 366923049 996 430653950 997 177674597 998 834023942 999 584577304 1000 378614468