1 1 2 4 3 8 4 20 5 28 6 56 7 64 8 122 9 150 10 218 11 216 12 424 13 346 14 544 15 667 16 863 17 733 18 1305 19 1000 20 1752 21 1715 22 1944 23 1728 24 3258 25 2535 26 3142 27 3495 28 4520 29 3382 30 6254 31 4096 32 6486 33 6243 34 6812 35 7315 36 10959 37 6868 38 9400 39 10121 40 13922 41 9271 42 16388 43 10648 44 16520 45 17805 46 16416 47 13824 48 25711 49 17479 50 24090 51 22084 52 26816 53 19696 54 33477 55 26923 56 36506 57 30563 58 32414 59 27000 60 53900 61 29806 62 39424 63 46761 64 50490 65 43789 66 60636 67 39304 68 58596 69 53523 70 71126 71 46656 72 89100 73 50671 74 66442 75 78550 76 81128 77 70899 78 98714 79 64000 80 111439 81 90513 82 89984 83 74088 84 142156 85 95896 86 103576 87 105925 88 135162 89 91147 90 173967 91 115393 92 142184 93 128963 94 134784 95 132859 96 204054 97 117673 98 170485 99 173325 100 208730 101 132676 102 216656 103 140608 104 220082 105 233182 106 192482 107 157464 108 290715 109 166402 110 264398 111 217619 112 294095 113 185221 114 300476 115 233107 116 281616 117 282291 118 264600 119 253180 120 445090 121 245476 122 292174 123 294958 124 342920 125 297270 126 459909 127 262144 128 398356 129 339683 130 430988 131 287496 132 528844 133 351091 134 386104 135 477030 136 483098 137 328543 138 527748 139 343000 140 620556 141 442275 142 458784 143 429081 144 719793 145 462217 146 498352 147 559454 148 578936 149 421912 150 775150 151 438976 152 670010 153 619842 154 699684 155 562963 156 862132 157 493078 158 630400 159 631951 160 890870 161 616515 162 891828 163 551368 164 784860 165 868942 166 730296 167 592704 168 1178202 169 657319 170 947378 171 859749 172 903944 173 658546 174 1047410 175 905430 176 1094703 177 869283 178 899144 179 729000 180 1520259 181 753616 182 1140994 183 959933 184 1176858 185 951031 186 1276196 187 942868 188 1177160 189 1262478 190 1314542 191 884736 192 1627386 193 912721 194 1162132 195 1417204 196 1489145 197 970348 198 1714605 199 1000000 200 1728590 201 1269155 202 1310954 203 1223293 204 1895672 205 1289698 206 1389856 207 1510329 208 1784879 209 1308195 210 2314394 211 1191016 212 1682376 213 1508403 214 1557144 215 1485547 216 2410572 217 1490419 218 1645654 219 1638566 220 2314092 221 1537558 222 2157086 223 1404928 224 2358678 225 2218440 226 1832492 227 1481544 228 2630764 229 1520932 230 2310614 231 2302170 232 2335826 233 1601671 234 2796795 235 1934995 236 2314568 237 2073443 238 2509880 239 1728000 240 3619039 241 1771621 242 2430329 243 2408436 244 2556080 245 2447998 246 2926196 247 2133481 248 2846042 249 2402403 250 2944440 251 2000376 252 4027155 253 2298963 254 2596864 255 3117943 256 3166308 257 2146753 258 3371228 259 2518795 260 3774948 261 2998047 262 2848824 263 2299968 264 4397498 265 2766259 266 3483652 267 2958370 268 3379880 269 2460442 270 4735707 271 2515456 272 3925279 273 3755900 274 3256592 275 3377110 276 4624780 277 2685688 278 3400600 279 3653025 280 5161346 281 2803291 282 4392228 283 2863288 284 4017320 285 4327822 286 4259322 287 3416614 288 5781498 289 3216417 290 4589348 291 3824624 292 4364156 293 3176596 294 5557097 295 3806539 296 4810658 297 4710810 298 4185074 299 3750081 300 6794510 301 3936115 302 4355104 303 4314883 304 5447663 305 4204033 306 6154161 307 3652264 308 6133100 309 4574963 310 5592758 311 3796416 312 7175154 313 3869971 314 4893022 315 6625272 316 5522888 317 4019758 318 6280694 319 4565077 320 7127802 321 5126115 322 6125388 323 4693540 324 7813872 325 5509320 326 5473336 327 5417585 328 6525962 329 5127891 330 8647154 331 4574296 332 6399464 333 6175077 334 5884704 335 5559835 336 9594271 337 4826893 338 6526078 339 6033196 340 8307240 341 5563011 342 8542701 343 5796028 344 7518458 345 7610302 346 6539702 347 5268024 348 9186692 349 5359462 350 8999670 351 7685724 352 8804886 353 5545321 354 8644956 355 6609043 356 7881036 357 8266831 358 7241400 359 5832000 360 12657396 361 6223906 362 7486114 363 8002643 364 10007348 365 7179994 366 9548066 367 6229504 368 9577551 369 8377140 370 9457328 371 7332103 372 11195884 373 6539296 374 9375152 375 9696445 376 9795546 377 7448311 378 12557697 379 6859000 380 11531724 381 8552195 382 8792064 383 7077888 384 12996628 385 10093150 386 9070372 387 9651309 388 10189556 389 7414972 390 14113088 391 8252284 392 12393416 393 9382563 394 9644282 395 9087379 396 15040419 397 7880698 398 9940000 399 11476490 400 14071235 401 8120701 402 12629948 403 9076801 404 11496120 405 12857436 406 12169946 407 9405603 408 15795034 409 8615227 410 12832118 411 10726294 412 12189224 413 10091571 414 15023301 415 10530427 416 14367030 417 11201123 418 13015260 419 9261000 420 20321360 421 9394036 422 11842744 423 12574641 424 14007362 425 12124515 426 15014916 427 11145589 428 13658120 429 14033196 430 14784974 431 10077696 432 19632801 433 10218421 434 14832364 435 15121360 436 14434976 437 11455443 438 16312484 439 10648000 440 19284962 441 15909558 442 15300254 443 10941048 444 18933292 445 12969622 446 13974016 447 13786615 448 18898554 449 11390737 450 22074075 451 12761086 452 16075716 453 14347283 454 14737464 455 16472044 456 21928698 457 12009103 458 15129514 459 16916979 460 20280780 461 12326506 462 22939608 463 12487168 464 19026415 465 18429742 466 15934112 467 12812904 468 24544779 469 14742451 470 19265846 471 16120229 472 19280250 473 14702883 474 20648996 475 16830870 476 22030584 477 17981841 478 17193600 479 13824000 480 29174198 481 15348613 482 17627884 483 20185362 484 21324435 485 16770436 486 23967864 487 14526784 488 21294482 489 18033443 490 24376667 491 14886936 492 25690544 493 16394866 494 21241882 495 24757500 496 23187983 497 17525859 498 23929788 499 15625000 500 25838990 501 19389555 502 19908504 503 16003008 504 33571116 505 18921703 506 22892196 507 21502598 508 22789640 509 16581502 510 31079366 511 19040158 512 25247048 513 23485314 514 21367172 515 20062867 516 29601100 517 19157859 518 25085830 519 21548641 520 31475546 521 17779711 522 29853267 523 17984728 524 25002920 525 29659825 526 22895136 527 19980988 528 35857791 529 19380835 530 27554888 531 24751389 532 30586124 533 20825536 534 29475260 535 22481515 536 28167866 537 23862243 538 24494534 539 24239334 540 41585199 541 19902646 542 25043584 543 24668783 544 31628246 545 23760757 546 37444742 547 20570824 548 28584636 549 27337335 550 33637390 551 22760485 552 38572250 553 24101011 554 26740402 555 31171438 556 29850248 557 21717778 558 36385605 559 23994841 560 42090559 561 30899839 562 27913064 563 22425768 564 38573356 565 26462464 566 28511896 567 34100712 568 33487002 569 23149267 570 43153874 571 23393656 572 37401236 573 28974723 574 34040924 575 29600950 576 46354878 577 24137713 578 32029836 579 29892056 580 40302516 581 27929715 582 38117576 583 27398431 584 36381002 585 40408482 586 31635722 587 25412184 588 48806317 589 27740035 590 37933262 591 31784299 592 39214799 593 26198221 594 46943817 595 36271087 596 36742056 597 32759603 598 37364994 599 27000000 600 56678670 601 27271051 602 39223588 603 36161781 604 38236520 605 35104443 606 43009406 607 28094464 608 43910934 609 40115992 610 41898068 611 31266753 612 54043359 613 28934596 614 36380344 615 42299857 616 51160986 617 29503783 618 45604868 619 29791000 620 49121772 621 41307582 622 37818144 623 34401178 624 58528447 625 36728725 626 38551192 627 42902898 628 42962576 629 33792592 630 66067035 631 31554496 632 46052570 633 39033443 634 40045262 635 37518355 636 55170812 637 39560836 638 45496274 639 42990825 640 57017492 641 33076321 642 51104988 643 33386248 644 53801516 645 48740302 646 46777040 647 34012224 648 65161458 649 37716195 650 54905340 651 48895730 652 48062504 653 34965946 654 54013610 655 41163163 656 53211583 657 46706316 658 51114732 659 35937000 660 75986000 661 36264856 662 45577624 663 50437285 664 53369658 665 50361118 666 61544511 667 40033405 668 51677480 669 46061123 670 55428206 671 41657421 672 77404758 673 38272921 674 48096892 675 60696465 676 57309590 677 38958388 678 60157664 679 44486440 680 69315074 681 48578595 682 55453764 683 40001688 684 75035427 685 47061706 686 57760297 687 49871075 688 61311791 689 44718721 690 75921434 691 41421736 692 57433056 693 65682156 694 52498584 695 49145899 696 76663954 697 45854803 698 53410174 699 52524286 700 79057070 701 43243726 702 76628103 703 46917235 704 70639610 705 63517582 706 55264532 707 50194939 708 75953164 709 44739052 710 65899478 711 59123409 712 65737706 713 48793683 714 82473884 715 61584964 716 63600488 717 56677923 718 58125600 719 46656000 720 103264545 721 53223715 722 62031865 723 58109708 724 65750600 725 58824900 726 79809741 727 48228544 728 83511506 729 64724454 730 71596838 731 52835284 732 83892004 733 49431046 734 62091904 735 80369485 736 77240214 737 55107939 738 83518485 739 50653000 740 83089500 741 70032236 742 73112414 743 51478848 744 93444378 745 60496027 746 65182402 747 68517669 748 82364376 749 59641971 750 96716140 751 53157376 752 79896975 753 65630883 754 74266352 755 62957203 756 110335695 757 54440128 758 68373400 759 75475098 760 96244514 761 55306531 762 85302308 763 63036073 764 77229320 765 88990041 766 70557696 767 61561401 768 103893348 769 57066817 770 100705466 771 70440904 772 79674836 773 57960796 774 96235821 775 71697510 776 85012538 777 82710806 778 73920794 779 63666190 780 124043768 781 65517171 782 82291256 783 82094952 784 101092901 785 70740841 786 93591996 787 61162984 788 84719256 789 75480243 790 90637622 791 70205668 792 125523660 793 67995631 794 78568582 795 90854794 796 87319208 797 63521398 798 114522488 799 68851900 800 113498590 801 84396792 802 80963804 803 71180406 804 110986156 805 88597102 806 90522082 807 80754505 808 95922722 809 66430327 810 128250666 811 66923416 812 106934532 813 82565603 814 93805182 815 79140187 816 128903215 817 73359523 818 85899304 819 107216718 820 112757472 821 69426736 822 107007236 823 69934528 824 101711258 825 110908425 826 100657572 827 70957944 828 132000531 829 71473582 830 105043694 831 88161239 832 115304058 833 87118003 834 111748316 835 85094035 836 114363788 837 100062390 838 92345400 839 74088000 840 169709890 841 77097399 842 93672394 843 92028658 844 104044520 845 94368586 846 125415429 847 93138199 848 114277519 849 94004003 850 120925490 851 82532619 852 131954764 853 77854696 854 111179914 855 123564756 856 113978106 857 78953803 858 140051934 859 79507000 860 129927660 861 112246345 862 100497024 863 80621568 864 158403642 865 94573669 866 101900812 867 105603592 868 130341260 869 90108195 870 150925400 871 89953033 872 120465266 873 109143582 874 114265476 875 112866045 876 143363152 877 84604738 878 106189600 879 104306131 880 157396639 881 85766341 882 158690700 883 86350888 884 134450448 885 125086222 886 109114776 887 87528384 888 158075874 889 99546931 890 129395198 891 127499328 892 122779784 893 95599971 894 137563910 895 104731579 896 151285780 897 123208284 898 113602724 899 96977917 900 193970145 901 98481388 902 127303124 903 129340442 904 134168282 905 108273043 906 143162756 907 93576664 908 129491240 909 123151125 910 164405288 911 94818816 912 178989631 913 104428323 914 119775472 915 138162952 916 132937016 917 109220019 918 168779229 919 97336000 920 169325570 921 119954915 922 122943974 923 106946241 924 201657856 925 121277490 926 124548736 927 130583049 928 153521078 929 100544857 930 183968954 931 120962926 932 140010396 933 124697043 934 127800504 935 135642631 936 204908868 937 103161943 938 147091972 939 127114346 940 169324716 941 104487346 942 160866866 943 112000678 944 157327023 945 181713477 946 146690556 947 106496424 948 181493164 949 116192056 950 167912430 951 132042109 952 183939386 953 108531571 954 179397015 955 127179283 956 151083848 957 150028360 958 137894400 959 124873870 960 234303674 961 114751801 962 153134524 963 146332461 964 154901060 965 131207404 966 201499296 967 113379904 968 177997732 969 154252159 970 167347178 971 114791256 972 210620052 973 130406131 974 144910624 975 181054495 976 173772143 977 116930413 978 179973308 979 128633842 980 214250925 981 154661307 982 148506264 983 119095488 984 214529098 985 139516111 986 163579382 987 168562482 988 186691316 989 129055443 990 247119747 991 122023936 992 187124886 993 150289763 994 174885324 995 143798419 996 210341740 997 124251748 998 155875000 999 169264254