0 0 1 1 2 9 3 27 4 73 5 126 6 243 7 344 8 585 9 729 10 1134 11 1332 12 1971 13 2198 14 3096 15 3402 16 4681 17 4914 18 6561 19 6860 20 9198 21 9288 22 11988 23 12168 24 15795 25 15751 26 19782 27 19683 28 25112 29 24390 30 30618 31 29792 32 37449 33 35964 34 44226 35 43344 36 53217 37 50654 38 61740 39 59346 40 73710 41 68922 42 83592 43 79508 44 97236 45 91854 46 109512 47 103824 48 126387 49 117993 50 141759 51 132678 52 160454 53 148878 54 177147 55 167832 56 201240 57 185220 58 219510 59 205380 60 248346 61 226982 62 268128 63 250776 64 299593 65 276948 66 323676 67 300764 68 358722 69 328536 70 390096 71 357912 72 426465 73 389018 74 455886 75 425277 76 500780 77 458208 78 534114 79 493040 80 589806 81 531441 82 620298 83 571788 84 678024 85 619164 86 715572 87 658530 88 779220 89 704970 90 826686 91 756112 92 888264 93 804384 94 934416 95 864360 96 1011123 97 912674 98 1061937 99 971028 100 1149823 101 1030302 102 1194102 103 1092728 104 1285830 105 1170288 106 1339902 107 1225044 108 1436859 109 1295030 110 1510488 111 1367658 112 1610264 113 1442898 114 1666980 115 1533168 116 1780470 117 1602342 118 1848420 119 1690416 120 1990170 121 1772893 122 2042838 123 1860894 124 2174816 125 1968876 126 2256984 127 2048384 128 2396745 129 2146716 130 2492532 131 2248092 132 2625372 133 2359840 134 2706876 135 2480058 136 2874690 137 2571354 138 2956824 139 2685620 140 3164112 141 2803248 142 3221208 143 2927736 144 3412449 145 3073140 146 3501162 147 3185811 148 3697742 149 3307950 150 3827493 151 3442952 152 4013100 153 3582306 154 4123872 155 3753792 156 4332258 157 3869894 158 4437360 159 4019706 160 4718574 161 4185792 162 4782969 163 4330748 164 5031306 165 4531464 166 5146092 167 4657464 168 5433480 169 4829007 170 5572476 171 5000940 172 5804084 173 5177718 174 5926770 175 5418344 176 6235092 177 5545260 178 6344730 179 5735340 180 6705342 181 5929742 182 6805008 183 6128514 184 7118280 185 6382404 186 7239456 187 6545448 188 7579152 189 6770952 190 7779240 191 6967872 192 8089011 193 7189058 194 8214066 195 7477596 196 8613489 197 7645374 198 8739252 199 7880600 200 9214335 201 8120628 202 9272718 203 8390160 204 9685494 205 8684172 206 9834552 207 8870472 208 10288838 209 9137520 210 10532592 211 9393932 212 10868094 213 9663624 214 11025396 215 10018008 216 11514555 217 10248448 218 11655270 219 10503486 220 12251736 221 10800972 222 12308922 223 11089568 224 12882456 225 11482479 226 12986082 227 11697084 228 13521060 229 12008990 230 13798512 231 12371616 232 14268150 233 12649338 234 14421078 235 13081824 236 14992740 237 13312080 238 15213744 239 13651920 240 15924762 241 13997522 242 15956037 243 14348907 244 16569686 245 14867118 246 16748046 247 15078280 248 17428320 249 15438276 250 17719884 251 15813252 252 18306648 253 16207776 254 18435456 255 16717428 256 19173961 257 16974594 258 19320444 259 17424976 260 20217204 261 17780310 262 20232828 263 18191448 264 21038940 265 18758628 266 21238560 267 19034190 268 21955772 269 19465110 270 22320522 271 19902512 272 23002434 273 20415024 274 23142186 275 20980332 276 23983128 277 21253934 278 24170580 279 21718368 280 25356240 281 22188042 282 25229232 283 22665188 284 26127576 285 23337720 286 26349624 287 23709168 288 27300321 289 24142483 290 27658260 291 24642198 292 28398314 293 25153758 294 28672299 295 25877880 296 29632590 297 26217756 298 29771550 299 26745264 300 31045221 301 27350752 302 30986568 303 27818154 304 32111660 305 28599732 306 32240754 307 28934444 308 33449184 309 29503656 310 33784128 311 30080232 312 34717410 313 30664298 314 34829046 315 31597776 316 35991920 317 31855014 318 36177354 319 32487480 320 37748718 321 33076188 322 37672128 323 33710040 324 38795193 325 34620698 326 38976732 327 34965810 328 40319370 329 35715456 330 40783176 331 36264692 332 41740524 333 36926766 334 41917176 335 37896264 336 43477128 337 38272754 338 43461063 339 38958246 340 45198972 341 39682944 342 45008460 343 40471600 344 46512180 345 41395536 346 46599462 347 41781924 348 48072690 349 42508550 350 48765096 351 43263234 352 49882068 353 43986978 354 49907340 355 45096912 356 51462810 357 45641232 358 51618060 359 46268280 360 53734590 361 47052741 362 53367678 363 47868111 364 55196176 365 49016268 366 55156626 367 49430864 368 56958408 369 50244138 370 57441636 371 51214032 372 58720032 373 51895118 374 58909032 375 53159652 376 60737040 377 53609220 378 60938568 379 54439940 380 63098280 381 55306368 382 62710848 383 56181888 384 64712115 385 57734208 386 64701522 387 57961332 388 66625202 389 58863870 390 67298364 391 59793552 392 69025905 393 60698484 394 68808366 395 62123040 396 70885044 397 62570774 398 70925400 399 63715680 400 73730431 401 64481202 402 73085652 403 65482816 404 75212046 405 66961566 406 75511440 407 67471128 408 77616630 409 68417930 410 78157548 411 69426558 412 79769144 413 70650720 414 79834248 415 72045288 416 82312902 417 72511740 418 82237680 419 73560060 420 85431024 421 74618462 422 84545388 423 75687696 424 87093630 425 77400414 426 86972616 427 78081808 428 89428212 429 79048872 430 90162072 431 80062992 432 92136123 433 81182738 434 92236032 435 82974780 436 94537190 437 83472480 438 94531374 439 84604520 440 98181720 441 86016897 442 97208748 443 86938308 444 99839034 445 88826220 446 99806112 447 89314650 448 103059992 449 90518850 450 103342311 451 91804104 452 105331554 453 92959704 454 105273756 455 95270112 456 108353700 457 95443994 458 108080910 459 96722262 460 111921264 461 97972182 462 111344544 463 99252848 464 114169590 465 101352384 466 113844042 467 101847564 468 116970966 469 103462816 470 117736416 471 104487138 472 120147300 473 105904656 474 119808720 475 108051860 476 123400368 477 108532062 478 122867280 479 109902240 480 127401498 481 111337492 482 125977698 483 113016384 484 129421189 485 114996924 486 129140163 487 115501304 488 132784470 489 116930196 490 133804062 491 118370772 492 135845262 493 119852460 494 135704520 495 122349528 496 139456352 497 123121728 498 138944484 499 124251500 500 143727948 501 125751528 502 142319268 503 127263528 504 146703960 505 129818052 506 145869984 507 130383189 508 149532032 509 131872230 510 150456852 511 133822192 512 153391689 513 135025380 514 152771346 515 137683728 516 156710268 517 138293568 518 156824784 519 139798386 520 162014580 521 141420762 522 160022790 523 143055668 524 164110716 525 146295288 526 163723032 527 146397888 528 168347484 529 148048057 530 168827652 531 149722020 532 172268320 533 151490556 534 171307710 535 154355544 536 175946940 537 154854180 538 175185990 539 157166676 540 181044234 541 158340422 542 179122608 543 160103034 544 184024386 545 163173780 546 183735216 547 163667324 548 187708842 549 165469878 550 188822988 551 167315400 552 192193560 553 169605760 554 191285406 555 172324908 556 196050260 557 172808694 558 195465312 559 174758584 560 202893264 561 176727096 562 199692378 563 178453548 564 204637104 565 181805148 566 203986692 567 182815704 568 209378520 569 184220010 570 210039480 571 186169412 572 213724728 573 188132544 574 213382512 575 191658168 576 218403297 577 192100034 578 217282347 579 194104566 580 224339220 581 196695072 582 221779782 583 198305496 584 227575530 585 201895092 586 226383822 587 202262004 588 232564203 589 204373120 590 232900920 591 206425098 592 237111374 593 208527858 594 235959804 595 212992416 596 241480350 597 212776200 598 240707376 599 214921800 600 248787045 601 217081802 602 246156768 603 219256956 604 251335496 605 223384518 606 250363386 607 223648544 608 256900140 609 226534320 610 257397588 611 228205152 612 261508338 613 230346398 614 260409996 615 234472644 616 268051680 617 234885114 618 265532904 619 237176660 620 274026816 621 239502744 622 270722088 623 242509680 624 277798626 625 246109501 626 275978682 627 246713040 628 282502262 629 248913756 630 284379984 631 251239592 632 288428400 633 253636164 634 286695126 635 258096384 636 293438538 637 259348614 638 292387320 639 260917848 640 301989870 641 263374722 642 297685692 643 265847708 644 305562816 645 270486216 646 303390360 647 270840024 648 310892985 649 273566160 650 311586282 651 276708096 652 316144604 653 278445078 654 314692290 655 283259592 656 322623882 657 283594122 658 321439104 659 286191180 660 330796872 661 288804782 662 326382228 663 291626244 664 334495980 665 297339840 666 332340894 667 296777520 668 339994872 669 299418336 670 341066376 671 302340024 672 347826312 673 304821218 674 344454786 675 310026933 676 352517511 677 310288734 678 350624214 679 313959856 680 362210940 681 315821268 682 357146496 683 318611988 684 365068620 685 323990604 686 364244400 687 324242730 688 372176948 689 327233844 690 372559824 691 329939372 692 377973414 693 334033632 694 376037316 695 338388120 696 385240050 697 338682708 698 382576950 699 341532126 700 395539112 701 344472102 702 389369106 703 347486440 704 399057876 705 353209248 706 395882802 707 354423888 708 404803980 709 356400830 710 405872208 711 359426160 712 412407450 713 362509056 714 410771088 715 368894736 716 418679820 717 368601840 718 416414520 719 371694960 720 429968574 721 375898432 722 423474669 723 377933094 724 432871166 725 384166890 726 430812999 727 384240584 728 442325520 729 387420489 730 441146412 731 390702312 732 447381522 733 393832838 734 444877776 735 401412186 736 455679432 737 400617648 738 452197242 739 403583420 740 465915492 741 407113560 742 460926288 743 410172408 744 470564640 745 416801700 746 467056062 747 416833452 748 477817704 749 421415136 750 478436868 751 423564752 752 486000144 753 426957804 754 482482980 755 433811952 756 494279496 757 433798094 758 489959460 759 437609952 760 505650600 761 440711082 762 497757312 763 445490320 764 508654656 765 451370556 766 505636992 767 451425240 768 517696947 769 454756610 770 519607872 771 458314038 772 524801234 773 461889918 774 521651988 775 469253792 776 533914290 777 470474352 778 529774830 779 472804920 780 545864508 781 476738784 782 538141968 783 480068370 784 552325233 785 487606644 786 546286356 787 487443404 788 558112302 789 491169096 790 559107360 791 496356912 792 568051380 793 498906436 794 563136966 795 506482956 796 575283800 797 506261574 798 573441120 799 510191136 800 589859199 801 513923130 802 580330818 803 518171976 804 592805844 805 527409792 806 589345344 807 525557970 808 602726670 809 529475130 810 602654094 811 533411732 812 612481680 813 537367824 814 607240152 815 545674248 816 621065718 817 545424880 818 615761370 819 551205648 820 633944556 821 553387662 822 624839022 823 557441768 824 639245880 825 566468964 826 635856480 827 565609284 828 647544456 829 569722790 830 648407592 831 573856218 832 658505414 833 579817602 834 652605660 835 586840464 836 667038960 837 586395936 838 662040540 839 590589720 840 684618480 841 594847711 842 671566158 843 599077134 844 685757036 845 608454882 846 681189264 847 609875192 848 696897918 849 611960076 850 696603726 851 616357872 852 705444552 853 620650478 854 702736272 855 630118440 856 716650740 857 629422794 858 711439848 859 633839780 860 731314584 861 640147536 862 720566928 863 642735648 864 737108667 865 652392468 866 730644642 867 651847041 868 748136704 869 656729280 870 746773020 871 661079272 872 757592550 873 665339346 874 751252320 875 677293344 876 766754478 877 674526134 878 761440680 879 679151466 880 785621592 881 683797842 882 774152073 883 688465388 884 788470956 885 698702760 886 782444772 887 697864104 888 800079930 889 704644096 890 799435980 891 707879412 892 809538464 893 712232640 894 803831850 895 722652840 896 824480280 897 722122128 898 814669650 899 726626880 900 838220967 901 731586492 902 826236936 903 738470304 904 844095330 905 747147492 906 836637336 907 746142644 908 853887132 909 751090158 910 857431008 911 756058032 912 867014820 913 761621616 914 858995946 915 772192764 916 876656270 917 773343648 918 870500358 919 776151560 920 896903280 921 781229988 922 881749638 923 786690576 924 903127968 925 797851154 926 893275632 927 796598712 928 913381110 929 801765090 930 912171456 931 809431980 932 923401674 933 812166264 934 916628076 935 824726448 936 937370070 937 822656954 938 931165344 939 827936046 940 954973152 941 833237622 942 940384242 943 838642896 944 961383780 945 853139952 946 953141904 947 849278124 948 971781840 949 855061564 950 972466740 951 860085378 952 988893360 953 865523178 954 976788558 955 877951872 956 996590160 957 877161960 958 989120160 959 884545776 960 1019215386 961 887533473 962 1002037428 963 893057076 964 1021819106 965 905821308 966 1017147456 967 904231064 968 1037142405 969 910171080 970 1034972316 971 915498612 972 1047470211 973 923853280 974 1039511736 975 934758846 976 1062502742 977 932574834 978 1052371764 979 939020040 980 1085299614 981 944076870 982 1065336948 983 949862088 984 1088622990 985 963317124 986 1078672140 987 964317312 988 1100714440 989 967453344 990 1101145752 991 973242272 992 1115680608 993 979146684 994 1108095552 995 992955600 996 1126994148 997 991026974 998 1118263500 999 997022682 1000 1151792460