0 1 1 1 2 9 3 41 4 129 5 313 6 649 7 1201 8 2049 9 3281 10 5001 11 7321 12 10369 13 14281 14 19209 15 25313 16 32769 17 41761 18 52489 19 65161 20 80001 21 97241 22 117129 23 139921 24 165889 25 195313 26 228489 27 265721 28 307329 29 353641 30 405001 31 461761 32 524289 33 592961 34 668169 35 750313 36 839809 37 937081 38 1042569 39 1156721 40 1280001 41 1412881 42 1555849 43 1709401 44 1874049 45 2050313 46 2238729 47 2439841 48 2654209 49 2882401 50 3125001 51 3382601 52 3655809 53 3945241 54 4251529 55 4575313 56 4917249 57 5278001 58 5658249 59 6058681 60 6480001 61 6922921 62 7388169 63 7876481 64 8388609 65 8925313 66 9487369 67 10075561 68 10690689 69 11333561 70 12005001 71 12705841 72 13436929 73 14199121 74 14993289 75 15820313 76 16681089 77 17576521 78 18507529 79 19475041 80 20480001 81 21523361 82 22606089 83 23729161 84 24893569 85 26100313 86 27350409 87 28644881 88 29984769 89 31371121 90 32805001 91 34287481 92 35819649 93 37402601 94 39037449 95 40725313 96 42467329 97 44264641 98 46118409 99 48029801 100 50000001 101 52030201 102 54121609 103 56275441 104 58492929 105 60775313 106 63123849 107 65539801 108 68024449 109 70579081 110 73205001 111 75903521 112 78675969 113 81523681 114 84448009 115 87450313 116 90531969 117 93694361 118 96938889 119 100266961 120 103680001 121 107179441 122 110766729 123 114443321 124 118210689 125 122070313 126 126023689 127 130072321 128 134217729 129 138461441 130 142805001 131 147249961 132 151797889 133 156450361 134 161208969 135 166075313 136 171051009 137 176137681 138 181336969 139 186650521 140 192080001 141 197627081 142 203293449 143 209080801 144 214990849 145 221025313 146 227185929 147 233474441 148 239892609 149 246442201 150 253125001 151 259942801 152 266897409 153 273990641 154 281224329 155 288600313 156 296120449 157 303786601 158 311600649 159 319564481 160 327680001 161 335949121 162 344373769 163 352955881 164 361697409 165 370600313 166 379666569 167 388898161 168 398297089 169 407865361 170 417605001 171 427518041 172 437606529 173 447872521 174 458318089 175 468945313 176 479756289 177 490753121 178 501937929 179 513312841 180 524880001 181 536641561 182 548599689 183 560756561 184 573114369 185 585675313 186 598441609 187 611415481 188 624599169 189 637994921 190 651605001 191 665431681 192 679477249 193 693744001 194 708234249 195 722950313 196 737894529 197 753069241 198 768476809 199 784119601 200 800000001 201 816120401 202 832483209 203 849090841 204 865945729 205 883050313 206 900407049 207 918018401 208 935886849 209 954014881 210 972405001 211 991059721 212 1009981569 213 1029173081 214 1048636809 215 1068375313 216 1088391169 217 1108686961 218 1129265289 219 1150128761 220 1171280001 221 1192721641 222 1214456329 223 1236486721 224 1258815489 225 1281445313 226 1304378889 227 1327618921 228 1351168129 229 1375029241 230 1399205001 231 1423698161 232 1448511489 233 1473647761 234 1499109769 235 1524900313 236 1551022209 237 1577478281 238 1604271369 239 1631404321 240 1658880001 241 1686701281 242 1714871049 243 1743392201 244 1772267649 245 1801500313 246 1831093129 247 1861049041 248 1891371009 249 1922062001 250 1953125001 251 1984563001 252 2016379009 253 2048576041 254 2081157129 255 2114125313 256 2147483649 257 2181235201 258 2215383049 259 2249930281 260 2284880001 261 2320235321 262 2355999369 263 2392175281 264 2428766209 265 2465775313 266 2503205769 267 2541060761 268 2579343489 269 2618057161 270 2657205001 271 2696790241 272 2736816129 273 2777285921 274 2818202889 275 2859570313 276 2901391489 277 2943669721 278 2986408329 279 3029610641 280 3073280001 281 3117419761 282 3162033289 283 3207123961 284 3252695169 285 3298750313 286 3345292809 287 3392326081 288 3439853569 289 3487878721 290 3536405001 291 3585435881 292 3634974849 293 3685025401 294 3735591049 295 3786675313 296 3838281729 297 3890413841 298 3943075209 299 3996269401 300 4050000001 301 4104270601 302 4159084809 303 4214446241 304 4270358529 305 4326825313 306 4383850249 307 4441437001 308 4499589249 309 4558310681 310 4617605001 311 4677475921 312 4737927169 313 4798962481 314 4860585609 315 4922800313 316 4985610369 317 5049019561 318 5113031689 319 5177650561 320 5242880001 321 5308723841 322 5375185929 323 5442270121 324 5509980289 325 5578320313 326 5647294089 327 5716905521 328 5787158529 329 5858057041 330 5929605001 331 6001806361 332 6074665089 333 6148185161 334 6222370569 335 6297225313 336 6372753409 337 6448958881 338 6525845769 339 6603418121 340 6681680001 341 6760635481 342 6840288649 343 6920643601 344 7001704449 345 7083475313 346 7165960329 347 7249163641 348 7333089409 349 7417741801 350 7503125001 351 7589243201 352 7676100609 353 7763701441 354 7852049929 355 7941150313 356 8031006849 357 8121623801 358 8213005449 359 8305156081 360 8398080001 361 8491781521 362 8586264969 363 8681534681 364 8777595009 365 8874450313 366 8972104969 367 9070563361 368 9169829889 369 9269908961 370 9370805001 371 9472522441 372 9575065729 373 9678439321 374 9782647689 375 9887695313 376 9993586689 377 10100326321 378 10207918729 379 10316368441 380 10425680001 381 10535857961 382 10646906889 383 10758831361 384 10871635969 385 10985325313 386 11099904009 387 11215376681 388 11331747969 389 11449022521 390 11567205001 391 11686300081 392 11806312449 393 11927246801 394 12049107849 395 12171900313 396 12295628929 397 12420298441 398 12545913609 399 12672479201 400 12800000001 401 12928480801 402 13057926409 403 13188341641 404 13319731329 405 13452100313 406 13585453449 407 13719795601 408 13855131649 409 13991466481 410 14128805001 411 14267152121 412 14406512769 413 14546891881 414 14688294409 415 14830725313 416 14974189569 417 15118692161 418 15264238089 419 15410832361 420 15558480001 421 15707186041 422 15856955529 423 16007793521 424 16159705089 425 16312695313 426 16466769289 427 16621932121 428 16778188929 429 16935544841 430 17094005001 431 17253574561 432 17414258689 433 17576062561 434 17738991369 435 17903050313 436 18068244609 437 18234579481 438 18402060169 439 18570691921 440 18740480001 441 18911429681 442 19083546249 443 19256835001 444 19431301249 445 19606950313 446 19783787529 447 19961818241 448 20141047809 449 20321481601 450 20503125001 451 20685983401 452 20870062209 453 21055366841 454 21241902729 455 21429675313 456 21618690049 457 21808952401 458 22000467849 459 22193241881 460 22387280001 461 22582587721 462 22779170569 463 22977034081 464 23176183809 465 23376625313 466 23578364169 467 23781405961 468 23985756289 469 24191420761 470 24398405001 471 24606714641 472 24816355329 473 25027332721 474 25239652489 475 25453320313 476 25668341889 477 25884722921 478 26102469129 479 26321586241 480 26542080001 481 26763956161 482 26987220489 483 27211878761 484 27437936769 485 27665400313 486 27894275209 487 28124567281 488 28356282369 489 28589426321 490 28824005001 491 29060024281 492 29297490049 493 29536408201 494 29776784649 495 30018625313 496 30261936129 497 30506723041 498 30752992009 499 31000749001 500 31250000001 501 31500751001 502 31753008009 503 32006777041 504 32262064129 505 32518875313 506 32777216649 507 33037094201 508 33298514049 509 33561482281 510 33826005001 511 34092088321 512 34359738369 513 34628961281 514 34899763209 515 35172150313 516 35446128769 517 35721704761 518 35998884489 519 36277674161 520 36558080001 521 36840108241 522 37123765129 523 37409056921 524 37695989889 525 37984570313 526 38274804489 527 38566698721 528 38860259329 529 39155492641 530 39452405001 531 39751002761 532 40051292289 533 40353279961 534 40656972169 535 40962375313 536 41269495809 537 41578340081 538 41888914569 539 42201225721 540 42515280001 541 42831083881 542 43148643849 543 43467966401 544 43789058049 545 44111925313 546 44436574729 547 44763012841 548 45091246209 549 45421281401 550 45753125001 551 46086783601 552 46422263809 553 46759572241 554 47098715529 555 47439700313 556 47782533249 557 48127221001 558 48473770249 559 48822187681 560 49172480001 561 49524653921 562 49878716169 563 50234673481 564 50592532609 565 50952300313 566 51313983369 567 51677588561 568 52043122689 569 52410592561 570 52780005001 571 53151366841 572 53524684929 573 53899966121 574 54277217289 575 54656445313 576 55037657089 577 55420859521 578 55806059529 579 56193264041 580 56582480001 581 56973714361 582 57366974089 583 57762266161 584 58159597569 585 58558975313 586 58960406409 587 59363897881 588 59769456769 589 60177090121 590 60586805001 591 60998608481 592 61412507649 593 61828509601 594 62246621449 595 62666850313 596 63089203329 597 63513687641 598 63940310409 599 64369078801 600 64800000001 601 65233081201 602 65668329609 603 66105752441 604 66545356929 605 66987150313 606 67431139849 607 67877332801 608 68325736449 609 68776358081 610 69229205001 611 69684284521 612 70141603969 613 70601170681 614 71062992009 615 71527075313 616 71993427969 617 72462057361 618 72932970889 619 73406175961 620 73881680001 621 74359490441 622 74839614729 623 75322060321 624 75806834689 625 76293945313 626 76783399689 627 77275205321 628 77769369729 629 78265900441 630 78764805001 631 79266090961 632 79769765889 633 80275837361 634 80784312969 635 81295200313 636 81808507009 637 82324240681 638 82842408969 639 83363019521 640 83886080001 641 84411598081 642 84939581449 643 85470037801 644 86002974849 645 86538400313 646 87076321929 647 87616747441 648 88159684609 649 88705141201 650 89253125001 651 89803643801 652 90356705409 653 90912317641 654 91470488329 655 92031225313 656 92594536449 657 93160429601 658 93728912649 659 94299993481 660 94873680001 661 95449980121 662 96028901769 663 96610452881 664 97194641409 665 97781475313 666 98370962569 667 98963111161 668 99557929089 669 100155424361 670 100755605001 671 101358479041 672 101964054529 673 102572339521 674 103183342089 675 103797070313 676 104413532289 677 105032736121 678 105654689929 679 106279401841 680 106906880001 681 107537132561 682 108170167689 683 108805993561 684 109444618369 685 110086050313 686 110730297609 687 111377368481 688 112027271169 689 112680013921 690 113335605001 691 113994052681 692 114655365249 693 115319551001 694 115986618249 695 116656575313 696 117329430529 697 118005192241 698 118683868809 699 119365468601 700 120050000001 701 120737471401 702 121427891209 703 122121267841 704 122817609729 705 123516925313 706 124219223049 707 124924511401 708 125632798849 709 126344093881 710 127058405001 711 127775740721 712 128496109569 713 129219520081 714 129945980809 715 130675500313 716 131408087169 717 132143749961 718 132882497289 719 133624337761 720 134369280001 721 135117332641 722 135868504329 723 136622803721 724 137380239489 725 138140820313 726 138904554889 727 139671451921 728 140441520129 729 141214768241 730 141991205001 731 142770839161 732 143553679489 733 144339734761 734 145129013769 735 145921525313 736 146717278209 737 147516281281 738 148318543369 739 149124073321 740 149932880001 741 150744972281 742 151560359049 743 152379049201 744 153201051649 745 154026375313 746 154855029129 747 155687022041 748 156522363009 749 157361061001 750 158203125001 751 159048564001 752 159897387009 753 160749603041 754 161605221129 755 162464250313 756 163326699649 757 164192578201 758 165061895049 759 165934659281 760 166810880001 761 167690566321 762 168573727369 763 169460372281 764 170350510209 765 171244150313 766 172141301769 767 173041973761 768 173946175489 769 174853916161 770 175765205001 771 176680051241 772 177598464129 773 178520452921 774 179446026889 775 180375195313 776 181307967489 777 182244352721 778 183184360329 779 184127999641 780 185075280001 781 186026210761 782 186980801289 783 187939060961 784 188900999169 785 189866625313 786 190835948809 787 191808979081 788 192785725569 789 193766197721 790 194750405001 791 195738356881 792 196730062849 793 197725532401 794 198724775049 795 199727800313 796 200734617729 797 201745236841 798 202759667209 799 203777918401 800 204800000001 801 205825921601 802 206855692809 803 207889323241 804 208926822529 805 209968200313 806 211013466249 807 212062630001 808 213115701249 809 214172689681 810 215233605001 811 216298456921 812 217367255169 813 218440009481 814 219516729609 815 220597425313 816 221682106369 817 222770782561 818 223863463689 819 224960159561 820 226060880001 821 227165634841 822 228274433929 823 229387287121 824 230504204289 825 231625195313 826 232750270089 827 233879438521 828 235012710529 829 236150096041 830 237291605001 831 238437247361 832 239587033089 833 240740972161 834 241899074569 835 243061350313 836 244227809409 837 245398461881 838 246573317769 839 247752387121 840 248935680001 841 250123206481 842 251314976649 843 252511000601 844 253711288449 845 254915850313 846 256124696329 847 257337836641 848 258555281409 849 259777040801 850 261003125001 851 262233544201 852 263468308609 853 264707428441 854 265950913929 855 267198775313 856 268451022849 857 269707666801 858 270968717449 859 272234185081 860 273504080001 861 274778412521 862 276057192969 863 277340431681 864 278628139009 865 279920325313 866 281217000969 867 282518176361 868 283823861889 869 285134067961 870 286448805001 871 287768083441 872 289091913729 873 290420306321 874 291753271689 875 293090820313 876 294432962689 877 295779709321 878 297131070729 879 298487057441 880 299847680001 881 301212948961 882 302582874889 883 303957468361 884 305336739969 885 306720700313 886 308109360009 887 309502729681 888 310900819969 889 312303641521 890 313711205001 891 315123521081 892 316540600449 893 317962453801 894 319389091849 895 320820525313 896 322256764929 897 323697821441 898 325143705609 899 326594428201 900 328050000001 901 329510431801 902 330975734409 903 332445918641 904 333920995329 905 335400975313 906 336885869449 907 338375688601 908 339870443649 909 341370145481 910 342874805001 911 344384433121 912 345899040769 913 347418638881 914 348943238409 915 350472850313 916 352007485569 917 353547155161 918 355091870089 919 356641641361 920 358196480001 921 359756397041 922 361321403529 923 362891510521 924 364466729089 925 366047070313 926 367632545289 927 369223165121 928 370818940929 929 372419883841 930 374026005001 931 375637315561 932 377253826689 933 378875549561 934 380502495369 935 382134675313 936 383772100609 937 385414782481 938 387062732169 939 388715960921 940 390374480001 941 392038300681 942 393707434249 943 395381892001 944 397061685249 945 398746825313 946 400437323529 947 402133191241 948 403834439809 949 405541080601 950 407253125001 951 408970584401 952 410693470209 953 412421793841 954 414155566729 955 415894800313 956 417639506049 957 419389695401 958 421145379849 959 422906570881 960 424673280001 961 426445518721 962 428223298569 963 430006631081 964 431795527809 965 433590000313 966 435390060169 967 437195718961 968 439006988289 969 440823879761 970 442646405001 971 444474575641 972 446308403329 973 448147899721 974 449993076489 975 451843945313 976 453700517889 977 455562805921 978 457430821129 979 459304575241 980 461184080001 981 463069347161 982 464960388489 983 466857215761 984 468759840769 985 470668275313 986 472582531209 987 474502620281 988 476428554369 989 478360345321 990 480298005001 991 482241545281 992 484190978049 993 486146315201 994 488107568649 995 490074750313 996 492047872129 997 494026946041 998 496011984009 999 498002998001 1000 500000000001