0 1 1 1 2 1 3 1 4 2 5 1 6 1 7 3 8 3 9 1 10 1 11 3 12 4 13 3 14 1 15 1 16 3 17 6 18 6 19 3 20 1 21 1 22 4 23 9 24 11 25 9 26 4 27 1 28 1 29 4 30 12 31 19 32 19 33 12 34 4 35 1 36 1 37 5 38 15 39 29 40 37 41 29 42 15 43 5 44 1 45 1 46 5 47 19 48 43 49 65 50 65 51 43 52 19 53 5 54 1 55 1 56 6 57 23 58 61 59 107 60 128 61 107 62 61 63 23 64 6 65 1 66 1 67 6 68 28 69 84 70 167 71 233 72 233 73 167 74 84 75 28 76 6 77 1 78 1 79 7 80 34 81 111 82 249 83 398 84 464 85 398 86 249 87 111 88 34 89 7 90 1 91 1 92 7 93 40 94 144 95 359 96 646 97 861 98 861 99 646 100 359 101 144 102 40 103 7 104 1 105 1 106 8 107 46 108 183 109 502 110 1003 111 1504 112 1719 113 1504 114 1003 115 502 116 183 117 46 118 8 119 1 120 1 121 8 122 53 123 228 124 684 125 1503 126 2505 127 3221 128 3221 129 2505 130 1503 131 684 132 228 133 53 134 8 135 1 136 1 137 9 138 61 139 281 140 911 141 2186 142 4007 143 5724 144 6439 145 5724 146 4007 147 2186 148 911 149 281 150 61 151 9 152 1 153 1 154 9 155 69 156 341 157 1191 158 3096 159 6191 160 9728 161 12160 162 12160 163 9728 164 6191 165 3096 166 1191 167 341 168 69 169 9 170 1 171 1 172 10 173 77 174 409 175 1531 176 4285 177 9284 178 15916 179 21884 180 24315 181 21884 182 15916 183 9284 184 4285 185 1531 186 409 187 77 188 10 189 1 190 1 191 10 192 86 193 485 194 1939 195 5815 196 13568 197 25198 198 37796 199 46195 200 46195 201 37796 202 25198 203 13568 204 5815 205 1939 206 485 207 86 208 10 209 1 210 1 211 11 212 96 213 571 214 2423 215 7753 216 19382 217 38763 218 62990 219 83987 220 92385 221 83987 222 62990 223 38763 224 19382 225 7753 226 2423 227 571 228 96 229 11 230 1 231 1 232 11 233 106 234 666 235 2993 236 10175 237 27134 238 58143 239 101750 240 146972 241 176367 242 176367 243 146972 244 101750 245 58143 246 27134 247 10175 248 2993 249 666 250 106 251 11 252 1 253 1 254 12 255 116 256 771 257 3658 258 13168 259 37308 260 85275 261 159890 262 248717 263 323332 264 352726 265 323332 266 248717 267 159890 268 85275 269 37308 270 13168 271 3658 272 771 273 116 274 12 275 1 276 1 277 12 278 127 279 886 280 4428 281 16825 282 50475 283 122581 284 245162 285 408602 286 572043 287 676051 288 676051 289 572043 290 408602 291 245162 292 122581 293 50475 294 16825 295 4428 296 886 297 127 298 12 299 1 300 1 301 13 302 139 303 1013 304 5314 305 21253 306 67299 307 173054 308 367740 309 653759 310 980638 311 1248085 312 1352092 313 1248085 314 980638 315 653759 316 367740 317 173054 318 67299 319 21253 320 5314 321 1013 322 139 323 13 324 1 325 1 326 13 327 151 328 1151 329 6326 330 26566 331 88551 332 240352 333 540791 334 1021494 335 1634391 336 2228714 337 2600166 338 2600166 339 2228714 340 1634391 341 1021494 342 540791 343 240352 344 88551 345 26566 346 6326 347 1151 348 151 349 13 350 1 351 1 352 14 353 163 354 1301 355 7476 356 32891 357 115116 358 328902 359 781141 360 1562281 361 2655878 362 3863095 363 4828868 364 5200320 365 4828868 366 3863095 367 2655878 368 1562281 369 781141 370 328902 371 115116 372 32891 373 7476 374 1301 375 163 376 14 377 1 378 1 379 14 380 176 381 1463 382 8776 383 40366 384 148006 385 444017 386 1110041 387 2343418 388 4218153 389 6518963 390 8691950 391 10029173 392 10029173 393 8691950 394 6518963 395 4218153 396 2343418 397 1110041 398 444017 399 148006 400 40366 401 8776 402 1463 403 176 404 14 405 1 406 1 407 15 408 190 409 1639 410 10238 411 49141 412 188371 413 592021 414 1554055 415 3453455 416 6561564 417 10737105 418 15210899 419 18721106 420 20058328 421 18721106 422 15210899 423 10737105 424 6561564 425 3453455 426 1554055 427 592021 428 188371 429 49141 430 10238 431 1639 432 190 433 15 434 1 435 1 436 15 437 204 438 1828 439 11876 440 59378 441 237511 442 780391 443 2146075 444 5007507 445 10015014 446 17298660 447 25947990 448 33931986 449 38779413 450 38779413 451 33931986 452 25947990 453 17298660 454 10015014 455 5007507 456 2146075 457 780391 458 237511 459 59378 460 11876 461 1828 462 204 463 15 464 1 465 1 466 16 467 218 468 2031 469 13703 470 71254 471 296888 472 1017901 473 2926464 474 7153579 475 15022516 476 27313664 477 43246635 478 59879956 479 72711375 480 77558800 481 72711375 482 59879956 483 43246635 484 27313664 485 15022516 486 7153579 487 2926464 488 1017901 489 296888 490 71254 491 13703 492 2031 493 218 494 16 495 1 496 1 497 16 498 233 499 2248 500 15733 501 84956 502 368141 503 1314788 504 3944364 505 10080041 506 22176090 507 42336171 508 70560285 509 103126570 510 132591304 511 150270144 512 150270144 513 132591304 514 103126570 515 70560285 516 42336171 517 22176090 518 10080041 519 3944364 520 1314788 521 368141 522 84956 523 15733 524 2248 525 233 526 16 527 1 528 1 529 17 530 249 531 2481 532 17981 533 100689 534 453097 535 1682929 536 5259151 537 14024403 538 32256126 539 64512252 540 112896441 541 173686833 542 235717844 543 282861413 544 300540251 545 282861413 546 235717844 547 173686833 548 112896441 549 64512252 550 32256126 551 14024403 552 5259151 553 1682929 554 453097 555 100689 556 17981 557 2481 558 249 559 17 560 1 561 1 562 17 563 265 564 2729 565 20461 566 118669 567 553785 568 2136025 569 6942079 570 19283553 571 46280526 572 96768371 573 177408680 574 286583253 575 409404647 576 518579219 577 583401621 578 583401621 579 518579219 580 409404647 581 286583253 582 177408680 583 96768371 584 46280526 585 19283553 586 6942079 587 2136025 588 553785 589 118669 590 20461 591 2729 592 265 593 17 594 1 595 1 596 18 597 281 598 2993 599 23189 600 139129 601 672453 602 2689809 603 9078103 604 26225630 605 65564075 606 143048890 607 274177039 608 463991912 609 695987868 610 927983824 611 1101980791 612 1166803190 613 1101980791 614 927983824 615 695987868 616 463991912 617 274177039 618 143048890 619 65564075 620 26225630 621 9078103 622 2689809 623 672453 624 139129 625 23189 626 2993 627 281 628 18 629 1 630 1 631 18 632 298 633 3273 634 26181 635 162317 636 811581 637 3362261 638 11767911 639 35303732 640 91789702 641 208612959 642 417225918 643 738168931 644 1159979749 645 1623971648 646 2029964560 647 2268783919 648 2268783919 649 2029964560 650 1623971648 651 1159979749 652 738168931 653 417225918 654 208612959 655 91789702 656 35303732 657 11767911 658 3362261 659 811581 660 162317 661 26181 662 3273 663 298 664 18 665 1 666 1 667 19 668 316 669 3571 670 29453 671 188497 672 973897 673 4173841 674 15130171 675 47071642 676 127093432 677 300402656 678 625838866 679 1155394830 680 1898148648 681 2783951350 682 3653936147 683 4298748408 684 4537567764 685 4298748408 686 3653936147 687 2783951350 688 1898148648 689 1155394830 690 625838866 691 300402656 692 127093432 693 47071642 694 15130171 695 4173841 696 973897 697 188497 698 29453 699 3571 700 316 701 19 702 1 703 1 704 19 705 334 706 3886 707 33023 708 217949 709 1162393 710 5147737 711 19304011 712 62201811 713 174165071 714 427496083 715 926241513 716 1781233678 717 3053543447 718 4682099952 719 6437887434 720 7952684477 721 8836316085 722 8836316085 723 7952684477 724 6437887434 725 4682099952 726 3053543447 727 1781233678 728 926241513 729 427496083 730 174165071 731 62201811 732 19304011 733 5147737 734 1162393 735 217949 736 33023 737 3886 738 334 739 19 740 1 741 1 742 20 743 352 744 4219 745 36908 746 250972 747 1380341 748 6310129 749 24451747 750 81505821 751 236366881 752 601661150 753 1353737587 754 2707475174 755 4834777095 756 7735643352 757 11119987318 758 14390571823 759 16789000461 760 17672632064 761 16789000461 762 14390571823 763 11119987318 764 7735643352 765 4834777095 766 2707475174 767 1353737587 768 601661150 769 236366881 770 81505821 771 24451747 772 6310129 773 1380341 774 250972 775 36908 776 4219 777 352 778 20 779 1 780 1 781 20 782 371 783 4570 784 41126 785 287879 786 1631312 787 7690469 788 30761875 789 105957567 790 317872700 791 838028027 792 1955398729 793 4061212745 794 7542252241 795 12570420401 796 18855630601 797 25510559048 798 31179572170 799 34461632399 800 34461632399 801 31179572170 802 25510559048 803 18855630601 804 12570420401 805 7542252241 806 4061212745 807 1955398729 808 838028027 809 317872700 810 105957567 811 30761875 812 7690469 813 1631312 814 287879 815 41126 816 4570 817 371 818 20 819 1 820 1 821 21 822 391 823 4941 824 45696 825 329005 826 1919191 827 9321781 828 38452343 829 136719441 830 423830266 831 1155900724 832 2793426750 833 6016611461 834 11603464960 835 20112672597 836 31426050932 837 44366189551 838 56690131093 839 65641204424 840 68923264645 841 65641204424 842 56690131093 843 44366189551 844 31426050932 845 20112672597 846 11603464960 847 6016611461 848 2793426750 849 1155900724 850 423830266 851 136719441 852 38452343 853 9321781 854 1919191 855 329005 856 45696 857 4941 858 391 859 21 860 1 861 1 862 21 863 411 864 5331 865 50636 866 374700 867 2248195 868 11240971 869 47774123 870 175171783 871 560549706 872 1579730988 873 3949327469 874 8810038199 875 17620076397 876 31716137514 877 51538723460 878 75792240382 879 101056320509 880 122331335353 881 134564468888 882 134564468888 883 122331335353 884 101056320509 885 75792240382 886 51538723460 887 31716137514 888 17620076397 889 8810038199 890 3949327469 891 1579730988 892 560549706 893 175171783 894 47774123 895 11240971 896 2248195 897 374700 898 50636 899 5331 900 411 901 21 902 1 903 1 904 22 905 431 906 5741 907 55966 908 425335 909 2622894 910 13489165 911 59015093 912 222945906 913 735721488 914 2140280691 915 5529058451 916 12759365656 917 26430114574 918 49336213870 919 83254860906 920 127330963738 921 176848560747 922 223387655680 923 256895804032 924 269128937557 925 256895804032 926 223387655680 927 176848560747 928 127330963738 929 83254860906 930 49336213870 931 26430114574 932 12759365656 933 5529058451 934 2140280691 935 735721488 936 222945906 937 59015093 938 13489165 939 2622894 940 425335 941 55966 942 5741 943 431 944 22 945 1 946 1 947 22 948 452 949 6171 950 61706 951 481300 952 3048228 953 16112058 954 72504257 955 281960998 956 958667393 957 2876002177 958 7669339138 959 18288424098 960 39189480210 961 75766328406 962 132591074710 963 210585824539 964 304179524334 965 400236216229 966 480283459475 967 526024741329 968 526024741329 969 480283459475 970 400236216229 971 304179524334 972 210585824539 973 132591074710 974 75766328406 975 39189480210 976 18288424098 977 7669339138 978 2876002177 979 958667393 980 281960998 981 72504257 982 16112058 983 3048228 984 481300 985 61706 986 6171 987 452 988 22 989 1 990 1 991 23 992 474 993 6623 994 67876 995 543005 996 3529527 997 19160285 998 88616314 999 354465255 1000 1240628390 1001 3834669568 1002 10545341312 1003 25957763228 1004 57477904291 1005 114955808581 1006 208357403053 1007 343176899146 1008 514765348719 1009 704415740352 1010 880519675440 1011 1006308200503 1012 1052049482344 1013 1006308200503 1014 880519675440 1015 704415740352 1016 514765348719 1017 343176899146 1018 208357403053 1019 114955808581 1020 57477904291 1021 25957763228 1022 10545341312 1023 3834669568 1024 1240628390 1025 354465255 1026 88616314 1027 19160285 1028 3529527 1029 543005 1030 67876 1031 6623 1032 474 1033 23 1034 1 1035 1 1036 23 1037 496 1038 7096 1039 74498 1040 610880 1041 4072531 1042 22689811 1043 107776598 1044 443081568 1045 1595093644 1046 5075297957 1047 14380010877 1048 36503104533 1049 83435667504 1050 172433712841 1051 323313211576 1052 551534302099 1053 857942247710 1054 1219181088851 1055 1584935415506 1056 1886827875602 1057 2058357682475 1058 2058357682475 1059 1886827875602 1060 1584935415506 1061 1219181088851 1062 857942247710 1063 551534302099 1064 323313211576 1065 172433712841 1066 83435667504 1067 36503104533 1068 14380010877 1069 5075297957 1070 1595093644 1071 443081568 1072 107776598 1073 22689811 1074 4072531 1075 610880 1076 74498 1077 7096 1078 496 1079 23 1080 1 1081 1 1082 24 1083 518 1084 7591 1085 81593 1086 685378 1087 4683410 1088 26762341 1089 130466408 1090 550858166 1091 2038175211 1092 6670391600 1093 19455308831 1094 50883115404 1095 119938772023 1096 255869380316 1097 495746924361 1098 874847513579 1099 1409476549654 1100 2077123336332 1101 2804116504048 1102 3471763290726 1103 3945185557643 1104 4116715364497 1105 3945185557643 1106 3471763290726 1107 2804116504048 1108 2077123336332 1109 1409476549654 1110 874847513579 1111 495746924361 1112 255869380316 1113 119938772023 1114 50883115404 1115 19455308831 1116 6670391600 1117 2038175211 1118 550858166 1119 130466408 1120 26762341 1121 4683410 1122 685378 1123 81593 1124 7591 1125 518 1126 24 1127 1 1128 1 1129 24 1130 541 1131 8108 1132 89183 1133 766970 1134 5368787 1135 31445750 1136 157228748 1137 681324573 1138 2589033376 1139 8708566810 1140 26125700429 1141 70338424230 1142 170821887416 1143 375808152314 1144 751616304627 1145 1370594437848 1146 2284324063080 1147 3486599885753 1148 4881239840054 1149 6275879794356 1150 7416948847875 1151 8061900921603 1152 8061900921603 1153 7416948847875 1154 6275879794356 1155 4881239840054 1156 3486599885753 1157 2284324063080 1158 1370594437848 1159 751616304627 1160 375808152314 1161 170821887416 1162 70338424230 1163 26125700429 1164 8708566810 1165 2589033376 1166 681324573 1167 157228748 1168 31445750 1169 5368787 1170 766970 1171 89183 1172 8108 1173 541 1174 24 1175 1 1176 1 1177 25 1178 565 1179 8649 1180 97291 1181 856153 1182 6135757 1183 36814537 1184 188674498 1185 838553321 1186 3270357949 1187 11297600185 1188 34834267237 1189 96464124655 1190 241160311636 1191 546630039707 1192 1127424456894 1193 2122210742389 1194 3654918500780 1195 5770923948600 1196 8367839725469 1197 11157119633959 1198 13692828641677 1199 15478849768852 1200 16123801842554 1201 15478849768852 1202 13692828641677 1203 11157119633959 1204 8367839725469 1205 5770923948600 1206 3654918500780 1207 2122210742389 1208 1127424456894 1209 546630039707 1210 241160311636 1211 96464124655 1212 34834267237 1213 11297600185 1214 3270357949 1215 838553321 1216 188674498 1217 36814537 1218 6135757 1219 856153 1220 97291 1221 8649 1222 565 1223 25 1224 1 1225 1 1226 25 1227 589 1228 9213 1229 105939 1230 953443 1231 6991909 1232 42950293 1233 225489034 1234 1027227818 1235 4108911269 1236 14567958133 1237 46131867420 1238 131298391887 1239 337624436281 1240 787790351322 1241 1674054496559 1242 3249635199203 1243 5777129243027 1244 9425842449148 1245 14138763673722 1246 19524959358950 1247 24849948275027 1248 29171678409814 1249 31602651610632 1250 31602651610632 1251 29171678409814 1252 24849948275027 1253 19524959358950 1254 14138763673722 1255 9425842449148 1256 5777129243027 1257 3249635199203 1258 1674054496559 1259 787790351322 1260 337624436281 1261 131298391887 1262 46131867420 1263 14567958133 1264 4108911269 1265 1027227818 1266 225489034 1267 42950293 1268 6991909 1269 953443 1270 105939 1271 9213 1272 589 1273 25 1274 1 1275 1 1276 26 1277 613 1278 9801 1279 115151 1280 1059381 1281 7945351 1282 49942201 1283 268439326 1284 1252716851 1285 5136139086 1286 18676869401 1287 60699825552 1288 177430259305 1289 468922828161 1290 1125414787586 1291 2461844847844 1292 4923689695688 1293 9026764442095 1294 15202971691949 1295 23564606122520 1296 33663723032171 1297 44374907633317 1298 54021626684037 1299 60774330019542 1300 63205303220324 1301 60774330019542 1302 54021626684037 1303 44374907633317 1304 33663723032171 1305 23564606122520 1306 15202971691949 1307 9026764442095 1308 4923689695688 1309 2461844847844 1310 1125414787586 1311 468922828161 1312 177430259305 1313 60699825552 1314 18676869401 1315 5136139086 1316 1252716851 1317 268439326 1318 49942201 1319 7945351 1320 1059381 1321 115151 1322 9801 1323 613 1324 26 1325 1