0 1 1 1 2 1 3 1 4 3 5 1 6 1 7 4 8 4 9 1 10 1 11 5 12 8 13 5 14 1 15 1 16 6 17 14 18 14 19 6 20 1 21 1 22 7 23 20 24 28 25 20 26 7 27 1 28 1 29 8 30 27 31 49 32 49 33 27 34 8 35 1 36 1 37 9 38 35 39 76 40 98 41 76 42 35 43 9 44 1 45 1 46 10 47 44 48 111 49 175 50 175 51 111 52 44 53 10 54 1 55 1 56 11 57 54 58 155 59 286 60 350 61 286 62 155 63 54 64 11 65 1 66 1 67 12 68 65 69 209 70 441 71 637 72 637 73 441 74 209 75 65 76 12 77 1 78 1 79 13 80 77 81 274 82 650 83 1078 84 1274 85 1078 86 650 87 274 88 77 89 13 90 1 91 1 92 14 93 90 94 351 95 924 96 1728 97 2352 98 2352 99 1728 100 924 101 351 102 90 103 14 104 1 105 1 106 15 107 104 108 441 109 1275 110 2652 111 4080 112 4704 113 4080 114 2652 115 1275 116 441 117 104 118 15 119 1 120 1 121 16 122 119 123 545 124 1716 125 3927 126 6732 127 8784 128 8784 129 6732 130 3927 131 1716 132 545 133 119 134 16 135 1 136 1 137 17 138 135 139 664 140 2261 141 5643 142 10659 143 15516 144 17568 145 15516 146 10659 147 5643 148 2261 149 664 150 135 151 17 152 1 153 1 154 18 155 152 156 799 157 2925 158 7904 159 16302 160 26175 161 33084 162 33084 163 26175 164 16302 165 7904 166 2925 167 799 168 152 169 18 170 1 171 1 172 19 173 170 174 951 175 3724 176 10829 177 24206 178 42477 179 59259 180 66168 181 59259 182 42477 183 24206 184 10829 185 3724 186 951 187 170 188 19 189 1 190 1 191 20 192 189 193 1121 194 4675 195 14553 196 35035 197 66683 198 101736 199 125427 200 125427 201 101736 202 66683 203 35035 204 14553 205 4675 206 1121 207 189 208 20 209 1 210 1 211 21 212 209 213 1310 214 5796 215 19228 216 49588 217 101718 218 168419 219 227163 220 250854 221 227163 222 168419 223 101718 224 49588 225 19228 226 5796 227 1310 228 209 229 21 230 1 231 1 232 22 233 230 234 1519 235 7106 236 25024 237 68816 238 151306 239 270137 240 395582 241 478017 242 478017 243 395582 244 270137 245 151306 246 68816 247 25024 248 7106 249 1519 250 230 251 22 252 1 253 1 254 23 255 252 256 1749 257 8625 258 32130 259 93840 260 220122 261 421443 262 665719 263 873599 264 956034 265 873599 266 665719 267 421443 268 220122 269 93840 270 32130 271 8625 272 1749 273 252 274 23 275 1 276 1 277 24 278 275 279 2001 280 10374 281 40755 282 125970 283 313962 284 641565 285 1087162 286 1539318 287 1829633 288 1829633 289 1539318 290 1087162 291 641565 292 313962 293 125970 294 40755 295 10374 296 2001 297 275 298 24 299 1 300 1 301 25 302 299 303 2276 304 12375 305 51129 306 166725 307 439932 308 955527 309 1728727 310 2626480 311 3368951 312 3659266 313 3368951 314 2626480 315 1728727 316 955527 317 439932 318 166725 319 51129 320 12375 321 2276 322 299 323 25 324 1 325 1 326 26 327 324 328 2575 329 14651 330 63504 331 217854 332 606657 333 1395459 334 2684254 335 4355207 336 5995431 337 7028217 338 7028217 339 5995431 340 4355207 341 2684254 342 1395459 343 606657 344 217854 345 63504 346 14651 347 2575 348 324 349 26 350 1 351 1 352 27 353 350 354 2899 355 17226 356 78155 357 281358 358 824511 359 2002116 360 4079713 361 7039461 362 10350638 363 13023648 364 14056434 365 13023648 366 10350638 367 7039461 368 4079713 369 2002116 370 824511 371 281358 372 78155 373 17226 374 2899 375 350 376 27 377 1 378 1 379 28 380 377 381 3249 382 20125 383 95381 384 359513 385 1105869 386 2826627 387 6081829 388 11119174 389 17390099 390 23374286 391 27080082 392 27080082 393 23374286 394 17390099 395 11119174 396 6081829 397 2826627 398 1105869 399 359513 400 95381 401 20125 402 3249 403 377 404 28 405 1 406 1 407 29 408 405 409 3626 410 23374 411 115506 412 454894 413 1465382 414 3932496 415 8908456 416 17201003 417 28509273 418 40764385 419 50454368 420 54160164 421 50454368 422 40764385 423 28509273 424 17201003 425 8908456 426 3932496 427 1465382 428 454894 429 115506 430 23374 431 3626 432 405 433 29 434 1 435 1 436 30 437 434 438 4031 439 27000 440 138880 441 570400 442 1920276 443 5397878 444 12840952 445 26109459 446 45710276 447 69273658 448 91218753 449 104614532 450 104614532 451 91218753 452 69273658 453 45710276 454 26109459 455 12840952 456 5397878 457 1920276 458 570400 459 138880 460 27000 461 4031 462 434 463 30 464 1 465 1 466 31 467 464 468 4465 469 31031 470 165880 471 709280 472 2490676 473 7318154 474 18238830 475 38950411 476 71819735 477 114983934 478 160492411 479 195833285 480 209229064 481 195833285 482 160492411 483 114983934 484 71819735 485 38950411 486 18238830 487 7318154 488 2490676 489 709280 490 165880 491 31031 492 4465 493 464 494 31 495 1 496 1 497 32 498 495 499 4929 500 35496 501 196911 502 875160 503 3199956 504 9808830 505 25556984 506 57189241 507 110770146 508 186803669 509 275476345 510 356325696 511 405062349 512 405062349 513 356325696 514 275476345 515 186803669 516 110770146 517 57189241 518 25556984 519 9808830 520 3199956 521 875160 522 196911 523 35496 524 4929 525 495 526 32 527 1 528 1 529 33 530 527 531 5424 532 40425 533 232407 534 1072071 535 4075116 536 13008786 537 35365814 538 82746225 539 167959387 540 297573815 541 462280014 542 631802041 543 761388045 544 810124698 545 761388045 546 631802041 547 462280014 548 297573815 549 167959387 550 82746225 551 35365814 552 13008786 553 4075116 554 1072071 555 232407 556 40425 557 5424 558 527 559 33 560 1 561 1 562 34 563 560 564 5951 565 45849 566 272832 567 1304478 568 5147187 569 17083902 570 48374600 571 118112039 572 250705612 573 465533202 574 759853829 575 1094082055 576 1393190086 577 1571512743 578 1571512743 579 1393190086 580 1094082055 581 759853829 582 465533202 583 250705612 584 118112039 585 48374600 586 17083902 587 5147187 588 1304478 589 272832 590 45849 591 5951 592 560 593 34 594 1 595 1 596 35 597 594 598 6511 599 51800 600 318681 601 1577310 602 6451665 603 22231089 604 65458502 605 166486639 606 368817651 607 716238814 608 1225387031 609 1853935884 610 2487272141 611 2964702829 612 3143025486 613 2964702829 614 2487272141 615 1853935884 616 1225387031 617 716238814 618 368817651 619 166486639 620 65458502 621 22231089 622 6451665 623 1577310 624 318681 625 51800 626 6511 627 594 628 35 629 1 630 1 631 36 632 629 633 7105 634 58311 635 370481 636 1895991 637 8028975 638 28682754 639 87689591 640 231945141 641 535304290 642 1085056465 643 1941625845 644 3079322915 645 4341208025 646 5451974970 647 6107728315 648 6107728315 649 5451974970 650 4341208025 651 3079322915 652 1941625845 653 1085056465 654 535304290 655 231945141 656 87689591 657 28682754 658 8028975 659 1895991 660 370481 661 58311 662 7105 663 629 664 36 665 1 666 1 667 37 668 665 669 7734 670 65416 671 428792 672 2266472 673 9924966 674 36711729 675 116372345 676 319634732 677 767249431 678 1620360755 679 3026682310 680 5020948760 681 7420530940 682 9793182995 683 11559703285 684 12215456630 685 11559703285 686 9793182995 687 7420530940 688 5020948760 689 3026682310 690 1620360755 691 767249431 692 319634732 693 116372345 694 36711729 695 9924966 696 2266472 697 428792 698 65416 699 7734 700 665 701 37 702 1 703 1 704 38 705 702 706 8399 707 73150 708 494208 709 2695264 710 12191438 711 46636695 712 153084074 713 436007077 714 1086884163 715 2387610186 716 4647043065 717 8047631070 718 12441479700 719 17213713935 720 21352886280 721 23775159915 722 23775159915 723 21352886280 724 17213713935 725 12441479700 726 8047631070 727 4647043065 728 2387610186 729 1086884163 730 436007077 731 153084074 732 46636695 733 12191438 734 2695264 735 494208 736 73150 737 8399 738 702 739 38 740 1 741 1 742 39 743 740 744 9101 745 81549 746 567358 747 3189472 748 14886702 749 58828133 750 199720769 751 589091151 752 1522891240 753 3474494349 754 7034653251 755 12694674135 756 20489110770 757 29655193635 758 38566600215 759 45128046195 760 47550319830 761 45128046195 762 38566600215 763 29655193635 764 20489110770 765 12694674135 766 7034653251 767 3474494349 768 1522891240 769 589091151 770 199720769 771 58828133 772 14886702 773 3189472 774 567358 775 81549 776 9101 777 740 778 39 779 1 780 1 781 40 782 779 783 9841 784 90650 785 648907 786 3756830 787 18076174 788 73714835 789 258548902 790 788811920 791 2111982391 792 4997385589 793 10509147600 794 19729327386 795 33183784905 796 50144304405 797 68221793850 798 83694646410 799 92678366025 800 92678366025 801 83694646410 802 68221793850 803 50144304405 804 33183784905 805 19729327386 806 10509147600 807 4997385589 808 2111982391 809 788811920 810 258548902 811 73714835 812 18076174 813 3756830 814 648907 815 90650 816 9841 817 779 818 40 819 1 820 1 821 41 822 819 823 10620 824 100491 825 739557 826 4405737 827 21833004 828 91791009 829 332263737 830 1047360822 831 2900794311 832 7109367980 833 15506533189 834 30238474986 835 52913112291 836 83328089310 837 118366098255 838 151916440260 839 176373012435 840 185356732050 841 176373012435 842 151916440260 843 118366098255 844 83328089310 845 52913112291 846 30238474986 847 15506533189 848 7109367980 849 2900794311 850 1047360822 851 332263737 852 91791009 853 21833004 854 4405737 855 739557 856 100491 857 10620 858 819 859 41 860 1 861 1 862 42 863 860 864 11439 865 111111 866 840048 867 5145294 868 26238741 869 113624013 870 424054746 871 1379624559 872 3948155133 873 10010162291 874 22615901169 875 45745008175 876 83151587277 877 136241201601 878 201694187565 879 270282538515 880 328289452695 881 361729744485 882 361729744485 883 328289452695 884 270282538515 885 201694187565 886 136241201601 887 83151587277 888 45745008175 889 22615901169 890 10010162291 891 3948155133 892 1379624559 893 424054746 894 113624013 895 26238741 896 5145294 897 840048 898 111111 899 11439 900 860 901 42 902 1 903 1 904 43 905 902 906 12299 907 122550 908 951159 909 5985342 910 31384035 911 139862754 912 537678759 913 1803679305 914 5327779692 915 13958317424 916 32626063460 917 68360909344 918 128896595452 919 219392788878 920 337935389166 921 471976726080 922 598571991210 923 690019197180 924 723459488970 925 690019197180 926 598571991210 927 471976726080 928 337935389166 929 219392788878 930 128896595452 931 68360909344 932 32626063460 933 13958317424 934 5327779692 935 1803679305 936 537678759 937 139862754 938 31384035 939 5985342 940 951159 941 122550 942 12299 943 902 944 43 945 1 946 1 947 44 948 945 949 13201 950 134849 951 1073709 952 6936501 953 37369377 954 171246789 955 677541513 956 2341358064 957 7131458997 958 19286097116 959 46584380884 960 100986972804 961 197257504796 962 348289384330 963 557328178044 964 809912115246 965 1070548717290 966 1288591188390 967 1413478686150 968 1413478686150 969 1288591188390 970 1070548717290 971 809912115246 972 557328178044 973 348289384330 974 197257504796 975 100986972804 976 46584380884 977 19286097116 978 7131458997 979 2341358064 980 677541513 981 171246789 982 37369377 983 6936501 984 1073709 985 134849 986 13201 987 945 988 44 989 1 990 1 991 45 992 989 993 14146 994 148050 995 1208558 996 8010210 997 44305878 998 208616166 999 848788302 1000 3018899577 1001 9472817061 1002 26417556113 1003 65870478000 1004 147571353688 1005 298244477600 1006 545546889126 1007 905617562374 1008 1367240293290 1009 1880460832536 1010 2359139905680 1011 2702069874540 1012 2826957372300 1013 2702069874540 1014 2359139905680 1015 1880460832536 1016 1367240293290 1017 905617562374 1018 545546889126 1019 298244477600 1020 147571353688 1021 65870478000 1022 26417556113 1023 9472817061 1024 3018899577 1025 848788302 1026 208616166 1027 44305878 1028 8010210 1029 1208558 1030 148050 1031 14146 1032 989 1033 45 1034 1 1035 1 1036 46 1037 1034 1038 15135 1039 162196 1040 1356608 1041 9218768 1042 52316088 1043 252922044 1044 1057404468 1045 3867687879 1046 12491716638 1047 35890373174 1048 92288034113 1049 213441831688 1050 445815831288 1051 843791366726 1052 1451164451500 1053 2272857855664 1054 3247701125826 1055 4239600738216 1056 5061209780220 1057 5529027246840 1058 5529027246840 1059 5061209780220 1060 4239600738216 1061 3247701125826 1062 2272857855664 1063 1451164451500 1064 843791366726 1065 445815831288 1066 213441831688 1067 92288034113 1068 35890373174 1069 12491716638 1070 3867687879 1071 1057404468 1072 252922044 1073 52316088 1074 9218768 1075 1356608 1076 162196 1077 15135 1078 1034 1079 46 1080 1 1081 1 1082 47 1083 1080 1084 16169 1085 177331 1086 1518804 1087 10575376 1088 61534856 1089 305238132 1090 1310326512 1091 4925092347 1092 16359404517 1093 48382089812 1094 128178407287 1095 305729865801 1096 659257662976 1097 1289607198014 1098 2294955818226 1099 3724022307164 1100 5520558981490 1101 7487301864042 1102 9300810518436 1103 10590237027060 1104 11058054493680 1105 10590237027060 1106 9300810518436 1107 7487301864042 1108 5520558981490 1109 3724022307164 1110 2294955818226 1111 1289607198014 1112 659257662976 1113 305729865801 1114 128178407287 1115 48382089812 1116 16359404517 1117 4925092347 1118 1310326512 1119 305238132 1120 61534856 1121 10575376 1122 1518804 1123 177331 1124 16169 1125 1080 1126 47 1127 1 1128 1 1129 48 1130 1127 1131 17249 1132 193500 1133 1696135 1134 12094180 1135 72110232 1136 366772988 1137 1615564644 1138 6235418859 1139 21284496864 1140 64741494329 1141 176560497099 1142 433908273088 1143 964987528777 1144 1948864860990 1145 3584563016240 1146 6018978125390 1147 9244581288654 1148 13007860845532 1149 16788112382478 1150 19891047545496 1151 21648291520740 1152 21648291520740 1153 19891047545496 1154 16788112382478 1155 13007860845532 1156 9244581288654 1157 6018978125390 1158 3584563016240 1159 1948864860990 1160 964987528777 1161 433908273088 1162 176560497099 1163 64741494329 1164 21284496864 1165 6235418859 1166 1615564644 1167 366772988 1168 72110232 1169 12094180 1170 1696135 1171 193500 1172 17249 1173 1127 1174 48 1175 1 1176 1 1177 49 1178 1175 1179 18376 1180 210749 1181 1889635 1182 13790315 1183 84204412 1184 438883220 1185 1982337632 1186 7850983503 1187 27519915723 1188 86025991193 1189 241301991428 1190 610468770187 1191 1398895801865 1192 2913852389767 1193 5533427877230 1194 9603541141630 1195 15263559414044 1196 22252442134186 1197 29795973228010 1198 36679159927974 1199 41539339066236 1200 43296583041480 1201 41539339066236 1202 36679159927974 1203 29795973228010 1204 22252442134186 1205 15263559414044 1206 9603541141630 1207 5533427877230 1208 2913852389767 1209 1398895801865 1210 610468770187 1211 241301991428 1212 86025991193 1213 27519915723 1214 7850983503 1215 1982337632 1216 438883220 1217 84204412 1218 13790315 1219 1889635 1220 210749 1221 18376 1222 1175 1223 49 1224 1 1225 1 1226 50 1227 1224 1228 19551 1229 229125 1230 2100384 1231 15679950 1232 97994727 1233 523087632 1234 2421220852 1235 9833321135 1236 35370899226 1237 113545906916 1238 327327982621 1239 851770761615 1240 2009364572052 1241 4312748191632 1242 8447280266997 1243 15136969018860 1244 24867100555674 1245 37516001548230 1246 52048415362196 1247 66475133155984 1248 78218498994210 1249 84835922107716 1250 84835922107716 1251 78218498994210 1252 66475133155984 1253 52048415362196 1254 37516001548230 1255 24867100555674 1256 15136969018860 1257 8447280266997 1258 4312748191632 1259 2009364572052 1260 851770761615 1261 327327982621 1262 113545906916 1263 35370899226 1264 9833321135 1265 2421220852 1266 523087632 1267 97994727 1268 15679950 1269 2100384 1270 229125 1271 19551 1272 1224 1273 50 1274 1 1275 1 1276 51 1277 1274 1278 20775 1279 248676 1280 2329509 1281 17780334 1282 113674677 1283 621082359 1284 2944308484 1285 12254541987 1286 45204220361 1287 148916806142 1288 440873889537 1289 1179098744236 1290 2861135333667 1291 6322112763684 1292 12760028458629 1293 23584249285857 1294 40004069574534 1295 62383102103904 1296 89564416910426 1297 118523548518180 1298 144693632150194 1299 163054421101926 1300 169671844215432 1301 163054421101926 1302 144693632150194 1303 118523548518180 1304 89564416910426 1305 62383102103904 1306 40004069574534 1307 23584249285857 1308 12760028458629 1309 6322112763684 1310 2861135333667 1311 1179098744236 1312 440873889537 1313 148916806142 1314 45204220361 1315 12254541987 1316 2944308484 1317 621082359 1318 113674677 1319 17780334 1320 2329509 1321 248676 1322 20775 1323 1274 1324 51 1325 1