0 1 1 1 2 1 3 1 4 2 5 1 6 1 7 9 8 9 9 1 10 1 11 8 12 36 13 8 14 1 15 1 16 8 17 33 18 33 19 8 20 1 21 1 22 9 23 38 24 33 25 38 26 9 27 1 28 1 29 10 30 44 31 41 32 41 33 44 34 10 35 1 36 1 37 11 38 52 39 52 40 54 41 52 42 52 43 11 44 1 45 1 46 12 47 62 48 67 49 76 50 76 51 67 52 62 53 12 54 1 55 1 56 12 57 72 58 86 59 105 60 113 61 105 62 86 63 72 64 12 65 1 66 1 67 13 68 84 69 108 70 144 71 169 72 169 73 144 74 108 75 84 76 13 77 1 78 1 79 14 80 97 81 134 82 194 83 249 84 271 85 249 86 194 87 134 88 97 89 14 90 1 91 1 92 15 93 111 94 165 95 258 96 359 97 425 98 425 99 359 100 258 101 165 102 111 103 15 104 1 105 1 106 16 107 125 108 201 109 337 110 506 111 651 112 708 113 651 114 506 115 337 116 201 117 125 118 16 119 1 120 1 121 17 122 141 123 241 124 434 125 701 126 973 127 1149 128 1149 129 973 130 701 131 434 132 241 133 141 134 17 135 1 136 1 137 18 138 158 139 287 140 552 141 953 142 1424 143 1816 144 1970 145 1816 146 1424 147 953 148 552 149 287 150 158 151 18 152 1 153 1 154 19 155 176 156 339 157 692 158 1275 159 2040 160 2799 161 3280 162 3280 163 2799 164 2040 165 1275 166 692 167 339 168 176 169 19 170 1 171 1 172 20 173 195 174 396 175 857 176 1681 177 2869 178 4216 179 5313 180 5740 181 5313 182 4216 183 2869 184 1681 185 857 186 396 187 195 188 20 189 1 190 1 191 21 192 215 193 460 194 1052 195 2185 196 3965 197 6217 198 8393 199 9751 200 9751 201 8393 202 6217 203 3965 204 2185 205 1052 206 460 207 215 208 21 209 1 210 1 211 22 212 236 213 531 214 1279 215 2805 216 5395 217 8992 218 12951 219 16117 220 17335 221 16117 222 12951 223 8992 224 5395 225 2805 226 1279 227 531 228 236 229 22 230 1 231 1 232 23 233 258 234 608 235 1540 236 3561 237 7235 238 12778 239 19566 240 25979 241 29927 242 29927 243 25979 244 19566 245 12778 246 7235 247 3561 248 1540 249 608 250 258 251 23 252 1 253 1 254 24 255 281 256 693 257 1841 258 4473 259 9575 260 17867 261 28990 262 40920 263 50295 264 53869 265 50295 266 40920 267 28990 268 17867 269 9575 270 4473 271 1841 272 693 273 281 274 24 275 1 276 1 277 25 278 305 279 786 280 2184 281 5564 282 12519 283 24613 284 42194 285 63110 286 82464 287 94236 288 94236 289 82464 290 63110 291 42194 292 24613 293 12519 294 5564 295 2184 296 786 297 305 298 25 299 1 300 1 301 26 302 330 303 887 304 2573 305 6860 306 16187 307 33447 308 60414 309 95469 310 132187 311 160591 312 171338 313 160591 314 132187 315 95469 316 60414 317 33447 318 16187 319 6860 320 2573 321 887 322 330 323 26 324 1 325 1 326 27 327 356 328 996 329 3012 330 8389 331 20713 332 44883 333 85208 334 141873 335 207540 336 267177 337 303048 338 303048 339 267177 340 207540 341 141873 342 85208 343 44883 344 20713 345 8389 346 3012 347 996 348 356 349 27 350 1 351 1 352 28 353 383 354 1113 355 3506 356 10180 357 26254 358 59534 359 118520 360 207410 361 319688 362 434806 363 522603 364 555588 365 522603 366 434806 367 319688 368 207410 369 118520 370 59534 371 26254 372 10180 373 3506 374 1113 375 383 376 28 377 1 378 1 379 29 380 411 381 1240 382 4058 383 12267 384 32984 385 78120 386 162750 387 298670 388 483846 389 693379 390 880481 391 991894 392 991894 393 880481 394 693379 395 483846 396 298670 397 162750 398 78120 399 32984 400 12267 401 4058 402 1240 403 411 404 29 405 1 406 1 407 30 408 440 409 1376 410 4674 411 14684 412 41099 413 101489 414 220839 415 424108 416 720484 417 1085193 418 1451947 419 1728100 420 1831189 421 1728100 422 1451947 423 1085193 424 720484 425 424108 426 220839 427 101489 428 41099 429 14684 430 4674 431 1376 432 440 433 30 434 1 435 1 436 31 437 470 438 1522 439 5357 440 17469 441 50819 442 130628 443 296362 444 594458 445 1056814 446 1669222 447 2347343 448 2943670 449 3295537 450 3295537 451 2943670 452 2347343 453 1669222 454 1056814 455 594458 456 296362 457 130628 458 50819 459 17469 460 5357 461 1522 462 470 463 31 464 1 465 1 466 32 467 501 468 1677 469 6113 470 20663 471 62389 472 166680 473 393634 474 823229 475 1528606 476 2526622 477 3725941 478 4910967 479 5792936 480 6120283 481 5792936 482 4910967 483 3725941 484 2526622 485 1528606 486 823229 487 393634 488 166680 489 62389 490 20663 491 6113 492 1677 493 501 494 32 495 1 496 1 497 33 498 533 499 1843 500 6947 501 24310 502 76082 503 210965 504 517823 505 1127277 506 2182408 507 3767715 508 5814376 509 8036507 510 9963629 511 11091364 512 11091364 513 9963629 514 8036507 515 5814376 516 3767715 517 2182408 518 1127277 519 517823 520 210965 521 76082 522 24310 523 6947 524 1843 525 533 526 33 527 1 528 1 529 34 530 566 531 2020 532 7864 533 28457 534 92199 535 264994 536 675088 537 1527471 538 3078218 539 5540792 540 8930881 541 12917777 542 16794660 543 19649753 544 20703880 545 19649753 546 16794660 547 12917777 548 8930881 549 5540792 550 3078218 551 1527471 552 675088 553 264994 554 92199 555 28457 556 7864 557 2020 558 566 559 34 560 1 561 1 562 35 563 600 564 2207 565 8869 566 33152 567 111072 568 330497 569 872718 570 2049459 571 4292686 572 8043084 573 13516850 574 20420505 575 27783000 576 34087743 577 37749512 578 37749512 579 34087743 580 27783000 581 20420505 582 13516850 583 8043084 584 4292686 585 2049459 586 872718 587 330497 588 111072 589 33152 590 8869 591 2207 592 600 593 35 594 1 595 1 596 36 597 635 598 2406 599 9968 600 38449 601 133067 602 409438 603 1119300 604 2724551 605 5922938 606 11534376 607 20177530 608 31782594 609 45164739 610 57989294 611 67343266 612 70780336 613 67343266 614 57989294 615 45164739 616 31782594 617 20177530 618 11534376 619 5922938 620 2724551 621 1119300 622 409438 623 133067 624 38449 625 9968 626 2406 627 635 628 36 629 1 630 1 631 37 632 671 633 2617 634 11166 635 44404 636 158585 637 504043 638 1424889 639 3590721 640 8091092 641 16353716 642 29734029 643 48752414 644 72233168 645 96868480 646 117722111 647 129750709 648 129750709 649 117722111 650 96868480 651 72233168 652 48752414 653 29734029 654 16353716 655 8091092 656 3590721 657 1424889 658 504043 659 158585 660 44404 661 11166 662 2617 663 671 664 37 665 1 666 1 667 38 668 707 669 2840 670 12470 671 51076 672 188063 673 616824 674 1801211 675 4693753 676 10949588 677 22939839 678 43289249 679 73771027 680 113775141 681 159082930 682 201928045 683 232904320 684 244236629 685 232904320 686 201928045 687 159082930 688 113775141 689 73771027 690 43289249 691 22939839 692 10949588 693 4693753 694 1801211 695 616824 696 188063 697 51076 698 12470 699 2840 700 707 701 38 702 1 703 1 704 39 705 745 706 3075 707 13884 708 58530 709 221979 710 750606 711 2261870 712 6088537 713 14687425 714 31855931 715 62310792 716 110210109 717 176663328 718 257124595 719 340288331 720 409944875 721 449870919 722 449870919 723 409944875 724 340288331 725 257124595 726 176663328 727 110210109 728 62310792 729 31855931 730 14687425 731 6088537 732 2261870 733 750606 734 221979 735 58530 736 13884 737 3075 738 745 739 39 740 1 741 1 742 40 743 784 744 3322 745 15417 746 66831 747 260855 748 908555 749 2822591 750 7840530 751 19537439 752 43819506 753 88734500 754 162679917 755 270652036 756 409422716 757 564022440 758 708443410 759 812017008 760 849756180 761 812017008 762 708443410 763 564022440 764 409422716 765 270652036 766 162679917 767 88734500 768 43819506 769 19537439 770 7840530 771 2822591 772 908555 773 260855 774 66831 775 15417 776 3322 777 784 778 40 779 1 780 1 781 41 782 824 783 3583 784 17072 785 76049 786 305253 787 1094208 788 3501467 789 10027402 790 25784748 791 59738217 792 125092847 793 237424744 794 409436548 795 642835160 796 920423070 797 1203420178 798 1438161397 799 1571934101 800 1571934101 801 1438161397 802 1203420178 803 920423070 804 642835160 805 409436548 806 237424744 807 125092847 808 59738217 809 25784748 810 10027402 811 3501467 812 1094208 813 305253 814 76049 815 17072 816 3583 817 824 818 41 819 1 820 1 821 42 822 865 823 3857 824 18858 825 86260 826 355786 827 1311506 828 4319244 829 12740880 830 33776511 831 80752581 832 174673149 833 342826863 834 612050897 835 996056163 836 1480212539 837 2011487313 838 2502238186 839 2851581135 840 2978401454 841 2851581135 842 2502238186 843 2011487313 844 1480212539 845 996056163 846 612050897 847 342826863 848 174673149 849 80752581 850 33776511 851 12740880 852 4319244 853 1311506 854 355786 855 86260 856 18858 857 3857 858 865 859 42 860 1 861 1 862 43 863 907 864 4145 865 20781 866 97541 867 413114 868 1564824 869 5299619 870 16088806 871 43933167 872 108286680 873 241711339 874 490044180 875 904696948 876 1524233419 877 2347875175 878 3311468296 879 4281494363 880 5078944573 881 5530970640 882 5530970640 883 5078944573 884 4281494363 885 3311468296 886 2347875175 887 1524233419 888 904696948 889 490044180 890 241711339 891 108286680 892 43933167 893 16088806 894 5299619 895 1564824 896 413114 897 97541 898 20781 899 4145 900 907 901 43 902 1 903 1 904 44 905 950 906 4446 907 22848 908 109974 909 477949 910 1859011 911 6469569 912 20197435 913 56761308 914 144108049 915 331627957 916 693811659 917 1323119287 918 2305167825 919 3676022315 920 5374115669 921 7211642067 922 8891513362 923 10079165504 924 10508844215 925 10079165504 926 8891513362 927 7211642067 928 5374115669 929 3676022315 930 2305167825 931 1323119287 932 693811659 933 331627957 934 144108049 935 56761308 936 20197435 937 6469569 938 1859011 939 477949 940 109974 941 22848 942 4446 943 950 944 44 945 1 946 1 947 45 948 994 949 4762 950 25065 951 123645 952 551061 953 2199424 954 7859705 955 25213981 956 72868405 957 190398091 958 451313994 959 973442201 960 1915666140 961 3447568380 962 5685172857 963 8604479612 964 11968370818 965 15315420925 966 18044350471 967 19583605074 968 19583605074 969 18044350471 970 15315420925 971 11968370818 972 8604479612 973 5685172857 974 3447568380 975 1915666140 976 973442201 977 451313994 978 190398091 979 72868405 980 25213981 981 7859705 982 2199424 983 551061 984 123645 985 25065 986 4762 987 994 988 45 989 1 990 1 991 46 992 1039 993 5093 994 27440 995 138646 996 633273 997 2591967 998 9504652 999 31309443 1000 92979557 1001 249834532 1002 609475371 1003 1354069148 1004 2747207146 1005 5101956128 1006 8690745291 1007 13601698778 1008 19586446241 1009 25979621445 1010 31768558832 1011 35835405881 1012 37302104902 1013 35835405881 1014 31768558832 1015 25979621445 1016 19586446241 1017 13601698778 1018 8690745291 1019 5101956128 1020 2747207146 1021 1354069148 1022 609475371 1023 249834532 1024 92979557 1025 31309443 1026 9504652 1027 2591967 1028 633273 1029 138646 1030 27440 1031 5093 1032 1039 1033 46 1034 1 1035 1 1036 47 1037 1085 1038 5439 1039 29981 1040 155069 1041 725471 1042 3043136 1043 11443461 1044 38681724 1045 117956505 1046 325687569 1047 817046072 1048 1868179977 1049 3904114891 1050 7474958978 1051 13139576329 1052 21242567652 1053 31631857624 1054 43436411251 1055 55055651260 1056 64456852875 1057 69735438122 1058 69735438122 1059 64456852875 1060 55055651260 1061 43436411251 1062 31631857624 1063 21242567652 1064 13139576329 1065 7474958978 1066 3904114891 1067 1868179977 1068 817046072 1069 325687569 1070 117956505 1071 38681724 1072 11443461 1073 3043136 1074 725471 1075 155069 1076 29981 1077 5439 1078 1085 1079 47 1080 1 1081 1 1082 48 1083 1132 1084 5800 1085 32694 1086 173016 1087 828603 1088 3560057 1089 13720050 1090 47559076 1091 148819142 1092 421931569 1093 1087681339 1094 2557499244 1095 5500559599 1096 10847918426 1097 19658929756 1098 32797275297 1099 50448118015 1100 71635682602 1101 94000342711 1102 114072222390 1103 128090440162 1104 133131290960 1105 128090440162 1106 114072222390 1107 94000342711 1108 71635682602 1109 50448118015 1110 32797275297 1111 19658929756 1112 10847918426 1113 5500559599 1114 2557499244 1115 1087681339 1116 421931569 1117 148819142 1118 47559076 1119 13720050 1120 3560057 1121 828603 1122 173016 1123 32694 1124 5800 1125 1132 1126 48 1127 1 1128 1 1129 49 1130 1180 1131 6176 1132 35587 1133 192589 1134 943684 1135 4150532 1136 16383678 1137 58203877 1138 186769775 1139 543374356 1140 1438343884 1141 3475288477 1142 7686416095 1143 15600945185 1144 29121764345 1145 50088322757 1146 79505274218 1147 116619155175 1148 158243222869 1149 198805159180 1150 231391679761 1151 249610898074 1152 249610898074 1153 231391679761 1154 198805159180 1155 158243222869 1156 116619155175 1157 79505274218 1158 50088322757 1159 29121764345 1160 15600945185 1161 7686416095 1162 3475288477 1163 1438343884 1164 543374356 1165 186769775 1166 58203877 1167 16383678 1168 4150532 1169 943684 1170 192589 1171 35587 1172 6176 1173 1180 1174 49 1175 1 1176 1 1177 50 1178 1229 1179 6569 1180 38669 1181 213896 1182 1071798 1183 4823089 1184 19489454 1185 70916790 1186 233220406 1187 695806334 1188 1889997760 1189 4689141676 1190 10657140174 1191 22243819796 1192 42733023767 1193 75706948680 1194 123889957738 1195 187526350751 1196 262849434969 1197 341479607823 1198 411468816699 1199 460082807330 1200 477516500663 1201 460082807330 1202 411468816699 1203 341479607823 1204 262849434969 1205 187526350751 1206 123889957738 1207 75706948680 1208 42733023767 1209 22243819796 1210 10657140174 1211 4689141676 1212 1889997760 1213 695806334 1214 233220406 1215 70916790 1216 19489454 1217 4823089 1218 1071798 1219 213896 1220 38669 1221 6569 1222 1229 1223 50 1224 1 1225 1 1226 51 1227 1279 1228 6978 1229 41947 1230 237050 1231 1214099 1232 5587030 1233 23098877 1234 86041304 1235 289823341 1236 886171926 1237 2468426430 1238 6284367475 1239 14666038861 1240 31455443617 1241 62142932067 1242 113305591619 1243 190987532210 1244 298038333529 1245 431091160997 1246 578517314317 1247 720848020383 1248 834439496714 1249 897698509485 1250 897698509485 1251 834439496714 1252 720848020383 1253 578517314317 1254 431091160997 1255 298038333529 1256 190987532210 1257 113305591619 1258 62142932067 1259 31455443617 1260 14666038861 1261 6284367475 1262 2468426430 1263 886171926 1264 289823341 1265 86041304 1266 23098877 1267 5587030 1268 1214099 1269 237050 1270 41947 1271 6978 1272 1279 1273 51 1274 1 1275 1 1276 52 1277 1330 1278 7404 1279 45430 1280 262170 1281 1371819 1282 6452481 1283 27280419 1284 103968709 1285 358505435 1286 1122766042 1287 3205193599 1288 8368062972 1289 20039437100 1290 44133913238 1291 89594769416 1292 167990192655 1293 291423846756 1294 468430870206 1295 698527344209 1296 967348362971 1297 1245087195070 1298 1490411195262 1299 1659945468723 1300 1720588809847 1301 1659945468723 1302 1490411195262 1303 1245087195070 1304 967348362971 1305 698527344209 1306 468430870206 1307 291423846756 1308 167990192655 1309 89594769416 1310 44133913238 1311 20039437100 1312 8368062972 1313 3205193599 1314 1122766042 1315 358505435 1316 103968709 1317 27280419 1318 6452481 1319 1371819 1320 262170 1321 45430 1322 7404 1323 1330 1324 52 1325 1