0 1 1 1 2 2 3 1 4 5 5 4 6 2 7 1 8 14 9 15 10 10 11 9 12 4 13 2 14 1 15 42 16 56 17 45 18 43 19 34 20 23 21 14 22 9 23 4 24 2 25 1 26 132 27 210 28 196 29 196 30 174 31 156 32 121 33 85 34 59 35 42 36 27 37 14 38 9 39 4 40 2 41 1 42 429 43 792 44 840 45 882 46 842 47 796 48 749 49 627 50 480 51 382 52 289 53 216 54 157 55 101 56 67 57 46 58 27 59 14 60 9 61 4 62 2 63 1 64 1430 65 3003 66 3564 67 3942 68 3990 69 3921 70 3848 71 3681 72 3242 73 2732 74 2267 75 1838 76 1489 77 1189 78 909 79 671 80 494 81 345 82 252 83 173 84 109 85 71 86 46 87 27 88 14 89 9 90 4 91 2 92 1 93 4862 94 11440 95 15015 96 17523 97 18678 98 19042 99 19237 100 19063 101 18478 102 17167 103 15160 104 13126 105 11223 106 9524 107 7989 108 6667 109 5409 110 4222 111 3326 112 2562 113 1939 114 1480 115 1097 116 779 117 550 118 381 119 268 120 181 121 113 122 71 123 46 124 27 125 14 126 9 127 4 128 2 129 1 130 16796 131 43758 132 62920 133 77506 134 86658 135 91608 136 95051 137 96638 138 96472 139 95562 140 91261 141 83559 142 75185 143 66650 144 58448 145 51199 146 44305 147 37870 148 32113 149 26501 150 21603 151 17576 152 14180 153 11278 154 8965 155 6980 156 5326 157 4064 158 3021 159 2227 160 1664 161 1205 162 835 163 586 164 397 165 276 166 185 167 113 168 71 169 46 170 27 171 14 172 9 173 4 174 2 175 1 176 58786 177 167960 178 262548 179 341198 180 399113 181 437294 182 465907 183 484943 184 495006 185 501006 186 501762 187 488471 188 461108 189 426886 190 388998 191 351923 192 316125 193 281598 194 249686 195 219842 196 190940 197 163382 198 138712 199 116554 200 97606 201 81362 202 67083 203 55141 204 44872 205 35820 206 28513 207 22557 208 17614 209 13669 210 10585 211 8098 212 6073 213 4520 214 3305 215 2411 216 1772 217 1261 218 871 219 602 220 405 221 280 222 185 223 113 224 71 225 46 226 27 227 14 228 9 229 4 230 2 231 1 232 208012 233 646646 234 1091740 235 1495286 236 1826396 237 2072928 238 2268266 239 2415634 240 2516956 241 2591990 242 2643891 243 2667514 244 2639875 245 2547451 246 2411273 247 2253062 248 2083491 249 1911957 250 1745442 251 1584965 252 1430160 253 1283498 254 1142180 255 1003098 256 874707 257 757852 258 652563 259 560304 260 478554 261 405599 262 342865 263 287669 264 238469 265 196530 266 161047 267 131430 268 106637 269 85820 270 68758 271 54758 272 43065 273 33651 274 26088 275 20054 276 15303 277 11712 278 8842 279 6525 280 4804 281 3489 282 2519 283 1828 284 1297 285 887 286 610 287 409 288 280 289 185 290 113 291 71 292 46 293 27 294 14 295 9 296 4 297 2 298 1 299 742900 300 2496144 301 4526522 302 6525246 303 8309600 304 9763338 305 10974184 306 11956098 307 12709850 308 13308736 309 13781698 310 14127060 311 14360631 312 14379899 313 14104204 314 13612365 315 12961522 316 12208257 317 11421894 318 10622848 319 9821540 320 9045612 321 8292493 322 7556492 323 6843744 324 6142759 325 5471258 326 4849278 327 4276482 328 3752753 329 3285293 330 2864920 331 2483428 332 2145273 333 1843313 334 1571739 335 1333361 336 1124772 337 944955 338 791765 339 659662 340 546644 341 451766 342 370969 343 301804 344 244782 345 197380 346 158173 347 126238 348 100014 349 78991 350 62164 351 48300 352 37231 353 28542 354 21697 355 16427 356 12452 357 9294 358 6809 359 4988 360 3597 361 2575 362 1864 363 1313 364 895 365 614 366 409 367 280 368 185 369 113 370 71 371 46 372 27 373 14 374 9 375 4 376 2 377 1 378 2674440 379 9657700 380 18721080 381 28361984 382 37606244 383 45708988 384 52780546 385 58824454 386 63789114 387 67919216 388 71363142 389 74147196 390 76391594 391 78104736 392 78881106 393 78420378 394 76817646 395 74278022 396 71120573 397 67596553 398 63823119 399 59960317 400 56098974 401 52258596 402 48482263 403 44784989 404 41139349 405 37538578 406 34047852 407 30705107 408 27579767 409 24694721 410 22022848 411 19580257 412 17360602 413 15328519 414 13484905 415 11813733 416 10292321 417 8927801 418 7713471 419 6636781 420 5693433 421 4871217 422 4149198 423 3520329 424 2978317 425 2508561 426 2100479 427 1750694 428 1453117 429 1202461 430 991352 431 813089 432 663870 433 540649 434 438063 435 352563 436 282589 437 224997 438 178363 439 140783 440 110408 441 86494 442 67448 443 51894 444 39694 445 30182 446 22817 447 17167 448 12904 449 9578 450 6993 451 5096 452 3653 453 2611 454 1880 455 1321 456 899 457 614 458 409 459 280 460 185 461 113 462 71 463 46 464 27 465 14 466 9 467 4 468 2 469 1 470 9694845 471 37442160 472 77261600 473 122816228 474 169357944 475 212792400 476 252412226 477 287776034 478 318314698 479 344684452 480 367476502 481 386844872 482 403316535 483 417219088 484 428457889 485 435867527 486 437719050 487 433825134 488 425109364 489 412612490 490 397346159 491 380263679 492 362033030 493 343133648 494 323976791 495 304790652 496 285670252 497 266761108 498 248028384 499 229304939 500 210917511 501 193144624 502 176121293 503 160081003 504 145088956 505 131106396 506 118169798 507 106219463 508 95161616 509 85007392 510 75681750 511 67089318 512 59254407 513 52158199 514 45762215 515 40042135 516 34944642 517 30415007 518 26394856 519 22828442 520 19685174 521 16925243 522 14492155 523 12360456 524 10506556 525 8903683 526 7524082 527 6340100 528 5323692 529 4453106 530 3715535 531 3088980 532 2554522 533 2105478 534 1729254 535 1414514 536 1153158 537 935894 538 756510 539 610256 540 490306 541 391256 542 310799 543 245538 544 193069 545 151274 546 117960 547 91792 548 71051 549 54354 550 41330 551 31302 552 23557 553 17619 554 13188 555 9762 556 7101 557 5152 558 3689 559 2627 560 1888 561 1325 562 899 563 614 564 409 565 280 566 185 567 113 568 71 569 46 570 27 571 14 572 9 573 4 574 2 575 1 576 35357670 577 145422675 578 318258360 579 529984860 580 759214084 581 985390958 582 1200562576 583 1400144922 584 1579696746 585 1739904389 586 1882479734 587 2007837462 588 2117890204 589 2214351283 590 2297877676 591 2369391801 592 2423774624 593 2452848642 594 2455023013 595 2432138826 596 2387331946 597 2325810040 598 2251717107 599 2168156400 600 2078449358 601 1984875263 602 1888720353 603 1791525379 604 1693989815 605 1596217418 606 1498699612 607 1401076660 608 1303813331 609 1208471907 610 1116157628 611 1027581189 612 943510661 613 864164378 614 789483485 615 719672388 616 654533848 617 593650170 618 537071051 619 484559896 620 435703761 621 390567400 622 349110811 623 311206277 624 276763865 625 245542852 626 217343038 627 191993779 628 169177325 629 148659996 630 130316033 631 113939473 632 99309639 633 86314446 634 74804329 635 64647166 636 55750089 637 47963747 638 41151371 639 35219014 640 30057438 641 25585011 642 21722694 643 18375935 644 15492304 645 13026967 646 10924225 647 9133534 648 7616121 649 6329648 650 5242711 651 4333004 652 3569586 653 2928009 654 2394131 655 1949682 656 1581897 657 1279726 658 1031057 659 827613 660 663389 661 529592 662 419817 663 331501 664 260341 665 203609 666 158840 667 123267 668 95392 669 73507 670 55990 671 42450 672 32042 673 24009 674 17903 675 13372 676 9870 677 7157 678 5188 679 3705 680 2635 681 1892 682 1325 683 899 684 614 685 409 686 280 687 185 688 113 689 71 690 46 691 27 692 14 693 9 694 4 695 2 696 1 697 129644790 698 565722720 699 1308804075 700 2279625795 701 3388961220 702 4540396788 703 5680642990 704 6776389482 705 7797942874 706 8737148366 707 9595056373 708 10370284261 709 11067965048 710 11694687858 711 12254231743 712 12753590531 713 13194366610 714 13555024335 715 13804413508 716 13926565072 717 13919737703 718 13796109043 719 13575055201 720 13273634682 721 12909376955 722 12498670886 723 12053178278 724 11583504025 725 11097712663 726 10600462922 727 10096714025 728 9589585160 729 9078669081 730 8563620228 731 8048016179 732 7536335974 733 7034194030 734 6546922423 735 6077377807 736 5628423499 737 5201796294 738 4797199650 739 4415156306 740 4055613668 741 3716923097 742 3398818459 743 3100947081 744 2821745125 745 2560846435 746 2318311882 747 2093898019 748 1887315460 749 1697748758 750 1524112264 751 1365606374 752 1221378153 753 1090148295 754 970889031 755 862880175 756 765187117 757 676907764 758 597426151 759 526045086 760 462164766 761 405212771 762 354564677 763 309649091 764 269870937 765 234661879 766 203581966 767 176262154 768 152266235 769 131194413 770 112753628 771 96653838 772 82665116 773 70562135 774 60088864 775 51047621 776 43264308 777 36572583 778 30845741 779 25953789 780 21766518 781 18205526 782 15189827 783 12636368 784 10483388 785 8674776 786 7156415 787 5886811 788 4832363 789 3955585 790 3225035 791 2620142 792 2120838 793 1711000 794 1376389 795 1103050 796 881339 797 703026 798 558314 799 440616 800 346353 801 270895 802 211184 803 164144 804 126863 805 97848 806 75143 807 57110 808 43190 809 32494 810 24293 811 18087 812 13480 813 9926 814 7193 815 5204 816 3713 817 2639 818 1892 819 1325 820 899 821 614 822 409 823 280 824 185 825 113 826 71 827 46 828 27 829 14 830 9 831 4 832 2 833 1 834 477638700 835 2203961430 836 5374365840 837 9775825470 838 15067126350 839 20822669810 840 26745284051 841 32629742948 842 38295803780 843 43652749090 844 48666178238 845 53306160068 846 57573558168 847 61484948440 848 65052202833 849 68304007212 850 71262380646 851 73923329630 852 76220417473 853 78016888269 854 79205655201 855 79757842586 856 79698800146 857 79089519046 858 78008816906 859 76536667434 860 74747594890 861 72711807468 862 70485535575 863 68111949578 864 65631692751 865 63075880660 866 60462026603 867 57805508592 868 55115539427 869 52389410794 870 49638974884 871 46886960806 872 44156361937 873 41474911354 874 38864146617 875 36336631419 876 33905816580 877 31579864275 878 29358995646 879 27245621007 880 25240387518 881 23338842088 882 21539160217 883 19838520656 884 18232373582 885 16720130969 886 15300843485 887 13973192863 888 12736970893 889 11590084033 890 10528594668 891 9548426026 892 8645310844 893 7814823089 894 7052179639 895 6352491627 896 5711821811 897 5126561619 898 4592201502 899 4105262613 900 3663058656 901 3262526297 902 2900588365 903 2574346435 904 2280991606 905 2017717991 906 1781816906 907 1570633035 908 1381782020 909 1213470682 910 1063765356 911 930607483 912 812476307 913 707919123 914 615588005 915 534342221 916 462996054 917 400409415 918 345638070 919 297767110 920 255991035 921 219665605 922 188120040 923 160722246 924 137002627 925 116528146 926 98908520 927 83786913 928 70818852 929 59720221 930 50251250 931 42185808 932 35338448 933 29538887 934 24623168 935 20471703 936 16976103 937 14039029 938 11579273 939 9528224 940 7819264 941 6398680 942 5226741 943 4258204 944 3454831 945 2793837 946 2251441 947 1808553 948 1448975 949 1157127 950 921137 951 731845 952 579162 953 455482 954 356916 955 278467 956 216484 957 167740 958 129319 959 99484 960 76263 961 57850 962 43642 963 32778 964 24477 965 18195 966 13536 967 9962 968 7209 969 5212 970 3717 971 2639 972 1892 973 1325 974 899 975 614 976 409 977 280 978 185 979 113 980 71 981 46 982 27 983 14 984 9 985 4 986 2 987 1 988 1767263190 989 8597496600 990 22039614300 991 41804551830 992 66736461555 993 95071819050 994 125322962695 995 156351068305 996 187137356906 997 217023778166 998 245646504545 999 272724721656 1000 298130426965 1001 321843696310 1002 343860373045 1003 364261912571 1004 383143074884 1005 400540642474 1006 416490153144 1007 430742413911 1008 442674278684 1009 451758832228 1010 457729153365 1011 460534759530 1012 460368569882 1013 457534639294 1014 452357703030 1015 445208176256 1016 436430644279 1017 426305852657 1018 415107018308 1019 403068827081 1020 390357887140 1021 377127555338 1022 363497428990 1023 349536990054 1024 335302783579 1025 320808532474 1026 306086633079 1027 291241192968 1028 276392905514 1029 261655856023 1030 247151635473 1031 232979413153 1032 219202083851 1033 205879045164 1034 193051164613 1035 180730333116 1036 168930853916 1037 157656154481 1038 146892754903 1039 136638861761 1040 126885374976 1041 117610594158 1042 108810508105 1043 100486204139 1044 92634403737 1045 85254627550 1046 78340323869 1047 71878513556 1048 65855268756 1049 60251065646 1050 55044569032 1051 50217753121 1052 45747684512 1053 41611308988 1054 37791497851 1055 34269288955 1056 31024142624 1057 28040110103 1058 25302079116 1059 22795340003 1060 20506457330 1061 18420399290 1062 16521961904 1063 14798207695 1064 13235794717 1065 11820968928 1066 10541578315 1067 9385865506 1068 8343686947 1069 7406050059 1070 6563076904 1071 5806162580 1072 5128229790 1073 4522181313 1074 3981380690 1075 3499974771 1076 3072176446 1077 2692424363 1078 2355905804 1079 2058056738 1080 1794802602 1081 1562770400 1082 1358517928 1083 1178767203 1084 1020953075 1085 882658135 1086 761741795 1087 656326131 1088 564532130 1089 484714339 1090 415456738 1091 355427873 1092 303486659 1093 258696786 1094 220110230 1095 186869928 1096 158335683 1097 133888523 1098 112979012 1099 95152683 1100 79968388 1101 67062490 1102 56127737 1103 46874112 1104 39067588 1105 32499150 1106 26963586 1107 22310854 1108 18416044 1109 15161591 1110 12451468 1111 10203589 1112 8339522 1113 6798663 1114 5533149 1115 4490539 1116 3630026 1117 2925330 1118 2349587 1119 1881490 1120 1503213 1121 1197022 1122 950005 1123 752707 1124 594037 1125 466042 1126 364484 1127 283767 1128 220080 1129 170196 1130 130955 1131 100604 1132 77003 1133 58302 1134 43926 1135 32962 1136 24585 1137 18251 1138 13572 1139 9978 1140 7217 1141 5216 1142 3717 1143 2639 1144 1892 1145 1325 1146 899 1147 614 1148 409 1149 280 1150 185 1151 113 1152 71 1153 46 1154 27 1155 14 1156 9 1157 4 1158 2 1159 1 1160 6564120420 1161 33578000610 1162 90273714300 1163 178302526710 1164 294552962880 1165 432261962970 1166 584577036930 1167 745660349830 1168 910081936320 1169 1073778531070 1170 1234071333257 1171 1388880533266 1172 1536889981831 1173 1677420396098 1174 1810033307418 1175 1934738445631 1176 2051762118594 1177 2161227718530 1178 2263410808429 1179 2358485604484 1180 2445345678385 1181 2521468409481 1182 2584241921969 1183 2631779864662 1184 2663298175835 1185 2679125427019 1186 2680191311877 1187 2667857255417 1188 2643738975212 1189 2609391790120 1190 2566345695887 1191 2516052164799 1192 2459707074416 1193 2398385456357 1194 2333042457876 1195 2264397560253 1196 2193044485700 1197 2119458465319 1198 2043909420512 1199 1966530125500 1200 1887553368536 1201 1807353372077 1202 1726470773576 1203 1645552219892 1204 1565162638432 1205 1485831006211 1206 1408041333591 1207 1332125290111 1208 1258348348102 1209 1186922911014 1210 1117951522966 1211 1051516714354 1212 987670144441 1213 926374980905 1214 867614913306 1215 811384297212 1216 757615176831 1217 706271741729 1218 657365498660 1219 610900915179 1220 566881921501 1221 525298968654 1222 486112879525 1223 449272011228 1224 414706309626 1225 382323902840 1226 352034346424 1227 323747638560 1228 297357616694 1229 272761161322 1230 249871422374 1231 228598649161 1232 208848395637 1233 190538484202 1234 173591475524 1235 157936811729 1236 143508475519 1237 130233326633 1238 118038264148 1239 106852838454 1240 96608139364 1241 87239157474 1242 78681776569 1243 70872397341 1244 63753811641 1245 57275388088 1246 51387066645 1247 46040986212 1248 41194781282 1249 36807870039 1250 32843313338 1251 29267128062 1252 26045943085 1253 23149331289 1254 20548976674 1255 18216845863 1256 16127673820 1257 14258601357 1258 12588346511 1259 11098485673 1260 9771801552 1261 8591148038 1262 7541777923 1263 6610829905 1264 5786229595 1265 5057282681 1266 4414080723 1267 3847151499 1268 3348162065 1269 2909671634 1270 2524751629 1271 2187359183 1272 1892267458 1273 1634493357 1274 1409460549 1275 1213384988 1276 1042856236 1277 894854916 1278 766649811 1279 655724845 1280 559907272 1281 477297967 1282 406163532 1283 345022371 1284 292612933 1285 247733954 1286 209331891 1287 176550209 1288 148599891 1289 124824496 1290 104659168 1291 87574989 1292 73135184 1293 60960379 1294 50706973 1295 42102160 1296 34892493 1297 28840013 1298 23777470 1299 19557359 1300 16046312 1301 13135234 1302 10729456 1303 8743294 1304 7107610 1305 5766984 1306 4666624 1307 3762112 1308 3023827 1309 2422685 1310 1935825 1311 1543157 1312 1225904 1313 970876 1314 767579 1315 604593 1316 473610 1317 369784 1318 287363 1319 222536 1320 171832 1321 132075 1322 101344 1323 77455 1324 58586 1325 44110 1326 33070 1327 24641 1328 18287 1329 13588 1330 9986 1331 7221 1332 5216 1333 3717 1334 2639 1335 1892 1336 1325 1337 899 1338 614 1339 409 1340 280 1341 185 1342 113 1343 71 1344 46 1345 27 1346 14 1347 9 1348 4 1349 2 1350 1