1 1 2 1 3 2 4 1 5 2 6 3 7 1 8 4 9 3 10 5 11 1 12 4 13 7 14 5 15 7 16 1 17 6 18 10 19 13 20 7 21 11 22 1 23 6 24 14 25 20 26 19 27 11 28 15 29 1 30 8 31 18 32 33 33 32 34 31 35 15 36 22 37 1 38 8 39 25 40 43 41 56 42 54 43 43 44 22 45 30 46 1 47 10 48 29 49 66 50 81 51 99 52 78 53 64 54 30 55 42 56 1 57 10 58 37 59 83 60 126 61 150 62 148 63 118 64 88 65 42 66 56 67 1 68 12 69 44 70 114 71 174 72 246 73 235 74 230 75 166 76 124 77 56 78 77 79 1 80 12 81 52 82 141 83 249 84 349 85 398 86 374 87 329 88 236 89 166 90 77 91 101 92 1 93 14 94 60 95 182 96 330 97 525 98 593 99 652 100 549 101 476 102 320 103 229 104 101 105 135 106 1 107 14 108 71 109 219 110 443 111 725 112 914 113 999 114 978 115 806 116 653 117 444 118 301 119 135 120 176 121 1 122 16 123 79 124 275 125 568 126 1014 127 1321 128 1585 129 1540 130 1462 131 1123 132 915 133 588 134 403 135 176 136 231 137 1 138 16 139 91 140 322 141 737 142 1349 143 1909 144 2345 145 2498 146 2346 147 2066 148 1588 149 1222 150 790 151 526 152 231 153 297 154 1 155 18 156 102 157 391 158 918 159 1821 160 2642 161 3494 162 3797 163 3881 164 3375 165 2956 166 2143 167 1653 168 1036 169 691 170 297 171 385 172 1 173 18 174 114 175 455 176 1151 177 2348 178 3672 179 4970 180 5776 181 6014 182 5672 183 4886 184 4028 185 2918 186 2179 187 1364 188 889 189 385 190 490 191 1 192 20 193 126 194 539 195 1409 196 3058 197 4920 198 7097 199 8445 200 9334 201 8953 202 8321 203 6739 204 5530 205 3873 206 2883 207 1760 208 1153 209 490 210 627 211 1 212 20 213 141 214 616 215 1724 216 3869 217 6594 218 9766 219 12334 220 13907 221 14128 222 13311 223 11608 224 9330 225 7390 226 5148 227 3734 228 2286 229 1468 230 627 231 792 232 1 233 22 234 153 235 720 236 2069 237 4899 238 8637 239 13445 240 17411 241 20733 242 21442 243 21301 244 18813 245 16225 246 12567 247 9882 248 6701 249 4865 250 2916 251 1879 252 792 253 1002 254 1 255 22 256 169 257 814 258 2487 259 6070 260 11253 261 18061 262 24509 263 29866 264 32493 265 32786 266 30482 267 26554 268 22030 269 16908 270 12928 271 8760 272 6223 273 3736 274 2374 275 1002 276 1255 277 1 278 24 279 184 280 936 281 2940 282 7539 283 14404 284 24156 285 33741 286 42883 287 47707 288 50395 289 47558 290 43477 291 36383 292 29847 293 22249 294 16974 295 11245 296 7991 297 4726 298 3004 299 1255 300 1575 301 1 302 24 303 200 304 1050 305 3478 306 9179 307 18373 308 31696 309 46124 310 60205 311 69687 312 75062 313 74032 314 68561 315 60104 316 49650 317 39512 318 29340 319 21872 320 14476 321 10127 322 5984 323 3763 324 1575 325 1958 326 1 327 26 328 216 329 1192 330 4060 331 11197 332 23076 333 41442 334 61976 335 83945 336 99632 337 111290 338 111804 339 107893 340 95713 341 82664 342 66172 343 52371 344 37971 345 28248 346 18393 347 12844 348 7502 349 4723 350 1958 351 2436 352 1 353 26 354 235 355 1326 356 4737 357 13453 358 28876 359 53322 360 82782 361 115000 362 141325 363 161479 364 167942 365 164772 366 152057 367 132704 368 110926 369 88177 370 68086 371 49204 372 35994 373 23372 374 16124 375 9420 376 5872 377 2436 378 3010 379 1 380 28 381 251 382 1493 383 5471 384 16152 385 35712 386 68335 387 108962 388 156596 389 197128 390 232463 391 247116 392 250310 393 234598 394 212586 395 179402 396 148672 397 115218 398 88573 399 62897 400 45852 401 29397 402 20269 403 11718 404 7306 405 3010 406 3718 407 1 408 28 409 271 410 1647 411 6315 412 19167 413 43964 414 86476 415 142588 416 210089 417 273014 418 329094 419 360550 420 372547 421 359939 422 330823 423 289520 424 241911 425 195284 426 150500 427 113614 428 80332 429 57798 430 37006 431 25239 432 14584 433 9028 434 3718 435 4565 436 1 437 30 438 290 439 1837 440 7221 441 22738 442 53606 443 108944 444 184433 445 280145 446 372811 447 462565 448 517566 449 549942 450 541329 451 512027 452 454127 453 392880 454 319562 455 256229 456 193790 457 145549 458 101511 459 72896 460 46147 461 31438 462 18028 463 11152 464 4565 465 5604 466 1 467 30 468 310 469 2018 470 8251 471 26678 472 65117 473 135832 474 237101 475 369157 476 505533 477 641048 478 737302 479 798748 480 807333 481 776967 482 708389 483 620336 484 521975 485 421267 486 331256 487 249058 488 184420 489 128280 490 91056 491 57544 492 38889 493 22274 494 13693 495 5604 496 6842 497 1 498 32 499 330 500 2233 501 9361 502 31290 503 78418 504 168664 505 301914 506 483401 507 677727 508 882141 509 1036046 510 1151259 511 1185228 512 1169311 513 1083775 514 974236 515 829250 516 691519 517 546994 518 427233 519 316514 520 233599 521 160547 522 113712 523 71259 524 48078 525 27356 526 16810 527 6842 528 8349 529 1 530 32 531 353 532 2437 533 10607 534 36382 535 94095 536 207537 537 382339 538 626777 539 902270 540 1200054 541 1444952 542 1636974 543 1726322 544 1732548 545 1644406 546 1500928 547 1310392 548 1104315 549 901927 550 708102 551 544668 552 401915 553 292982 554 200808 555 140998 556 88170 557 59078 558 33588 559 20524 560 8349 561 10143 562 1 563 34 564 373 565 2682 566 11941 567 42250 568 112123 569 254376 570 480088 571 808065 572 1189729 573 1621075 574 1992810 575 2310153 576 2481262 577 2547135 578 2457190 579 2293591 580 2031908 581 1754440 582 1447222 583 1172186 584 905836 585 693532 586 505276 587 367139 588 249363 589 174660 590 108433 591 72568 592 41016 593 25045 594 10143 595 12310 596 1 597 34 598 397 599 2913 600 13432 601 48703 602 133111 603 309434 604 599795 605 1032757 606 1558853 607 2168726 608 2728171 609 3223986 610 3539052 611 3695729 612 3642974 613 3452292 614 3125237 615 2735591 616 2310440 617 1888675 618 1504862 619 1156773 620 874094 621 634429 622 456678 623 309282 624 215020 625 133278 626 88651 627 50056 628 30427 629 12310 630 14883 631 1 632 36 633 420 634 3186 635 15022 636 56091 637 157071 638 374959 639 744007 640 1312917 641 2025320 642 2882669 643 3699557 644 4466132 645 4992803 646 5321306 647 5331763 648 5156153 649 4735881 650 4231570 651 3620982 652 3028207 653 2433928 654 1927746 655 1461926 656 1099954 657 790622 658 567255 659 381201 660 264524 661 162919 662 108225 663 60820 664 36928 665 14883 666 17977 667 1 668 36 669 444 670 3447 671 16786 672 64156 673 184752 674 451372 675 918408 676 1656793 677 2615914 678 3799100 679 4982930 680 6128318 681 6990850 682 7579142 683 7743307 684 7603401 685 7121179 686 6450001 687 5630268 688 4767158 689 3917721 690 3128119 691 2443279 692 1844007 693 1373514 694 983628 695 700106 696 469426 697 323616 698 198990 699 131534 700 73820 701 44647 702 17977 703 21637 704 1 705 38 706 468 707 3750 708 18665 709 73321 710 216117 711 541462 712 1126621 713 2080145 714 3354246 715 4976839 716 6655342 717 8351870 718 9697256 719 10714178 720 11125980 721 11126637 722 10574412 723 9756492 724 8628350 725 7446695 726 6192856 727 5052448 728 3976805 729 3089659 730 2307625 731 1711871 732 1215812 733 863161 734 574835 735 395546 736 241965 737 159688 738 89258 739 53929 740 21637 741 26015 742 1 743 38 744 495 745 4041 746 20731 747 83314 748 252052 749 645735 750 1375976 751 2594727 752 4277257 753 6471726 754 8833272 755 11286967 756 13358065 757 15005594 758 15866197 759 16110905 760 15582635 761 14576176 762 13122764 763 11466412 764 9714491 765 8015238 766 6443604 767 5042305 768 3875407 769 2881565 770 2119416 771 1500902 772 1058132 773 703162 774 481276 775 293870 776 193124 777 107820 778 64909 779 26015 780 31185 781 1 782 40 783 519 784 4379 785 22930 786 94549 787 292586 788 767558 789 1671097 790 3221665 791 5419221 792 8368089 793 11638416 794 15156722 795 18248755 796 20869987 797 22418981 798 23153672 799 22724500 800 21612694 801 19715746 802 17524033 803 15023914 804 12619989 805 10256313 806 8193015 807 6340209 808 4849272 809 3573892 810 2620167 811 1842156 812 1295595 813 856207 814 584846 815 355535 816 233327 817 129780 818 78043 819 31185 820 37338 821 1 822 40 823 547 824 4700 825 25337 826 106770 827 338644 828 907702 829 2021306 830 3976826 831 6831420 832 10749512 833 15244161 834 20204097 835 24768931 836 28787407 837 31456817 838 32973450 839 32892479 840 31717054 841 29399374 842 26459904 843 23063237 844 19592696 845 16204064 846 13079218 847 10328452 848 7950713 849 6025774 850 4425105 851 3220196 852 2257931 853 1578966 854 1041134 855 707926 856 429676 857 280894 858 156046 859 93553 860 37338 861 44583 862 1 863 42 864 574 865 5071 866 27887 867 120444 868 390323 869 1070079 870 2432801 871 4887957 872 8561917 873 13736964 874 19837049 875 26772101 876 33374182 877 39451122 878 43779034 879 46631418 880 47183713 881 46201597 882 43395158 883 39656593 884 34983979 885 30195918 886 25247154 887 20727255 888 16532936 889 12981871 890 9899599 891 7473560 892 5446329 893 3951670 894 2754484 895 1921499 896 1261005 897 855934 898 517423 899 337789 900 187066 901 112012 902 44583 903 53174 904 1 905 42 906 602 907 5429 908 30666 909 135234 910 448708 911 1255771 912 2916909 913 5976845 914 10680671 915 17451385 916 25674129 917 35242663 918 44696861 919 53672495 920 60530608 921 65414338 922 67214249 923 66703950 924 63583641 925 58839464 926 52676723 927 45990316 928 39052998 929 32397324 930 26274137 931 20830503 932 16198317 933 12299968 934 9212679 935 6691952 936 4825948 937 3354913 938 2328950 939 1525438 940 1031146 941 622374 942 404984 943 223982 944 133747 945 53174 946 63261 947 1 948 44 949 630 950 5835 951 33609 952 151697 953 513855 954 1469426 955 3481880 956 7278913 957 13254878 958 22063533 959 33033222 960 46138564 961 59470179 962 72576693 963 83089259 964 91166087 965 94983964 966 95640434 967 92348070 968 86667337 969 78532057 970 69538106 971 59705736 972 50277345 973 41187783 974 33187358 975 26049752 976 20164113 977 15187386 978 11335508 979 8182152 980 5883662 981 4069584 982 2819121 983 1838609 984 1240740 985 746349 986 484954 987 267452 988 159520 989 63261 990 75175 991 1 992 44 993 661 994 6226 995 36798 996 169480 997 587025 998 1712342 999 4141732 1000 8823492 1001 16377977 1002 27747110 1003 42288658 1004 60044672 1005 78683786 1006 97498391 1007 113357735 1008 126145697 1009 133354154 1010 136045426 1011 133205062 1012 126549393 1013 116234498 1014 104112475 1015 90624649 1016 77126273 1017 64112097 1018 52161760 1019 41599391 1020 32492056 1021 24941424 1022 18714465 1023 13877628 1024 9985921 1025 7143422 1026 4929574 1027 3399870 1028 2213272 1029 1488370 1030 893892 1031 579124 1032 318996 1033 189781 1034 75175 1035 89134 1036 1 1037 46 1038 689 1039 6672 1040 40165 1041 189132 1042 668359 1043 1990043 1044 4906673 1045 10656180 1046 20142223 1047 34738207 1048 53849602 1049 77743705 1050 103487766 1051 130240886 1052 153648298 1053 173481376 1054 185895837 1055 192269647 1056 190635819 1057 183527710 1058 170562940 1059 154766159 1060 136221889 1061 117472779 1062 98656715 1063 81414758 1064 65542517 1065 51995664 1066 40264746 1067 30782264 1068 22942789 1069 16956659 1070 12135858 1071 8659935 1072 5949024 1073 4094817 1074 2656063 1075 1783110 1076 1067661 1077 690786 1078 379518 1079 225523 1080 89134 1081 105558 1082 1 1083 46 1084 721 1085 7100 1086 43804 1087 210307 1088 759178 1089 2304243 1090 5794092 1091 12814980 1092 24672158 1093 43282058 1094 68251045 1095 100118443 1096 135403815 1097 172945727 1098 207078679 1099 237036643 1100 257557685 1101 269816476 1102 271072953 1103 264099211 1104 248595705 1105 228112690 1106 203314765 1107 177208033 1108 150747430 1109 125635112 1110 102556888 1111 82101197 1112 64558988 1113 49776587 1114 37792287 1115 28067527 1116 20629490 1117 14724998 1118 10458622 1119 7169212 1120 4916382 1121 3183150 1122 2130290 1123 1273704 1124 821902 1125 451000 1126 267400 1127 105558 1128 124754 1129 1 1130 48 1131 752 1132 7584 1133 47639 1134 233623 1135 859701 1136 2661250 1137 6817002 1138 15358004 1139 30091475 1140 53703137 1141 86084856 1142 128320110 1143 176207890 1144 228450916 1145 277437131 1146 322039605 1147 354553333 1148 376341086 1149 382761782 1150 377617278 1151 359553635 1152 333972599 1153 300906091 1154 265450461 1155 228153087 1156 192526276 1157 158673943 1158 128757987 1159 102145795 1160 79949468 1161 61206557 1162 46295043 1163 34185949 1164 25054923 1165 17797852 1166 12612197 1167 8612304 1168 5894555 1169 3804171 1170 2541988 1171 1515673 1172 976763 1173 534754 1174 316672 1175 124754 1176 147273 1177 1 1178 48 1179 784 1180 8052 1181 51766 1182 258650 1183 971461 1184 3063252 1185 7996127 1186 18334928 1187 36564322 1188 66340128 1189 108108937 1190 163657417 1191 228197627 1192 300136506 1193 369738914 1194 434942132 1195 485308469 1196 521573158 1197 537201982 1198 536197009 1199 516739702 1200 485251734 1201 442390515 1202 394329674 1203 342914314 1204 292253398 1205 243808075 1206 199680169 1207 160530973 1208 126728006 1209 98467241 1210 75081683 1211 56455847 1212 41561977 1213 30310672 1214 21478226 1215 15160262 1216 10330831 1217 7047344 1218 4540656 1219 3025526 1220 1801460 1221 1158213 1222 633296 1223 374260 1224 147273 1225 173525 1226 1 1227 50 1228 816 1229 8576 1230 56110 1231 286096 1232 1094645 1233 3517648 1234 9347900 1235 21818250 1236 44255737 1237 81634113 1238 135162867 1239 207804871 1240 294066933 1241 392389518 1242 490083740 1243 584322132 1244 660383975 1245 718765790 1246 749187225 1247 756801366 1248 737560320 1249 700625814 1250 645520954 1251 581937699 1252 511160447 1253 440598476 1254 371123459 1255 307559986 1256 249499593 1257 199543545 1258 156345890 1259 120966843 1260 91679166 1261 68712834 1262 50328488 1263 36608255 1264 25834936 1265 18195542 1266 12356820 1267 8414687 1268 5405837 1269 3596668 1270 2136345 1271 1371704 1272 748472 1273 441817 1274 173525 1275 204226