1 1 2 3 3 2 4 7 5 5 6 4 7 16 8 12 9 10 10 6 11 37 12 28 13 23 14 14 15 8 16 84 17 64 18 53 19 32 20 19 21 9 22 191 23 146 24 121 25 73 26 44 27 21 28 11 29 434 30 332 31 275 32 166 33 100 34 48 35 25 36 13 37 985 38 753 39 624 40 377 41 227 42 109 43 57 44 30 45 15 46 2234 47 1708 48 1416 49 856 50 515 51 248 52 130 53 69 54 35 55 17 56 5067 57 3874 58 3212 59 1942 60 1168 61 563 62 295 63 157 64 80 65 39 66 18 67 11492 68 8787 69 7285 70 4405 71 2649 72 1277 73 670 74 357 75 182 76 89 77 41 78 20 79 26064 80 19929 81 16523 82 9991 83 6008 84 2897 85 1520 86 810 87 413 88 202 89 93 90 46 91 22 92 59112 93 45198 94 37474 95 22660 96 13626 97 6571 98 3448 99 1838 100 937 101 459 102 211 103 105 104 50 105 24 106 134064 107 102507 108 84990 109 51392 110 30904 111 14903 112 7820 113 4169 114 2126 115 1041 116 479 117 239 118 114 119 55 120 26 121 304051 122 232481 123 192754 124 116555 125 70089 126 33800 127 17736 128 9456 129 4822 130 2361 131 1087 132 543 133 259 134 125 135 59 136 27 137 689573 138 527256 139 437157 140 264341 141 158959 142 76657 143 40225 144 21446 145 10937 146 5355 147 2466 148 1232 149 588 150 284 151 134 152 62 153 29 154 1563917 155 1195790 156 991450 157 599512 158 360511 159 173855 160 91229 161 48639 162 24805 163 12145 164 5593 165 2795 166 1334 167 645 168 304 169 141 170 66 171 31 172 3546885 173 2711991 174 2248559 175 1359663 176 817621 177 394295 178 206903 179 110311 180 56257 181 27545 182 12685 183 6339 184 3026 185 1463 186 690 187 320 188 150 189 71 190 33 191 8044155 192 6150658 193 5099618 194 3083647 195 1854323 196 894242 197 469246 198 250180 199 127589 200 62471 201 28769 202 14377 203 6863 204 3319 205 1565 206 726 207 341 208 162 209 75 210 34 211 18243735 212 13949380 213 11565675 214 6993555 215 4205511 216 2028096 217 1064227 218 567396 219 289366 220 141682 221 65247 222 32607 223 15565 224 7528 225 3550 226 1647 227 774 228 368 229 171 230 78 231 36 232 41375865 233 31636486 234 26230364 235 15861028 236 9537886 237 4599619 238 2413613 239 1286826 240 656268 241 321328 242 147977 243 73952 244 35301 245 17074 246 8052 247 3736 248 1756 249 835 250 388 251 177 252 82 253 38 254 93838360 255 71749943 256 59489133 257 35972006 258 21631441 259 10431703 260 5473952 261 2918456 262 1488383 263 728756 264 335605 265 167720 266 80061 267 38723 268 18262 269 8474 270 3983 271 1894 272 880 273 402 274 186 275 87 276 40 277 212820633 278 162725226 279 134918332 280 81582682 281 49059010 282 23658573 283 12414646 284 6618910 285 3375578 286 1652782 287 761136 288 380381 289 181575 290 87822 291 41418 292 19219 293 9034 294 4296 295 1996 296 912 297 422 298 198 299 91 300 42 301 482666383 302 369052545 303 305987923 304 185025378 305 111263343 306 53656442 307 28155787 308 15011352 309 7655640 310 3748426 311 1726218 312 862685 313 411803 314 199176 315 93934 316 43588 317 20489 318 9744 319 4527 320 2069 321 958 322 450 323 207 324 96 325 43 326 1094662834 327 836992422 328 693965063 329 419628157 330 252339609 331 121690085 332 63855895 333 34044984 334 17362603 335 8501240 336 3914975 337 1956526 338 933949 339 451722 340 213038 341 98856 342 46469 343 22099 344 10268 345 4693 346 2173 347 1021 348 470 349 218 350 98 351 45 352 2482639691 353 1898256288 354 1573877505 355 951695340 356 572293413 357 275986931 358 144821926 359 77212294 360 39377502 361 19280381 362 8878965 363 4437302 364 2118149 365 1024483 366 483160 367 224201 368 105390 369 50120 370 23288 371 10644 372 4929 373 2316 374 1066 375 495 376 223 377 103 378 47 379 5630500683 380 4305148816 381 3569474217 382 2158396678 383 1297932384 384 625924338 385 328448771 386 175113560 387 89306174 388 43726925 389 20137042 390 10063576 391 4803855 392 2323476 393 1095783 394 508477 395 239020 396 113670 397 52817 398 24141 399 11179 400 5253 401 2418 402 1123 403 506 404 234 405 107 406 49 407 12769689477 408 9763858781 409 8095386168 410 4895134003 411 2943644703 412 1419564597 413 744905125 414 397148657 415 202541866 416 99170445 417 45669789 418 22823680 419 10894900 420 5269526 421 2485181 422 1153201 423 542086 424 257798 425 119787 426 54751 427 25354 428 11914 429 5484 430 2547 431 1148 432 531 433 243 434 112 435 51 436 28961006937 437 22143935638 438 18359924523 439 11101915209 440 6676036627 441 3219500382 442 1689406977 443 900712976 444 459354662 445 224913531 446 103576762 447 51762947 448 24709080 449 11951018 450 5636265 451 2615402 452 1229424 453 584673 454 271671 455 124173 456 57502 457 27021 458 12438 459 5777 460 2604 461 1205 462 552 463 255 464 116 465 52 466 65682092295 467 50221320948 468 41639375996 469 25178579633 470 15140911877 471 7301663292 472 3831489190 473 2042771267 474 1041793035 475 510092461 476 234906834 477 117395734 478 56038939 479 27104302 480 12782763 481 5931599 482 2788272 483 1326009 484 616137 485 281619 486 130412 487 61283 488 28209 489 13102 490 5906 491 2733 492 1252 493 579 494 264 495 118 496 54 497 148963648178 498 113899404287 499 94435989164 500 57103739346 501 34338818865 502 16559801367 503 8689622815 504 4632901446 505 2362733673 506 1156863785 507 532756765 508 266247561 509 127093467 510 61471180 511 28990658 512 13452566 513 6323660 514 3007322 515 1397368 516 638698 517 295768 518 138987 519 63977 520 29715 521 13395 522 6199 523 2840 524 1314 525 599 526 268 527 123 528 56 529 337841985587 530 258318061972 531 214176025361 532 129508379535 533 77878696514 534 37556788138 535 19707623046 536 10507185094 537 5358559926 538 2623708287 539 1208265275 540 603835941 541 288241526 542 139413514 543 65749340 544 30509737 545 14341740 546 6820454 547 3169160 548 1448535 549 670787 550 315216 551 145097 552 67393 553 30380 554 14060 555 6441 556 2981 557 1359 558 608 559 279 560 128 561 58 562 766208458382 563 585852240040 564 485740343756 565 293718424780 566 176624926867 567 85176887328 568 44695887772 569 23829761949 570 12152941657 571 5950437091 572 2740284255 573 1369469235 574 653717137 575 316182767 576 149116163 577 69194534 578 32526338 579 15468444 580 7187494 581 3285204 582 1521311 583 714894 584 329073 585 152844 586 68901 587 31888 588 14608 589 6761 590 3083 591 1379 592 633 593 291 594 132 595 60 596 1737721854422 597 1328683114683 598 1101634420353 599 666138464282 600 400576360252 601 193176852830 602 101368002578 603 54044689369 604 27562254217 605 13495288996 606 6214825464 607 3105886646 608 1482597253 609 717086452 610 338187882 611 156929688 612 73768082 613 35081646 614 16300872 615 7450676 616 3450257 617 1621344 618 746321 619 346643 620 156264 621 72321 622 33131 623 15334 624 6993 625 3128 626 1436 627 660 628 300 629 137 630 61 631 3941064876407 632 3013385796943 633 2498450893994 634 1510768192116 635 908486832741 636 438115287373 637 229897479586 638 122570609610 639 62509792194 640 30606629781 641 14094908393 642 7043993111 643 3362455243 644 1626315640 645 766992934 646 355908560 647 167302262 648 79563391 649 36969550 650 16897755 651 7825008 652 3677126 653 1692619 654 786169 655 354399 656 164021 657 75140 658 34777 659 15860 660 7095 661 3257 662 1497 663 681 664 311 665 139 666 63 667 8938134903766 668 6834205884661 669 5666359687363 670 3426345501261 671 2060401978650 672 993623212190 673 521395803170 674 277983915081 675 141769032726 676 69414281295 677 31966536108 678 15975418488 679 7625877653 680 3688401243 681 1739501006 682 807182532 683 379433030 684 180445729 685 83845062 686 38323250 687 17746721 688 8339535 689 3838774 690 1782992 691 803759 692 371992 693 170414 694 78873 695 35970 696 16092 697 7387 698 3396 699 1545 700 706 701 316 702 143 703 65 704 20271235836837 705 15499631717025 706 12851015876980 707 7770777512575 708 4672887003563 709 2253486961668 710 1182499190737 711 630453395717 712 321524963283 713 157428063207 714 72498479751 715 36231437459 716 17295103065 717 8365106621 718 3945099902 719 1830648972 720 860534834 721 409241746 722 190156341 723 86915184 724 40248662 725 18913642 726 8706145 727 4043736 728 1822885 729 843659 730 386491 731 178880 732 81579 733 36496 734 16754 735 7702 736 3504 737 1602 738 717 739 325 740 148 741 67 742 45974132945736 743 35152377235607 744 29145451080117 745 17623728584207 746 10597870306053 747 5110793934870 748 2681848084683 749 1429836269682 750 729202280825 751 357038848817 752 164422868604 753 82171059326 754 39224415030 755 18971636806 756 8947286137 757 4151818858 758 1951649282 759 928139488 760 431264921 761 197119222 762 91281921 763 42895180 764 19745095 765 9170988 766 4134211 767 1913376 768 876542 769 405691 770 185018 771 82772 772 37998 773 17468 774 7947 775 3634 776 1627 777 738 778 336 779 152 780 68 781 104266997687004 782 79723805563530 783 66100402240193 784 39969721010178 785 24035431402103 786 11591020977271 787 6082295197880 788 3242796013135 789 1653793723916 790 809745968842 791 372902712068 792 186359787640 793 88958980391 794 43026708374 795 20291990369 796 9416114227 797 4426241414 798 2104973203 799 978086930 800 447056381 801 207022760 802 97284089 803 44780873 804 20799335 805 9376181 806 4339440 807 1987953 808 920087 809 419612 810 187723 811 86178 812 39617 813 18024 814 8242 815 3690 816 1674 817 763 818 345 819 155 820 70 821 236472253201459 822 180809540445344 823 149912353880019 824 90649296486731 825 54511137238134 826 26287846664854 827 13794336482160 828 7354496599209 829 3750720140603 830 1836462716110 831 845724404690 832 422654529880 833 201754447738 834 97582388510 835 46021203171 836 21355268657 837 10038490641 838 4773972276 839 2218251464 840 1013901159 841 469517102 842 220635372 843 101560745 844 47171836 845 21264703 846 9841630 847 4508577 848 2086711 849 951659 850 425747 851 195448 852 89850 853 40878 854 18693 855 8369 856 3797 857 1731 858 783 859 352 860 159 861 72 862 536307055680617 863 410066851236861 864 339993601917638 865 205587998761531 866 123628489677729 867 59619500614309 868 31284854284838 869 16679624622914 870 8506442713916 871 4165004133932 872 1918059980636 873 958558999719 874 457568836817 875 221311899217 876 104373750567 877 48432664305 878 22766786743 879 10827126569 880 5030881617 881 2299476315 882 1064840933 883 500389814 884 230334610 885 106983328 886 48227266 887 22320317 888 10225224 889 4732555 890 2158315 891 965573 892 443267 893 203776 894 92710 895 42395 896 18981 897 8612 898 3926 899 1776 900 799 901 361 902 164 903 74 904 1216317153825969 905 930010784105413 906 771088214900856 907 466263135764745 908 280383133326085 909 135213998271369 910 70952460010624 911 37828541193593 912 19292179883488 913 9446017762024 914 4350062584118 915 2173963109311 916 1037742873941 917 501924143105 918 236714363310 919 109842821898 920 51633915609 921 24555372959 922 11409783901 923 5215095452 924 2415005135 925 1134858675 926 522387193 927 242632753 928 109376989 929 50621345 930 23190289 931 10733195 932 4894949 933 2189871 934 1005308 935 462154 936 210262 937 96150 938 43048 939 19532 940 8904 941 4028 942 1813 943 819 944 372 945 168 946 76 947 2758545506759729 948 2109217206764107 949 1748788894277553 950 1057461102218057 951 635894700798203 952 306658478184935 953 160916574382097 954 85793209450857 955 43753683786993 956 21423088355073 957 9865720924676 958 4930437878137 959 2353548112906 960 1138338455017 961 536856149106 962 249117939218 963 117103097208 964 55690338273 965 25876810185 966 11827571519 967 5477108946 968 2573801816 969 1184747613 970 550278757 971 248061454 972 114806639 973 52594398 974 24342341 975 11101496 976 4966517 977 2279988 978 1048142 979 476864 980 218064 981 97631 982 44298 983 20194 984 9136 985 4112 986 1858 987 844 988 382 989 173 990 77 991 6256241054340230 992 4783597460742485 993 3966164360509293 994 2398268052802768 995 1442176873146515 996 695485847951681 997 364950614918660 998 194574640090146 999 99231131810598 1000 48586475934269 1001 22374953803870 1002 11181982604053 1003 5337727542013 1004 2581693779770 1005 1217562469817 1006 564986829070 1007 265583874745 1008 126302857713 1009 58687290762 1010 26824331275 1011 12421804811 1012 5837251751 1013 2686947393 1014 1248004263 1015 562590775 1016 260375625 1017 119281423 1018 55207193 1019 25177629 1020 11263809 1021 5170897 1022 2377133 1023 1081504 1024 494559 1025 221423 1026 100466 1027 45799 1028 20720 1029 9326 1030 4214 1031 1915 1032 867 1033 393 1034 175 1035 79 1036 14188836846845361 1037 10848955998006489 1038 8995059258466152 1039 5439150093587399 1040 3270783874795481 1041 1577326567209290 1042 827689452382017 1043 441285397860023 1044 225051165253873 1045 110191658858200 1046 50745258410171 1047 25360168416641 1048 12105694868326 1049 5855150322934 1050 2761369820156 1051 1281361422724 1052 602330734251 1053 286448464152 1054 133099793690 1055 60836220453 1056 28172022190 1057 13238590395 1058 6093860171 1059 2830410261 1060 1275927294 1061 590518689 1062 270524207 1063 125207109 1064 57101584 1065 25545747 1066 11727332 1067 5391217 1068 2452797 1069 1121635 1070 502177 1071 227852 1072 103870 1073 46992 1074 21151 1075 9558 1076 4344 1077 1967 1078 892 1079 397 1080 180 1081 81 1082 32179561068339894 1083 24604880994399602 1084 20400337381108403 1085 12335716062263208 1086 7417971647459150 1087 3577296514302465 1088 1877157625113554 1089 1000812861708286 1090 510404608493205 1091 249909083720101 1092 115087667831056 1093 57515573480439 1094 27455100900438 1095 13279183446461 1096 6262646453627 1097 2906062603880 1098 1366055502322 1099 649650562947 1100 301863569612 1101 137973457047 1102 63892714975 1103 30024450396 1104 13820565254 1105 6419226666 1106 2893738277 1107 1339266384 1108 613535157 1109 283963362 1110 129503492 1111 57936457 1112 26596994 1113 12227007 1114 5562819 1115 2543812 1116 1138912 1117 516757 1118 235572 1119 106576 1120 47970 1121 21678 1122 9852 1123 4462 1124 2024 1125 901 1126 409 1127 184 1128 83 1129 72981609537729459 1130 55802619981112457 1131 46266928688807248 1132 27976777281469472 1133 16823582807331945 1134 8113126740698946 1135 4257298119942209 1136 2269792721485989 1137 1157571719645288 1138 566781104604205 1139 261012983316225 1140 130442398427175 1141 62266773915264 1142 30116513373546 1143 14203363966985 1144 6590802335624 1145 3098144473308 1146 1473374469599 1147 684611238926 1148 312916790487 1149 144905431330 1150 68093928029 1151 31344339807 1152 14558479934 1153 6562851389 1154 3037388115 1155 1391466564 1156 644014478 1157 293707341 1158 131396941 1159 60320632 1160 27730231 1161 12616191 1162 5769237 1163 2582995 1164 1171979 1165 534266 1166 241709 1167 108794 1168 49165 1169 22344 1170 10120 1171 4591 1172 2044 1173 928 1174 418 1175 189 1176 85 1177 165518582413417050 1178 126557506921704829 1179 104931043556048742 1180 63449909442334070 1181 38155031041686605 1182 18400159239659522 1183 9655335833061470 1184 5147774569680189 1185 2625313846750637 1186 1285430748472327 1187 591964184726071 1188 295836732171691 1189 141217879616415 1190 68302722184375 1191 32212507838729 1192 14947604834552 1193 7026434256274 1194 3341538438476 1195 1552663506452 1196 709679382284 1197 328638155964 1198 154433569083 1199 71087370153 1200 33017892810 1201 14884213508 1202 6888641923 1203 3155775471 1204 1460592116 1205 666113327 1206 298001587 1207 136804129 1208 62890756 1209 28612881 1210 13084337 1211 5858102 1212 2657989 1213 1211689 1214 548184 1215 246740 1216 111504 1217 50676 1218 22952 1219 10413 1220 4636 1221 2105 1222 949 1223 429 1224 193 1225 86 1226 375387735316853428 1227 287025995619176690 1228 237978275493895707 1229 143901170879569422 1230 86533671838177555 1231 41730626288189874 1232 21897811105243043 1233 11674891178123655 1234 5954078418616352 1235 2915291627923948 1236 1342544694697641 1237 670942677820249 1238 320274976032884 1239 154907103618901 1240 73056331139027 1241 33900408313302 1242 15935595897187 1243 7578439403020 1244 3521361945576 1245 1609516781937 1246 745334640421 1247 350247488287 1248 161222543731 1249 74882903335 1250 33756640006 1251 15623089887 1252 7157138431 1253 3312548710 1254 1510711183 1255 675852459 1256 310264814 1257 142633040 1258 64892561 1259 29674612 1260 13285878 1261 6028185 1262 2748050 1263 1243254 1264 559594 1265 252886 1266 114931 1267 52054 1268 23617 1269 10515 1270 4775 1271 2153 1272 973 1273 438 1274 196 1275 88