0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 2 8 3 9 4 10 5 11 4 12 3 13 2 14 1 15 1 16 3 17 6 18 10 19 15 20 18 21 19 22 18 23 15 24 10 25 6 26 3 27 1 28 1 29 4 30 10 31 20 32 35 33 52 34 68 35 80 36 85 37 80 38 68 39 52 40 35 41 20 42 10 43 4 44 1 45 1 46 5 47 15 48 35 49 70 50 121 51 185 52 255 53 320 54 365 55 381 56 365 57 320 58 255 59 185 60 121 61 70 62 35 63 15 64 5 65 1 66 1 67 6 68 21 69 56 70 126 71 246 72 426 73 666 74 951 75 1246 76 1506 77 1686 78 1751 79 1686 80 1506 81 1246 82 951 83 666 84 426 85 246 86 126 87 56 88 21 89 6 90 1 91 1 92 7 93 28 94 84 95 210 96 455 97 875 98 1520 99 2415 100 3535 101 4795 102 6055 103 7140 104 7875 105 8135 106 7875 107 7140 108 6055 109 4795 110 3535 111 2415 112 1520 113 875 114 455 115 210 116 84 117 28 118 7 119 1 120 1 121 8 122 36 123 120 124 330 125 784 126 1652 127 3144 128 5475 129 8800 130 13140 131 18320 132 23940 133 29400 134 34000 135 37080 136 38165 137 37080 138 34000 139 29400 140 23940 141 18320 142 13140 143 8800 144 5475 145 3144 146 1652 147 784 148 330 149 120 150 36 151 8 152 1 153 1 154 9 155 45 156 165 157 495 158 1278 159 2922 160 6030 161 11385 162 19855 163 32211 164 48879 165 69675 166 93600 167 118800 168 142740 169 162585 170 175725 171 180325 172 175725 173 162585 174 142740 175 118800 176 93600 177 69675 178 48879 179 32211 180 19855 181 11385 182 6030 183 2922 184 1278 185 495 186 165 187 45 188 9 189 1 190 1 191 10 192 55 193 220 194 715 195 1992 196 4905 197 10890 198 22110 199 41470 200 72403 201 118360 202 182005 203 264220 204 363165 205 473694 206 587400 207 693450 208 780175 209 837100 210 856945 211 837100 212 780175 213 693450 214 587400 215 473694 216 363165 217 264220 218 182005 219 118360 220 72403 221 41470 222 22110 223 10890 224 4905 225 1992 226 715 227 220 228 55 229 10 230 1 231 1 232 11 233 66 234 286 235 1001 236 2992 237 7887 238 18722 239 40612 240 81367 241 151778 242 265233 243 436348 244 678458 245 1000153 246 1401444 247 1870484 248 2381929 249 2897884 250 3371819 251 3755070 252 4004770 253 4091495 254 4004770 255 3755070 256 3371819 257 2897884 258 2381929 259 1870484 260 1401444 261 1000153 262 678458 263 436348 264 265233 265 151778 266 81367 267 40612 268 18722 269 7887 270 2992 271 1001 272 286 273 66 274 11 275 1 276 1 277 12 278 78 279 364 280 1365 281 4356 282 12232 283 30888 284 71214 285 151580 286 300366 287 557712 288 975338 289 1613184 290 2531970 291 3781636 292 5386887 293 7332468 294 9551894 295 11923560 296 14277186 297 16411472 298 18121038 299 19227924 300 19611175 301 19227924 302 18121038 303 16411472 304 14277186 305 11923560 306 9551894 307 7332468 308 5386887 309 3781636 310 2531970 311 1613184 312 975338 313 557712 314 300366 315 151580 316 71214 317 30888 318 12232 319 4356 320 1365 321 364 322 78 323 12 324 1 325 1 326 13 327 91 328 455 329 1820 330 6175 331 18395 332 49205 333 120055 334 270270 335 566280 336 1111760 337 2056210 338 3598180 339 5978570 340 9459840 341 14289015 342 20646145 343 28584855 344 37976445 345 48471995 346 59496580 347 70285150 348 79961180 349 87648795 350 92599533 351 94309099 352 92599533 353 87648795 354 79961180 355 70285150 356 59496580 357 48471995 358 37976445 359 28584855 360 20646145 361 14289015 362 9459840 363 5978570 364 3598180 365 2056210 366 1111760 367 566280 368 270270 369 120055 370 49205 371 18395 372 6175 373 1820 374 455 375 91 376 13 377 1 378 1 379 14 380 105 381 560 382 2380 383 8554 384 26936 385 76050 386 195650 387 464100 388 1024205 389 2117570 390 4124575 391 7602700 392 13311000 393 22204560 394 35381815 395 53971750 396 78958425 397 110956300 398 149968455 399 195176020 400 244815025 401 296191350 402 345863700 403 389991238 404 424803757 405 447118140 406 454805755 407 447118140 408 424803757 409 389991238 410 345863700 411 296191350 412 244815025 413 195176020 414 149968455 415 110956300 416 78958425 417 53971750 418 35381815 419 22204560 420 13311000 421 7602700 422 4124575 423 2117570 424 1024205 425 464100 426 195650 427 76050 428 26936 429 8554 430 2380 431 560 432 105 433 14 434 1 435 1 436 15 437 120 438 680 439 3060 440 11613 441 38535 442 114480 443 309570 444 771290 445 1786941 446 3877575 447 7926100 448 15333150 449 28180050 450 49360405 451 82624650 452 132471825 453 203827550 454 301472850 455 429236745 456 589030950 457 779874225 458 997107150 459 1232014550 460 1472037333 461 1701665070 462 1903968185 463 2062582590 464 2163837030 465 2198649549 466 2163837030 467 2062582590 468 1903968185 469 1701665070 470 1472037333 471 1232014550 472 997107150 473 779874225 474 589030950 475 429236745 476 301472850 477 203827550 478 132471825 479 82624650 480 49360405 481 28180050 482 15333150 483 7926100 484 3877575 485 1786941 486 771290 487 309570 488 114480 489 38535 490 11613 491 3060 492 680 493 120 494 15 495 1 496 1 497 16 498 136 499 816 500 3876 501 15488 502 54008 503 168368 504 477258 505 1245488 506 3020816 507 6859856 508 14671476 509 29695056 510 57103816 511 104677280 512 183424355 513 307970080 514 496464480 515 769757280 516 1149633620 517 1656039920 518 2303442320 519 3096721920 520 4027263620 521 5070064208 522 6182698328 523 7306792288 524 8372267728 525 9304090208 526 10030702424 527 10492874384 528 10651488789 529 10492874384 530 10030702424 531 9304090208 532 8372267728 533 7306792288 534 6182698328 535 5070064208 536 4027263620 537 3096721920 538 2303442320 539 1656039920 540 1149633620 541 769757280 542 496464480 543 307970080 544 183424355 545 104677280 546 57103816 547 29695056 548 14671476 549 6859856 550 3020816 551 1245488 552 477258 553 168368 554 54008 555 15488 556 3876 557 816 558 136 559 16 560 1 561 1 562 17 563 153 564 969 565 4845 566 20332 567 74324 568 242556 569 718998 570 1960610 571 4965938 572 11771786 573 26274894 574 55492692 575 111351020 576 213007484 577 389571983 578 682870587 579 1149640011 580 1862293475 581 2907249815 582 4379865380 583 6375337620 584 8975595060 585 12233101400 586 16153531988 587 20680190396 588 25683540364 589 30959086172 590 36235912760 591 41196550976 592 45506727032 593 48851423533 594 50972030189 595 51698642405 596 50972030189 597 48851423533 598 45506727032 599 41196550976 600 36235912760 601 30959086172 602 25683540364 603 20680190396 604 16153531988 605 12233101400 606 8975595060 607 6375337620 608 4379865380 609 2907249815 610 1862293475 611 1149640011 612 682870587 613 389571983 614 213007484 615 111351020 616 55492692 617 26274894 618 11771786 619 4965938 620 1960610 621 718998 622 242556 623 74324 624 20332 625 4845 626 969 627 153 628 17 629 1 630 1 631 18 632 171 633 1140 634 5985 635 26316 636 100623 637 343026 638 1061055 639 3016820 640 7962426 641 19659888 642 45692226 643 100465920 644 209856330 645 417897876 646 795698073 647 1452293766 648 2546441085 649 4297383540 650 6991625871 651 10981919268 652 16674386301 653 24500341350 654 34871149275 655 48117431448 656 64417756464 657 83725959208 658 105709450320 659 129712261680 660 154755280668 661 179581817304 662 202749700473 663 222762644490 664 238225374135 665 248000853348 666 251345549849 667 248000853348 668 238225374135 669 222762644490 670 202749700473 671 179581817304 672 154755280668 673 129712261680 674 105709450320 675 83725959208 676 64417756464 677 48117431448 678 34871149275 679 24500341350 680 16674386301 681 10981919268 682 6991625871 683 4297383540 684 2546441085 685 1452293766 686 795698073 687 417897876 688 209856330 689 100465920 690 45692226 691 19659888 692 7962426 693 3016820 694 1061055 695 343026 696 100623 697 26316 698 5985 699 1140 700 171 701 18 702 1 703 1 704 19 705 190 706 1330 707 7315 708 33630 709 134235 710 477090 711 1537005 712 4547840 713 12483950 714 32043215 715 77392415 716 176797280 717 383636790 718 793572240 719 1569610425 720 2976211965 721 5422187130 722 9509714340 723 16083442335 724 26269663530 725 41491756065 726 63445656330 727 94019422065 728 135145227642 729 188581064838 730 255632637745 731 336841746715 732 431682859120 733 538320708340 734 653484769180 735 772508510445 736 889561704615 737 998074817070 738 1091320389750 739 1163084122295 740 1208335275170 741 1223798004815 742 1208335275170 743 1163084122295 744 1091320389750 745 998074817070 746 889561704615 747 772508510445 748 653484769180 749 538320708340 750 431682859120 751 336841746715 752 255632637745 753 188581064838 754 135145227642 755 94019422065 756 63445656330 757 41491756065 758 26269663530 759 16083442335 760 9509714340 761 5422187130 762 2976211965 763 1569610425 764 793572240 765 383636790 766 176797280 767 77392415 768 32043215 769 12483950 770 4547840 771 1537005 772 477090 773 134235 774 33630 775 7315 776 1330 777 190 778 19 779 1 780 1 781 20 782 210 783 1540 784 8855 785 42484 786 176700 787 653600 788 2189275 789 6729800 790 19180120 791 51089100 792 128004425 793 303264700 794 682353650 795 1463441940 796 3001009150 797 5899828700 798 11145218550 799 20271296100 800 35561166195 801 60261219300 802 98776763400 803 156800232600 804 241309940325 805 360371725632 806 522683126940 807 736824008620 808 1010220099005 809 1347883536060 810 1751059016758 811 2215962721100 812 2732838593800 813 3285558551700 814 3851950509650 815 4404950191060 816 4914549544175 817 5350376308900 818 5684612609100 819 5894873067200 820 5966636799745 821 5894873067200 822 5684612609100 823 5350376308900 824 4914549544175 825 4404950191060 826 3851950509650 827 3285558551700 828 2732838593800 829 2215962721100 830 1751059016758 831 1347883536060 832 1010220099005 833 736824008620 834 522683126940 835 360371725632 836 241309940325 837 156800232600 838 98776763400 839 60261219300 840 35561166195 841 20271296100 842 11145218550 843 5899828700 844 3001009150 845 1463441940 846 682353650 847 303264700 848 128004425 849 51089100 850 19180120 851 6729800 852 2189275 853 653600 854 176700 855 42484 856 8855 857 1540 858 210 859 20 860 1 861 1 862 21 863 231 864 1771 865 10626 866 53109 867 229789 868 883179 869 3070914 870 9791859 871 28929495 872 79841895 873 207192720 874 508268145 875 1183891995 876 2628153815 877 5578073865 878 11349898140 879 22191851990 880 41780794440 881 75878518695 882 133138728845 883 226015663545 884 371670677595 885 592709321820 886 917519881257 887 1379941788897 888 2017989034117 889 2871408900522 890 3977982496257 891 5368669787383 892 7061949381543 893 9057963966723 894 11333302419418 895 13837369393008 896 16491260567310 897 19189847390385 898 21807385105485 899 24206439162885 900 26249361720435 901 27811048329120 902 28791371852145 903 29125608152345 904 28791371852145 905 27811048329120 906 26249361720435 907 24206439162885 908 21807385105485 909 19189847390385 910 16491260567310 911 13837369393008 912 11333302419418 913 9057963966723 914 7061949381543 915 5368669787383 916 3977982496257 917 2871408900522 918 2017989034117 919 1379941788897 920 917519881257 921 592709321820 922 371670677595 923 226015663545 924 133138728845 925 75878518695 926 41780794440 927 22191851990 928 11349898140 929 5578073865 930 2628153815 931 1183891995 932 508268145 933 207192720 934 79841895 935 28929495 936 9791859 937 3070914 938 883179 939 229789 940 53109 941 10626 942 1771 943 231 944 21 945 1 946 1 947 22 948 253 949 2024 950 12650 951 65758 952 295526 953 1178474 954 4247617 955 14028850 956 42905236 957 122517342 958 328826883 959 834024114 960 2008124250 961 4607348570 962 10105580540 963 21248285960 964 42931869805 965 83528772250 966 156779137130 967 284339792110 968 499005557515 969 848484383120 970 1399412910500 971 2241054273062 972 3487857333114 973 5279830703686 974 7779568926613 975 11164842101050 976 15615992007176 977 21297999599822 978 28337974532428 979 36799868051324 980 46659254948075 981 57781845728002 982 69909743736844 983 82659164875606 984 95532301619073 985 107944293946500 986 119264081708310 987 128865606170070 988 136183829216930 989 140768761906190 990 142330448514875 991 140768761906190 992 136183829216930 993 128865606170070 994 119264081708310 995 107944293946500 996 95532301619073 997 82659164875606 998 69909743736844 999 57781845728002 1000 46659254948075 1001 36799868051324 1002 28337974532428 1003 21297999599822 1004 15615992007176 1005 11164842101050 1006 7779568926613 1007 5279830703686 1008 3487857333114 1009 2241054273062 1010 1399412910500 1011 848484383120 1012 499005557515 1013 284339792110 1014 156779137130 1015 83528772250 1016 42931869805 1017 21248285960 1018 10105580540 1019 4607348570 1020 2008124250 1021 834024114 1022 328826883 1023 122517342 1024 42905236 1025 14028850 1026 4247617 1027 1178474 1028 295526 1029 65758 1030 12650 1031 2024 1032 253 1033 22 1034 1 1035 1 1036 23 1037 276 1038 2300 1039 14950 1040 80707 1041 376211 1042 1554432 1043 5800025 1044 19816225 1045 62655703 1046 184877519 1047 512525928 1048 1342302425 1049 3336397825 1050 7900841159 1051 17883904357 1052 38803363434 1053 80901209125 1054 162421857125 1055 314593645685 1056 588827857255 1057 1066585128810 1058 1872137642125 1059 3188021780375 1060 5272296916307 1061 8475814457311 1062 13256639603482 1063 20187724146975 1064 29953153337525 1065 43328091071639 1066 61138233338347 1067 84196377167089 1068 113216676291800 1069 148711089138825 1070 190876942859651 1071 239488686996673 1072 293809877339851 1073 352542310907600 1074 413827349906025 1075 475309585886333 1076 534265448319559 1077 587790112660883 1078 633026572948000 1079 667412727516375 1080 688917407714255 1081 696235630761115 1082 688917407714255 1083 667412727516375 1084 633026572948000 1085 587790112660883 1086 534265448319559 1087 475309585886333 1088 413827349906025 1089 352542310907600 1090 293809877339851 1091 239488686996673 1092 190876942859651 1093 148711089138825 1094 113216676291800 1095 84196377167089 1096 61138233338347 1097 43328091071639 1098 29953153337525 1099 20187724146975 1100 13256639603482 1101 8475814457311 1102 5272296916307 1103 3188021780375 1104 1872137642125 1105 1066585128810 1106 588827857255 1107 314593645685 1108 162421857125 1109 80901209125 1110 38803363434 1111 17883904357 1112 7900841159 1113 3336397825 1114 1342302425 1115 512525928 1116 184877519 1117 62655703 1118 19816225 1119 5800025 1120 1554432 1121 376211 1122 80707 1123 14950 1124 2300 1125 276 1126 23 1127 1 1128 1 1129 24 1130 300 1131 2600 1132 17550 1133 98256 1134 474444 1135 2028600 1136 7826325 1137 27627600 1138 90202596 1139 274703904 1140 785675400 1141 2122177800 1142 5438759400 1143 13276944856 1144 30975971694 1145 69266809200 1146 148825715900 1147 307911175200 1148 614603979726 1149 1185547932624 1150 2213329698000 1151 4004566131000 1152 7030166054250 1153 11987869324872 1154 19874855924928 1155 32064910399600 1156 50380496904450 1157 77145628461600 1158 115201422616932 1159 167863841497968 1160 238803579061575 1161 331832531206400 1162 450590467007700 1163 598139318795712 1164 776489772454038 1165 986103272626800 1166 1225428907242600 1167 1490545168009800 1168 1774977811036482 1169 2069754572359368 1170 2363734807680400 1171 2644219069720800 1172 2897804447331150 1173 3111412269159072 1174 3273382451600628 1175 3374509746654000 1176 3408895901222375 1177 3374509746654000 1178 3273382451600628 1179 3111412269159072 1180 2897804447331150 1181 2644219069720800 1182 2363734807680400 1183 2069754572359368 1184 1774977811036482 1185 1490545168009800 1186 1225428907242600 1187 986103272626800 1188 776489772454038 1189 598139318795712 1190 450590467007700 1191 331832531206400 1192 238803579061575 1193 167863841497968 1194 115201422616932 1195 77145628461600 1196 50380496904450 1197 32064910399600 1198 19874855924928 1199 11987869324872 1200 7030166054250 1201 4004566131000 1202 2213329698000 1203 1185547932624 1204 614603979726 1205 307911175200 1206 148825715900 1207 69266809200 1208 30975971694 1209 13276944856 1210 5438759400 1211 2122177800 1212 785675400 1213 274703904 1214 90202596 1215 27627600 1216 7826325 1217 2028600 1218 474444 1219 98256 1220 17550 1221 2600 1222 300 1223 24 1224 1 1225 1 1226 25 1227 325 1228 2925 1229 20475 1230 118730 1231 593150 1232 2621450 1233 10445175 1234 38055225 1235 128159565 1236 402389025 1237 1186035825 1238 3300387300 1239 8711519100 1240 21898261360 1241 52599529150 1242 121080662950 1243 267784201050 1244 570256616850 1245 1171583651720 1246 2326155612650 1247 4470218501450 1248 8325958916550 1249 15048213795600 1250 26421479140746 1251 45110787133050 1252 74962367834650 1253 121338298608100 1254 191453761015450 1255 294667314307510 1256 442656299880550 1257 649394968542525 1258 930847002844475 1259 1304291841390575 1260 1787229737569355 1261 2395855668525425 1262 3143155362090650 1263 4036751738126850 1264 5076706439128950 1265 6253544931369720 1266 7546809731275050 1267 8924441266328650 1268 10343231428806850 1269 11750490708128200 1270 13086925166250790 1271 14290553045492050 1272 15301327984465650 1273 16066004815967225 1274 16542710115290075 1275 16704680297731631 1276 16542710115290075 1277 16066004815967225 1278 15301327984465650 1279 14290553045492050 1280 13086925166250790 1281 11750490708128200 1282 10343231428806850 1283 8924441266328650 1284 7546809731275050 1285 6253544931369720 1286 5076706439128950 1287 4036751738126850 1288 3143155362090650 1289 2395855668525425 1290 1787229737569355 1291 1304291841390575 1292 930847002844475 1293 649394968542525 1294 442656299880550 1295 294667314307510 1296 191453761015450 1297 121338298608100 1298 74962367834650 1299 45110787133050 1300 26421479140746 1301 15048213795600 1302 8325958916550 1303 4470218501450 1304 2326155612650 1305 1171583651720 1306 570256616850 1307 267784201050 1308 121080662950 1309 52599529150 1310 21898261360 1311 8711519100 1312 3300387300 1313 1186035825 1314 402389025 1315 128159565 1316 38055225 1317 10445175 1318 2621450 1319 593150 1320 118730 1321 20475 1322 2925 1323 325 1324 25 1325 1