1 1 2 1 3 2 4 1 5 3 6 3 7 3 8 1 9 4 10 6 11 8 12 8 13 4 14 4 15 1 16 5 17 10 18 15 19 20 20 20 21 20 22 15 23 10 24 5 25 5 26 1 27 6 28 15 29 26 30 39 31 48 32 57 33 60 34 54 35 48 36 36 37 30 38 18 39 12 40 6 41 6 42 1 43 7 44 21 45 42 46 70 47 98 48 126 49 154 50 168 51 175 52 168 53 154 54 133 55 112 56 84 57 70 58 49 59 35 60 21 61 14 62 7 63 7 64 1 65 8 66 28 67 64 68 118 69 184 70 256 71 336 72 408 73 472 74 516 75 536 76 532 77 504 78 464 79 408 80 360 81 296 82 248 83 192 84 152 85 112 86 88 87 56 88 40 89 24 90 16 91 8 92 8 93 1 94 9 95 36 96 93 97 189 98 324 99 489 100 684 101 891 102 1101 103 1305 104 1476 105 1611 106 1683 107 1701 108 1665 109 1593 110 1476 111 1350 112 1197 113 1053 114 900 115 765 116 630 117 522 118 405 119 324 120 243 121 189 122 135 123 99 124 63 125 45 126 27 127 18 128 9 129 9 130 1 131 10 132 45 133 130 134 290 135 542 136 885 137 1320 138 1830 139 2390 140 2990 141 3590 142 4170 143 4680 144 5085 145 5360 146 5510 147 5520 148 5405 149 5200 150 4895 151 4560 152 4160 153 3760 154 3340 155 2950 156 2540 157 2190 158 1840 159 1550 160 1270 161 1040 162 820 163 660 164 500 165 390 166 290 167 220 168 150 169 110 170 70 171 50 172 30 173 20 174 10 175 10 176 1 177 11 178 55 179 176 180 429 181 869 182 1529 183 2431 184 3575 185 4928 186 6468 187 8140 188 9900 189 11682 190 13387 191 14938 192 16247 193 17270 194 17941 195 18282 196 18271 197 17985 198 17424 199 16665 200 15719 201 14685 202 13541 203 12386 204 11187 205 10043 206 8899 207 7854 208 6820 209 5907 210 5038 211 4279 212 3575 213 2992 214 2442 215 2002 216 1595 217 1276 218 990 219 781 220 583 221 451 222 330 223 242 224 165 225 121 226 77 227 55 228 33 229 22 230 11 231 11 232 1 233 12 234 66 235 232 236 615 237 1344 238 2538 239 4296 240 6687 241 9716 242 13368 243 17580 244 22265 245 27336 246 32628 247 37984 248 43194 249 48060 250 52360 251 55956 252 58692 253 60552 254 61518 255 61608 256 60930 257 59520 258 57540 259 55044 260 52206 261 49032 262 45738 263 42264 264 38832 265 35352 266 32016 267 28728 268 25668 269 22704 270 20016 271 17460 272 15180 273 13044 274 11184 275 9456 276 7992 277 6660 278 5544 279 4536 280 3720 281 2976 282 2400 283 1884 284 1488 285 1140 286 888 287 660 288 504 289 360 290 264 291 180 292 132 293 84 294 60 295 36 296 24 297 12 298 12 299 1 300 13 301 78 302 299 303 858 304 2015 305 4069 306 7319 307 12038 308 18408 309 26533 310 36426 311 47996 312 61126 313 75582 314 91091 315 107302 316 123786 317 140036 318 155519 319 169728 320 182182 321 192608 322 200681 323 206375 324 209612 325 210522 326 209196 327 205946 328 200889 329 194415 330 186641 331 177944 332 168441 333 158509 334 148135 335 137735 336 127231 337 116961 338 106847 339 97175 340 87802 341 79027 342 70629 343 62881 344 55601 345 48997 346 42835 347 37349 348 32279 349 27820 350 23764 351 20241 352 17069 353 14378 354 11960 355 9945 356 8164 357 6695 358 5395 359 4368 360 3458 361 2756 362 2145 363 1677 364 1274 365 988 366 728 367 546 368 390 369 286 370 195 371 143 372 91 373 65 374 39 375 26 376 13 377 13 378 1 379 14 380 91 381 378 382 1169 383 2940 384 6328 385 12070 386 20944 387 33656 388 50778 389 72716 390 99638 391 131558 392 168266 393 209370 394 254352 395 302484 396 352877 397 404390 398 455770 399 505610 400 552650 401 595574 402 633409 403 665308 404 690760 405 709450 406 721350 407 726656 408 725690 409 718984 410 706965 411 690396 412 669753 413 645890 414 619157 415 590464 416 560014 417 528668 418 496517 419 464338 420 432117 421 400568 422 369488 423 339570 424 310576 425 283052 426 256704 427 232036 428 208656 429 187040 430 166768 431 148218 432 131012 433 115472 434 101150 435 88368 436 76720 437 66416 438 57092 439 48972 440 41664 441 35392 442 29806 443 25046 444 20860 445 17360 446 14266 447 11732 448 9520 449 7728 450 6174 451 4956 452 3892 453 3080 454 2380 455 1848 456 1400 457 1078 458 784 459 588 460 420 461 308 462 210 463 154 464 98 465 70 466 42 467 28 468 14 469 14 470 1 471 15 472 105 473 470 474 1560 475 4188 476 9580 477 19335 478 35340 479 59595 480 94023 481 140340 482 199865 483 273510 484 361710 485 464363 486 580980 487 710595 488 851855 489 1002885 490 1161315 491 1324215 492 1488360 493 1650195 494 1806100 495 1952745 496 2086920 497 2206175 498 2308350 499 2392170 500 2456750 501 2502090 502 2528235 503 2536155 504 2526630 505 2501250 506 2461245 507 2408505 508 2344305 509 2270715 510 2188845 511 2100705 512 2007270 513 1910385 514 1810740 515 1710015 516 1608600 517 1508025 518 1408440 519 1311150 520 1216080 521 1124415 522 1035810 523 951315 524 870480 525 794160 526 721830 527 654195 528 590595 529 531690 530 476760 531 426285 532 379575 533 337065 534 297990 535 262755 536 230610 537 201870 538 175845 539 152790 540 132030 541 113820 542 97560 543 83415 544 70875 545 60105 546 50595 547 42525 548 35460 549 29520 550 24360 551 20085 552 16365 553 13350 554 10755 555 8670 556 6885 557 5490 558 4290 559 3375 560 2595 561 2010 562 1515 563 1155 564 840 565 630 566 450 567 330 568 225 569 165 570 105 571 75 572 45 573 30 574 15 575 15 576 1 577 16 578 120 579 576 580 2044 581 5840 582 14160 583 30176 584 58006 585 102512 586 168952 587 262640 588 388512 589 550832 590 752976 591 997136 592 1284392 593 1614624 594 1986600 595 2397968 596 2845140 597 3323232 598 3826024 599 4346096 600 4874740 601 5402752 602 5920280 603 6417872 604 6886416 605 7317952 606 7705544 607 8044016 608 8329352 609 8559264 610 8732744 611 8850016 612 8912568 613 8922640 614 8883424 615 8798256 616 8671512 617 8506816 618 8309136 619 8082128 620 7830728 621 7558304 622 7269624 623 6967344 624 6655976 625 6337568 626 6016088 627 5693072 628 5372000 629 5053680 630 4741288 631 4435056 632 4137656 633 3849008 634 3571296 635 3304000 636 3049072 637 2805616 638 2575184 639 2356752 640 2151536 641 1958288 642 1778112 643 1609536 644 1453424 645 1308352 646 1174896 647 1051600 648 939008 649 835584 650 741776 651 656176 652 579056 653 509072 654 446528 655 390080 656 339984 657 295072 658 255488 659 220192 660 189376 661 162032 662 138352 663 117504 664 99584 665 83888 666 70560 667 58928 668 49152 669 40688 670 33632 671 27552 672 22576 673 18288 674 14832 675 11888 676 9536 677 7536 678 5984 679 4656 680 3648 681 2800 682 2160 683 1616 684 1232 685 896 686 672 687 480 688 352 689 240 690 176 691 112 692 80 693 48 694 32 695 16 696 16 697 1 698 17 699 136 700 697 701 2635 702 7990 703 20485 704 46002 705 92854 706 171751 707 295392 708 477853 709 733737 710 1077290 711 1521670 712 2078080 713 2755326 714 3559460 715 4493576 716 5557895 717 6749561 718 8062658 719 9487955 720 11012906 721 12621191 722 14293294 723 16006435 724 17735573 725 19454273 726 21135556 727 22753429 728 24283327 729 25703575 730 26995167 731 28143296 732 29136096 733 29966325 734 30629376 735 31125045 736 31454913 737 31624369 738 31639465 739 31509500 740 31243433 741 30852909 742 30348230 743 29742231 744 29045418 745 28270609 746 27427749 747 26529044 748 25583385 749 24602128 750 23592634 751 22565154 752 21525655 753 20483045 754 19441863 755 18409895 756 17390235 757 16389547 758 15409752 759 14456341 760 13530215 761 12635930 762 11773299 763 10946113 764 10153505 765 9398331 766 8679112 767 7998160 768 7353282 769 6746314 770 6174723 771 5639699 772 5138607 773 4672263 774 4237675 775 3835489 776 3462696 777 3119517 778 2803028 779 2513331 780 2247434 781 2005422 782 1784439 783 1584366 784 1402619 785 1239079 786 1091179 787 958902 788 839936 789 734111 790 639421 791 555764 792 481236 793 415837 794 357901 795 307360 796 262854 797 224349 798 190553 799 161551 800 136272 801 114716 802 96033 803 80274 804 66640 805 55267 806 45492 807 37400 808 30498 809 24871 810 20060 811 16201 812 12937 813 10336 814 8143 815 6443 816 4998 817 3910 818 2992 819 2295 820 1717 821 1309 822 952 823 714 824 510 825 374 826 255 827 187 828 119 829 85 830 51 831 34 832 17 833 17 834 1 835 18 836 153 837 834 838 3348 839 10746 840 29067 841 68652 842 145287 843 280916 844 503658 845 847170 846 1349355 847 2050560 848 2991708 849 4212138 850 5747715 851 7629318 852 9881481 853 12521808 854 15560307 855 18999168 856 22832478 857 27046008 858 31616487 859 36511308 860 41688279 861 47095464 862 52672725 863 58352202 864 64061433 865 69724908 866 75267441 867 80615640 868 85701582 869 90463086 870 94846896 871 98808066 872 102311739 873 105332358 874 107854173 875 109869804 876 111380172 877 112393512 878 112923603 879 112990542 880 112617162 881 111831480 882 110661840 883 109140642 884 107298171 885 105168726 886 102782448 887 100173258 888 97369569 889 94403610 890 91300833 891 88091046 892 84796047 893 81442692 894 78049305 895 74639412 896 71227719 897 67834728 898 64471635 899 61155882 900 57895551 901 54705150 902 51590052 903 48562236 904 45624339 905 42786144 906 40048173 907 37417914 908 34894080 909 32482386 910 30179916 911 27990846 912 25911018 913 23943150 914 22082220 915 20329830 916 18680004 917 17133570 918 15684138 919 14331618 920 13069404 921 11896938 922 10807362 923 9799830 924 8867538 925 8009244 926 7218450 927 6493752 928 5828742 929 5222124 930 4667886 931 4164570 932 3706650 933 3292812 934 2917872 935 2580696 936 2276532 937 2004300 938 1759824 939 1542168 940 1347498 941 1175112 942 1021662 943 886464 944 766656 945 661752 946 569178 947 488628 948 417888 949 356688 950 303228 951 257310 952 217332 953 183258 954 153774 955 128808 956 107298 957 89262 958 73764 959 60912 960 49932 961 40896 962 33228 963 27000 964 21708 965 17478 966 13914 967 11088 968 8712 969 6876 970 5328 971 4158 972 3168 973 2430 974 1818 975 1386 976 1008 977 756 978 540 979 396 980 270 981 198 982 126 983 90 984 54 985 36 986 18 987 18 988 1 989 19 990 171 991 988 992 4199 993 14231 994 40527 995 100491 996 222642 997 449445 998 839173 999 1466439 1000 2421208 1001 3806232 1002 5733478 1003 8319568 1004 11680763 1005 15928251 1006 21163492 1007 27474665 1008 34933647 1009 43593771 1010 53488477 1011 64630248 1012 77009603 1013 90593710 1014 105325398 1015 121121105 1016 137871106 1017 155438753 1018 173662907 1019 192360731 1020 211332440 1021 230366507 1022 249245933 1023 267754821 1024 285683772 1025 302836896 1026 319034206 1027 334117907 1028 347952130 1029 360427606 1030 371458208 1031 380985549 1032 388972161 1033 395406226 1034 400293083 1035 403659788 1036 405545576 1037 406007637 1038 405109108 1039 402927357 1040 399541006 1041 395039146 1042 389508056 1043 383042318 1044 375729389 1045 367664003 1046 358930653 1047 349619817 1048 339810174 1049 329586103 1050 319017980 1051 308182736 1052 297141950 1053 285963908 1054 274701221 1055 263413549 1056 252144155 1057 240944738 1058 229849916 1059 218903123 1060 208131358 1061 197570683 1062 187240421 1063 177170212 1064 167372653 1065 157871095 1066 148672682 1067 139795084 1068 131240239 1069 123021371 1070 115135820 1071 107592383 1072 100385132 1073 93519045 1074 86985059 1075 80785397 1076 74908393 1077 69353724 1078 64108223 1079 59169325 1080 54522495 1081 50163971 1082 46078097 1083 42259876 1084 38693576 1085 35373212 1086 32282938 1087 29416541 1088 26758194 1089 24301551 1090 22031507 1091 19941431 1092 18016940 1093 16251840 1094 14632337 1095 13152541 1096 11799817 1097 10568503 1098 9446952 1099 8430186 1100 7507356 1101 6674092 1102 5920742 1103 5243221 1104 4632941 1105 4086520 1106 3596149 1107 3158959 1108 2768205 1109 2421360 1110 2112553 1111 1839789 1112 1597843 1113 1385157 1114 1197361 1115 1033049 1116 888554 1117 762888 1118 652783 1119 557555 1120 474525 1121 403104 1122 341107 1123 288154 1124 242345 1125 203490 1126 170069 1127 141892 1128 117743 1129 97603 1130 80389 1131 66158 1132 54074 1133 44156 1134 35777 1135 28994 1136 23256 1137 18677 1138 14839 1139 11799 1140 9253 1141 7296 1142 5643 1143 4389 1144 3344 1145 2565 1146 1919 1147 1463 1148 1064 1149 798 1150 570 1151 418 1152 285 1153 209 1154 133 1155 95 1156 57 1157 38 1158 19 1159 19 1160 1 1161 20 1162 190 1163 1160 1164 5205 1165 18584 1166 55610 1167 144520 1168 334730 1169 704640 1170 1368746 1171 2482860 1172 4246525 1173 6901900 1174 10729340 1175 16039848 1176 23164850 1177 32444760 1178 44216590 1179 58802120 1180 76497118 1181 97561620 1182 122212510 1183 150617580 1184 182891270 1185 219090724 1186 259212700 1187 303188980 1188 350882985 1189 402085740 1190 456513244 1191 513807460 1192 573538250 1193 635211120 1194 698275460 1195 762138740 1196 826179085 1197 889763960 1198 952262820 1199 1013065920 1200 1071594515 1201 1127316220 1202 1179750780 1203 1228480960 1204 1273153040 1205 1313482820 1206 1349252420 1207 1380311220 1208 1406571200 1209 1428003400 1210 1444633450 1211 1456533680 1212 1463821280 1213 1466646340 1214 1465193890 1215 1459668880 1216 1450302240 1217 1437332460 1218 1421017050 1219 1401609920 1220 1379378910 1221 1354579580 1222 1327477840 1223 1298320320 1224 1267362480 1225 1234834720 1226 1200975840 1227 1165995760 1228 1130112580 1229 1093512980 1230 1056392910 1231 1018914680 1232 981251330 1233 943541400 1234 905935120 1235 868547860 1236 831508390 1237 794909760 1238 758860370 1239 723433340 1240 688717650 1241 654768140 1242 621656590 1243 589420700 1244 558116690 1245 527767580 1246 498414960 1247 470069000 1248 442758910 1249 416483000 1250 391259790 1251 367078100 1252 343946560 1253 321846160 1254 300777680 1255 280715000 1256 261652500 1257 243559040 1258 226423140 1259 210210000 1260 194904100 1261 180467380 1262 166881520 1263 154106920 1264 142122580 1265 130888400 1266 120382160 1267 110563240 1268 101409100 1269 92879920 1270 84952640 1271 77588960 1272 70766400 1273 64447860 1274 58612040 1275 53223940 1276 48263000 1277 43696720 1278 39506020 1279 35660380 1280 32142520 1281 28924480 1282 25990200 1283 23314480 1284 20882960 1285 18672560 1286 16670780 1287 14857000 1288 13219980 1289 11741600 1290 10412180 1291 9215400 1292 8143200 1293 7181340 1294 6322720 1295 5555140 1296 4872700 1297 4264640 1298 3726240 1299 3248300 1300 2826780 1301 2453980 1302 2126700 1303 1838220 1304 1586160 1305 1364900 1306 1172400 1307 1004100 1308 858480 1309 731580 1310 622400 1311 527680 1312 446580 1313 376540 1314 316980 1315 265680 1316 222360 1317 185240 1318 154080 1319 127500 1320 105400 1321 86580 1322 71080 1323 57960 1324 47220 1325 38180 1326 30880 1327 24720 1328 19820 1329 15720 1330 12480 1331 9780 1332 7700 1333 5940 1334 4620 1335 3520 1336 2700 1337 2020 1338 1540 1339 1120 1340 840 1341 600 1342 440 1343 300 1344 220 1345 140 1346 100 1347 60 1348 40 1349 20 1350 20