0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 2 8 2 9 1 10 1 11 3 12 2 13 3 14 1 15 1 16 4 17 5 18 5 19 4 20 1 21 1 22 5 23 9 24 5 25 9 26 5 27 1 28 1 29 6 30 14 31 14 32 14 33 14 34 6 35 1 36 1 37 7 38 20 39 28 40 28 41 28 42 20 43 7 44 1 45 1 46 8 47 27 48 48 49 56 50 28 51 48 52 27 53 8 54 1 55 1 56 9 57 35 58 75 59 104 60 84 61 76 62 75 63 35 64 9 65 1 66 1 67 10 68 44 69 110 70 179 71 188 72 84 73 151 74 110 75 44 76 10 77 1 78 1 79 11 80 54 81 154 82 289 83 367 84 272 85 235 86 261 87 154 88 54 89 11 90 1 91 1 92 12 93 65 94 208 95 443 96 656 97 639 98 272 99 496 100 415 101 208 102 65 103 12 104 1 105 1 106 13 107 77 108 273 109 651 110 1099 111 1295 112 911 113 768 114 911 115 623 116 273 117 77 118 13 119 1 120 1 121 14 122 90 123 350 124 924 125 1750 126 2394 127 2206 128 1679 129 1679 130 1534 131 896 132 350 133 90 134 14 135 1 136 1 137 15 138 104 139 440 140 1274 141 2674 142 4144 143 4600 144 3885 145 1679 146 3213 147 2430 148 1246 149 440 150 104 151 15 152 1 153 1 154 16 155 119 156 544 157 1714 158 3948 159 6818 160 8744 161 8485 162 5564 163 4892 164 5643 165 3676 166 1686 167 544 168 119 169 16 170 1 171 1 172 17 173 135 174 663 175 2258 176 5662 177 10766 178 15562 179 17229 180 14049 181 5564 182 10535 183 9319 184 5362 185 2230 186 663 187 135 188 17 189 1 190 1 191 18 192 152 193 798 194 2921 195 7920 196 16428 197 26328 198 32791 199 31278 200 19613 201 16099 202 19854 203 14681 204 7592 205 2893 206 798 207 152 208 18 209 1 210 1 211 19 212 170 213 950 214 3719 215 10841 216 24348 217 42756 218 59119 219 64069 220 50891 221 19613 222 35953 223 34535 224 22273 225 10485 226 3691 227 950 228 170 229 19 230 1 231 1 232 20 233 189 234 1120 235 4669 236 14560 237 35189 238 67104 239 101875 240 123188 241 114960 242 70504 243 55566 244 70488 245 56808 246 32758 247 14176 248 4641 249 1120 250 189 251 20 252 1 253 1 254 21 255 209 256 1309 257 5789 258 19229 259 49749 260 102293 261 168979 262 225063 263 238148 264 185464 265 126070 266 126054 267 127296 268 89566 269 46934 270 18817 271 5761 272 1309 273 209 274 21 275 1 276 1 277 22 278 230 279 1518 280 7098 281 25018 282 68978 283 152042 284 271272 285 394042 286 463211 287 423612 288 311534 289 126070 290 253350 291 216862 292 136500 293 65751 294 24578 295 7070 296 1518 297 230 298 22 299 1 300 1 301 23 302 252 303 1748 304 8616 305 32116 306 93996 307 221020 308 423314 309 665314 310 857253 311 886823 312 735146 313 437604 314 379420 315 470212 316 353362 317 202251 318 90329 319 31648 320 8588 321 1748 322 252 323 23 324 1 325 1 326 24 327 275 328 2000 329 10364 330 40732 331 126112 332 315016 333 644334 334 1088628 335 1522567 336 1744076 337 1621969 338 1172750 339 437604 340 849632 341 823574 342 555613 343 292580 344 121977 345 40236 346 10336 347 2000 348 275 349 24 350 1 351 1 352 25 353 299 354 2275 355 12364 356 51096 357 166844 358 441128 359 959350 360 1732962 361 2611195 362 3266643 363 3366045 364 2794719 365 1610354 366 1287236 367 1673206 368 1379187 369 848193 370 414557 371 162213 372 50572 373 12336 374 2275 375 299 376 25 377 1 378 1 379 26 380 324 381 2574 382 14639 383 63460 384 217940 385 607972 386 1400478 387 2692312 388 4344157 389 5877838 390 6632688 391 6160764 392 4405073 393 1610354 394 2960442 395 3052393 396 2227380 397 1262750 398 576770 399 212785 400 62908 401 14611 402 2574 403 324 404 26 405 1 406 1 407 27 408 350 409 2898 410 17213 411 78099 412 281400 413 825912 414 2008450 415 4092790 416 7036469 417 10221995 418 12510526 419 12793452 420 10565837 421 6015427 422 4570796 423 6012835 424 5279773 425 3490130 426 1839520 427 789555 428 275693 429 77519 430 17185 431 2898 432 350 433 27 434 1 435 1 436 28 437 377 438 3248 439 20111 440 95312 441 359499 442 1107312 443 2834362 444 6101240 445 11129259 446 17258464 447 22732521 448 25303978 449 23359289 450 16581264 451 10586223 452 10583631 453 11292608 454 8769903 455 5329650 456 2629075 457 1065248 458 353212 459 94704 460 20083 461 3248 462 377 463 28 464 1 465 1 466 29 467 405 468 3625 469 23359 470 115423 471 454811 472 1466811 473 3941674 474 8935602 475 17230499 476 28387723 477 39990985 478 48036499 479 48663267 480 39940553 481 27167487 482 10586223 483 21876239 484 20062511 485 14099553 486 7958725 487 3694323 488 1418460 489 447916 490 114787 491 23331 492 3625 493 405 494 29 495 1 496 1 497 30 498 434 499 4030 500 26984 501 138782 502 570234 503 1921622 504 5408485 505 12877276 506 26166101 507 45618222 508 68378708 509 88027484 510 96699766 511 88603820 512 67108040 513 37753710 514 32462462 515 41938750 516 34162064 517 22058278 518 11653048 519 5112783 520 1866376 521 562703 522 138118 523 26956 524 4030 525 434 526 30 527 1 528 1 529 31 530 464 531 4464 532 31014 533 165766 534 709016 535 2491856 536 7330107 537 18285761 538 39043377 539 71784323 540 113996930 541 156406192 542 184727250 543 185303586 544 155711860 545 104861750 546 37753710 547 74401212 548 76100814 549 56220342 550 33711326 551 16765831 552 6979159 553 2429079 554 700821 555 165074 556 30986 557 4464 558 464 559 31 560 1 561 1 562 32 563 495 564 4928 565 35478 566 196780 567 874782 568 3200872 569 9821963 570 25615868 571 57329138 572 110827700 573 185781253 574 270403122 575 341133442 576 370030836 577 341015446 578 260573610 579 142615460 580 112154922 581 150502026 582 132321156 583 89931668 584 50477157 585 23744990 586 9408238 587 3129900 588 865895 589 196060 590 35450 591 4928 592 495 593 32 594 1 595 1 596 33 597 527 598 5423 599 40406 600 232258 601 1071562 602 4075654 603 13022835 604 35437831 605 82945006 606 168156838 607 296608953 608 456184375 609 611536564 610 711164278 611 711046282 612 601589056 613 403189070 614 142615460 615 262656948 616 282823182 617 222252824 618 140408825 619 74222147 620 33153228 621 12538138 622 3995795 623 1061955 624 231510 625 40378 626 5423 627 527 628 33 629 1 630 1 631 34 632 560 633 5950 634 45829 635 272664 636 1303820 637 5147216 638 17098489 639 48460666 640 118382837 641 251101844 642 464765791 643 752793328 644 1067720939 645 1322700842 646 1422210560 647 1312635338 648 1004778126 649 545804530 650 405272408 651 545480130 652 505076006 653 362661649 654 214630972 655 107375375 656 45691366 657 16533933 658 5057750 659 1293465 660 271888 661 45801 662 5950 663 560 664 34 665 1 666 1 667 35 668 594 669 6510 670 51779 671 318493 672 1576484 673 6451036 674 22245705 675 65559155 676 166843503 677 369484681 678 715867635 679 1217559119 680 1820514267 681 2390421781 682 2744911402 683 2734845898 684 2317413464 685 1550582656 686 951076938 687 950752538 688 1050556136 689 867737655 690 577292621 691 322006347 692 153066741 693 62225299 694 21591683 695 6351215 696 1565353 697 317689 698 51751 699 6510 700 594 701 35 702 1 703 1 704 36 705 629 706 7104 707 58289 708 370272 709 1894977 710 8027520 711 28696741 712 87804860 713 232402658 714 536328184 715 1085352316 716 1933426754 717 3038073386 718 4210936048 719 5135333183 720 5479757300 721 5052259362 722 3867996120 723 2501659594 724 951076938 725 2001308674 726 1918293791 727 1445030276 728 899298968 729 475073088 730 215292040 731 83816982 732 27942898 733 7916568 734 1883042 735 369440 736 58261 737 7104 738 629 739 36 740 1 741 1 742 37 743 665 744 7733 745 65393 746 428561 747 2265249 748 9922497 749 36724261 750 116501601 751 320207518 752 768730842 753 1621680500 754 3018779070 755 4971500140 756 7249009434 757 9346269231 758 10615090483 759 10532016662 760 8920255482 761 6369655714 762 3452736532 763 2952385612 764 3919602465 765 3363324067 766 2344329244 767 1374372056 768 690365128 769 299109022 770 111759880 771 35859466 772 9799610 773 2252482 774 427701 775 65365 776 7733 777 665 778 37 779 1 780 1 781 38 782 702 783 8398 784 73126 785 493954 786 2693810 787 12187746 788 46646758 789 153225862 790 436709119 791 1088938360 792 2390411342 793 4640459570 794 7990279210 795 12220509574 796 16595278665 797 19961359714 798 21147107145 799 19452272144 800 15289911196 801 9822392246 802 3452736532 803 6871988077 804 7282926532 805 5707653311 806 3718701300 807 2064737184 808 989474150 809 410868902 810 147619346 811 45659076 812 12052092 813 2680183 814 493066 815 73098 816 8398 817 702 818 38 819 1 820 1 821 39 822 740 823 9100 824 81524 825 567080 826 3187764 827 14881556 828 58834504 829 199872620 830 589934981 831 1525647479 832 3479349702 833 7030870912 834 12630738780 835 20210788784 836 28815788239 837 36556638379 838 41108466859 839 40599379289 840 34742183340 841 25112303442 842 13275128778 843 10324724609 844 14154914609 845 12990579843 846 9426354611 847 5783438484 848 3054211334 849 1400343052 850 558488248 851 193278422 852 57711168 853 14732275 854 3173249 855 566164 856 81496 857 9100 858 740 859 39 860 1 861 1 862 40 863 779 864 9840 865 90624 866 648604 867 3754844 868 18069320 869 73716060 870 258707124 871 789807601 872 2115582460 873 5004997181 874 10510220614 875 19661609692 876 32841527564 877 49026577023 878 65372426618 879 77665105238 880 81707846148 881 75341562629 882 59854486782 883 38387432220 884 13275128778 885 24479639218 886 27145494452 887 22416934454 888 15209793095 889 8837649818 890 4454554386 891 1958831300 892 751766670 893 250989590 894 72443443 895 17905524 896 3739413 897 647660 898 90596 899 9840 900 779 901 40 902 1 903 1 904 41 905 819 906 10619 907 100464 908 739228 909 4403448 910 21824164 911 91785380 912 332423184 913 1048514725 914 2905390061 915 7120579641 916 15515217795 917 30171830306 918 52503137256 919 81868104587 920 114399003641 921 143037531856 922 159372951386 923 157049408777 924 135196049411 925 98241919002 926 51662560998 927 37754767996 928 51625133670 929 49562428906 930 37626727549 931 24047442913 932 13292204204 933 6413385686 934 2710597970 935 1002756260 936 323433033 937 90348967 938 21644937 939 4387073 940 738256 941 100436 942 10619 943 819 944 41 945 1 946 1 947 42 948 860 949 11438 950 111083 951 839692 952 5142676 953 26227612 954 113609544 955 424208564 956 1380937909 957 3953904786 958 10025969702 959 22635797436 960 45687048101 961 82674967562 962 134371241843 963 196267108228 964 257436535497 965 302410483242 966 316422360163 967 292245458188 968 233437968413 969 149904480000 970 89417328994 971 89379901666 972 101187562576 973 87189156455 974 61674170462 975 37339647117 976 19705589890 977 9123983656 978 3713354230 979 1326189293 980 413782000 981 111993904 982 26032010 983 5125329 984 838692 985 111055 986 11438 987 860 988 42 989 1 990 1 991 43 992 902 993 12298 994 122521 995 950775 996 5982368 997 31370288 998 139837156 999 537818108 1000 1805146473 1001 5334842695 1002 13979874488 1003 32661767138 1004 68322845537 1005 128362015663 1006 217046209405 1007 330638350071 1008 453703643725 1009 559847018739 1010 618832843405 1011 608667818351 1012 525683426601 1013 383342448413 1014 239321808994 1015 89417328994 1016 190567464242 1017 188376719031 1018 148863326917 1019 99013817579 1020 57045237007 1021 28829573546 1022 12837337886 1023 5039543523 1024 1739971293 1025 525775904 1026 138025914 1027 31157339 1028 5964021 1029 949747 1030 122493 1031 12298 1032 902 1033 43 1034 1 1035 1 1036 44 1037 945 1038 13200 1039 134819 1040 1073296 1041 6933143 1042 37352656 1043 171207444 1044 677655264 1045 2342964581 1046 7139989168 1047 19314717183 1048 46641641626 1049 100984612675 1050 196684861200 1051 345408225068 1052 547684559476 1053 784341993796 1054 1013550662464 1055 1178679862144 1056 1227500661756 1057 1134351244952 1058 909025875014 1059 622664257407 1060 328739137988 1061 279984793236 1062 378944183273 1063 337240045948 1064 247877144496 1065 156059054586 1066 85874810553 1067 41666911432 1068 17876881409 1069 6779514816 1070 2265747197 1071 663801818 1072 169183253 1073 37121360 1074 6913768 1075 1072240 1076 134791 1077 13200 1078 945 1079 44 1080 1 1081 1 1082 45 1083 989 1084 14145 1085 148019 1086 1208115 1087 8006439 1088 44285799 1089 208560100 1090 848862708 1091 3020619845 1092 9482953749 1093 26454706351 1094 65956358809 1095 147626254301 1096 297669473875 1097 542093086268 1098 893092784544 1099 1332026553272 1100 1797892656260 1101 2192230524608 1102 2406180523900 1103 2361851906708 1104 2043377119966 1105 1531690132421 1106 951403395395 1107 328739137988 1108 658928976509 1109 716184229221 1110 585117190444 1111 403936199082 1112 241933865139 1113 127541721985 1114 59543792841 1115 24656396225 1116 9045262013 1117 2929549015 1118 832985071 1119 206304613 1120 44035128 1121 7986008 1122 1207031 1123 147991 1124 14145 1125 989 1126 45 1127 1 1128 1 1129 46 1130 1034 1131 15134 1132 162164 1133 1356134 1134 9214554 1135 52292238 1136 252845899 1137 1057422808 1138 3869482553 1139 12503573594 1140 35937660100 1141 92411065160 1142 213582613110 1143 445295728176 1144 839762560143 1145 1435185870812 1146 2225119337816 1147 3129919209532 1148 3990123180868 1149 4598411048508 1150 4768032430608 1151 4405229026674 1152 3575067252387 1153 2483093527816 1154 1280142533383 1155 987668114497 1156 1375113205730 1157 1301301419665 1158 989053389526 1159 645870064221 1160 369475587124 1161 187085514826 1162 84200189066 1163 33701658238 1164 11974811028 1165 3762534086 1166 1039289684 1167 250339741 1168 52021136 1169 9193039 1170 1355022 1171 162136 1172 15134 1173 1034 1174 46 1175 1 1176 1 1177 47 1178 1080 1179 16168 1180 177298 1181 1518298 1182 10570688 1183 61506792 1184 305138137 1185 1310268707 1186 4926905361 1187 16373056147 1188 48441233694 1189 128348725260 1190 305993678270 1191 658878341286 1192 1285058288319 1193 2274948430955 1194 3660305208628 1195 5355038547348 1196 7120042390400 1197 8588534229376 1198 9366443479116 1199 9173261457282 1200 7980296279061 1201 6058160780203 1202 3763236061199 1203 1280142533383 1204 2362781320227 1205 2676414625395 1206 2290354809191 1207 1634923453747 1208 1015345651345 1209 556561101950 1210 271285703892 1211 117901847304 1212 45676469266 1213 15737345114 1214 4801823770 1215 1289629425 1216 302360877 1217 61214175 1218 10548061 1219 1517158 1220 177270 1221 16168 1222 1080 1223 47 1224 1 1225 1 1226 48 1227 1127 1228 17248 1229 193466 1230 1695596 1231 12088986 1232 72077480 1233 366644929 1234 1615406844 1235 6237174068 1236 21299961508 1237 64814289841 1238 176789958954 1239 434342403530 1240 964872019556 1241 1943936629605 1242 3560006719274 1243 5935253639583 1244 9015343755976 1245 12475080937748 1246 15708576619776 1247 17954977708492 1248 18539704936398 1249 17153557736343 1250 14038457059264 1251 9821396841402 1252 5043378594582 1253 3642923853610 1254 5039195945622 1255 4966769434586 1256 3925278262938 1257 2650269105092 1258 1571906753295 1259 827846805842 1260 389187551196 1261 163578316570 1262 61413814380 1263 20539168884 1264 6091453195 1265 1591990302 1266 363575052 1267 71762236 1268 12065219 1269 1694428 1270 193438 1271 17248 1272 1127 1273 48 1274 1 1275 1 1276 49 1277 1175 1278 18375 1279 210714 1280 1889062 1281 13784582 1282 84166466 1283 438722409 1284 1982051773 1285 7852580912 1286 27537135576 1287 86114251349 1288 241604248795 1289 611132362484 1290 1399214423086 1291 2908808649161 1292 5503943348879 1293 9495260358857 1294 14950597395559 1295 21490424693724 1296 28183657557524 1297 33663554328268 1298 36494682644890 1299 35693262672741 1300 31192014795607 1301 23859853900666 1302 14864775435984 1303 8686302448192 1304 8682119799232 1305 10005965380208 1306 8892047697524 1307 6575547368030 1308 4222175858387 1309 2399753559137 1310 1217034357038 1311 552765867766 1312 224992130950 1313 81952983264 1314 26630622079 1315 7683443497 1316 1955565354 1317 435337288 1318 83827455 1319 13759647 1320 1887866 1321 210686 1322 18375 1323 1175 1324 49 1325 1