0 1 1 1 2 1 3 1 4 3 5 1 6 1 7 5 8 5 9 1 10 1 11 7 12 14 13 7 14 1 15 1 16 9 17 27 18 27 19 9 20 1 21 1 22 11 23 44 24 72 25 44 26 11 27 1 28 1 29 13 30 65 31 149 32 149 33 65 34 13 35 1 36 1 37 15 38 90 39 266 40 388 41 266 42 90 43 15 44 1 45 1 46 17 47 119 48 431 49 836 50 836 51 431 52 119 53 17 54 1 55 1 56 19 57 152 58 652 59 1585 60 2150 61 1585 62 652 63 152 64 19 65 1 66 1 67 21 68 189 69 937 70 2743 71 4753 72 4753 73 2743 74 937 75 189 76 21 77 1 78 1 79 23 80 230 81 1294 82 4434 83 9399 84 12134 85 9399 86 4434 87 1294 88 230 89 23 90 1 91 1 92 25 93 275 94 1731 95 6798 96 17082 97 27304 98 27304 99 17082 100 6798 101 1731 102 275 103 25 104 1 105 1 106 27 107 324 108 2256 109 9991 110 29068 111 55688 112 69370 113 55688 114 29068 115 9991 116 2256 117 324 118 27 119 1 120 1 121 29 122 377 123 2877 124 14185 125 46927 126 105087 127 158133 128 158133 129 105087 130 46927 131 14185 132 2877 133 377 134 29 135 1 136 1 137 31 138 434 139 3602 140 19568 141 72565 142 186270 143 330210 144 400398 145 330210 146 186270 147 72565 148 19568 149 3602 150 434 151 31 152 1 153 1 154 33 155 495 156 4439 157 26344 158 108256 159 313630 160 641898 161 921816 162 921816 163 641898 164 313630 165 108256 166 26344 167 4439 168 495 169 33 170 1 171 1 172 35 173 560 174 5396 175 34733 176 156674 177 505904 178 1176054 179 1960914 180 2328162 181 1960914 182 1176054 183 505904 184 156674 185 34733 186 5396 187 560 188 35 189 1 190 1 191 37 192 629 193 6481 194 44971 195 220925 196 786957 197 2050383 198 3904284 199 5402100 200 5402100 201 3904284 202 2050383 203 786957 204 220925 205 44971 206 6481 207 629 208 37 209 1 210 1 211 39 212 702 213 7702 214 57310 215 304579 216 1186630 217 3427262 218 7351247 219 11664498 220 13616892 221 11664498 222 7351247 223 3427262 224 1186630 225 304579 226 57310 227 7702 228 702 229 39 230 1 231 1 232 41 233 779 234 9067 235 72018 236 411702 237 1741652 238 5525228 239 13197317 240 23687345 241 31796514 242 31796514 243 23687345 244 13197317 245 5525228 246 1741652 247 411702 248 72018 249 9067 250 779 251 41 252 1 253 1 254 43 255 860 256 10584 257 89379 258 546888 259 2496616 260 8632258 261 22739729 262 45632489 263 69506471 264 80022612 265 69506471 266 45632489 267 22739729 268 8632258 269 2496616 270 546888 271 89379 272 10584 273 860 274 43 275 1 276 1 277 45 278 945 279 12261 280 109693 281 715291 282 3505019 283 13120969 284 37808551 285 83988343 286 143497905 287 187840721 288 187840721 289 143497905 290 83988343 291 37808551 292 13120969 293 3505019 294 715291 295 109693 296 12261 297 945 298 45 299 1 300 1 301 47 302 1034 303 14106 304 133276 305 922657 306 4830366 307 19465866 308 60927156 309 148553807 310 281866564 311 414867709 312 472133638 313 414867709 314 281866564 315 148553807 316 60927156 317 19465866 318 4830366 319 922657 320 133276 321 14106 322 1034 323 47 324 1 325 1 326 49 327 1127 328 16127 329 160460 330 1175356 331 6547338 332 28262766 333 95506086 334 253726078 335 530024839 336 868591123 337 1113153706 338 1113153706 339 868591123 340 530024839 341 253726078 342 95506086 343 28262766 344 6547338 345 1175356 346 160460 347 16127 348 1127 349 49 350 1 351 1 352 51 353 1224 354 18332 355 191593 356 1480414 357 8743024 358 40250526 359 146074596 360 420156956 361 959061637 362 1734862842 363 2480141621 364 2794893246 365 2480141621 366 1734862842 367 959061637 368 420156956 369 146074596 370 40250526 371 8743024 372 1480414 373 191593 374 18332 375 1224 376 51 377 1 378 1 379 53 380 1325 381 20729 382 227039 383 1845545 384 11518217 385 56335203 386 218554422 387 676850702 388 1677189786 389 3323553786 390 5255452436 391 6614340932 392 6614340932 393 5255452436 394 3323553786 395 1677189786 396 676850702 397 218554422 398 56335203 399 11518217 400 1845545 401 227039 402 20729 403 1325 404 53 405 1 406 1 407 55 408 1430 409 23326 410 267178 411 2279183 412 14988774 413 77616774 414 320580573 415 1063785464 416 2845122236 417 6135115929 418 10650115944 419 14848331781 420 16592160944 421 14848331781 422 10650115944 423 6135115929 424 2845122236 425 1063785464 426 320580573 427 77616774 428 14988774 429 2279183 430 267178 431 23326 432 1430 433 55 434 1 435 1 436 57 437 1539 438 26131 439 312406 440 2790514 441 19287040 442 105418544 443 461874203 444 1635149759 445 4696377552 446 10955399144 447 20738414966 448 31794348134 449 39394139722 450 39394139722 451 31794348134 452 20738414966 453 10955399144 454 4696377552 455 1635149759 456 461874203 457 105418544 458 19287040 459 2790514 460 312406 461 26131 462 1539 463 57 464 1 465 1 466 59 467 1652 468 29152 469 363135 470 3389508 471 24563336 472 141319370 473 654672875 474 2463295483 475 7563693115 476 18987980680 477 38963302396 478 65253988766 479 89015358050 480 98743919468 481 89015358050 482 65253988766 483 38963302396 484 18987980680 485 7563693115 486 2463295483 487 654672875 488 141319370 489 24563336 490 3389508 491 363135 492 29152 493 1652 494 59 495 1 496 1 497 61 498 1769 499 32397 500 419793 501 4086951 502 30987511 503 187188829 504 914223785 505 3643519417 506 11912922079 507 32035521199 508 70881843199 509 128908889221 510 192359595359 511 235107064237 512 235107064237 513 192359595359 514 128908889221 515 70881843199 516 32035521199 517 11912922079 518 3643519417 519 914223785 520 187188829 521 30987511 522 4086951 523 419793 524 32397 525 1769 526 61 527 1 528 1 529 63 530 1890 531 35874 532 482824 533 4894477 534 38750558 535 245225458 536 1259345770 537 5299796205 538 18386008500 539 52744302197 540 125241549062 541 246023523102 542 399243699012 543 534308887840 544 588913687966 545 534308887840 546 399243699012 547 246023523102 548 125241549062 549 52744302197 550 18386008500 551 5299796205 552 1259345770 553 245225458 554 38750558 555 4894477 556 482824 557 35874 558 1890 559 63 560 1 561 1 562 65 563 2015 564 39591 565 552688 566 5824600 567 48066294 568 317998194 569 1713066180 570 7591597300 571 27854875181 572 84929166257 573 215505219862 574 455077475486 575 798867709394 576 1164002430754 577 1405677426762 578 1405677426762 579 1164002430754 580 798867709394 581 455077475486 582 215505219862 583 84929166257 584 27854875181 585 7591597300 586 1713066180 587 317998194 588 48066294 589 5824600 590 552688 591 39591 592 2015 593 65 594 1 595 1 596 67 597 2144 598 43556 599 629861 600 6890746 601 59173104 602 408491142 603 2303338950 604 10721942406 605 41488321689 606 133999616942 607 361974547235 608 818148429074 609 1546201498664 610 2440089053592 611 3210830973600 612 3518968100982 613 3210830973600 614 2440089053592 615 1546201498664 616 818148429074 617 361974547235 618 133999616942 619 41488321689 620 10721942406 621 2303338950 622 408491142 623 59173104 624 6890746 625 629861 626 43556 627 2144 628 67 629 1 630 1 631 69 632 2277 633 47777 634 714835 635 8107285 636 72335749 637 520151799 638 3063850464 639 14946842488 640 60834316720 641 207511884288 642 594702185994 643 1433147564774 644 2903239806546 645 4938758748930 646 7045372301848 647 8417931352300 648 8417931352300 649 7045372301848 650 4938758748930 651 2903239806546 652 1433147564774 653 594702185994 654 207511884288 655 60834316720 656 14946842488 657 3063850464 658 520151799 659 72335749 660 8107285 661 714835 662 47777 663 2277 664 69 665 1 666 1 667 71 668 2414 669 52262 670 808118 671 9489563 672 87847238 673 656942862 674 4034920059 675 20586306478 676 87920380540 677 315876371905 678 957429262728 679 2451364459119 680 5302101534120 681 9680456367924 682 14901439017814 683 19315285743832 684 21062444053040 685 19315285743832 686 14901439017814 687 9680456367924 688 5302101534120 689 2451364459119 690 957429262728 691 315876371905 692 87920380540 693 20586306478 694 4034920059 695 656942862 696 87847238 697 9489563 698 808118 699 52262 700 2414 701 71 702 1 703 1 704 73 705 2555 706 57019 707 910234 708 11053934 709 106030764 710 823397748 711 5264502273 712 28037097373 713 125375090638 714 473255121790 715 1512841464578 716 4102223929658 717 9439638146478 718 18424687587398 719 30473122331342 720 42656549338150 721 50483793426890 722 50483793426890 723 42656549338150 724 30473122331342 725 18424687587398 726 9439638146478 727 4102223929658 728 1512841464578 729 473255121790 730 125375090638 731 28037097373 732 5264502273 733 823397748 734 106030764 735 11053934 736 910234 737 57019 738 2555 739 73 740 1 741 1 742 75 743 2700 744 62056 745 1021723 746 12817792 747 127241704 748 1024679954 749 6809298197 750 37787437501 751 176574108015 752 698689814300 753 2349503129170 754 6727709849410 755 16416741243606 756 34132141430796 757 60416724099112 758 90948418654342 759 116307610598556 760 126256612255260 761 116307610598556 762 90948418654342 763 60416724099112 764 34132141430796 765 16416741243606 766 6727709849410 767 2349503129170 768 698689814300 769 176574108015 770 37787437501 771 6809298197 772 1024679954 773 127241704 774 12817792 775 1021723 776 62056 777 2700 778 75 779 1 780 1 781 77 782 2849 783 67381 784 1143141 785 14799603 786 151869683 787 1266646385 788 8735983547 789 50433877323 790 245814513725 791 1017507416573 792 3590906434605 793 10829590273103 794 27940105230485 795 61674692974119 796 116415682802660 797 187729492030400 798 258352403167552 799 303154079910724 800 303154079910724 801 258352403167552 802 187729492030400 803 116415682802660 804 61674692974119 805 27940105230485 806 10829590273103 807 3590906434605 808 1017507416573 809 245814513725 810 50433877323 811 8735983547 812 1266646385 813 151869683 814 14799603 815 1143141 816 67381 817 2849 818 77 819 1 820 1 821 79 822 3002 823 73002 824 1275060 825 17018937 826 180340702 827 1555914778 828 11122561328 829 66700557243 830 338521666404 831 1463057958317 832 5407163267350 833 17133406379680 834 46610049808172 835 108906418615680 836 218490332904495 837 376080813112544 838 554849060837144 839 700981361510348 840 757853797478188 841 700981361510348 842 554849060837144 843 376080813112544 844 218490332904495 845 108906418615680 846 46610049808172 847 17133406379680 848 5407163267350 849 1463057958317 850 338521666404 851 66700557243 852 11122561328 853 1555914778 854 180340702 855 17018937 856 1275060 857 73002 858 3002 859 79 860 1 861 1 862 81 863 3159 864 78927 865 1418068 866 19496500 867 213119330 868 1899935350 869 14059847218 870 87461107514 871 461493242595 872 2078847106655 873 8029972136498 874 26674189572770 875 76325423755478 876 188252227791806 877 400197254794011 878 732853646092451 879 1155023715257034 880 1565279199429698 881 1822579095956168 882 1822579095956168 883 1565279199429698 884 1155023715257034 885 732853646092451 886 400197254794011 887 188252227791806 888 76325423755478 889 26674189572770 890 8029972136498 891 2078847106655 892 461493242595 893 87461107514 894 14059847218 895 1899935350 896 213119330 897 19496500 898 1418068 899 78927 900 3159 901 81 902 1 903 1 904 83 905 3320 906 85164 907 1572769 908 22254166 909 250710960 910 2307066798 911 17653096056 912 113763447456 913 623185603725 914 2921135291010 915 11771613229489 916 40910074392790 917 122845929379900 918 319028055660040 919 716647521612573 920 1391941190918673 921 2335893812741513 922 3383919141163068 923 4228314535328286 924 4554557627047264 925 4228314535328286 926 3383919141163068 927 2335893812741513 928 1391941190918673 929 716647521612573 930 319028055660040 931 122845929379900 932 40910074392790 933 11771613229489 934 2921135291010 935 623185603725 936 113763447456 937 17653096056 938 2307066798 939 250710960 940 22254166 941 1572769 942 85164 943 3320 944 83 945 1 946 1 947 85 948 3485 949 91721 950 1739783 951 25315009 952 293664129 953 2786656779 954 22023778074 955 146857761842 956 834048147638 957 4062085156278 958 17048863109088 959 61871410669608 960 194563813271200 961 530781376363044 962 1256663564432373 963 2581586470599093 964 4598971149828049 965 7098930510468961 966 9486961653003258 967 10969195195299350 968 10969195195299350 969 9486961653003258 970 7098930510468961 971 4598971149828049 972 2581586470599093 973 1256663564432373 974 530781376363044 975 194563813271200 976 61871410669608 977 17048863109088 978 4062085156278 979 834048147638 980 146857761842 981 22023778074 982 2786656779 983 293664129 984 25315009 985 1739783 986 91721 987 3485 988 85 989 1 990 1 991 87 992 3654 993 98606 994 1919746 995 28703335 996 342572902 997 3349126998 998 27311513769 999 188227949460 1000 1106911849660 1001 5593550161257 1002 24412878498136 1003 92354680994521 1004 303551211017120 1005 868037435065796 1006 2160923400568213 1007 4683095595670795 1008 8831389101378026 1009 14481811924430551 1010 20633427531111623 1011 25524927623573314 1012 27402347452780892 1013 25524927623573314 1014 20633427531111623 1015 14481811924430551 1016 8831389101378026 1017 4683095595670795 1018 2160923400568213 1019 868037435065796 1020 303551211017120 1021 92354680994521 1022 24412878498136 1023 5593550161257 1024 1106911849660 1025 188227949460 1026 27311513769 1027 3349126998 1028 342572902 1029 28703335 1030 1919746 1031 98606 1032 3654 1033 87 1034 1 1035 1 1036 89 1037 3827 1038 105827 1039 2113310 1040 32444714 1041 398079320 1042 4006063032 1043 33676176567 1044 239626856523 1045 1457438779292 1046 7631609255012 1047 34586278077214 1048 136172537190334 1049 466967025728578 1050 1396960268852626 1051 3648649603320157 1052 8321670547831141 1053 16569068925715761 1054 28783308321804489 1055 43593287522575515 1056 57520044784200099 1057 66082793304577356 1058 66082793304577356 1059 57520044784200099 1060 43593287522575515 1061 28783308321804489 1062 16569068925715761 1063 8321670547831141 1064 3648649603320157 1065 1396960268852626 1066 466967025728578 1067 136172537190334 1068 34586278077214 1069 7631609255012 1070 1457438779292 1071 239626856523 1072 33676176567 1073 4006063032 1074 398079320 1075 32444714 1076 2113310 1077 105827 1078 3827 1079 89 1080 1 1081 1 1082 91 1083 4004 1084 113392 1085 2321143 1086 36566012 1087 460875912 1088 4770309018 1089 41300172687 1090 303115625775 1091 1904639994819 1092 10321965824144 1093 48508854350824 1094 198473623998454 1095 708928651129258 1096 2214594492674636 1097 6056339552670131 1098 14504722011492307 1099 30418680629857026 1100 55834597829849160 1101 89642318032944096 1102 125794295205526641 1103 154196536487621475 1104 165031891124117796 1105 154196536487621475 1106 125794295205526641 1107 89642318032944096 1108 55834597829849160 1109 30418680629857026 1110 14504722011492307 1111 6056339552670131 1112 2214594492674636 1113 708928651129258 1114 198473623998454 1115 48508854350824 1116 10321965824144 1117 1904639994819 1118 303115625775 1119 41300172687 1120 4770309018 1121 460875912 1122 36566012 1123 2321143 1124 113392 1125 4004 1126 91 1127 1 1128 1 1129 93 1130 4185 1131 121309 1132 2543929 1133 41095423 1134 531708271 1135 5656067333 1136 50390907869 1137 381107510829 1138 2471469870411 1139 13846343578427 1140 67393576674075 1141 286148605844313 1142 1062979790015723 1143 3461551303249409 1144 9893265936967103 1145 24829399935168743 1146 54722724740772607 1147 105876931614088887 1148 179730331480593657 1149 267507948828079593 1150 348872566106863377 1151 398466739144539777 1152 398466739144539777 1153 348872566106863377 1154 267507948828079593 1155 179730331480593657 1156 105876931614088887 1157 54722724740772607 1158 24829399935168743 1159 9893265936967103 1160 3461551303249409 1161 1062979790015723 1162 286148605844313 1163 67393576674075 1164 13846343578427 1165 2471469870411 1166 381107510829 1167 50390907869 1168 5656067333 1169 531708271 1170 41095423 1171 2543929 1172 121309 1173 4185 1174 93 1175 1 1176 1 1177 95 1178 4370 1179 129586 1180 2782368 1181 46062501 1182 611377694 1183 6679003394 1184 61183450886 1185 476416524473 1186 3185505599700 1187 18430027802661 1188 92794803866486 1189 408342003887810 1190 1575316828589396 1191 5339248832604736 1192 15920078930984580 1193 41789735105303325 1194 96591248547774666 1195 196546278141028644 1196 351924081506860614 1197 554146320530181438 1198 766855773039220638 1199 932129540137868649 1200 994831673928160434 1201 932129540137868649 1202 766855773039220638 1203 554146320530181438 1204 351924081506860614 1205 196546278141028644 1206 96591248547774666 1207 41789735105303325 1208 15920078930984580 1209 5339248832604736 1210 1575316828589396 1211 408342003887810 1212 92794803866486 1213 18430027802661 1214 3185505599700 1215 476416524473 1216 61183450886 1217 6679003394 1218 611377694 1219 46062501 1220 2782368 1221 129586 1222 4370 1223 95 1224 1 1225 1 1226 97 1227 4559 1228 138231 1229 3037176 1230 51498192 1231 700743886 1232 7856355706 1233 73943404016 1234 592311309392 1235 4079721347369 1236 24350717522589 1237 126690913007038 1238 577093140927478 1239 2308973565816554 1240 8133122966097866 1241 25258907226284240 1242 69225411864877344 1243 167478721959253039 1244 357659573528999191 1245 673970944416360846 1246 1120054149135436110 1247 1640581377987090525 1248 2116739613697667925 1249 2404666264743369366 1250 2404666264743369366 1251 2116739613697667925 1252 1640581377987090525 1253 1120054149135436110 1254 673970944416360846 1255 357659573528999191 1256 167478721959253039 1257 69225411864877344 1258 25258907226284240 1259 8133122966097866 1260 2308973565816554 1261 577093140927478 1262 126690913007038 1263 24350717522589 1264 4079721347369 1265 592311309392 1266 73943404016 1267 7856355706 1268 700743886 1269 51498192 1270 3037176 1271 138231 1272 4559 1273 97 1274 1 1275 1 1276 99 1277 4752 1278 147252 1279 3309085 1280 57434866 1281 800727728 1282 9207051286 1283 88969990906 1284 732574639978 1285 5193367287009 1286 31948872688118 1287 171583872686111 1288 808133741414986 1289 3349208532001264 1290 12243601793233176 1291 39545996764326446 1292 112969659712914232 1293 285560938162601187 1294 638768667907860212 1295 1264123417872555831 1296 2212265993470835640 1297 3421689887874216261 1298 4674652022828256756 1299 5638325653465371435 1300 6002062399053980046 1301 5638325653465371435 1302 4674652022828256756 1303 3421689887874216261 1304 2212265993470835640 1305 1264123417872555831 1306 638768667907860212 1307 285560938162601187 1308 112969659712914232 1309 39545996764326446 1310 12243601793233176 1311 3349208532001264 1312 808133741414986 1313 171583872686111 1314 31948872688118 1315 5193367287009 1316 732574639978 1317 88969990906 1318 9207051286 1319 800727728 1320 57434866 1321 3309085 1322 147252 1323 4752 1324 99 1325 1