1 1 2 6 3 7 4 22 5 41 6 28 7 63 8 146 9 161 10 84 11 154 12 406 13 561 14 476 15 210 16 336 17 966 18 1526 19 1631 20 1176 21 462 22 672 23 2058 24 3556 25 4361 26 3976 27 2562 28 924 29 1254 30 4032 31 7434 32 9996 33 10486 34 8568 35 5082 36 1716 37 2211 38 7392 39 14322 40 20580 41 23716 42 22344 43 16842 44 9372 45 3003 46 3718 47 12837 48 25872 49 39102 50 48216 51 49980 52 43512 53 30822 54 16302 55 5005 56 6006 57 21307 58 44352 59 69762 60 90552 61 100548 62 96432 63 79002 64 53262 65 27027 66 8008 67 9373 68 34034 69 72787 70 118272 71 159852 72 186984 73 192276 74 173712 75 135597 76 87802 77 43043 78 12376 79 14196 80 52598 81 115115 82 192192 83 268422 84 327096 85 354564 86 343728 87 296142 88 222222 89 139139 90 66248 91 18564 92 20944 93 78988 94 176358 95 301301 96 432432 97 544698 98 615384 99 629244 100 582120 101 482482 102 350350 103 213213 104 99008 105 27132 106 30192 107 115668 108 262808 109 458003 110 672672 111 870870 112 1017324 113 1084644 114 1058904 115 942942 116 756756 117 534443 118 317408 119 144228 120 38760 121 42636 122 165648 123 382228 124 677768 125 1015378 126 1345344 127 1615614 128 1781604 129 1814274 130 1705704 131 1471470 132 1149148 133 792428 134 460768 135 205428 136 54264 137 59109 138 232560 139 544068 140 979608 141 1493128 142 2018016 143 2480478 144 2812524 145 2963169 146 2906904 147 2648646 148 2224404 149 1696968 150 1146208 151 654228 152 286824 153 74613 154 80598 155 320739 156 759696 157 1386588 158 2145808 159 2950584 160 3699696 161 4294290 162 4652934 163 4723719 164 4492488 165 3986346 166 3271632 167 2445688 168 1622208 169 910860 170 393414 171 100947 172 108262 173 435309 174 1042644 175 1926372 176 3021648 177 4218312 178 5381376 179 6372366 180 7069062 181 7382089 182 7267260 183 6732726 184 5840016 185 4698120 186 3450048 187 2251956 188 1246134 189 531069 190 134596 191 143451 192 582274 193 1408869 194 2631804 195 4178328 196 5911920 197 7656936 198 9225216 199 10441431 200 11165154 201 11308297 202 10846836 203 9825816 204 8356656 205 6605928 206 4775232 207 3072699 208 1678194 209 706629 210 177100 211 187726 212 768614 213 1877029 214 3541524 215 5684154 216 8139600 217 10684296 218 13069056 219 15051036 220 16422406 221 17034017 222 16812796 223 15771756 224 14011536 225 11712456 226 9116352 227 6498114 228 4128054 229 2228149 230 928004 231 230230 232 242880 233 1002386 234 2468774 235 4700619 236 7619304 237 11029158 238 14651280 239 18162936 240 21237216 241 23579556 242 24958934 243 25232207 244 24360336 245 22415316 246 19576656 247 16116408 248 12372192 249 8708574 250 5468694 251 2920379 252 1204280 253 296010 254 310960 255 1292830 256 3209052 257 6161309 258 10077144 259 14730282 260 19779228 261 24814152 262 29405376 263 33149116 264 35707672 265 36842169 266 36436400 267 34510476 268 31223016 269 26860680 270 21814128 271 16540146 272 11510884 273 7153069 274 3782856 275 1545830 276 376740 277 394290 278 1650480 279 4126430 280 7983668 281 13165614 282 19416936 283 26326818 284 33383988 285 40035204 286 45741696 287 50029980 288 52534664 289 53031524 290 51459408 291 47929596 292 42721272 293 36261918 294 29091888 295 21813330 296 15025164 297 9248162 298 4847480 299 1964430 300 475020 301 495495 302 2087280 303 5253430 304 10236380 305 17008684 306 25289880 307 34594098 308 44293788 309 53689383 310 62078016 311 68816748 312 73377304 313 75390224 314 74676784 315 71267196 316 65403624 317 57526623 318 48243888 319 38280858 320 28413924 321 19388908 322 11830280 323 6150430 324 2473380 325 593775 326 617526 327 2616705 328 6626880 329 12997530 330 21747880 331 32579316 332 44926728 333 58031358 334 71022798 335 83001633 336 93117024 337 100635444 338 104997984 339 105864304 340 103141584 341 96996900 342 87851478 343 76355433 344 63342048 345 49761558 346 36595944 347 24758580 348 14985880 349 7732530 350 3087630 351 736281 352 763686 353 3253887 354 8288280 355 16355430 356 27543880 357 41547660 358 57720432 359 75157698 360 92792238 361 109492383 362 124156032 363 135795660 364 143611104 365 147047824 366 145838784 367 140028252 368 129975846 369 116339223 370 100034088 371 82170858 372 63968520 373 46648140 374 31311280 375 18812430 376 9639630 377 3823911 378 906192 379 937657 380 4015746 381 10284183 382 20409480 383 34578180 384 52492440 385 73425660 386 96314064 387 119866593 388 142680538 389 163354191 390 180590592 391 193288368 392 200616864 393 202073424 394 197520960 395 187204017 396 171741570 397 152094943 398 129509688 399 105431172 400 81395160 401 58897020 402 39246480 403 23419305 404 11923002 405 4700871 406 1107568 407 1143528 408 4921126 409 12666591 410 25271064 411 43054830 412 65749320 413 92552460 414 122229360 415 153237546 416 183861678 417 212347135 418 237025152 419 256424532 420 269366496 421 275040144 422 273056448 423 263478852 424 246828582 425 224062839 426 196524328 427 165861234 428 133917960 429 102598860 430 73710000 431 48787830 432 28928718 433 14639751 434 5739216 435 1344904 436 1385824 437 5990936 438 15493366 439 31064481 440 53202240 441 81695250 442 115675560 443 153727860 444 194030760 445 234512278 446 273006734 447 307404097 448 335785632 449 356541612 450 368468064 451 370840176 452 363460272 453 346678332 454 321383062 455 288961673 456 251226976 457 210311310 458 168528360 459 128206260 460 91498680 461 60185034 462 35476686 463 17853241 464 6961856 465 1623160 466 1669536 467 7248296 468 18828656 469 37927911 470 65275056 471 100751742 472 143439660 473 191737260 474 243517560 475 296306010 476 347463116 477 394360967 478 434546112 479 465883572 480 486678312 481 495771408 482 492608592 483 477279012 484 450522072 485 413700287 486 368736368 487 318013410 488 264238260 489 210270060 490 158918760 491 112722246 492 73715796 493 43214031 494 21633536 495 8394056 496 1947792 497 2000152 498 8718688 499 22743336 500 46014416 501 79556106 502 123388272 503 176564934 504 237297060 505 303127110 506 371130760 507 438127690 508 500888388 509 556327772 510 601679232 511 634644612 512 653516856 513 657272700 514 645633072 515 619088932 516 578890312 517 526996470 518 465985520 519 398922810 520 329188860 521 260270010 522 195518232 523 137890998 524 89687836 525 52307416 526 26057856 527 10063592 528 2324784 529 2383689 530 10430112 531 27315464 532 55492976 533 96358416 534 150125808 535 215852742 536 291567276 537 374459085 538 461106360 539 547717170 540 630369740 541 705240536 542 768812352 543 818056932 544 850588200 545 864783081 546 859867344 547 835964052 548 794102232 549 736183448 550 664904240 551 583633050 552 496241460 553 406891485 554 319783464 555 238872942 556 167570004 557 108440976 558 62940416 559 31211048 560 12000912 561 2760681 562 2826726 563 12413247 564 32630752 565 66549560 566 116027296 567 181540464 568 262191552 569 355837482 570 459296838 571 568603035 572 679278600 573 786612190 574 885925040 575 972817384 576 1043388192 577 1094423484 578 1123549686 579 1129349151 580 1111435248 581 1070484492 582 1008223216 583 927366440 584 831507040 585 724954230 586 612521910 587 499269771 588 390203352 589 289943682 590 202382880 591 130349296 592 75314624 593 37186072 594 14239302 595 3262623 596 3336438 597 14701617 598 38783052 599 79388232 600 138942496 601 218267280 602 316563072 603 431536182 604 559621062 605 696260565 606 836215380 607 973881090 608 1103597040 609 1219935640 610 1317964032 611 1393472388 612 1443164646 613 1464808401 614 1457341116 615 1420929972 616 1356982704 617 1268106840 618 1158015040 619 1031374890 620 893602710 621 750602853 622 608456772 623 473069982 624 349790112 625 243015696 626 155823360 627 89650792 628 44084502 629 16815057 630 3838380 631 3920631 632 17331762 633 45874857 634 94232292 635 165520432 636 261004128 637 380048592 638 520240512 639 677623947 640 847008162 641 1022314293 642 1196935740 643 1364093640 644 1517173840 645 1650035640 646 1757285376 647 1834509831 648 1878465666 649 1887221721 650 1860251316 651 1798471752 652 1704228240 653 1581219640 654 1434363840 655 1269601515 656 1093638546 657 913629717 658 736809612 659 570081072 660 419577312 661 290221008 662 185312512 663 106190007 664 52017042 665 19767657 666 4496388 667 4587778 668 20343414 669 54017817 670 111325452 671 196216482 672 310515744 673 453835536 674 623686272 675 815723832 676 1024085062 677 1241773533 678 1461066516 679 1673921340 680 1872365040 681 2048855640 682 2196606720 683 2309869254 684 2384166246 685 2416476601 686 2405365116 687 2351055630 688 2255444400 689 2122050840 690 1955903040 691 1763356140 692 1551842838 693 1329557229 694 1105075972 695 886924632 696 683102112 697 500582544 698 344822016 699 219307242 700 125194902 701 61104057 702 23139948 703 5245786 704 5347056 705 23779678 706 63333270 707 130933047 708 231527352 709 367637886 710 539224224 711 743778288 712 976580352 713 1231061832 714 1499231734 715 1772133363 716 2040305904 717 2294231940 718 2524757040 719 2723471400 720 2883046320 721 2997520218 722 3062530086 723 3075484951 724 3035678184 725 2944335570 726 2804596080 727 2621422440 728 2401439040 729 2152695636 730 1884356838 731 1606319715 732 1328765152 733 1061653032 734 814177056 735 594202224 736 407716848 737 258341622 738 146950902 739 71476119 740 26978328 741 6096454 742 6208384 743 27687218 744 73952788 745 153343281 746 271993512 747 433281618 748 637634844 749 882601104 750 1163110080 751 1471862392 752 1799798000 753 2136605653 754 2471244048 755 2792452572 756 3089235240 757 3351305880 758 3569485920 759 3736048470 760 3845003932 761 3892323281 762 3876095608 763 3796616670 764 3656405220 765 3460143960 766 3214542240 767 2928118284 768 2610899928 769 2274044773 770 1929383456 771 1588893592 772 1264117008 773 965539344 774 701959104 775 479882970 776 302995812 777 171767505 778 83274568 779 31332938 780 7059052 781 7182462 782 32116448 783 86018738 784 178868508 785 318201702 786 508437720 787 750614634 788 1042430004 789 1378502664 790 1750786752 791 2149082936 792 2561603408 793 2975556948 794 3377728368 795 3755033100 796 4095032760 797 4386401370 798 4619334720 799 4785897270 800 4880302196 801 4899120842 802 4841418120 803 4708810470 804 4505443020 805 4237882740 806 3914924832 807 3547310508 808 3147355848 809 2728493768 810 2304734432 811 1890053880 812 1497726384 813 1139623254 814 825509664 815 562381722 816 353898636 817 199979598 818 96652088 819 36257858 820 8145060 821 8280811 822 37121728 823 99684858 824 207846548 825 370787508 826 594181224 827 879845274 828 1225742364 829 1626237459 830 2072534464 831 2553230680 832 3054939888 833 3562945568 834 4061854608 835 4536229068 836 4971179304 837 5352906195 838 5669183520 839 5909773870 840 6066773020 841 6134878596 842 6111579320 843 5997261270 844 5795227620 845 5511628395 846 5155297056 847 4737491388 848 4271537368 849 3772376608 850 3256020768 851 2738920184 852 2237259024 853 1766195739 854 1339075584 855 966651714 856 656362980 857 411730228 858 231948808 859 111773298 860 41811308 861 9366819 862 9515814 863 42761565 864 115116848 865 240642038 866 430438008 867 691676076 868 1027150488 869 1435229334 870 1910100654 871 2442228789 872 3018951936 873 3625165544 874 4244047808 875 4857793248 876 5448328368 877 5997989844 878 6490150758 879 6909784245 880 7243956720 881 7482244770 882 7617071000 883 7643954780 884 7561674120 885 7372334970 886 7081344270 887 6697283229 888 6231677760 889 5698663908 890 5114547648 891 4497260768 892 3865717856 893 3239083848 894 2635967334 895 2073562029 896 1566767664 897 1127332206 898 763069944 899 477224748 900 268064888 901 128815358 902 48055854 903 10737573 904 10900758 905 49098819 906 132492976 907 277647818 908 497894488 909 802179924 910 1194503856 911 1673807850 912 2234202894 913 2865441579 914 3553558008 915 4281613336 916 5030497472 917 5779748128 918 6508357248 919 7195542060 920 7821463734 921 8367881067 922 8818729920 923 9160621470 924 9383253880 925 9479732900 926 9446797360 927 9284945670 928 8998459470 929 8595320643 930 8087018184 931 7488242076 932 6816462528 933 6091394848 934 5334353024 935 4567498936 936 3812999190 937 3092108019 938 2424202704 939 1825807698 940 1309655256 941 883844052 942 551173168 943 308747138 944 147968590 945 55058619 946 12271512 947 12449877 948 56200914 949 152004699 950 319286352 951 573955228 952 927049032 953 1384036836 954 1944632976 955 2602997397 956 3348218874 957 4164995835 958 5034445416 959 5934985056 960 6843242560 961 7734960288 962 8585867136 963 9372498429 964 10072948914 965 10667547891 966 11139448320 967 11475123660 968 11664767400 969 11702590900 970 11587015440 971 11320754445 972 10910781882 973 10368182979 974 9707883864 975 8948257632 976 8110605888 977 7218517152 978 6297106816 979 5372147781 980 4469106642 981 3612107499 982 2822854320 983 2119553436 984 1515890376 985 1020130020 986 634426128 987 354445861 988 169437114 989 62891499 990 13983816 991 14178396 992 64140054 993 173857299 994 366011184 995 659478358 996 1067743320 997 1598046996 998 2251110576 999 3021298566 1000 3897107214 1001 4861884027 1002 5894701176 1003 6971320356 1004 8065199296 1005 9148500768 1006 10193073792 1007 11171383944 1008 12057375414 1009 12827251899 1010 13460166720 1011 13938814890 1012 14249921400 1013 14384620900 1014 14338724400 1015 14112868770 1016 13712544846 1017 13148000019 1018 12434011464 1019 11589526824 1020 10637170368 1021 9602614560 1022 8513819776 1023 7400148756 1024 6291367446 1025 5216550339 1026 4202916432 1027 3274631646 1028 2451625176 1029 1748480916 1030 1173481008 1031 727896862 1032 405643854 1033 193439499 1034 71631384 1035 15890700 1036 16102576 1037 72993444 1038 198270534 1039 418308429 1040 755384784 1041 1225831530 1042 1839006456 1043 2596910316 1044 3494301096 1045 4519180666 1046 5653549902 1047 6874346661 1048 8154496896 1049 9464022876 1050 10771164096 1051 12043476192 1052 13248881184 1053 14356648824 1054 15338293894 1055 16168378149 1056 16825208400 1057 17291424150 1058 17554469400 1059 17606943900 1060 17446829400 1061 17077586526 1062 16508117934 1063 15752593549 1064 14830134144 1065 13764350424 1066 12582736320 1067 11315917536 1068 9996759696 1069 8659344876 1070 7337831046 1071 6065216157 1072 4872037456 1073 3785047266 1074 2825919096 1075 2010052716 1076 1345563912 1077 832564194 1078 462857934 1079 220209429 1080 81360384 1081 18009460 1082 18239760 1083 82843516 1084 225479304 1085 476698299 1086 862661184 1087 1402996518 1088 2109570540 1089 2985978996 1090 4027599576 1091 5222068566 1092 6550067524 1093 7986325347 1094 9500758176 1095 11059684356 1096 12627064296 1097 14165725728 1098 15638543712 1099 17009551944 1100 18244967664 1101 19314116899 1102 20190250080 1103 20851240410 1104 21280158900 1105 21465720900 1106 21402599400 1107 21091600530 1108 20539696716 1109 19759913019 1110 18771062464 1111 17597326824 1112 16267680528 1113 14815157280 1114 13275961776 1115 11688432756 1116 10091868696 1117 8525233899 1118 7025770752 1119 5627553646 1120 4360031676 1121 3246620916 1122 2303422968 1123 1538164782 1124 949475604 1125 526640499 1126 249996384 1127 92166060 1128 20358520 1129 20608420 1130 93778160 1131 255734332 1132 541736664 1133 982363074 1134 1601040672 1135 2412586638 1136 3422554212 1137 4627208586 1138 6013983976 1139 7562296742 1140 9244610284 1141 11027665740 1142 12873808416 1143 14742353556 1144 16590946680 1145 18376883448 1146 20058362016 1147 21595647304 1148 22952131664 1149 24095280286 1150 24997452480 1151 25636591890 1152 25996779900 1153 26068647150 1154 25849638360 1155 25344125730 1156 24563366212 1157 23525298104 1158 22254172864 1159 20780018952 1160 19137936048 1161 17367220332 1162 15510324816 1163 13611663156 1164 11716271112 1165 9868347034 1166 8109701600 1167 6478157686 1168 5005953876 1169 3718219890 1170 2631609288 1171 1753194366 1172 1079750364 1173 597581124 1174 283066336 1175 104141660 1176 22957480 1177 23228205 1178 105890960 1179 289302860 1180 614016648 1181 1115617944 1182 1821891456 1183 2751103278 1184 3911178348 1185 5299583289 1186 6903752856 1187 8701923230 1188 10664257604 1189 12754169064 1190 14929762848 1191 17145334836 1192 19352875752 1193 21503541213 1194 23549056608 1195 25443033000 1196 27142175984 1197 28607373872 1198 29804654880 1199 30706005330 1200 31290042420 1201 31542536025 1202 31456774440 1203 31033769130 1204 30282293580 1205 29218751408 1206 27866869184 1207 26257210056 1208 24426505488 1209 22416804333 1210 20274441264 1211 18048830436 1212 15791095320 1213 13552552104 1214 11383072064 1215 9329358038 1216 7433181756 1217 5729642457 1218 4245523128 1219 2997838998 1220 1992693780 1221 1224582744 1222 676308192 1223 319702460 1224 117386360 1225 25827165 1226 26119990 1227 119281435 1228 326469360 1229 694170260 1230 1263628464 1231 2067607080 1232 3128379408 1233 4456712898 1234 6051640518 1235 7900843951 1236 9981499528 1237 12261461394 1238 14700677264 1239 17252750424 1240 19866577536 1241 22488005484 1242 25061462118 1243 27531525483 1244 29844404128 1245 31949307544 1246 33799690848 1247 35354361680 1248 36578440080 1249 37444164030 1250 37931534550 1251 38028794895 1252 37732738680 1253 37048841830 1254 35991213280 1255 34582359504 1256 32852758400 1257 30840238968 1258 28589164758 1259 26149421403 1260 23575211856 1261 20923667388 1262 18253288144 1263 15622234264 1264 13086497424 1265 10697993306 1266 8502628134 1267 6538407183 1268 4833670248 1269 3405558618 1270 2258840304 1271 1385245288 1272 763490560 1273 360205860 1274 132005510 1275 28989675