1 1 2 5 3 6 4 16 5 29 6 21 7 41 8 89 9 99 10 56 11 91 12 219 13 295 14 259 15 126 16 182 17 469 18 705 19 755 20 574 21 252 22 336 23 910 24 1470 25 1765 26 1645 27 1134 28 462 29 582 30 1638 31 2786 32 3605 33 3780 34 3206 35 2058 36 792 37 957 38 2778 39 4914 40 6706 41 7595 42 7266 43 5754 44 3498 45 1287 46 1507 47 4488 48 8190 49 11634 50 13916 51 14406 52 12894 53 9690 54 5643 55 2002 56 2288 57 6963 58 13035 59 19110 60 23814 61 26068 62 25284 63 21510 64 15510 65 8723 66 3003 67 3367 68 10439 69 19965 70 30030 71 38640 72 44100 73 45276 74 41790 75 34155 76 23815 77 13013 78 4368 79 4823 80 15197 81 29601 82 45485 83 60060 84 70812 85 75852 86 74172 87 65835 88 52085 89 35321 90 18837 91 6188 92 6748 93 21567 94 42679 95 66781 96 90090 97 109032 98 120708 99 123228 100 115962 101 99715 102 76791 103 50869 104 26572 105 8568 106 9248 107 29932 108 60060 109 95459 110 131131 111 162162 112 184338 113 194580 114 191268 115 174482 116 146146 117 110019 118 71435 119 36652 120 11628 121 12444 122 40732 123 82740 124 133315 125 186004 126 234234 127 272118 128 295020 129 299970 130 285978 131 254254 132 208299 133 153790 134 98140 135 49572 136 15504 137 16473 138 54468 139 111860 140 182420 141 257985 142 329966 143 390390 144 432630 145 451935 146 445830 147 414414 148 360542 149 289835 150 210420 151 132260 152 65892 153 20349 154 21489 155 71706 156 148716 157 245140 158 350840 159 454818 160 546546 161 616902 162 658845 163 667920 164 642642 165 584766 166 499408 167 394940 168 282540 169 175236 170 86241 171 26334 172 27664 173 93081 174 194769 175 324156 176 468860 177 615048 178 749112 179 858858 180 934362 181 968605 182 957957 183 902538 184 806442 185 677768 186 528360 187 373116 188 228684 189 111321 190 33649 191 35189 192 119301 193 251655 194 422484 195 616896 196 817768 197 1007832 198 1171170 199 1294293 200 1366937 201 1382667 202 1339338 203 1239420 204 1090152 205 903448 206 695436 207 485469 208 294405 209 141911 210 42504 211 44275 212 151151 213 321195 214 543495 215 800394 216 1071000 217 1333752 218 1568280 219 1756755 220 1884883 221 1942655 222 1924923 223 1831830 224 1669080 225 1447992 226 1185240 227 902139 228 623295 229 374395 230 178871 231 53130 232 55154 233 189497 234 405405 235 690935 236 1025430 237 1383732 238 1739304 239 2066520 240 2342340 241 2547545 242 2667665 243 2693691 244 2622620 245 2457840 246 2209320 247 1893528 248 1532958 249 1155105 250 790685 251 470855 252 223146 253 65780 254 68080 255 235290 256 506506 257 868945 258 1298745 259 1765974 260 2238390 261 2684232 262 3074280 263 3383380 264 3591588 265 3685045 266 3656653 267 3506580 268 3242580 269 2880072 270 2441880 271 1957494 272 1461670 273 992145 274 586201 275 275770 276 80730 277 83330 278 289570 279 626934 280 1082081 281 1627780 282 2228814 283 2846466 284 3441888 285 3978612 286 4424420 287 4752748 288 4943757 289 4985162 290 4872868 291 4611420 292 4214232 293 3703518 294 3109806 295 2470874 296 1829905 297 1232616 298 723074 299 337870 300 98280 301 101205 302 353470 303 769350 304 1335334 305 2020711 306 2784474 307 3580626 308 4362210 309 5084343 310 5706492 311 6194188 312 6520332 313 6666205 314 6622252 315 6388668 316 5975772 317 5404113 318 4704210 319 3915786 320 3086314 321 2268651 322 1517494 323 884350 324 410670 325 118755 326 122031 327 428220 328 936650 329 1634150 330 2486484 331 3446366 332 4459686 333 5470290 334 6423615 335 7269438 336 7963956 337 8471372 338 8765120 339 8828820 340 8657012 341 8255676 342 7642503 343 6846840 344 5909190 345 4880106 346 3818276 347 2787554 348 1852650 349 1073150 350 495495 351 142506 352 146160 353 515151 354 1131975 355 1984450 356 3034850 357 4229148 358 5504268 359 6793710 360 8031870 361 9157335 362 10115391 363 10859940 364 11354980 365 11575760 366 11509680 367 11156964 368 10531092 369 9658935 370 8580495 371 7348110 372 6024942 373 4682524 374 3397100 375 2244450 376 1292850 377 593775 378 169911 379 173971 380 615699 381 1358721 382 2392650 383 3676400 384 5148780 385 6736884 386 8362662 387 9948015 388 11418715 389 12707409 390 13755924 391 14517048 392 14955920 393 15051120 394 14795508 395 14196819 396 13277979 397 12077065 398 10646790 399 9053352 400 7374444 401 5696180 402 4108650 403 2699775 404 1547091 405 707049 406 201376 407 205871 408 731409 409 1620549 410 2865681 411 4422600 412 6222580 413 8182020 414 10210068 415 12214587 416 14106785 417 15804789 418 17236401 419 18341232 420 19072368 421 19397680 422 19300848 423 18782127 424 17858841 425 16565549 426 14953785 427 13091232 428 11060148 429 8954820 430 6877780 431 4934475 432 3226041 433 1839789 434 836969 435 237336 436 242296 437 863939 438 1921395 439 3411009 440 5285826 441 7469280 442 9866220 443 12371700 444 14877918 445 17279647 446 19478459 447 21386001 448 22926540 449 24038952 450 24678288 451 24817008 452 24445932 453 23574915 454 22233211 455 20469449 456 18351102 457 15963288 458 13406700 459 10794420 460 8247330 461 5887791 462 3831219 463 2175145 464 985304 465 278256 466 283712 467 1015064 468 2265480 469 4036655 470 6279399 471 8909082 472 11818170 473 14886300 474 17988300 475 21000518 476 23805782 477 26297271 478 28381535 479 29980860 480 31035132 481 31503312 482 31364592 483 30619260 484 29289260 485 27418391 486 25072047 487 22336358 488 19316550 489 16134300 490 12923820 491 9826362 492 6982794 493 4523855 494 2557655 495 1153944 496 324632 497 330616 498 1186680 499 2657320 500 4751215 501 7417620 502 10563714 503 14068782 504 17795700 505 21600150 506 25337950 507 28870842 508 32071039 509 34824790 510 37035180 511 38624340 512 39535200 513 39732876 514 39205740 515 37966180 516 36051015 517 33521488 518 30462718 519 26982450 520 23208900 521 19287450 522 15375906 523 11637990 524 8234695 525 5313090 526 2992120 527 1344904 528 376992 529 383537 530 1380808 531 3101736 532 5563880 533 8715805 534 12456486 535 16651278 536 21144942 537 25772175 538 30366050 539 34764730 540 38816778 541 42385343 542 45351460 543 47616660 544 49105044 545 49764933 546 49570164 547 48521060 548 46645060 549 43996953 550 40658618 551 36738130 552 32368050 553 27702675 554 22913982 555 18185958 556 13706966 557 9659755 558 6208680 559 3483656 560 1560328 561 435897 562 443037 563 1599598 564 3603864 565 6484456 566 10190320 567 14612346 568 19601274 569 24982398 570 30567537 571 36164700 572 41585830 573 46652970 574 51203152 575 55092268 576 58198140 577 60422964 578 61695261 579 61971426 580 61236924 581 59507140 582 56827848 583 53275222 584 48955270 585 44002530 586 38577825 587 32864832 588 27065178 589 21391734 590 16059736 591 11275320 592 7221016 593 4037704 594 1802493 595 501942 596 509712 597 1845333 598 4169165 599 7523384 600 11858616 601 17057936 602 22956864 603 29359890 604 36054018 605 42819777 606 49440105 607 55707470 608 61429550 609 66433752 610 70570808 611 73717644 612 75779676 613 76692645 614 76424061 615 74974284 616 72377228 617 68700632 618 64045800 619 58546670 620 52368030 621 45702657 622 38767113 623 31795890 624 25033554 625 18724496 626 13099856 627 8361144 628 4660040 629 2073813 630 575757 631 584193 632 2120433 633 4803435 634 8691760 635 13739264 636 19821648 637 26758704 638 34332810 639 42304185 640 50423373 641 58441383 642 66117870 643 73227700 644 79566200 645 84953352 646 89237148 647 92296281 648 94042305 649 94421355 650 93415476 651 91043568 652 87361912 653 82464200 654 76480950 655 69578145 656 61954893 657 53839863 658 45486210 659 37164660 660 29154384 661 21731248 662 15152984 663 9640785 664 5356785 665 2376843 666 658008 667 667147 668 2427459 669 5512815 670 10001355 671 15851990 672 22933680 673 31050096 674 39960240 675 49395555 676 59074015 677 68711643 678 78031863 679 86773050 680 94694600 681 101581800 682 107249736 683 111546435 684 114355395 685 115597615 686 115233195 687 113262534 688 109727112 689 104709800 690 98334600 691 90765675 692 82205487 693 72891819 694 63093415 695 53103930 696 43233840 697 33799920 698 25111856 699 17455515 700 11072355 701 6134415 702 2714283 703 749398 704 759278 705 2769117 706 6303801 707 11464635 708 18217710 709 26426092 710 35877072 711 46305072 712 57410760 713 68876885 714 80381301 715 91607607 716 102253788 717 112039200 718 120710200 719 128044680 720 133855722 721 137994549 722 140352905 723 140864955 724 139508754 725 136307292 726 131329080 727 124688200 728 116543700 729 107098173 730 96595317 731 85316231 732 73574160 733 61707360 734 50069712 735 39018672 736 28900102 737 20029485 738 12668985 739 6999771 740 3088982 741 850668 742 861328 743 3148262 744 7183254 745 13094781 746 20858565 747 30332862 748 41288478 749 53434128 750 66437712 751 79944040 752 93589496 753 107014089 754 119871297 755 131836068 756 142611300 757 151933080 758 159574920 759 165351186 760 169119874 761 170784845 762 170297589 763 167658546 764 162917970 765 156176280 766 147583800 767 137339748 768 125690292 769 112925449 770 99374561 771 85400040 772 71389032 773 57742608 774 44862048 775 33131742 776 22898190 777 14444541 778 7960069 779 3503942 780 962598 781 974078 782 3567902 783 8158410 784 14905709 785 23797956 786 34689942 787 47336058 788 61418280 789 76569768 790 92394632 791 108484376 792 124431489 793 139840610 794 154337652 795 167577228 796 179248680 797 189080970 798 196846650 799 202365086 800 205505069 801 206186904 802 204384026 803 200124150 804 193489920 805 184618980 806 173703348 807 160987932 808 146767985 809 131385254 810 115222536 811 98696312 812 82247088 813 66327030 814 51384438 815 37844562 816 26086221 817 16413644 818 9022910 819 3962322 820 1086008 821 1098349 822 4031202 823 9236890 824 16912090 825 27060579 826 39535314 827 54074538 828 70332570 829 87905895 830 106355128 831 125223384 832 144051544 833 162390865 834 179813340 835 195920172 836 210348684 837 222777945 838 232933350 839 240590350 840 245577486 841 247778839 842 247135966 843 243649350 844 237379350 845 228446595 846 217031724 847 203374332 848 187770940 849 170571765 850 152176024 851 133025464 852 113595768 853 94385445 854 75901770 855 58643298 856 43078434 857 29619499 858 18591690 859 10196290 860 4467442 861 1221759 862 1235003 863 4541488 864 10426710 865 19129370 866 30672460 867 44909046 868 61561710 869 80256330 870 100550835 871 121959530 872 143973544 873 166077912 874 187765760 875 208550020 876 227973060 877 245614572 878 261098019 879 274095900 880 284334050 881 291595150 882 295721580 883 296617706 884 294251650 885 288656550 886 279931275 887 268240518 888 253814148 889 236945660 890 217989520 891 197357160 892 175511336 893 152958520 894 130238955 895 107913960 896 86550030 897 66699234 898 48875372 899 33525310 900 20994870 901 11488610 902 5022787 903 1370754 904 1384944 905 5102251 906 11736291 907 21573790 908 34660990 909 50853348 910 69858516 911 91273302 912 114615270 913 139349595 914 164911747 915 190726536 916 216224008 917 240852640 918 264090240 919 285452916 920 304502436 921 320852259 922 334172475 923 344193850 924 350711130 925 353585716 926 352747780 927 348197850 928 340007850 929 328321539 930 313354251 931 295391796 932 274788340 933 251963040 934 227395168 935 201617416 936 175207032 937 148774395 938 122948595 939 98359542 940 75616086 941 55279588 942 37832340 943 23640190 944 12908686 945 5632011 946 1533939 947 1549119 948 5717151 949 13174469 950 24262406 951 39054960 952 57412628 953 79029132 954 103471758 955 130215987 956 158675055 957 188225037 958 218226008 959 248039792 960 277044768 961 304648160 962 330296196 963 353482479 964 373754871 965 390721149 966 404053650 967 413493080 968 418851620 969 420015420 970 416946530 971 409684275 972 398346039 973 383127381 974 364301364 975 342216936 976 317296160 977 290030048 978 260972712 979 230733503 980 199966767 981 169358805 982 139611582 983 111422688 984 85461012 985 62337548 986 42570710 987 26545491 988 14465759 989 6298941 990 1712304 991 1728519 992 6390021 993 14750505 994 27213109 995 43884596 996 64633548 997 89141052 998 116944620 999 147476043 1000 180093837 1001 214110897 1002 248817933 1003 283503220 1004 317469152 1005 350046048 1006 380603616 1007 408560439 1008 433391805 1009 454636161 1010 471900429 1011 484864380 1012 493284220 1013 496995500 1014 495915420 1015 490044555 1016 479467989 1017 464355801 1018 444962805 1019 421627404 1020 394769376 1021 364886368 1022 332548832 1023 298393095 1024 263112213 1025 227444217 1026 192157317 1027 158031588 1028 125836620 1029 96304572 1030 70098028 1031 47772011 1032 29729469 1033 16169505 1034 7027581 1035 1906884 1036 1924180 1037 7124871 1038 16474095 1039 30444645 1040 49181594 1041 72565080 1042 100265172 1043 131789580 1044 166524930 1045 203772283 1046 242777535 1047 282757293 1048 322920780 1049 362488280 1050 400706592 1051 436861920 1052 470290584 1053 500387895 1054 526615495 1055 548507421 1056 565675110 1057 577811520 1058 584694500 1059 586189500 1060 582251670 1061 572927355 1062 558354951 1063 538765045 1064 514479720 1065 485910864 1066 453557280 1067 418000352 1068 379897980 1069 339976455 1070 299019903 1071 257856885 1072 217343698 1073 178343880 1074 141703380 1075 108220812 1076 78612170 1077 53469339 1078 33211695 1079 18030045 1080 7822116 1081 2118760 1082 2137184 1083 7925892 1084 18355380 1085 33976635 1086 54979155 1087 81258562 1088 112475874 1089 148109220 1090 187498740 1091 229885370 1092 274444170 1093 320312811 1094 366615795 1095 412484940 1096 457076620 1097 499586208 1098 539260128 1099 575405880 1100 607400360 1101 634696755 1102 656830251 1103 673422750 1104 684186750 1105 688928500 1106 687550500 1107 680053374 1108 666537102 1109 647201555 1110 622346235 1111 592369080 1112 557764152 1113 519117984 1114 477104320 1115 432476940 1116 386060220 1117 338737035 1118 291433571 1119 245100570 1120 200690490 1121 159130020 1122 121287348 1123 87933538 1124 59697330 1125 37012635 1126 20057955 1127 8686916 1128 2349060 1129 2368660 1130 8797460 1131 20404956 1132 37829595 1133 61312020 1134 90767754 1135 125851110 1136 166011132 1137 210540330 1138 258616930 1139 309341318 1140 361767315 1141 414928878 1142 467862780 1143 519627780 1144 569320752 1145 616090200 1146 659147544 1147 697776520 1148 731340995 1149 759291456 1150 781170390 1151 796616730 1152 805369500 1153 807270750 1154 802267830 1155 790415010 1156 771874411 1157 746916170 1158 715917720 1159 679362024 1160 637834560 1161 592018812 1162 542689980 1163 490706580 1164 436999563 1165 382558540 1166 328414658 1167 275619630 1168 225220380 1169 178228722 1170 135585450 1171 98118174 1172 66492195 1173 41153670 1174 22264276 1175 9626540 1176 2598960 1177 2619785 1178 9744140 1179 22633884 1180 42024956 1181 68216505 1182 101148894 1183 140472486 1184 185608038 1185 235799487 1186 290159870 1187 347711078 1188 407418102 1189 468218387 1190 529046868 1191 588857220 1192 646639812 1193 701436813 1194 752354856 1195 798575624 1196 839364680 1197 874078821 1198 902172194 1199 923201370 1200 936829530 1201 942829875 1202 941088330 1203 931605570 1204 914498354 1205 890000111 1206 858460680 1207 820345064 1208 776231016 1209 726805233 1210 672857892 1211 615275220 1212 555029748 1213 493167857 1214 430794182 1215 369052398 1216 309101870 1217 252089607 1218 199116918 1219 151200126 1220 109224654 1221 73891755 1222 45657116 1223 24660524 1224 10645740 1225 2869685 1226 2891785 1227 10770690 1228 25053700 1229 46585084 1230 75730536 1231 112460754 1232 156425346 1233 207017910 1234 263433093 1235 324716392 1236 389807418 1237 457577302 1238 526860880 1239 596484252 1240 665288268 1241 732148452 1242 795991833 1243 855811110 1244 910676536 1245 959745864 1246 1002272656 1247 1037613214 1248 1065232350 1249 1084708170 1250 1095736005 1251 1098131580 1252 1091833470 1253 1076904850 1254 1053534504 1255 1022037016 1256 982852024 1257 936542376 1258 883790985 1259 825396138 1260 762264972 1261 695404788 1262 625911832 1263 554957130 1264 483768922 1265 413611198 1266 345757797 1267 281461488 1268 221917410 1269 168220206 1270 121314144 1271 81935476 1272 50546244 1273 27258700 1274 11749465 1275 3162510