0 1 1 0 2 72 3 192 4 504 5 576 6 2280 7 1728 8 4248 9 4800 10 7920 11 6336 12 19416 13 10368 14 21312 15 22464 16 33624 17 24192 18 63048 19 32832 20 65808 21 60864 22 83232 23 57600 24 155640 25 76032 26 137520 27 130944 28 180288 29 116928 30 290736 31 143424 32 269784 33 236736 34 305424 35 208512 36 527736 37 241920 38 428256 39 390912 40 530640 41 330624 42 794688 43 381888 44 696672 45 609984 46 760896 47 498816 48 1247160 49 566784 50 982008 51 870912 52 1149264 53 713664 54 1700328 55 805248 56 1447488 57 1218624 58 1522224 59 988992 60 2439504 61 1092096 62 1858176 63 1666752 64 2156760 65 1328256 66 3074976 67 1439424 68 2573424 69 2163456 70 2703744 71 1714176 72 4247832 73 1866240 74 3163248 75 2796096 76 3588768 77 2200320 78 5073648 79 2369088 80 4245840 81 3531648 82 4301136 83 2746944 84 6658368 85 2975616 86 4960800 87 4332096 88 5607648 89 3379968 90 7933680 91 3632256 92 6363072 93 5289792 94 6477696 95 4148352 96 9975864 97 4375296 98 7361928 99 6450624 100 8242632 101 4948416 102 11349072 103 5244480 104 9254160 105 7696512 106 9291888 107 5887296 108 14259288 109 6210432 110 10473408 111 8999808 112 11594304 113 6928128 114 15837792 115 7354368 116 12760272 117 10643712 118 12809376 119 8104320 120 19624464 121 8515584 122 14158512 123 12241152 124 15588864 125 9456768 126 21657408 127 9844416 128 17257176 129 14119872 130 17283744 131 10779840 132 25786080 133 11328768 134 18776160 135 16483392 136 20681136 137 12345984 138 28088640 139 12889152 140 22679424 141 18437760 142 22341312 143 14050944 144 34003416 145 14750208 146 24276816 147 20954304 148 26497296 149 15870528 150 36368472 151 16514496 152 28878624 153 23804928 154 28590336 155 18020736 156 42551952 157 18572544 158 30760704 159 26443584 160 33974352 161 20104704 162 45917256 163 20796480 164 36059184 165 29808000 166 35674848 167 22366080 168 53581632 169 23182848 170 38628576 171 33223488 172 41599584 173 24844608 174 56310768 175 26001216 176 44888544 177 36465984 178 43997904 179 27532224 180 66515472 181 28453248 182 47175552 183 40304256 184 51228864 185 30628224 186 68786304 187 31425408 188 54322560 189 44998080 190 53937216 191 33458688 192 79812408 193 34518528 194 56961936 195 49189248 196 61735608 197 36676800 198 83865888 199 37834560 200 66301992 201 53428416 202 64284912 203 40275072 204 95119920 205 41682816 206 68187456 207 58924800 208 74071440 209 43858944 210 100075392 211 45074880 212 77889168 213 63576576 214 76428576 215 48087936 216 114723192 217 49185792 218 80821296 219 69092736 220 87808320 221 51867648 222 116942640 223 53217216 224 92750400 225 76289088 226 90032400 227 56135232 228 132799776 229 57670272 230 95679360 231 81374976 232 102673296 233 60694272 234 138392880 235 62795520 236 107467488 237 87556416 238 105501312 239 65534976 240 157114512 241 67191552 242 110617128 243 95366208 244 118767312 245 71364672 246 159125904 247 72372096 248 125409024 249 101542464 250 122845536 251 75874752 252 181603392 253 77787648 254 127794816 255 109952640 256 138051288 257 81487872 258 183569568 259 83659392 260 144894816 261 118124352 262 140302944 263 87348096 264 207464544 265 90035712 266 147250944 267 125214336 268 157342752 269 93465792 270 214272432 271 95525568 272 165615408 273 134276736 274 160445520 275 100710720 276 235562688 277 102024576 278 167586336 279 144292416 280 182457216 281 106490880 282 239711616 283 108779328 284 187244352 285 153512064 286 182695104 287 113807232 288 272058456 289 115831296 290 191765664 291 162107520 292 203530032 293 120715200 294 272424744 295 124232832 296 213242832 297 174246336 298 206431344 299 128346624 300 304909032 301 131279616 302 214863552 303 182972736 304 231185952 305 137294208 306 309382416 307 138926016 308 239738112 309 194070336 310 234231552 311 144362880 312 342345552 313 147211776 314 241487280 315 209927808 316 257968512 317 152920512 318 343723824 319 155938176 320 271788624 321 217546560 322 261167616 323 161820288 324 384990456 325 166195584 326 270220896 327 230014464 328 290135664 329 171426816 330 387488448 331 174083904 332 299168928 333 245316480 334 290605248 335 181876608 336 428940096 337 183707136 338 301322808 339 256252032 340 323961120 341 190483200 342 431918304 343 194230656 344 334694880 345 272305152 346 323106480 347 200521152 348 472153104 349 204028416 350 338118336 351 287534976 352 359149536 353 211173120 354 474200352 355 216442368 356 368824752 357 300246912 358 357880032 359 222137856 360 535185360 361 225884160 362 370034928 363 314848704 364 395609472 365 235271808 366 524071536 367 237218112 368 410058432 369 333801216 370 398276640 371 245842560 372 576720384 373 249080832 374 408421440 375 349653888 376 437053824 377 257318784 378 585006144 379 261282240 380 452230848 381 363756480 382 434769408 383 269687808 384 638490936 385 277129728 386 448575120 387 385075392 388 477488880 389 282517056 390 639410976 391 287110656 392 496699992 393 399294144 394 477113328 395 298205568 396 703172448 397 300340224 398 491734080 399 419102976 400 530828136 401 309518208 402 694378464 403 314333568 404 539065872 405 445034304 406 523541376 407 323846784 408 765395568 409 328423680 410 541894752 411 456662016 412 571712832 413 339072768 414 766131264 415 345831552 416 592653456 417 476971584 418 570183552 419 353134656 420 839064960 421 358128000 422 586213344 423 502844544 424 626724432 425 371468160 426 826324416 427 374751360 428 640971360 429 519972480 430 625120704 431 384255360 432 918449976 433 389712384 434 639516672 435 545792256 436 677536848 437 400651776 438 898158480 439 406050624 440 706508352 441 571467456 442 673934688 443 417387456 444 980595024 445 426342528 446 692014464 447 587514816 448 742036032 449 434498688 450 991700472 451 440657280 452 754933104 453 611503296 454 729919584 455 457314048 456 1068478368 457 458134272 458 749306736 459 642805632 460 802134144 461 470295360 462 1057916160 463 476445888 464 821960208 465 666665856 466 789363792 467 488842560 468 1160336976 469 496689408 470 816300288 471 687302016 472 864542304 473 508345344 474 1138345728 475 518657472 476 884386944 477 721037376 478 851868288 479 527483520 480 1257014160 481 534373632 482 873438480 483 743357952 484 927600408 485 551952000 486 1239743208 487 554399424 488 955482768 489 769114176 490 927703152 491 568201536 492 1334222064 493 575309952 494 940891968 495 812840832 496 1004020992 497 591045120 498 1320158304 499 596376000 500 1030140576 501 827134848 502 986804640 503 610806528 504 1461129792 505 623144448 506 1011384576 507 857620800 508 1071763200 509 633087936 510 1429547616 511 642363264 512 1104422616 513 897389376 514 1059195024 515 660878208 516 1539144672 517 663814656 518 1087279488 519 919588032 520 1165849056 521 678844800 522 1535636016 523 686625984 524 1176157728 525 962318400 526 1135088064 527 702656640 528 1660912992 529 710553600 530 1170549792 531 994724928 532 1234674432 533 727147008 534 1627611408 535 740949120 536 1266130080 537 1018588608 538 1214556336 539 754405056 540 1796608080 541 760019328 542 1241929728 543 1053150720 544 1324944432 545 783199872 546 1745728896 547 785643840 548 1345346352 549 1099342464 550 1309162464 551 803111040 552 1895209920 553 814067712 554 1326234096 555 1133536896 556 1405109088 557 829541952 558 1875744384 559 838850688 560 1460734848 561 1162449792 562 1384557264 563 856577088 564 2009860992 565 872678016 566 1414334880 567 1215026880 568 1506696768 569 884163456 570 1995630912 571 893671488 572 1531782720 573 1237455360 574 1479445632 575 920030976 576 2176478040 577 922129920 578 1506596184 579 1276743552 580 1607863392 581 944098560 582 2107148496 583 951854976 584 1637618544 585 1341304704 586 1569640176 587 970820928 588 2284150680 589 980999424 590 1614741696 591 1357881408 592 1707060816 593 1000892160 594 2265179040 595 1022305536 596 1730688912 597 1399571520 598 1668965760 599 1031500800 600 2453310408 601 1041914880 602 1706694912 603 1456622016 604 1801305792 605 1072279872 606 2378779056 607 1073628864 608 1849667616 609 1490085504 610 1784592288 611 1095402240 612 2594165616 613 1105684992 614 1805427936 615 1542312576 616 1928865024 617 1127480832 618 2522886720 619 1138549824 620 1963994112 621 1591771392 622 1877050944 623 1164108672 624 2740760016 625 1181309184 626 1913405904 627 1622827008 628 2024716752 629 1194939648 630 2728999296 631 1205807040 632 2075481216 633 1668410304 634 1987719984 635 1238935680 636 2882051280 637 1244889216 638 2027222208 639 1733405184 640 2174330448 641 1264247424 642 2828424096 643 1275925824 644 2190057984 645 1779193728 646 2103482304 647 1300022784 648 3097599384 649 1313155584 650 2160299088 651 1820144640 652 2265882912 653 1336408128 654 2989930992 655 1359580032 656 2322723312 657 1884082560 658 2228659200 659 1373697216 660 3248963136 661 1386153216 662 2262890016 663 1918183680 664 2406979872 665 1427240448 666 3189278832 667 1424507904 668 2436826176 669 1969545408 670 2364777792 671 1451263104 672 3431863104 673 1463298048 674 2388224016 675 2060446080 676 2526550920 677 1489317696 678 3331376208 679 1507095936 680 2606403744 681 2077434432 682 2476205568 683 1529371584 684 3621450912 685 1555175808 686 2525493888 687 2132715264 688 2679487200 689 1570686336 690 3539749248 691 1583772480 692 2708948304 693 2219201280 694 2607256224 695 1624252032 696 3798865872 697 1625702400 698 2652558768 699 2246590080 700 2834850240 701 1653331392 702 3737880816 703 1667910528 704 2873209824 705 2323323648 706 2744716176 707 1701187200 708 3975790176 709 1710854784 710 2814092928 711 2387913792 712 2967672816 713 1740114432 714 3902774400 715 1770681600 716 3000740256 717 2424563712 718 2887040448 719 1784204928 720 4284513360 721 1804322304 722 2936029032 723 2485949568 724 3102402960 725 1844013888 726 4093289544 727 1844268480 728 3182905728 729 2574852672 730 3058627680 731 1875339648 732 4393977360 733 1890317952 734 3084585984 735 2640392640 736 3280888512 737 1922913792 738 4339443024 739 1937193408 740 3339244512 741 2677913472 742 3195725184 743 1968971904 744 4640269056 745 2000602368 746 3238286832 747 2769304896 748 3424607424 749 2022679296 750 4545777888 751 2033197632 752 3498959232 753 2808520128 754 3345226272 755 2082227328 756 4905008448 757 2082112128 758 3397111200 759 2878530048 760 3638614464 761 2115520128 762 4729382016 763 2138444928 764 3645642240 765 2998767744 766 3505720320 767 2166961536 768 5107946808 769 2182754304 770 3602603520 771 3014658432 772 3761359344 773 2216928960 774 5005946400 775 2252380608 776 3842036784 777 3094617216 778 3673164528 779 2269459584 780 5361283296 781 2288300544 782 3730914432 783 3190567104 784 3976465176 785 2340494208 786 5190328800 787 2339682624 788 3999975696 789 3230713728 790 3876447744 791 2382477696 792 5657656032 793 2394849024 794 3904415280 795 3331549440 796 4123160640 797 2430218304 798 5448407808 799 2448859392 800 4246934760 801 3414275712 802 4023610128 803 2487212928 804 5822360736 805 2531644416 806 4086095616 807 3456903744 808 4337135568 809 2541483648 810 5785480944 811 2560476096 812 4389740928 813 3534705600 814 4210227648 815 2619289728 816 6127383024 817 2618044416 818 4269243600 819 3662027904 820 4543553952 821 2656467648 822 5936763024 823 2675788992 824 4599952704 825 3726091584 826 4408706304 827 2714859072 828 6423565248 829 2734680960 830 4495597632 831 3774681600 832 4741222032 833 2783071872 834 6200548512 835 2816895744 836 4780745856 837 3897211200 838 4590055008 839 2834719488 840 6751064448 841 2855381760 842 4656273264 843 3940631424 844 4914841248 845 2920605120 846 6536916864 847 2927309760 848 5017292496 849 4025378112 850 4829893488 851 2958312960 852 6928649280 853 2978968320 854 4872387456 855 4186263168 856 5156888544 857 3021298560 858 6759543744 859 3042283968 860 5241427776 861 4210738560 862 4996024704 863 3085046784 864 7348233144 865 3131433216 866 5065732368 867 4287862848 868 5361960960 869 3152330496 870 7095260448 871 3173019264 872 5451603984 873 4420212864 874 5208715008 875 3250909440 876 7530778608 877 3237829632 878 5279424192 879 4467375936 880 5656067136 881 3282301440 882 7429020552 883 3304791360 884 5651160480 885 4595854464 886 5424783264 887 3349934208 888 7889594640 889 3382096896 890 5542802784 891 4704668352 892 5802011136 893 3418725888 894 7637349168 895 3468749184 896 5936247360 897 4750050816 898 5648359824 899 3487821696 900 8315106888 901 3511734912 902 5728580928 903 4857505536 904 6074005680 905 3586250880 906 7949017536 907 3581620416 908 6119871264 909 4989985344 910 5944819968 911 3629039616 912 8553941664 913 3655812096 914 5955699024 915 5079265920 916 6283212048 917 3712225536 918 8356718160 919 3725652672 920 6454062720 921 5138635200 922 6113406384 923 3775970304 924 8870162688 925 3829794048 926 6193313280 927 5292294720 928 6576290064 929 3848236416 930 8666770176 931 3885281856 932 6618043440 933 5342315904 934 6355339488 935 3958730496 936 9335988240 937 3948521472 938 6455943936 939 5445909888 940 6844421376 941 3999373632 942 8934793584 943 4025452032 944 6921520992 945 5670006912 946 6608444544 947 4076655552 948 9544435584 949 4104255744 950 6742418976 951 5657401152 952 7116052608 953 4154585472 954 9373614192 955 4214246400 956 7142707584 957 5769781632 958 6857994240 959 4245763968 960 10056252816 961 4260266496 962 6947552160 963 5933196864 964 7323517296 965 4348008576 966 9664233984 967 4340312640 968 7463124792 969 5986866816 970 7175874528 971 4394533824 972 10394794200 973 4434524928 974 7207295040 975 6148587264 976 7649516304 977 4476279168 978 9998884320 979 4507249536 980 7778486160 981 6272037888 982 7386292512 983 4559488128 984 10734955056 985 4623796224 986 7478757216 987 6343087104 988 7888941504 989 4643817984 990 10566977472 991 4671639360 992 8032815360 993 6440569152 994 7682674176 995 4766232960 996 11068872480 997 4756727808 998 7753356000 999 6626305536 1000 8288131104