0 1 1 1 2 1 3 1 4 2 5 1 6 1 7 1 8 3 9 1 10 1 11 2 12 4 13 4 14 1 15 1 16 3 17 2 18 8 19 5 20 1 21 1 22 4 23 5 24 10 25 13 26 6 27 1 28 1 29 5 30 9 31 15 32 23 33 19 34 7 35 1 36 1 37 6 38 14 39 24 40 38 41 42 42 26 43 8 44 1 45 1 46 7 47 20 48 38 49 62 50 80 51 68 52 34 53 9 54 1 55 1 56 8 57 27 58 58 59 38 60 142 61 148 62 102 63 43 64 10 65 1 66 1 67 9 68 35 69 85 70 96 71 180 72 290 73 250 74 145 75 53 76 11 77 1 78 1 79 10 80 44 81 120 82 181 83 96 84 470 85 540 86 395 87 198 88 64 89 12 90 1 91 1 92 11 93 54 94 164 95 301 96 277 97 566 98 1010 99 935 100 593 101 262 102 76 103 13 104 1 105 1 106 12 107 65 108 218 109 465 110 578 111 843 112 1576 113 1945 114 1528 115 855 116 338 117 89 118 14 119 1 120 1 121 13 122 77 123 283 124 683 125 1043 126 1421 127 2419 128 3521 129 3473 130 2383 131 1193 132 427 133 103 134 15 135 1 136 1 137 14 138 90 139 360 140 966 141 1726 142 2464 143 3840 144 5940 145 6994 146 5856 147 3576 148 1620 149 530 150 118 151 16 152 1 153 1 154 15 155 104 156 450 157 1326 158 2692 159 4190 160 2464 161 9780 162 12934 163 12850 164 9432 165 5196 166 2150 167 648 168 134 169 17 170 1 171 1 172 16 173 119 174 554 175 1776 176 4018 177 6882 178 6654 179 12244 180 22714 181 25784 182 22282 183 14628 184 7346 185 2798 186 782 187 151 188 18 189 1 190 1 191 17 192 135 193 673 194 2330 195 5794 196 10900 197 13536 198 6654 199 34958 200 48498 201 48066 202 36910 203 21974 204 10144 205 3580 206 933 207 169 208 19 209 1 210 1 211 18 212 152 213 808 214 3003 215 8124 216 16694 217 24436 218 20190 219 41612 220 83456 221 96564 222 84976 223 58884 224 32118 225 13724 226 4513 227 1102 228 188 229 20 230 1 231 1 232 19 233 170 234 960 235 3811 236 11127 237 24818 238 41130 239 44626 240 61802 241 125068 242 180020 243 181540 244 143860 245 91002 246 45842 247 18237 248 5615 249 1290 250 208 251 21 252 1 253 1 254 20 255 189 256 1130 257 4771 258 14938 259 35945 260 65948 261 85756 262 106428 263 186870 264 305088 265 361560 266 325400 267 234862 268 136844 269 64079 270 23852 271 6905 272 1498 273 229 274 22 275 1 276 1 277 21 278 209 279 1319 280 5901 281 19709 282 50883 283 101893 284 151704 285 192184 286 293298 287 491958 288 666648 289 686960 290 560262 291 371706 292 200923 293 87931 294 30757 295 8403 296 1727 297 251 298 23 299 1 300 1 301 22 302 230 303 1528 304 7220 305 25610 306 70592 307 152776 308 253597 309 343888 310 192184 311 785256 312 1158606 313 1353608 314 1247222 315 931968 316 572629 317 288854 318 118688 319 39160 320 10130 321 1978 322 274 323 24 324 1 325 1 326 23 327 252 328 1758 329 8748 330 32830 331 96202 332 223368 333 406373 334 597485 335 536072 336 977440 337 1943862 338 2512214 339 2600830 340 2179190 341 1504597 342 861483 343 407542 344 157848 345 49290 346 12108 347 2252 348 298 349 25 350 1 351 1 352 24 353 275 354 2010 355 10506 356 41578 357 129032 358 319570 359 629741 360 1003858 361 1133557 362 536072 363 2921302 364 4456076 365 5113044 366 4780020 367 3683787 368 2366080 369 1269025 370 565390 371 207138 372 61398 373 14360 374 2550 375 323 376 26 377 1 378 1 379 25 380 299 381 2285 382 12516 383 52084 384 170610 385 448602 386 949311 387 1633599 388 2137415 389 1669629 390 3457374 391 7377378 392 9569120 393 9893064 394 8463807 395 6049867 396 3635105 397 1834415 398 772528 399 268536 400 75758 401 16910 402 2873 403 349 404 27 405 1 406 1 407 26 408 324 409 2584 410 14801 411 64600 412 222694 413 619212 414 1397913 415 2582910 416 3771014 417 3807044 418 5127003 419 10834752 420 16946498 421 19462184 422 18356871 423 14513674 424 9684972 425 5469520 426 2606943 427 1041064 428 344294 429 92668 430 19783 431 3222 432 376 433 28 434 1 435 1 436 27 437 350 438 2908 439 17385 440 79401 441 287294 442 841906 443 2017125 444 3980823 445 6353924 446 7578058 447 8934047 448 15961755 449 27781250 450 36408682 451 37819055 452 32870545 453 24198646 454 15154492 455 8076463 456 3648007 457 1385358 458 436962 459 112451 460 23005 461 3598 462 404 463 29 464 1 465 1 466 28 467 377 468 3258 469 20293 470 96786 471 366695 472 1129200 473 2859031 474 5997948 475 10334747 476 13931982 477 16512105 478 24895802 479 43743005 480 64189932 481 74227737 482 70689600 483 57069191 484 39353138 485 23230955 486 11724470 487 5033365 488 1822320 489 549413 490 135456 491 26603 492 4002 493 433 494 30 495 1 496 1 497 29 498 405 499 3635 500 23551 501 117079 502 463481 503 1495895 504 3988231 505 8856979 506 16332695 507 24266729 508 30444087 509 16512105 510 68638807 511 107932937 512 138417669 513 144917337 514 127758791 515 96422329 516 62584093 517 34955425 518 16757835 519 6855685 520 2371733 521 684869 522 162059 523 30605 524 4435 525 463 526 31 527 1 528 1 529 30 530 434 531 4040 532 27186 533 140630 534 580560 535 1959376 536 5484126 537 12845210 538 25189674 539 40599424 540 54710816 541 46956192 542 85150912 543 176571744 544 246350606 545 283335006 546 272676128 547 224181120 548 159006422 549 97539518 550 51713260 551 23613520 552 9227418 553 3056602 554 846928 555 192664 556 35040 557 4898 558 494 559 32 560 1 561 1 562 31 563 464 564 4474 565 31226 566 167816 567 721190 568 2539936 569 7443502 570 18329336 571 38034884 572 65789098 573 95310240 574 101667008 575 46956192 576 261722656 577 422922350 578 529685612 579 556011134 580 496857248 581 383187542 582 256545940 583 149252778 584 75326780 585 32840938 586 12284020 587 3903530 588 1039592 589 227704 590 39938 591 5392 592 526 593 33 594 1 595 1 596 32 597 495 598 4938 599 35700 600 199042 601 889006 602 3261126 603 9983438 604 25772838 605 56364220 606 103823982 607 161099338 608 196977248 609 148623200 610 308678848 611 684645006 612 952607962 613 1085696746 614 1052868382 615 880044790 616 639733482 617 405798718 618 224579558 619 108167718 620 45124958 621 16187550 622 4943122 623 1267296 624 267642 625 45330 626 5918 627 559 628 34 629 1 630 1 631 33 632 527 633 5433 634 40638 635 234742 636 1088048 637 4150132 638 13244564 639 35756276 640 82137058 641 160188202 642 264923320 643 358076586 644 345600448 645 457302048 646 993323854 647 1637252968 648 2038304708 649 2138565128 650 1932913172 651 1519778272 652 1045532200 653 630378276 654 332747276 655 153292676 656 61312508 657 21130672 658 6210418 659 1534938 660 312972 661 51248 662 6477 663 593 664 35 665 1 666 1 667 34 668 560 669 5960 670 46071 671 275380 672 1322790 673 5238180 674 17394696 675 49000840 676 117893334 677 242325260 678 425111522 679 622999906 680 703677034 681 802902496 682 1450625902 683 2630576822 684 3675557676 685 4176869836 686 4071478300 687 3452691444 688 2565310472 689 1675910476 690 963125552 691 486039952 692 214605184 693 82443180 694 27341090 695 7745356 696 1847910 697 364220 698 57725 699 7070 700 628 701 36 702 1 703 1 704 35 705 594 706 6520 707 52031 708 321451 709 1598170 710 6560970 711 22632876 712 66395536 713 166894174 714 360218594 715 667436782 716 1048111428 717 1326676940 718 1506579530 719 2253528398 720 4081202724 721 6306134498 722 7852427512 723 8248348136 724 7524169744 725 6018001916 726 4241220948 727 2639036028 728 1449165504 729 700645136 730 297048364 731 109784270 732 35086446 733 9593266 734 2212130 735 421945 736 64795 737 7698 738 664 739 37 740 1 741 1 742 36 743 629 744 7114 745 58551 746 373482 747 1919621 748 8159140 749 29193846 750 89028412 751 233289710 752 527112768 753 1027655376 754 1715548210 755 2374788368 756 2833256470 757 1506579530 758 6334731122 759 10387337222 760 14158562010 761 16100775648 762 15772517880 763 13542171660 764 10259222864 765 6880256976 766 4088201532 767 2149810640 768 997693500 769 406832634 770 144870716 771 44679712 772 11805396 773 2634075 774 486740 775 72493 776 8362 777 701 778 38 779 1 780 1 781 37 782 665 783 7743 784 65665 785 432033 786 2293103 787 10078761 788 37352986 789 118222258 790 322318122 791 760402478 792 1554768144 793 2743203586 794 4090336578 795 5208044838 796 4339836000 797 7841310652 798 16722068344 799 24545899232 800 30259337658 801 31873293528 802 29314689540 803 23801394524 804 17139479840 805 10968458508 806 6238012172 807 3147504140 808 1404526134 809 551703350 810 189550428 811 56485108 812 14439471 813 3120815 814 559233 815 80855 816 9063 817 739 818 39 819 1 820 1 821 38 822 702 823 8408 824 73408 825 497698 826 2725136 827 12371864 828 47431747 829 155575244 830 440540380 831 1082720600 832 2315170622 833 4297971730 834 6833540164 835 9298381416 836 9547880838 837 4339836000 838 24563378996 839 41267967576 840 54805236890 841 62132631186 842 61187983068 843 53116084064 844 40940874364 845 28107938348 846 17206470680 847 9385516312 848 4552030274 849 1956229484 850 741253778 851 246035536 852 70924579 853 17560286 854 3680048 855 640088 856 89918 857 9802 858 778 859 40 860 1 861 1 862 39 863 740 864 9110 865 81816 866 571106 867 3222834 868 15097000 869 59803611 870 203006991 871 596115624 872 1523260980 873 3397891222 874 6613142352 875 11131511894 876 16131921580 877 18846262254 878 13887716838 879 28903214996 880 65831346572 881 96073204466 882 116937868076 883 123320614254 884 114304067132 885 94056958428 886 69048812712 887 45314409028 888 26591986992 889 13937546586 890 6508259758 891 2697483262 892 987289314 893 316960115 894 88484865 895 21240334 896 4320136 897 730006 898 99720 899 10580 900 818 901 41 902 1 903 1 904 40 905 779 906 9850 907 90926 908 652922 909 3793940 910 18319834 911 74900611 912 262810602 913 799122615 914 2119376604 915 4921152202 916 10011033574 917 17744654246 918 27263433474 919 34978183834 920 32733979092 921 42790931834 922 94734561568 923 161904551038 924 213011072542 925 240258482330 926 237624681386 927 208361025560 928 163105771140 929 114363221740 930 71906396020 931 40529533578 932 20445806344 933 9205743020 934 3684772576 935 1304249429 936 405444980 937 109725199 938 25560470 939 5050142 940 829726 941 110300 942 11398 943 859 944 42 945 1 946 1 947 41 948 819 949 10629 950 100776 951 743848 952 4446862 953 22113774 954 93220445 955 337711213 956 1061933217 957 2918499219 958 7040528806 959 14932185776 960 27755687820 961 45008087720 962 62241617308 963 67712162926 964 75524910926 965 137525493402 966 256639112606 967 374915623580 968 453269554872 969 477883163716 970 445985706946 971 371466796700 972 277468992880 973 186269617760 974 112435929598 975 60975339922 976 29651549364 977 12890515596 978 4989022005 979 1709694409 980 515170179 981 135285669 982 30610612 983 5879868 984 940026 985 121698 986 12257 987 901 988 43 989 1 990 1 991 42 992 860 993 11448 994 111405 995 844624 996 5190710 997 26560636 998 115334219 999 430931658 1000 1399644430 1001 3980432436 1002 9959028025 1003 21972714582 1004 42687873596 1005 72763775540 1006 107249705028 1007 129953780234 1008 143237073852 1009 213050404328 1010 394164606008 1011 631554736186 1012 828185178452 1013 931152718588 1014 923868870662 1015 817452503646 1016 648935789580 1017 463738610640 1018 298705547358 1019 173411269520 1020 90626889286 1021 42542064960 1022 17879537601 1023 6698716414 1024 2224864588 1025 650455848 1026 165896281 1027 36490480 1028 6819894 1029 1061724 1030 133955 1031 13158 1032 944 1033 44 1034 1 1035 1 1036 43 1037 902 1038 12308 1039 122853 1040 956029 1041 6035334 1042 31751346 1043 141894855 1044 546265877 1045 1830576088 1046 5380076866 1047 13939460461 1048 31931742607 1049 64660588178 1050 115451649136 1051 180013480568 1052 237203485262 1053 273190854086 1054 143237073852 1055 607215010336 1056 1025719342194 1057 1459739914638 1058 1759337897040 1059 1855021589250 1060 1741321374308 1061 1466388293226 1062 1112674400220 1063 762444157998 1064 472116816878 1065 264038158806 1066 133168954246 1067 60421602561 1068 24578254015 1069 8923581002 1070 2875320436 1071 816352129 1072 202386761 1073 43310374 1074 7881618 1075 1195679 1076 147113 1077 14102 1078 988 1079 45 1080 1 1081 1 1082 44 1083 945 1084 13210 1085 135161 1086 1078882 1087 6991363 1088 37786680 1089 173646201 1090 688160732 1091 2376841965 1092 7210652954 1093 19319537327 1094 45871203068 1095 96592330785 1096 180112237314 1097 295465129704 1098 417216965830 1099 510394339348 1100 416427927938 1101 750452084188 1102 1632934352530 1103 2485459256832 1104 3219077811678 1105 3614359486290 1106 3596342963558 1107 3207709667534 1108 2579062693446 1109 1875118558218 1110 1234560974876 1111 736154975684 1112 397207113052 1113 193590556807 1114 84999856576 1115 33501835017 1116 11798901438 1117 3691672565 1118 1018738890 1119 245697135 1120 51191992 1121 9077297 1122 1342792 1123 161215 1124 15090 1125 1033 1126 46 1127 1 1128 1 1129 45 1130 989 1131 14155 1132 148371 1133 1214043 1134 8070245 1135 44778043 1136 211432881 1137 861806933 1138 3065002697 1139 9587494919 1140 26530190281 1141 65190740395 1142 142463533853 1143 276704568099 1144 475577367018 1145 712682095534 1146 927611305178 1147 926822267286 1148 416427927938 1149 2383386436718 1150 4118393609362 1151 5704537068510 1152 6833437297968 1153 7210702449848 1154 6804052631092 1155 5786772360980 1156 4454181251664 1157 3109679533094 1158 1970715950560 1159 1133362088736 1160 590797669859 1161 278590413383 1162 118501691593 1163 45300736455 1164 15490574003 1165 4710411455 1166 1264436025 1167 296889127 1168 60269289 1169 10420089 1170 1504007 1171 176305 1172 16123 1173 1079 1174 47 1175 1 1176 1 1177 46 1178 1034 1179 15144 1180 162526 1181 1362414 1182 9284288 1183 52848288 1184 256210924 1185 1073239814 1186 3926809630 1187 12652497616 1188 36117685200 1189 91720930676 1190 207654274248 1191 419168101952 1192 752281935117 1193 1188259462552 1194 1640293400712 1195 1854433572464 1196 1343250195224 1197 2799814364656 1198 6501780046080 1199 9822930677872 1200 12537974366478 1201 14044139747816 1202 14014755080940 1203 12590824992072 1204 10240953612644 1205 7563860784758 1206 5080395483654 1207 3104078039296 1208 1724159758595 1209 869388083242 1210 397092104976 1211 163802428048 1212 60791310458 1213 20200985458 1214 5974847480 1215 1561325152 1216 357158416 1217 70689378 1218 11924096 1219 1680312 1220 192428 1221 17202 1222 1126 1223 48 1224 1 1225 1 1226 47 1227 1080 1228 16178 1229 177670 1230 1524940 1231 10646702 1232 62132576 1233 309059212 1234 1329450738 1235 5000049444 1236 16579307246 1237 48770182816 1238 127838615876 1239 299375204924 1240 626822376200 1241 1171450037069 1242 1940541397669 1243 2828552863264 1244 3494726973176 1245 3197683767688 1246 4143064559880 1247 9301594410736 1248 16324710723952 1249 22360905044350 1250 26582114114294 1251 28058894828756 1252 26605580073012 1253 22831778604716 1254 17804814397402 1255 12644256268412 1256 8184473522950 1257 4828237797891 1258 2593547841837 1259 1266480188218 1260 560894533024 1261 224593738506 1262 80992295916 1263 26175832938 1264 7536172632 1265 1918483568 1266 427847794 1267 82613474 1268 13604408 1269 1872740 1270 209630 1271 18328 1272 1174 1273 49 1274 1 1275 1 1276 48 1277 1127 1278 17258 1279 193848 1280 1702610 1281 12171642 1282 72779278 1283 371191788 1284 1638509950 1285 6329500182 1286 21579356690 1287 65349490062 1288 176608798692 1289 427213820800 1290 926197581124 1291 1798272413269 1292 3111991434738 1293 4769094260933 1294 6323279836440 1295 6692410740864 1296 7340748327568 1297 13444658970616 1298 25626305134688 1299 38685615768302 1300 48943019158644 1301 54641008943050 1302 54664474901768 1303 49437358677728 1304 40636593002118 1305 30449070665814 1306 20828729791362 1307 13012711320841 1308 7421785639728 1309 3860028030055 1310 1827374721242 1311 785488271530 1312 305586034422 1313 107168128854 1314 33712005570 1315 9454656200 1316 2346331362 1317 510461268 1318 96217882 1319 15477148 1320 2082370 1321 227958 1322 19502 1323 1223 1324 50 1325 1