0 1 1 1 2 1 3 1 4 5 5 1 6 1 7 6 8 6 9 1 10 1 11 7 12 12 13 7 14 1 15 1 16 8 17 19 18 19 19 8 20 1 21 1 22 9 23 27 24 38 25 27 26 9 27 1 28 1 29 10 30 36 31 65 32 65 33 36 34 10 35 1 36 1 37 11 38 46 39 101 40 130 41 101 42 46 43 11 44 1 45 1 46 12 47 57 48 147 49 231 50 231 51 147 52 57 53 12 54 1 55 1 56 13 57 69 58 204 59 378 60 462 61 378 62 204 63 69 64 13 65 1 66 1 67 14 68 82 69 273 70 582 71 840 72 840 73 582 74 273 75 82 76 14 77 1 78 1 79 15 80 96 81 355 82 855 83 1422 84 1680 85 1422 86 855 87 355 88 96 89 15 90 1 91 1 92 16 93 111 94 451 95 1210 96 2277 97 3102 98 3102 99 2277 100 1210 101 451 102 111 103 16 104 1 105 1 106 17 107 127 108 562 109 1661 110 3487 111 5379 112 6204 113 5379 114 3487 115 1661 116 562 117 127 118 17 119 1 120 1 121 18 122 144 123 689 124 2223 125 5148 126 8866 127 11583 128 11583 129 8866 130 5148 131 2223 132 689 133 144 134 18 135 1 136 1 137 19 138 162 139 833 140 2912 141 7371 142 14014 143 20449 144 23166 145 20449 146 14014 147 7371 148 2912 149 833 150 162 151 19 152 1 153 1 154 20 155 181 156 995 157 3745 158 10283 159 21385 160 34463 161 43615 162 43615 163 34463 164 21385 165 10283 166 3745 167 995 168 181 169 20 170 1 171 1 172 21 173 201 174 1176 175 4740 176 14028 177 31668 178 55848 179 78078 180 87230 181 78078 182 55848 183 31668 184 14028 185 4740 186 1176 187 201 188 21 189 1 190 1 191 22 192 222 193 1377 194 5916 195 18768 196 45696 197 87516 198 133926 199 165308 200 165308 201 133926 202 87516 203 45696 204 18768 205 5916 206 1377 207 222 208 22 209 1 210 1 211 23 212 244 213 1599 214 7293 215 24684 216 64464 217 133212 218 221442 219 299234 220 330616 221 299234 222 221442 223 133212 224 64464 225 24684 226 7293 227 1599 228 244 229 23 230 1 231 1 232 24 233 267 234 1843 235 8892 236 31977 237 89148 238 197676 239 354654 240 520676 241 629850 242 629850 243 520676 244 354654 245 197676 246 89148 247 31977 248 8892 249 1843 250 267 251 24 252 1 253 1 254 25 255 291 256 2110 257 10735 258 40869 259 121125 260 286824 261 552330 262 875330 263 1150526 264 1259700 265 1150526 266 875330 267 552330 268 286824 269 121125 270 40869 271 10735 272 2110 273 291 274 25 275 1 276 1 277 26 278 316 279 2401 280 12845 281 51604 282 161994 283 407949 284 839154 285 1427660 286 2025856 287 2410226 288 2410226 289 2025856 290 1427660 291 839154 292 407949 293 161994 294 51604 295 12845 296 2401 297 316 298 26 299 1 300 1 301 27 302 342 303 2717 304 15246 305 64449 306 213598 307 569943 308 1247103 309 2266814 310 3453516 311 4436082 312 4820452 313 4436082 314 3453516 315 2266814 316 1247103 317 569943 318 213598 319 64449 320 15246 321 2717 322 342 323 27 324 1 325 1 326 28 327 369 328 3059 329 17963 330 79695 331 278047 332 783541 333 1817046 334 3513917 335 5720330 336 7889598 337 9256534 338 9256534 339 7889598 340 5720330 341 3513917 342 1817046 343 783541 344 278047 345 79695 346 17963 347 3059 348 369 349 28 350 1 351 1 352 29 353 397 354 3428 355 21022 356 97658 357 357742 358 1061588 359 2600587 360 5330963 361 9234247 362 13609928 363 17146132 364 18513068 365 17146132 366 13609928 367 9234247 368 5330963 369 2600587 370 1061588 371 357742 372 97658 373 21022 374 3428 375 397 376 29 377 1 378 1 379 30 380 426 381 3825 382 24450 383 118680 384 455400 385 1419330 386 3662175 387 7931550 388 14565210 389 22844175 390 30756060 391 35659200 392 35659200 393 30756060 394 22844175 395 14565210 396 7931550 397 3662175 398 1419330 399 455400 400 118680 401 24450 402 3825 403 426 404 30 405 1 406 1 407 31 408 456 409 4251 410 28275 411 143130 412 574080 413 1874730 414 5081505 415 11593725 416 22496760 417 37409385 418 53600235 419 66415260 420 71318400 421 66415260 422 53600235 423 37409385 424 22496760 425 11593725 426 5081505 427 1874730 428 574080 429 143130 430 28275 431 4251 432 456 433 31 434 1 435 1 436 32 437 487 438 4707 439 32526 440 171405 441 717210 442 2448810 443 6956235 444 16675230 445 34090485 446 59906145 447 91009620 448 120015495 449 137733660 450 137733660 451 120015495 452 91009620 453 59906145 454 34090485 455 16675230 456 6956235 457 2448810 458 717210 459 171405 460 32526 461 4707 462 487 463 32 464 1 465 1 466 33 467 519 468 5194 469 37233 470 203931 471 888615 472 3166020 473 9405045 474 23631465 475 50765715 476 93996630 477 150915765 478 211025115 479 257749155 480 275467320 481 257749155 482 211025115 483 150915765 484 93996630 485 50765715 486 23631465 487 9405045 488 3166020 489 888615 490 203931 491 37233 492 5194 493 519 494 33 495 1 496 1 497 34 498 552 499 5713 500 42427 501 241164 502 1092546 503 4054635 504 12571065 505 33036510 506 74397180 507 144762345 508 244912395 509 361940880 510 468774270 511 533216475 512 533216475 513 468774270 514 361940880 515 244912395 516 144762345 517 74397180 518 33036510 519 12571065 520 4054635 521 1092546 522 241164 523 42427 524 5713 525 552 526 34 527 1 528 1 529 35 530 586 531 6265 532 48140 533 283591 534 1333710 535 5147181 536 16625700 537 45607575 538 107433690 539 219159525 540 389674740 541 606853275 542 830715150 543 1001990745 544 1066432950 545 1001990745 546 830715150 547 606853275 548 389674740 549 219159525 550 107433690 551 45607575 552 16625700 553 5147181 554 1333710 555 283591 556 48140 557 6265 558 586 559 35 560 1 561 1 562 36 563 621 564 6851 565 54405 566 331731 567 1617301 568 6480891 569 21772881 570 62233275 571 153041265 572 326593215 573 608834265 574 996528015 575 1437568425 576 1832705895 577 2068423695 578 2068423695 579 1832705895 580 1437568425 581 996528015 582 608834265 583 326593215 584 153041265 585 62233275 586 21772881 587 6480891 588 1617301 589 331731 590 54405 591 6851 592 621 593 36 594 1 595 1 596 37 597 657 598 7472 599 61256 600 386136 601 1949032 602 8098192 603 28253772 604 84006156 605 215274540 606 479634480 607 935427480 608 1605362280 609 2434096440 610 3270274320 611 3901129590 612 4136847390 613 3901129590 614 3270274320 615 2434096440 616 1605362280 617 935427480 618 479634480 619 215274540 620 84006156 621 28253772 622 8098192 623 1949032 624 386136 625 61256 626 7472 627 657 628 37 629 1 630 1 631 38 632 694 633 8129 634 68728 635 447392 636 2335168 637 10047224 638 36351964 639 112259928 640 299280696 641 694909020 642 1415061960 643 2540789760 644 4039458720 645 5704370760 646 7171403910 647 8037976980 648 8037976980 649 7171403910 650 5704370760 651 4039458720 652 2540789760 653 1415061960 654 694909020 655 299280696 656 112259928 657 36351964 658 10047224 659 2335168 660 447392 661 68728 662 8129 663 694 664 38 665 1 666 1 667 39 668 732 669 8823 670 76857 671 516120 672 2782560 673 12382392 674 46399188 675 148611892 676 411540624 677 994189716 678 2109970980 679 3955851720 680 6580248480 681 9743829480 682 12875774670 683 15209380890 684 16075953960 685 15209380890 686 12875774670 687 9743829480 688 6580248480 689 3955851720 690 2109970980 691 994189716 692 411540624 693 148611892 694 46399188 695 12382392 696 2782560 697 516120 698 76857 699 8823 700 732 701 39 702 1 703 1 704 40 705 771 706 9555 707 85680 708 592977 709 3298680 710 15164952 711 58781580 712 195011080 713 560152516 714 1405730340 715 3104160696 716 6065822700 717 10536100200 718 16324077960 719 22619604150 720 28085155560 721 31285334850 722 31285334850 723 28085155560 724 22619604150 725 16324077960 726 10536100200 727 6065822700 728 3104160696 729 1405730340 730 560152516 731 195011080 732 58781580 733 15164952 734 3298680 735 592977 736 85680 737 9555 738 771 739 40 740 1 741 1 742 41 743 811 744 10326 745 95235 746 678657 747 3891657 748 18463632 749 73946532 750 253792660 751 755163596 752 1965882856 753 4509891036 754 9169983396 755 16601922900 756 26860178160 757 38943682110 758 50704759710 759 59370490410 760 62570669700 761 59370490410 762 50704759710 763 38943682110 764 26860178160 765 16601922900 766 9169983396 767 4509891036 768 1965882856 769 755163596 770 253792660 771 73946532 772 18463632 773 3891657 774 678657 775 95235 776 10326 777 811 778 41 779 1 780 1 781 42 782 852 783 11137 784 105561 785 773892 786 4570314 787 22355289 788 92410164 789 327739192 790 1008956256 791 2721046452 792 6475773892 793 13679874432 794 25771906296 795 43462101060 796 65803860270 797 89648441820 798 110075250120 799 121941160110 800 121941160110 801 110075250120 802 89648441820 803 65803860270 804 43462101060 805 25771906296 806 13679874432 807 6475773892 808 2721046452 809 1008956256 810 327739192 811 92410164 812 22355289 813 4570314 814 773892 815 105561 816 11137 817 852 818 42 819 1 820 1 821 43 822 894 823 11989 824 116698 825 879453 826 5344206 827 26925603 828 114765453 829 420149356 830 1336695448 831 3730002708 832 9196820344 833 20155648324 834 39451780728 835 69234007356 836 109265961330 837 155452302090 838 199723691940 839 232016410230 840 243882320220 841 232016410230 842 199723691940 843 155452302090 844 109265961330 845 69234007356 846 39451780728 847 20155648324 848 9196820344 849 3730002708 850 1336695448 851 420149356 852 114765453 853 26925603 854 5344206 855 879453 856 116698 857 11989 858 894 859 43 860 1 861 1 862 44 863 937 864 12883 865 128687 866 996151 867 6223659 868 32269809 869 141691056 870 534914809 871 1756844804 872 5066698156 873 12926823052 874 29352468668 875 59607429052 876 108685788084 877 178499968686 878 264718263420 879 355175994030 880 431740102170 881 475898730450 882 475898730450 883 431740102170 884 355175994030 885 264718263420 886 178499968686 887 108685788084 888 59607429052 889 29352468668 890 12926823052 891 5066698156 892 1756844804 893 534914809 894 141691056 895 32269809 896 6223659 897 996151 898 128687 899 12883 900 937 901 44 902 1 903 1 904 45 905 981 906 13820 907 141570 908 1124838 909 7219810 910 38493468 911 173960865 912 676605865 913 2291759613 914 6823542960 915 17993521208 916 42279291720 917 88959897720 918 168293217136 919 287185756770 920 443218232106 921 619894257450 922 786916096200 923 907638832620 924 951797460900 925 907638832620 926 786916096200 927 619894257450 928 443218232106 929 287185756770 930 168293217136 931 88959897720 932 42279291720 933 17993521208 934 6823542960 935 2291759613 936 676605865 937 173960865 938 38493468 939 7219810 940 1124838 941 141570 942 13820 943 981 944 45 945 1 946 1 947 46 948 1026 949 14801 950 155390 951 1266408 952 8344648 953 45713278 954 212454333 955 850566730 956 2968365478 957 9115302573 958 24817064168 959 60272812928 960 131239189440 961 257253114856 962 455478973906 963 730403988876 964 1063112489556 965 1406810353650 966 1694554928820 967 1859436293520 968 1859436293520 969 1694554928820 970 1406810353650 971 1063112489556 972 730403988876 973 455478973906 974 257253114856 975 131239189440 976 60272812928 977 24817064168 978 9115302573 979 2968365478 980 850566730 981 212454333 982 45713278 983 8344648 984 1266408 985 155390 986 14801 987 1026 988 46 989 1 990 1 991 47 992 1072 993 15827 994 170191 995 1421798 996 9611056 997 54057926 998 258167611 999 1063021063 1000 3818932208 1001 12083668051 1002 33932366741 1003 85089877096 1004 191512002368 1005 388492304296 1006 712732088762 1007 1185882962782 1008 1793516478432 1009 2469922843206 1010 3101365282470 1011 3553991222340 1012 3718872587040 1013 3553991222340 1014 3101365282470 1015 2469922843206 1016 1793516478432 1017 1185882962782 1018 712732088762 1019 388492304296 1020 191512002368 1021 85089877096 1022 33932366741 1023 12083668051 1024 3818932208 1025 1063021063 1026 258167611 1027 54057926 1028 9611056 1029 1421798 1030 170191 1031 15827 1032 1072 1033 47 1034 1 1035 1 1036 48 1037 1119 1038 16899 1039 186018 1040 1591989 1041 11032854 1042 63668982 1043 312225537 1044 1321188674 1045 4881953271 1046 15902600259 1047 46016034792 1048 119022243837 1049 276601879464 1050 580004306664 1051 1101224393058 1052 1898615051544 1053 2979399441214 1054 4263439321638 1055 5571288125676 1056 6655356504810 1057 7272863809380 1058 7272863809380 1059 6655356504810 1060 5571288125676 1061 4263439321638 1062 2979399441214 1063 1898615051544 1064 1101224393058 1065 580004306664 1066 276601879464 1067 119022243837 1068 46016034792 1069 15902600259 1070 4881953271 1071 1321188674 1072 312225537 1073 63668982 1074 11032854 1075 1591989 1076 186018 1077 16899 1078 1119 1079 48 1080 1 1081 1 1082 49 1083 1167 1084 18018 1085 202917 1086 1778007 1087 12624843 1088 74701836 1089 375894519 1090 1633414211 1091 6203141945 1092 20784553530 1093 61918635051 1094 165038278629 1095 395624123301 1096 856606186128 1097 1681228699722 1098 2999839444602 1099 4878014492758 1100 7242838762852 1101 9834727447314 1102 12226644630486 1103 13928220314190 1104 14545727618760 1105 13928220314190 1106 12226644630486 1107 9834727447314 1108 7242838762852 1109 4878014492758 1110 2999839444602 1111 1681228699722 1112 856606186128 1113 395624123301 1114 165038278629 1115 61918635051 1116 20784553530 1117 6203141945 1118 1633414211 1119 375894519 1120 74701836 1121 12624843 1122 1778007 1123 202917 1124 18018 1125 1167 1126 49 1127 1 1128 1 1129 50 1130 1216 1131 19185 1132 220935 1133 1980924 1134 14402850 1135 87326679 1136 450596355 1137 2009308730 1138 7836556156 1139 26987695475 1140 82703188581 1141 226956913680 1142 560662401930 1143 1252230309429 1144 2537834885850 1145 4681068144324 1146 7877853937360 1147 12120853255610 1148 17077566210166 1149 22061372077800 1150 26154864944676 1151 28473947932950 1152 28473947932950 1153 26154864944676 1154 22061372077800 1155 17077566210166 1156 12120853255610 1157 7877853937360 1158 4681068144324 1159 2537834885850 1160 1252230309429 1161 560662401930 1162 226956913680 1163 82703188581 1164 26987695475 1165 7836556156 1166 2009308730 1167 450596355 1168 87326679 1169 14402850 1170 1980924 1171 220935 1172 19185 1173 1216 1174 50 1175 1 1176 1 1177 51 1178 1266 1179 20401 1180 240120 1181 2201859 1182 16383774 1183 101729529 1184 537923034 1185 2459905085 1186 9845864886 1187 34824251631 1188 109690884056 1189 309660102261 1190 787619315610 1191 1812892711359 1192 3790065195279 1193 7218903030174 1194 12558922081684 1195 19998707192970 1196 29198419465776 1197 39138938287966 1198 48216237022476 1199 54628812877626 1200 56947895865900 1201 54628812877626 1202 48216237022476 1203 39138938287966 1204 29198419465776 1205 19998707192970 1206 12558922081684 1207 7218903030174 1208 3790065195279 1209 1812892711359 1210 787619315610 1211 309660102261 1212 109690884056 1213 34824251631 1214 9845864886 1215 2459905085 1216 537923034 1217 101729529 1218 16383774 1219 2201859 1220 240120 1221 20401 1222 1266 1223 51 1224 1 1225 1 1226 52 1227 1317 1228 21667 1229 260521 1230 2441979 1231 18585633 1232 118113303 1233 639652563 1234 2997828119 1235 12305769971 1236 44670116517 1237 144515135687 1238 419350986317 1239 1097279417871 1240 2600512026969 1241 5602957906638 1242 11008968225453 1243 19777825111858 1244 32557629274654 1245 49197126658746 1246 68337357753742 1247 87355175310442 1248 102845049900102 1249 111576708743526 1250 111576708743526 1251 102845049900102 1252 87355175310442 1253 68337357753742 1254 49197126658746 1255 32557629274654 1256 19777825111858 1257 11008968225453 1258 5602957906638 1259 2600512026969 1260 1097279417871 1261 419350986317 1262 144515135687 1263 44670116517 1264 12305769971 1265 2997828119 1266 639652563 1267 118113303 1268 18585633 1269 2441979 1270 260521 1271 21667 1272 1317 1273 52 1274 1 1275 1 1276 53 1277 1369 1278 22984 1279 282188 1280 2702500 1281 21027612 1282 136698936 1283 757765866 1284 3637480682 1285 15303598090 1286 56975886488 1287 189185252204 1288 563866122004 1289 1516630404188 1290 3697791444840 1291 8203469933607 1292 16611926132091 1293 30786793337311 1294 52335454386512 1295 81754755933400 1296 117534484412488 1297 155692533064184 1298 190200225210544 1299 214421758643628 1300 223153417487052 1301 214421758643628 1302 190200225210544 1303 155692533064184 1304 117534484412488 1305 81754755933400 1306 52335454386512 1307 30786793337311 1308 16611926132091 1309 8203469933607 1310 3697791444840 1311 1516630404188 1312 563866122004 1313 189185252204 1314 56975886488 1315 15303598090 1316 3637480682 1317 757765866 1318 136698936 1319 21027612 1320 2702500 1321 282188 1322 22984 1323 1369 1324 53 1325 1