0 1 1 2 2 17 3 82 4 257 5 626 6 1297 7 2402 8 4097 9 6562 10 10001 11 14642 12 20737 13 28562 14 38417 15 50626 16 65537 17 83522 18 104977 19 130322 20 160001 21 194482 22 234257 23 279842 24 331777 25 390626 26 456977 27 531442 28 614657 29 707282 30 810001 31 923522 32 1048577 33 1185922 34 1336337 35 1500626 36 1679617 37 1874162 38 2085137 39 2313442 40 2560001 41 2825762 42 3111697 43 3418802 44 3748097 45 4100626 46 4477457 47 4879682 48 5308417 49 5764802 50 6250001 51 6765202 52 7311617 53 7890482 54 8503057 55 9150626 56 9834497 57 10556002 58 11316497 59 12117362 60 12960001 61 13845842 62 14776337 63 15752962 64 16777217 65 17850626 66 18974737 67 20151122 68 21381377 69 22667122 70 24010001 71 25411682 72 26873857 73 28398242 74 29986577 75 31640626 76 33362177 77 35153042 78 37015057 79 38950082 80 40960001 81 43046722 82 45212177 83 47458322 84 49787137 85 52200626 86 54700817 87 57289762 88 59969537 89 62742242 90 65610001 91 68574962 92 71639297 93 74805202 94 78074897 95 81450626 96 84934657 97 88529282 98 92236817 99 96059602 100 100000001 101 104060402 102 108243217 103 112550882 104 116985857 105 121550626 106 126247697 107 131079602 108 136048897 109 141158162 110 146410001 111 151807042 112 157351937 113 163047362 114 168896017 115 174900626 116 181063937 117 187388722 118 193877777 119 200533922 120 207360001 121 214358882 122 221533457 123 228886642 124 236421377 125 244140626 126 252047377 127 260144642 128 268435457 129 276922882 130 285610001 131 294499922 132 303595777 133 312900722 134 322417937 135 332150626 136 342102017 137 352275362 138 362673937 139 373301042 140 384160001 141 395254162 142 406586897 143 418161602 144 429981697 145 442050626 146 454371857 147 466948882 148 479785217 149 492884402 150 506250001 151 519885602 152 533794817 153 547981282 154 562448657 155 577200626 156 592240897 157 607573202 158 623201297 159 639128962 160 655360001 161 671898242 162 688747537 163 705911762 164 723394817 165 741200626 166 759333137 167 777796322 168 796594177 169 815730722 170 835210001 171 855036082 172 875213057 173 895745042 174 916636177 175 937890626 176 959512577 177 981506242 178 1003875857 179 1026625682 180 1049760001 181 1073283122 182 1097199377 183 1121513122 184 1146228737 185 1171350626 186 1196883217 187 1222830962 188 1249198337 189 1275989842 190 1303210001 191 1330863362 192 1358954497 193 1387488002 194 1416468497 195 1445900626 196 1475789057 197 1506138482 198 1536953617 199 1568239202 200 1600000001 201 1632240802 202 1664966417 203 1698181682 204 1731891457 205 1766100626 206 1800814097 207 1836036802 208 1871773697 209 1908029762 210 1944810001 211 1982119442 212 2019963137 213 2058346162 214 2097273617 215 2136750626 216 2176782337 217 2217373922 218 2258530577 219 2300257522 220 2342560001 221 2385443282 222 2428912657 223 2472973442 224 2517630977 225 2562890626 226 2608757777 227 2655237842 228 2702336257 229 2750058482 230 2798410001 231 2847396322 232 2897022977 233 2947295522 234 2998219537 235 3049800626 236 3102044417 237 3154956562 238 3208542737 239 3262808642 240 3317760001 241 3373402562 242 3429742097 243 3486784402 244 3544535297 245 3603000626 246 3662186257 247 3722098082 248 3782742017 249 3844124002 250 3906250001 251 3969126002 252 4032758017 253 4097152082 254 4162314257 255 4228250626 256 4294967297 257 4362470402 258 4430766097 259 4499860562 260 4569760001 261 4640470642 262 4711998737 263 4784350562 264 4857532417 265 4931550626 266 5006411537 267 5082121522 268 5158686977 269 5236114322 270 5314410001 271 5393580482 272 5473632257 273 5554571842 274 5636405777 275 5719140626 276 5802782977 277 5887339442 278 5972816657 279 6059221282 280 6146560001 281 6234839522 282 6324066577 283 6414247922 284 6505390337 285 6597500626 286 6690585617 287 6784652162 288 6879707137 289 6975757442 290 7072810001 291 7170871762 292 7269949697 293 7370050802 294 7471182097 295 7573350626 296 7676563457 297 7780827682 298 7886150417 299 7992538802 300 8100000001 301 8208541202 302 8318169617 303 8428892482 304 8540717057 305 8653650626 306 8767700497 307 8882874002 308 8999178497 309 9116621362 310 9235210001 311 9354951842 312 9475854337 313 9597924962 314 9721171217 315 9845600626 316 9971220737 317 10098039122 318 10226063377 319 10355301122 320 10485760001 321 10617447682 322 10750371857 323 10884540242 324 11019960577 325 11156640626 326 11294588177 327 11433811042 328 11574317057 329 11716114082 330 11859210001 331 12003612722 332 12149330177 333 12296370322 334 12444741137 335 12594450626 336 12745506817 337 12897917762 338 13051691537 339 13206836242 340 13363360001 341 13521270962 342 13680577297 343 13841287202 344 14003408897 345 14166950626 346 14331920657 347 14498327282 348 14666178817 349 14835483602 350 15006250001 351 15178486402 352 15352201217 353 15527402882 354 15704099857 355 15882300626 356 16062013697 357 16243247602 358 16426010897 359 16610312162 360 16796160001 361 16983563042 362 17172529937 363 17363069362 364 17555190017 365 17748900626 366 17944209937 367 18141126722 368 18339659777 369 18539817922 370 18741610001 371 18945044882 372 19150131457 373 19356878642 374 19565295377 375 19775390626 376 19987173377 377 20200652642 378 20415837457 379 20632736882 380 20851360001 381 21071715922 382 21293813777 383 21517662722 384 21743271937 385 21970650626 386 22199808017 387 22430753362 388 22663495937 389 22898045042 390 23134410001 391 23372600162 392 23612624897 393 23854493602 394 24098215697 395 24343800626 396 24591257857 397 24840596882 398 25091827217 399 25344958402 400 25600000001 401 25856961602 402 26115852817 403 26376683282 404 26639462657 405 26904200626 406 27170906897 407 27439591202 408 27710263297 409 27982932962 410 28257610001 411 28534304242 412 28813025537 413 29093783762 414 29376588817 415 29661450626 416 29948379137 417 30237384322 418 30528476177 419 30821664722 420 31116960001 421 31414372082 422 31713911057 423 32015587042 424 32319410177 425 32625390626 426 32933538577 427 33243864242 428 33556377857 429 33871089682 430 34188010001 431 34507149122 432 34828517377 433 35152125122 434 35477982737 435 35806100626 436 36136489217 437 36469158962 438 36804120337 439 37141383842 440 37480960001 441 37822859362 442 38167092497 443 38513670002 444 38862602497 445 39213900626 446 39567575057 447 39923636482 448 40282095617 449 40642963202 450 41006250001 451 41371966802 452 41740124417 453 42110733682 454 42483805457 455 42859350626 456 43237380097 457 43617904802 458 44000935697 459 44386483762 460 44774560001 461 45165175442 462 45558341137 463 45954068162 464 46352367617 465 46753250626 466 47156728337 467 47562811922 468 47971512577 469 48382841522 470 48796810001 471 49213429282 472 49632710657 473 50054665442 474 50479304977 475 50906640626 476 51336683777 477 51769445842 478 52204938257 479 52643172482 480 53084160001 481 53527912322 482 53974440977 483 54423757522 484 54875873537 485 55330800626 486 55788550417 487 56249134562 488 56712564737 489 57178852642 490 57648010001 491 58120048562 492 58594980097 493 59072816402 494 59553569297 495 60037250626 496 60523872257 497 61013446082 498 61505984017 499 62001498002 500 62500000001 501 63001502002 502 63506016017 503 64013554082 504 64524128257 505 65037750626 506 65554433297 507 66074188402 508 66597028097 509 67122964562 510 67652010001 511 68184176642 512 68719476737 513 69257922562 514 69799526417 515 70344300626 516 70892257537 517 71443409522 518 71997768977 519 72555348322 520 73116160001 521 73680216482 522 74247530257 523 74818113842 524 75391979777 525 75969140626 526 76549608977 527 77133397442 528 77720518657 529 78310985282 530 78904810001 531 79502005522 532 80102584577 533 80706559922 534 81313944337 535 81924750626 536 82538991617 537 83156680162 538 83777829137 539 84402451442 540 85030560001 541 85662167762 542 86297287697 543 86935932802 544 87578116097 545 88223850626 546 88873149457 547 89526025682 548 90182492417 549 90842562802 550 91506250001 551 92173567202 552 92844527617 553 93519144482 554 94197431057 555 94879400626 556 95565066497 557 96254442002 558 96947540497 559 97644375362 560 98344960001 561 99049307842 562 99757432337 563 100469346962 564 101185065217 565 101904600626 566 102627966737 567 103355177122 568 104086245377 569 104821185122 570 105560010001 571 106302733682 572 107049369857 573 107799932242 574 108554434577 575 109312890626 576 110075314177 577 110841719042 578 111612119057 579 112386528082 580 113164960001 581 113947428722 582 114733948177 583 115524532322 584 116319195137 585 117117950626 586 117920812817 587 118727795762 588 119538913537 589 120354180242 590 121173610001 591 121997216962 592 122825015297 593 123657019202 594 124493242897 595 125333700626 596 126178406657 597 127027375282 598 127880620817 599 128738157602 600 129600000001 601 130466162402 602 131336659217 603 132211504882 604 133090713857 605 133974300626 606 134862279697 607 135754665602 608 136651472897 609 137552716162 610 138458410001 611 139368569042 612 140283207937 613 141202341362 614 142125984017 615 143054150626 616 143986855937 617 144924114722 618 145865941777 619 146812351922 620 147763360001 621 148718980882 622 149679229457 623 150644120642 624 151613669377 625 152587890626 626 153566799377 627 154550410642 628 155538739457 629 156531800882 630 157529610001 631 158532181922 632 159539531777 633 160551674722 634 161568625937 635 162590400626 636 163617014017 637 164648481362 638 165684817937 639 166726039042 640 167772160001 641 168823196162 642 169879162897 643 170940075602 644 172005949697 645 173076800626 646 174152643857 647 175233494882 648 176319369217 649 177410282402 650 178506250001 651 179607287602 652 180713410817 653 181824635282 654 182940976657 655 184062450626 656 185189072897 657 186320859202 658 187457825297 659 188599986962 660 189747360001 661 190899960242 662 192057803537 663 193220905762 664 194389282817 665 195562950626 666 196741925137 667 197926222322 668 199115858177 669 200310848722 670 201511210001 671 202716958082 672 203928109057 673 205144679042 674 206366684177 675 207594140626 676 208827064577 677 210065472242 678 211309379857 679 212558803682 680 213813760001 681 215074265122 682 216340335377 683 217611987122 684 218889236737 685 220172100626 686 221460595217 687 222754736962 688 224054542337 689 225360027842 690 226671210001 691 227988105362 692 229310730497 693 230639102002 694 231973236497 695 233313150626 696 234658861057 697 236010384482 698 237367737617 699 238730937202 700 240100000001 701 241474942802 702 242855782417 703 244242535682 704 245635219457 705 247033850626 706 248438446097 707 249849022802 708 251265597697 709 252688187762 710 254116810001 711 255551481442 712 256992219137 713 258439040162 714 259891961617 715 261351000626 716 262816174337 717 264287499922 718 265764994577 719 267248675522 720 268738560001 721 270234665282 722 271737008657 723 273245607442 724 274760478977 725 276281640626 726 277809109777 727 279342903842 728 280883040257 729 282429536482 730 283982410001 731 285541678322 732 287107358977 733 288679469522 734 290258027537 735 291843050626 736 293434556417 737 295032562562 738 296637086737 739 298248146642 740 299865760001 741 301489944562 742 303120718097 743 304758098402 744 306402103297 745 308052750626 746 309710058257 747 311374044082 748 313044726017 749 314722122002 750 316406250001 751 318097128002 752 319794774017 753 321499206082 754 323210442257 755 324928500626 756 326653399297 757 328385156402 758 330123790097 759 331869318562 760 333621760001 761 335381132642 762 337147454737 763 338920744562 764 340701020417 765 342488300626 766 344282603537 767 346083947522 768 347892350977 769 349707832322 770 351530410001 771 353360102482 772 355196928257 773 357040905842 774 358892053777 775 360750390626 776 362615934977 777 364488705442 778 366368720657 779 368255999282 780 370150560001 781 372052421522 782 373961602577 783 375878121922 784 377801998337 785 379733250626 786 381671897617 787 383617958162 788 385571451137 789 387532395442 790 389500810001 791 391476713762 792 393460125697 793 395451064802 794 397449550097 795 399455600626 796 401469235457 797 403490473682 798 405519334417 799 407555836802 800 409600000001 801 411651843202 802 413711385617 803 415778646482 804 417853645057 805 419936400626 806 422026932497 807 424125260002 808 426231402497 809 428345379362 810 430467210001 811 432596913842 812 434734510337 813 436880018962 814 439033459217 815 441194850626 816 443364212737 817 445541565122 818 447726927377 819 449920319122 820 452121760001 821 454331269682 822 456548867857 823 458774574242 824 461008408577 825 463250390626 826 465500540177 827 467758877042 828 470025421057 829 472300192082 830 474583210001 831 476874494722 832 479174066177 833 481481944322 834 483798149137 835 486122700626 836 488455618817 837 490796923762 838 493146635537 839 495504774242 840 497871360001 841 500246412962 842 502629953297 843 505022001202 844 507422576897 845 509831700626 846 512249392657 847 514675673282 848 517110562817 849 519554081602 850 522006250001 851 524467088402 852 526936617217 853 529414856882 854 531901827857 855 534397550626 856 536902045697 857 539415333602 858 541937434897 859 544468370162 860 547008160001 861 549556825042 862 552114385937 863 554680863362 864 557256278017 865 559840650626 866 562434001937 867 565036352722 868 567647723777 869 570268135922 870 572897610001 871 575536166882 872 578183827457 873 580840612642 874 583506543377 875 586181640626 876 588865925377 877 591559418642 878 594262141457 879 596974114882 880 599695360001 881 602425897922 882 605165749777 883 607914936722 884 610673479937 885 613441400626 886 616218720017 887 619005459362 888 621801639937 889 624607283042 890 627422410001 891 630247042162 892 633081200897 893 635924907602 894 638778183697 895 641641050626 896 644513529857 897 647395642882 898 650287411217 899 653188856402 900 656100000001 901 659020863602 902 661951468817 903 664891837282 904 667841990657 905 670801950626 906 673771738897 907 676751377202 908 679740887297 909 682740290962 910 685749610001 911 688768866242 912 691798081537 913 694837277762 914 697886476817 915 700945700626 916 704014971137 917 707094310322 918 710183740177 919 713283282722 920 716392960001 921 719512794082 922 722642807057 923 725783021042 924 728933458177 925 732094140626 926 735265090577 927 738446330242 928 741637881857 929 744839767682 930 748052010001 931 751274631122 932 754507653377 933 757751099122 934 761004990737 935 764269350626 936 767544201217 937 770829564962 938 774125464337 939 777431921842 940 780748960001 941 784076601362 942 787414868497 943 790763784002 944 794123370497 945 797493650626 946 800874647057 947 804266382482 948 807668879617 949 811082161202 950 814506250001 951 817941168802 952 821386940417 953 824843587682 954 828311133457 955 831789600626 956 835279012097 957 838779390802 958 842290759697 959 845813141762 960 849346560001 961 852891037442 962 856446597137 963 860013262162 964 863591055617 965 867180000626 966 870780120337 967 874391437922 968 878013976577 969 881647759522 970 885292810001 971 888949151282 972 892616806657 973 896295799442 974 899986152977 975 903687890626 976 907401035777 977 911125611842 978 914861642257 979 918609150482 980 922368160001 981 926138694322 982 929920776977 983 933714431522 984 937519681537 985 941336550626 986 945165062417 987 949005240562 988 952857108737 989 956720690642 990 960596010001 991 964483090562 992 968381956097 993 972292630402 994 976215137297 995 980149500626 996 984095744257 997 988053892082 998 992023968017 999 996005996002 1000 1000000000001