0 1 1 1 2 1 3 1 4 2 5 1 6 1 7 3 8 3 9 1 10 1 11 4 12 5 13 4 14 1 15 1 16 4 17 8 18 8 19 4 20 1 21 1 22 5 23 11 24 15 25 11 26 5 27 1 28 1 29 5 30 15 31 24 32 24 33 15 34 5 35 1 36 1 37 6 38 19 39 37 40 46 41 37 42 19 43 6 44 1 45 1 46 6 47 23 48 54 49 80 50 80 51 54 52 23 53 6 54 1 55 1 56 7 57 28 58 74 59 129 60 155 61 129 62 74 63 28 64 7 65 1 66 1 67 7 68 33 69 99 70 197 71 275 72 275 73 197 74 99 75 33 76 7 77 1 78 1 79 7 80 39 81 128 82 288 83 460 84 536 85 460 86 288 87 128 88 39 89 7 90 1 91 1 92 8 93 45 94 163 95 406 96 731 97 975 98 975 99 731 100 406 101 163 102 45 103 8 104 1 105 1 106 8 107 51 108 203 109 558 110 1116 111 1674 112 1913 113 1674 114 1116 115 558 116 203 117 51 118 8 119 1 120 1 121 9 122 58 123 250 124 749 125 1648 126 2746 127 3530 128 3530 129 2746 130 1648 131 749 132 250 133 58 134 9 135 1 136 1 137 9 138 65 139 303 140 985 141 2364 142 4333 143 6190 144 6964 145 6190 146 4333 147 2364 148 985 149 303 150 65 151 9 152 1 153 1 154 10 155 73 156 364 157 1273 158 3309 159 6618 160 10400 161 13000 162 13000 163 10400 164 6618 165 3309 166 1273 167 364 168 73 169 10 170 1 171 1 172 10 173 81 174 432 175 1620 176 4536 177 9828 178 16848 179 23166 180 25740 181 23166 182 16848 183 9828 184 4536 185 1620 186 432 187 81 188 10 189 1 190 1 191 10 192 90 193 509 194 2035 195 6104 196 14242 197 26449 198 39673 199 48489 200 48489 201 39673 202 26449 203 14242 204 6104 205 2035 206 509 207 90 208 10 209 1 210 1 211 11 212 100 213 595 214 2525 215 8079 216 20197 217 40394 218 65640 219 87520 220 96272 221 87520 222 65640 223 40394 224 20197 225 8079 226 2525 227 595 228 100 229 11 230 1 231 1 232 11 233 109 234 689 235 3100 236 10538 237 28100 238 60215 239 105375 240 152208 241 182650 242 182650 243 152208 244 105375 245 60215 246 28100 247 10538 248 3100 249 689 250 109 251 11 252 1 253 1 254 12 255 119 256 794 257 3768 258 13565 259 38434 260 87847 261 164714 262 256221 263 333087 264 363368 265 333087 266 256221 267 164714 268 87847 269 38434 270 13565 271 3768 272 794 273 119 274 12 275 1 276 1 277 12 278 130 279 909 280 4541 281 17255 282 51764 283 125712 284 251424 285 419040 286 586656 287 693320 288 693320 289 586656 290 419040 291 251424 292 125712 293 51764 294 17255 295 4541 296 909 297 130 298 12 299 1 300 1 301 13 302 141 303 1034 304 5428 305 21712 306 68755 307 176797 308 375693 309 667898 310 1001847 311 1275077 312 1381334 313 1275077 314 1001847 315 667898 316 375693 317 176797 318 68755 319 21712 320 5428 321 1034 322 141 323 13 324 1 325 1 326 13 327 153 328 1172 329 6441 330 27052 331 90172 332 244753 333 550693 334 1040197 335 1664315 336 2269521 337 2647774 338 2647774 339 2269521 340 1664315 341 1040197 342 550693 343 244753 344 90172 345 27052 346 6441 347 1172 348 153 349 13 350 1 351 1 352 14 353 166 354 1321 355 7591 356 33400 357 116900 358 334000 359 793249 360 1586497 361 2697044 362 3922973 363 4903716 364 5280925 365 4903716 366 3922973 367 2697044 368 1586497 369 793249 370 334000 371 116900 372 33400 373 7591 374 1321 375 166 376 14 377 1 378 1 379 14 380 178 381 1482 382 8891 383 40895 384 149948 385 449843 386 1124606 387 2374167 388 4273501 389 6604501 390 8806001 391 10160770 392 10160770 393 8806001 394 6604501 395 4273501 396 2374167 397 1124606 398 449843 399 149948 400 40895 401 8891 402 1482 403 178 404 14 405 1 406 1 407 15 408 192 409 1657 410 10352 411 49686 412 190463 413 598597 414 1571317 415 3491815 416 6634448 417 10856369 418 15379856 419 18929053 420 20281128 421 18929053 422 15379856 423 10856369 424 6634448 425 3491815 426 1571317 427 598597 428 190463 429 49686 430 10352 431 1657 432 192 433 15 434 1 435 1 436 15 437 205 438 1845 439 11988 440 59936 441 239744 442 787729 443 2166254 444 5054591 445 10109182 446 17461314 447 26191971 448 34251039 449 39144045 450 39144045 451 34251039 452 26191971 453 17461314 454 10109182 455 5054591 456 2166254 457 787729 458 239744 459 59936 460 11988 461 1845 462 205 463 15 464 1 465 1 466 16 467 220 468 2047 469 13812 470 71821 471 299251 472 1026003 473 2949757 474 7210518 475 15142086 476 27531066 477 43590854 478 60356566 479 73290116 480 78176124 481 73290116 482 60356566 483 43590854 484 27531066 485 15142086 486 7210518 487 2949757 488 1026003 489 299251 490 71821 491 13812 492 2047 493 220 494 16 495 1 496 1 497 16 498 235 499 2263 500 15839 501 85528 502 370622 503 1323647 504 3970940 505 10147957 506 22325504 507 42621417 508 71035694 509 103821399 510 133484656 511 151282610 512 151282610 513 133484656 514 103821399 515 71035694 516 42621417 517 22325504 518 10147957 519 3970940 520 1323647 521 370622 522 85528 523 15839 524 2263 525 235 526 16 527 1 528 1 529 17 530 250 531 2495 532 18083 533 101263 534 455681 535 1692527 536 5289146 537 14104389 538 32440095 539 64880189 540 113540331 541 174677432 542 237062229 543 284474674 544 302254341 545 284474674 546 237062229 547 174677432 548 113540331 549 64880189 550 32440095 551 14104389 552 5289146 553 1692527 554 455681 555 101263 556 18083 557 2495 558 250 559 17 560 1 561 1 562 17 563 266 564 2742 565 20559 566 119241 567 556458 568 2146337 569 6975595 570 19376651 571 46503961 572 97235553 573 178265181 574 287966830 575 411381185 576 521082835 577 586218189 578 586218189 579 521082835 580 411381185 581 287966830 582 178265181 583 97235553 584 46503961 585 19376651 586 6975595 587 2146337 588 556458 589 119241 590 20559 591 2742 592 266 593 17 594 1 595 1 596 18 597 282 598 3005 599 23283 600 139697 601 675201 602 2700801 603 9115203 604 26332807 605 65832016 606 143633489 607 275297519 608 465888109 609 698832164 610 931776218 611 1106484259 612 1171571568 613 1106484259 614 931776218 615 698832164 616 465888109 617 275297519 618 143633489 619 65832016 620 26332807 621 9115203 622 2700801 623 675201 624 139697 625 23283 626 3005 627 282 628 18 629 1 630 1 631 18 632 299 633 3284 634 26271 635 162878 636 814388 637 3373892 638 11808620 639 35425859 640 92107234 641 209334621 642 418669242 643 740722505 644 1163992508 645 1629589511 646 2036986889 647 2276632405 648 2276632405 649 2036986889 650 1629589511 651 1163992508 652 740722505 653 418669242 654 209334621 655 92107234 656 35425859 657 11808620 658 3373892 659 814388 660 162878 661 26271 662 3284 663 299 664 18 665 1 666 1 667 19 668 316 669 3581 670 29539 671 189048 672 976748 673 4186063 674 15174476 675 47209480 676 127465596 677 301282317 678 627671494 679 1158778143 680 1903706948 681 2792103524 682 3664635875 683 4311336324 684 4550855008 685 4311336324 686 3664635875 687 2792103524 688 1903706948 689 1158778143 690 627671494 691 301282317 692 127465596 693 47209480 694 15174476 695 4186063 696 976748 697 189048 698 29539 699 3581 700 316 701 19 702 1 703 1 704 19 705 334 706 3895 707 33105 708 218489 709 1165274 710 5160496 711 19351860 712 62355993 713 174596781 714 428555733 715 928537422 716 1785648887 717 3061112378 718 4693705646 719 6453845263 720 7972397089 721 8858218988 722 8858218988 723 7972397089 724 6453845263 725 4693705646 726 3061112378 727 1785648887 728 928537422 729 428555733 730 174596781 731 62355993 732 19351860 733 5160496 734 1165274 735 218489 736 33105 737 3895 738 334 739 19 740 1 741 1 742 20 743 353 744 4227 745 36985 746 251498 747 1383237 748 6323369 749 24503052 750 81676838 751 236862828 752 602923561 753 1356578012 754 2713156023 755 4844921469 756 7751874350 757 11143319377 758 14420766253 759 16824227295 760 17709712942 761 16824227295 762 14420766253 763 11143319377 764 7751874350 765 4844921469 766 2713156023 767 1356578012 768 602923561 769 236862828 770 81676838 771 24503052 772 6323369 773 1383237 774 251498 775 36985 776 4227 777 353 778 20 779 1 780 1 781 20 782 372 783 4578 784 41199 785 288390 786 1634209 787 7704128 788 30816511 789 106145758 790 318437273 791 839516447 792 1958871709 793 4068425857 794 7555648019 795 12592746699 796 18889120048 797 25555868300 798 31234950144 799 34522839633 800 34522839633 801 31234950144 802 25555868300 803 18889120048 804 12592746699 805 7555648019 806 4068425857 807 1958871709 808 839516447 809 318437273 810 106145758 811 30816511 812 7704128 813 1634209 814 288390 815 41199 816 4578 817 372 818 20 819 1 820 1 821 21 822 391 823 4948 824 45764 825 329499 826 1922076 827 9335795 828 38510154 829 136924990 830 424467468 831 1157638547 832 2797626488 833 6025657050 834 11620910024 835 20142910709 836 31473297982 837 44432891268 838 56775361065 839 65739891760 840 69026886348 841 65739891760 842 56775361065 843 44432891268 844 31473297982 845 20142910709 846 11620910024 847 6025657050 848 2797626488 849 1157638547 850 424467468 851 136924990 852 38510154 853 9335795 854 1922076 855 329499 856 45764 857 4948 858 391 859 21 860 1 861 1 862 21 863 411 864 5337 865 50700 866 375176 867 2251056 868 11255276 869 47834922 870 175394713 871 561263079 872 1581741404 873 3954353508 874 8821250133 875 17642500265 876 31756500477 877 51604313275 878 75888695992 879 101184927990 880 122487018093 881 134735719902 882 134735719902 883 122487018093 884 101184927990 885 75888695992 886 51604313275 887 31756500477 888 17642500265 889 8821250133 890 3954353508 891 1581741404 892 561263079 893 175394713 894 47834922 895 11255276 896 2251056 897 375176 898 50700 899 5337 900 411 901 21 902 1 903 1 904 22 905 431 906 5747 907 56026 908 425793 909 2625719 910 13503696 911 59078668 912 223186076 913 736514051 914 2142586330 915 5535014685 916 12773110811 917 26458586679 918 49389361800 919 83344548037 920 127468132292 921 177039072628 922 223628302267 923 257172547606 924 269418859397 925 257172547606 926 223628302267 927 177039072628 928 127468132292 929 83344548037 930 49389361800 931 26458586679 932 12773110811 933 5535014685 934 2142586330 935 736514051 936 223186076 937 59078668 938 13503696 939 2625719 940 425793 941 56026 942 5747 943 431 944 22 945 1 946 1 947 22 948 452 949 6177 950 61762 951 481738 952 3051007 953 16126750 954 72570372 955 282218113 956 959541584 957 2878624750 958 7676332665 959 18305100969 960 39225216361 961 75835418297 962 132711982019 963 210777853795 964 304456899926 965 400601184113 966 480721420935 967 526504413405 968 526504413405 969 480721420935 970 400601184113 971 304456899926 972 210777853795 973 132711982019 974 75835418297 975 39225216361 976 18305100969 977 7676332665 978 2878624750 979 959541584 980 282218113 981 72570372 982 16126750 983 3051007 984 481738 985 61762 986 6177 987 452 988 22 989 1 990 1 991 23 992 474 993 6628 994 67928 995 543424 996 3532251 997 19175074 998 88684716 999 354738863 1000 1241586020 1001 3837629515 1002 10553481165 1003 25977799791 1004 57522270966 1005 115044541931 1006 208518232249 1007 343441794292 1008 515162691438 1009 704959472494 1010 881199340617 1011 1007084960705 1012 1052861549828 1013 1007084960705 1014 881199340617 1015 704959472494 1016 515162691438 1017 343441794292 1018 208518232249 1019 115044541931 1020 57522270966 1021 25977799791 1022 10553481165 1023 3837629515 1024 1241586020 1025 354738863 1026 88684716 1027 19175074 1028 3532251 1029 543424 1030 67928 1031 6628 1032 474 1033 23 1034 1 1035 1 1036 23 1037 496 1038 7100 1039 74547 1040 611279 1041 4075191 1042 22704636 1043 107847018 1044 443371074 1045 1596135865 1046 5078614114 1047 14389406657 1048 36526955359 1049 83490183676 1050 172546379597 1051 323524461745 1052 551894670035 1053 858502820054 1054 1219977691656 1055 1585970999152 1056 1888060713276 1057 2059702596302 1058 2059702596302 1059 1888060713276 1060 1585970999152 1061 1219977691656 1062 858502820054 1063 551894670035 1064 323524461745 1065 172546379597 1066 83490183676 1067 36526955359 1068 14389406657 1069 5078614114 1070 1596135865 1071 443371074 1072 107847018 1073 22704636 1074 4075191 1075 611279 1076 74547 1077 7100 1078 496 1079 23 1080 1 1081 1 1082 24 1083 518 1084 7595 1085 81638 1086 685757 1087 4686000 1088 26777142 1089 130538567 1090 551162837 1091 2039302494 1092 6674080888 1093 19466069255 1094 50911258051 1095 120005108263 1096 256010897628 1097 496021114153 1098 875331377916 1099 1410256108865 1100 2078272160432 1101 2805667416584 1102 3473683468151 1103 3947367577444 1104 4118992254725 1105 3947367577444 1106 3473683468151 1107 2805667416584 1108 2078272160432 1109 1410256108865 1110 875331377916 1111 496021114153 1112 256010897628 1113 120005108263 1114 50911258051 1115 19466069255 1116 6674080888 1117 2039302494 1118 551162837 1119 130538567 1120 26777142 1121 4686000 1122 685757 1123 81638 1124 7595 1125 518 1126 24 1127 1 1128 1 1129 24 1130 541 1131 8112 1132 89225 1133 767329 1134 5371301 1135 31460472 1136 157302359 1137 681643553 1138 2590245499 1139 8712643949 1140 26137931847 1141 70371354972 1142 170901862074 1143 375984096562 1144 751968193123 1145 1371236116871 1146 2285393528118 1147 3488232227127 1148 4883525117977 1149 6278818008828 1150 7420421283160 1151 8065675307783 1152 8065675307783 1153 7420421283160 1154 6278818008828 1155 4883525117977 1156 3488232227127 1157 2285393528118 1158 1371236116871 1159 751968193123 1160 375984096562 1161 170901862074 1162 70371354972 1163 26137931847 1164 8712643949 1165 2590245499 1166 681643553 1167 157302359 1168 31460472 1169 5371301 1170 767329 1171 89225 1172 8112 1173 541 1174 24 1175 1 1176 1 1177 25 1178 565 1179 8652 1180 97329 1181 856492 1182 6138188 1183 36829126 1184 188749270 1185 838885641 1186 3271653999 1187 11302077449 1188 34848072134 1189 96502353600 1190 241255883999 1191 546846670397 1192 1127871257694 1193 2123051779188 1194 3656366953046 1195 5773210978493 1196 8371155918815 1197 11161541225086 1198 13698255139878 1199 15484984071167 1200 16130191740799 1201 15484984071167 1202 13698255139878 1203 11161541225086 1204 8371155918815 1205 5773210978493 1206 3656366953046 1207 2123051779188 1208 1127871257694 1209 546846670397 1210 241255883999 1211 96502353600 1212 34848072134 1213 11302077449 1214 3271653999 1215 838885641 1216 188749270 1217 36829126 1218 6138188 1219 856492 1220 97329 1221 8652 1222 565 1223 25 1224 1 1225 1 1226 25 1227 589 1228 9216 1229 105974 1230 953762 1231 6994254 1232 42964701 1233 225564677 1234 1027572414 1235 4110289655 1236 14572845138 1237 46147342936 1238 131342437586 1239 337737696649 1240 788054625514 1241 1674616079217 1242 3250725330244 1243 5779067253766 1244 9429004466671 1245 14143506700006 1246 19531509252388 1247 24858284503040 1248 29181464416612 1249 31613253117996 1250 31613253117996 1251 29181464416612 1252 24858284503040 1253 19531509252388 1254 14143506700006 1255 9429004466671 1256 5779067253766 1257 3250725330244 1258 1674616079217 1259 788054625514 1260 337737696649 1261 131342437586 1262 46147342936 1263 14572845138 1264 4110289655 1265 1027572414 1266 225564677 1267 42964701 1268 6994254 1269 953762 1270 105974 1271 9216 1272 589 1273 25 1274 1 1275 1 1276 26 1277 613 1278 9803 1279 115183 1280 1059681 1281 7947607 1282 49956382 1283 268515552 1284 1253072576 1285 5137597559 1286 18682172940 1287 60717062054 1288 177480642926 1289 469055984876 1290 1125734363702 1291 2462543920597 1292 4925087841193 1293 9029327708854 1294 15207288772806 1295 23571297597849 1296 33673282282642 1297 44387508463482 1298 54036966825109 1299 60791587678247 1300 63223251185377 1301 60791587678247 1302 54036966825109 1303 44387508463482 1304 33673282282642 1305 23571297597849 1306 15207288772806 1307 9029327708854 1308 4925087841193 1309 2462543920597 1310 1125734363702 1311 469055984876 1312 177480642926 1313 60717062054 1314 18682172940 1315 5137597559 1316 1253072576 1317 268515552 1318 49956382 1319 7947607 1320 1059681 1321 115183 1322 9803 1323 613 1324 26 1325 1