0 1 1 1 2 1 3 1 4 2 5 1 6 1 7 4 8 3 9 1 10 1 11 6 12 9 13 4 14 1 15 1 16 9 17 19 18 16 19 5 20 1 21 1 22 12 23 38 24 44 25 25 26 6 27 1 28 1 29 16 30 66 31 111 32 85 33 36 34 7 35 1 36 1 37 20 38 110 39 240 40 260 41 146 42 49 43 8 44 1 45 1 46 25 47 170 48 485 49 676 50 526 51 231 52 64 53 9 54 1 55 1 56 30 57 255 58 900 59 1615 60 1602 61 959 62 344 63 81 64 10 65 1 66 1 67 36 68 365 69 1590 70 3515 71 4432 72 3353 73 1618 74 489 75 100 76 11 77 1 78 1 79 42 80 511 81 2660 82 7189 83 11102 84 10563 85 6392 86 2571 87 670 88 121 89 12 90 1 91 1 92 49 93 693 94 4291 95 13825 96 25893 97 29989 98 22618 99 11331 100 3895 101 891 102 144 103 13 104 1 105 1 106 56 107 924 108 6664 109 25382 110 56448 111 78736 112 71864 113 44529 114 18952 115 5676 116 1156 117 169 118 14 119 1 120 1 121 64 122 1204 123 10066 124 44590 125 116620 126 192304 127 210079 128 156681 129 81940 130 30228 131 8009 132 1469 133 196 134 15 135 1 136 1 137 72 138 1548 139 14784 140 75600 141 229320 142 442596 143 569088 144 505224 145 316480 146 142648 147 46344 148 10998 149 1834 150 225 151 16 152 1 153 1 154 81 155 1956 156 21246 157 123984 158 432600 159 965244 160 1446300 161 1504936 162 1116688 163 600248 164 237095 165 68718 166 14756 167 2255 168 256 169 17 170 1 171 1 172 90 173 2445 174 29880 175 197730 176 785736 177 2009916 178 3470112 179 4190844 180 3630560 181 2301640 182 1079948 183 378911 184 99022 185 19405 186 2736 187 289 188 18 189 1 190 1 191 100 192 3015 193 41295 194 307242 195 1380996 196 4013604 197 7918956 198 10983996 199 11003312 200 8114920 201 4473327 202 1857843 203 585508 204 139203 205 25076 206 3281 207 324 208 19 209 1 210 1 211 110 212 3685 213 56100 214 466785 215 2355408 216 7724376 217 17271936 218 27295224 219 31306880 220 26608472 221 17007288 222 8269638 223 3075242 224 878725 225 191504 226 31909 227 3894 228 361 229 20 230 1 231 1 232 121 233 4455 234 75130 235 694485 236 3911853 237 14375592 238 36184797 239 64642776 240 84233600 241 81731992 242 60017959 243 33736326 244 14642278 245 4922795 246 1285524 247 258485 248 40053 249 4579 250 400 251 21 252 1 253 1 254 132 255 5346 256 99220 257 1014343 258 6340158 259 25961397 260 73084968 261 146634939 262 215469056 263 236886232 264 198051372 265 127537787 266 63815402 267 24970347 268 7652464 269 1838737 270 343044 271 49666 272 5340 273 441 274 22 275 1 276 1 277 144 278 6358 279 129481 280 1456235 281 10052680 282 45613491 283 142820172 284 319844019 285 526657340 286 651395096 287 615522415 288 450154055 289 257375860 290 115812805 291 41202442 292 11591297 293 2577864 294 448438 295 60915 296 6181 297 484 298 23 299 1 300 1 301 156 302 7514 303 167024 304 2058628 305 15619890 306 78167089 307 270795096 308 673286471 309 1235031512 310 1708068076 311 1811751240 312 1494051390 313 967870190 314 496473715 315 202655792 316 66031723 317 17157132 318 3549922 319 578304 320 73976 321 7106 322 529 323 24 324 1 325 1 326 169 327 8814 328 213291 329 2868580 330 23827518 331 130916071 332 499493566 333 1371912399 334 2788952595 335 4288729588 336 5076297525 337 4689178950 338 3417889060 339 1982196765 340 920355232 341 343348507 342 103108707 343 24876358 344 4810345 345 736680 346 89034 347 8119 348 576 349 25 350 1 351 1 352 182 353 10283 354 269724 355 3945305 356 35733698 357 214701487 358 898283672 359 2713357361 360 6083781990 361 10350088463 362 13596477908 363 13988247585 364 11398620170 365 7422970175 366 3888938512 367 1646981675 368 565195754 369 157296877 370 35403860 371 6423935 372 928026 373 106283 374 9224 375 625 376 26 377 1 378 1 379 196 380 11921 381 338156 382 5360173 383 52757068 384 345333417 385 1578238948 386 5221059129 387 12855795524 388 24084919573 389 34944810056 390 39831166973 391 36083563180 392 26221791601 393 15397200612 394 7344182971 395 2855829372 396 906637383 397 234976516 398 49545275 399 8465864 400 1157245 401 125926 402 10425 403 676 404 27 405 1 406 1 407 210 408 13755 409 420420 410 7201285 411 76764870 412 545572391 413 2713708712 414 9794979909 415 26380232450 416 54197919919 417 86464325532 418 108676181289 419 108893445598 420 87823237815 421 57447099056 422 30657927551 423 13403979342 424 4813665789 425 1420811660 426 344402499 427 68281686 428 11022727 429 1429704 430 148175 431 11726 432 729 433 28 434 1 435 1 436 225 437 15785 438 518805 439 9573473 440 110204185 441 847670369 442 4573802311 443 17949312381 444 52682853509 445 118236473069 446 206566989213 447 285061285197 448 314482428197 449 280092245977 450 203009839166 451 120495746479 452 58848497271 453 23724190191 454 7908793891 455 2179980439 456 496122099 457 92796881 458 14193646 459 1751255 460 173251 461 13131 462 784 463 29 464 1 465 1 466 240 467 18040 468 635600 469 12604060 470 156233168 471 1296813336 472 7566952016 473 32182698054 474 102592558640 475 250631838808 476 477721920832 477 720978837072 478 872064511528 479 853906598060 480 682460111088 481 448161715841 482 243066268176 483 109295306184 484 40840822640 485 12695865700 486 3280964236 487 703459186 488 124507304 489 18091425 490 2128256 491 201384 492 14644 493 841 494 30 495 1 496 1 497 256 498 20520 499 773620 500 16442860 501 218910888 502 1955465512 503 12304066762 504 56542636566 505 195155974520 506 517263909448 507 1071979347816 508 1762897766864 509 2328941422472 510 2496909955860 511 2190915281263 512 1584252872497 513 949299350472 514 473363718936 515 197015797900 516 68556316500 517 19953736044 518 4851751422 519 983071521 520 165094825 521 22843756 522 2567592 523 232813 524 16269 525 900 526 31 527 1 528 1 529 272 530 23256 531 935680 532 21269312 533 303387168 534 2909116432 535 19685788928 536 97476148224 537 363203464832 538 1041284879648 539 2338803389728 540 4177113982808 541 6005937669448 542 7024055141332 543 6739612655488 544 5343430307552 545 3520997964288 546 1937179849344 547 892932907904 548 345629732480 549 112463371836 550 30759238830 551 7059462704 552 1355588170 553 216542456 554 28594476 555 3076696 556 267786 557 18010 558 961 559 32 560 1 561 1 562 289 563 26248 564 1125196 565 27292480 566 416170336 567 4273430896 568 31023074512 569 165089135744 570 662277206240 571 2047946202016 572 4970603674140 573 9611427117240 574 14991786476240 575 19060361141740 576 19926056156936 577 17254393464736 578 12450670262512 579 7523543773824 580 3821576145040 581 1636219375616 582 591503131604 583 180645044418 584 46580222956 585 10119869850 586 1846334386 587 281173140 588 35504875 589 3663570 590 306560 591 19871 592 1024 593 33 594 1 595 1 596 306 597 29529 598 1345584 599 34759764 600 565394976 601 6203516784 602 48200317056 603 274991494896 604 1184705810496 605 3940974459136 606 10307775831600 607 21517483457340 608 36300176436760 609 50012807145156 610 56775218133376 611 53503724030584 612 42117780547296 613 27837675987056 614 15512019399104 615 7310211912816 616 2919775402236 617 989549241794 618 284598136944 619 69391685390 620 14308686236 621 2486151630 622 361691740 623 43755055 624 4336806 625 349401 626 21856 627 1089 628 34 629 1 630 1 631 324 632 33099 633 1600941 634 43956900 635 761191320 636 8905310736 637 73895908176 638 450959627504 639 2081478340800 640 7430340686912 641 20889419455580 642 46950182074380 643 85426129407920 644 127169285656700 645 156280323660712 646 159754565216696 647 136712511788416 648 98465727677264 649 59948227940800 650 30957949877680 651 13594898591604 652 5085056139694 653 1621226607856 654 440436485150 655 101819387176 656 19974866250 657 3312320725 658 461230355 659 53545340 660 5105607 661 396584 662 23969 663 1156 664 35 665 1 666 1 667 342 668 36993 669 1895364 670 55218465 671 1016054640 672 12650077944 673 111875127552 674 728742326016 675 3595733468480 676 13742524430272 677 41428356406112 678 100001724981560 679 195732951884680 680 313970851791940 681 416496000592512 682 460437626272576 683 426978317747232 684 333968359461936 685 221335640191040 686 124751961636400 687 59969653773436 688 24636858090518 689 8660065524944 690 2605414170750 691 670441705076 692 147315936366 693 27556170880 694 4369596460 695 583397090 696 65097737 697 5979808 698 448393 699 26214 700 1225 701 36 702 1 703 1 704 361 705 41211 706 2233716 707 68927877 708 1345345065 709 17792026056 710 167378693670 711 1161430314624 712 6113386136672 713 24961048596352 714 80506484973084 715 208220415137592 716 437345409342520 717 754012828856700 718 1076818864444532 719 1283797789886720 720 1286252573049072 721 1089134874960144 722 783107265828016 723 479999578556400 724 251590432238244 725 113031591890330 726 43595867999331 727 14446773919150 728 4113010783726 729 1005041460762 730 210374972311 731 37597277940 732 5711362284 733 732328407 734 78657448 735 6969897 736 505121 737 28595 738 1296 739 37 740 1 741 1 742 380 743 45790 744 2620860 745 85529925 746 1767787398 747 24790393089 748 247630306608 749 1826967090426 750 10238664440960 751 44570033198240 752 153472444312368 753 424377892713036 754 954350045806472 755 1764241639097980 756 2705735370381632 757 3469781610176812 758 3745717426486464 759 3423621870191328 760 2662418587852160 761 1768810289766464 762 1007277240660636 763 492964741467322 764 207734438653304 765 75464604943675 766 23643309669176 767 6386305604004 768 1485309466228 769 296789790561 770 50770737350 771 7400914053 772 912745184 773 94494433 774 8087036 775 567070 776 31116 777 1369 778 38 779 1 780 1 781 400 782 50730 783 3062515 784 105530769 785 2306135868 786 34236009351 787 362498763339 788 2838536066634 789 16905545442248 790 78309664560160 791 287315709025372 792 847649097196668 793 2036548730921008 794 4027855299911492 795 6618442205474532 796 9107106536797868 797 10565964561081312 798 10396503353564832 799 8719485881170816 800 6259798700690624 801 3860336068814324 802 2050776242954486 803 940558165038421 804 372979396564035 805 127991435115076 806 38012505422076 807 9764400746929 808 2166097393269 809 413963509012 810 67901094683 811 9512882116 812 1130012609 813 112905024 814 9343082 815 634551 816 33781 817 1444 818 39 819 1 820 1 821 420 822 56070 823 3564400 824 129512740 825 2987838882 826 46884156249 827 525350226024 828 4358813658021 829 27540260294480 830 135505241958328 831 528741378455328 832 1661083470465848 833 4255194052114712 834 8985014916346620 835 15783742137495424 836 23251768628624752 837 28923292151085312 838 30561007680035328 839 27570053426360960 840 21328205189054400 841 14200874614927836 842 8162737313349006 843 4060327212239904 844 1750930036344800 845 655340399410736 846 213003163940544 847 60111548578984 848 14716243039486 849 3119926764690 850 571278696085 851 89992529824 852 12134801349 853 1390204036 854 134213590 855 10750608 856 707884 857 36594 858 1521 859 40 860 1 861 1 862 441 863 61810 864 4133185 865 158134340 866 3845909662 867 63693721983 868 754143623388 869 6619332586989 870 44295878219165 871 231106286476328 872 957358217279920 873 3196825516955096 874 8715097336711888 875 19608186361490500 876 36749371223240584 877 57835237413954992 878 76962900076936224 879 87122579945693952 880 84333755698166320 881 70119391434583360 882 50268544794000564 883 31171781422712802 884 16763430645615046 885 7833908665353200 886 3185942660942236 887 1128537257347152 888 348275399368783 889 93601347394214 890 21883142721600 891 4441788924235 892 780535262816 893 118260382053 894 15368839069 895 1700168930 896 158774253 897 12322924 898 787398 899 39559 900 1600 901 41 902 1 903 1 904 462 905 67991 906 4775540 907 192147571 908 4919796882 909 85875058423 910 1072822165272 911 9946600712521 912 70387475490002 913 388778977671733 914 1706927446721184 915 6047902293288648 916 17514831043013192 917 41911322845534828 918 83642955655336064 919 140345901462402760 920 199379371290845504 921 241274887413419808 922 250028759141643584 923 222894522827201680 924 171611153735710876 925 114491646810765570 926 66371935967668304 927 33507466339615410 928 14756258985104936 929 5675261712499356 930 1907331174473116 931 560143962107191 932 143658896680174 933 32133028960765 934 6255023448544 935 1056466364965 936 154166958166 937 19333691083 938 2067605028 939 186972655 940 14074098 941 873431 942 42680 943 1681 944 42 945 1 946 1 947 484 948 74613 949 5499186 950 232397935 951 6256509336 952 114946539169 953 1513078193638 954 14797021708161 955 110566652150020 956 645543823093831 957 2999164566013149 958 11257049547063528 959 34573130651951416 960 87834212271972180 961 186319835181069736 962 332689535758795144 963 503570446582966848 964 650110203036252256 965 719685603942522640 966 686354714448399696 967 566176981882987284 968 405368746859464558 969 252641267650945926 970 137388723259116850 971 65314360927074376 972 27181738019592900 973 9911422237494715 974 3167625577302795 975 887108249262780 976 217521540837411 977 46629120930456 978 8718470067717 979 1417343070804 980 199462046385 981 24166656450 982 2501134843 983 219227776 984 16018977 985 966330 986 45961 987 1764 988 43 989 1 990 1 991 506 992 81719 993 6311844 994 279844565 995 7911740606 996 152802944371 997 2116568593304 998 21803280341799 999 171787175670550 1000 1058658387981821 1001 5196858971920316 1002 20631293352186309 1003 67089988236570824 1004 180660376887415460 1005 406640950327789696 1006 771310333315199696 1007 1241622062881437504 1008 1706776663718445664 1009 2014370325239985920 1010 2050825113151628576 1011 1808544616244966556 1012 1386379019285551094 1013 926618527288584224 1014 541359296885452720 1015 277030659258679976 1016 124370035914359940 1017 49037961888550600 1018 16992257737239330 1019 5175169243687962 1020 1384749021552621 1021 325198733266464 1022 66916185251421 1023 12035116459986 1024 1885679627307 1025 256228585780 1026 30025901857 1027 3010386638 1028 255993803 1029 18173208 1030 1066451 1031 49406 1032 1849 1033 44 1034 1 1035 1 1036 529 1037 89309 1038 7222391 1039 335560225 1040 9951303901 1041 201795672309 1042 2937691184824 1043 31835471536671 1044 264131019871675 1045 1715729541829831 1046 8886395885375984 1047 37259199038353409 1048 128092064916708781 1049 365027979544822300 1050 870407566742337021 1051 1750851826072286224 1052 2992213909568825184 1053 4371742674103948576 1054 5490415194442075600 1055 5955553526810419616 1056 5603016452416464884 1057 4588634961232384954 1058 3281455739236094701 1059 2054585478296906400 1060 1128787519462195996 1061 545121855927507420 1062 231707598537967195 1063 86762122988017890 1064 28631303754257910 1065 8326050861759603 1066 2132371513528716 1067 480394842866301 1068 95028112552509 1069 16462494358905 1070 2489052304227 1071 326933968733 1072 37092926833 1073 3606079997 1074 297762050 1075 20553259 1076 1174159 1077 53019 1078 1936 1079 45 1080 1 1081 1 1082 552 1083 97428 1084 8239704 1085 400754530 1086 12452566896 1087 264828788312 1088 4047032521928 1089 46081179478719 1090 402086029157560 1091 2749430775082596 1092 15004553309034132 1093 66350817325875693 1094 240805347909767854 1095 725140821864454065 1096 1828940120460072656 1097 3895332930181289747 1098 7055957367966895488 1099 10938327795845552704 1100 14592114105404166720 1101 16832879522438161296 1102 16862255688466804572 1103 14723198325957422698 1104 11241308553183991224 1105 7525920390663264875 1106 4428340763664414896 1107 2294504354429056656 1108 1048457887280182300 1109 422955721367527915 1110 150731441309351610 1111 47464554968298723 1112 13203187040328672 1113 3241893258026577 1114 701695940665416 1115 133621184984100 1116 22325109440472 1117 3261046014194 1118 414487482616 1119 45575241348 1120 4300116120 1121 345062929 1122 23176440 1123 1289828 1124 56804 1125 2025 1126 46 1127 1 1128 1 1129 576 1130 106076 1131 9373926 1132 476773946 1133 15506261716 1134 345470911016 1135 5535642276241 1136 66149640121191 1137 606295473208876 1138 4358727463176636 1139 25031307611195861 1140 116585538640030161 1141 446067207698569436 1142 1417407635672838751 1143 3775885991425343816 1144 8502131846724988291 1145 16297854766839408216 1146 26764382518309575616 1147 37862841648216930096 1148 46368062446302612176 1149 49367680487602949076 1150 45869664715876656326 1151 37316487352383325051 1152 26656837180507376675 1153 16761289799245605796 1154 9295673506468175232 1155 4554516388935998191 1156 1973949121666298135 1157 757417731735113308 1158 257417707205993853 1159 77492229396856602 1160 20654290316766513 1161 4869628235652624 1162 1014084511933836 1163 186138130402662 1164 30029226630602 1165 4242344199692 1166 522304426332 1167 55709267667 1168 5105672969 1169 398467972 1170 26060924 1171 1413841 1172 60765 1173 2116 1174 47 1175 1 1176 1 1177 600 1178 115300 1179 10635200 1180 565128400 1181 19218294920 1182 448088021700 1183 7520289392000 1184 94206487524600 1185 905935865718400 1186 6839225983739160 1187 41280102006843400 1188 202250662870016150 1189 814731776464562650 1190 2728119155608588025 1191 7665353949803577840 1192 18221479838096829275 1193 36909278552697140400 1194 64110622775537019400 1195 96025426579238678400 1196 124635662175483220480 1197 140795110550951275100 1198 138959502316943571550 1199 120228538937637813200 1200 91457891812391213550 1201 61323771180207359096 1202 36321419056786531164 1203 19036764789421281448 1204 8841592300797443686 1205 3642720296897072910 1206 1332194709761488435 1207 432589596026415456 1208 124707657897154827 1209 31898420187487704 1210 7231779091163940 1211 1450858900816896 1212 257008875825440 1213 40080371984080 1214 5481978846760 1215 654377467680 1216 67763478652 1217 6037305392 1218 458591904 1219 29225768 1220 1546590 1221 64906 1222 2209 1223 48 1224 1 1225 1 1226 625 1227 125100 1228 12035050 1229 667491280 1230 23712007320 1231 577997196700 1232 10149914694700 1233 133146951557400 1234 1341926471316640 1235 10626210803273560 1236 67330719510168375 1237 346598114175139150 1238 1468182388737276100 1239 5174003708518042935 1240 15313249578506963740 1241 38376951564796472875 1242 82027977600175024275 1243 150485299644987400600 1244 238285972364523842020 1245 327286811815837130880 1246 391644446727177229300 1247 409899356051217672850 1248 376507587288215476800 1249 304430402408166328126 1250 217248162220466287246 1251 137136348483987319236 1252 76717936745422655809 1253 38094055454035954494 1254 16809370980841718208 1255 6596996795845374445 1256 2303843923702553824 1257 716013311561231211 1258 197982908821711611 1259 48670239737910252 1260 10624641956104626 1261 2056049246524640 1262 351894831327040 1263 53103955334040 1264 7038758932700 1265 815355838652 1266 82041785028 1267 7111050352 1268 526094767 1269 32690934 1270 1688476 1271 69231 1272 2304 1273 49 1274 1 1275 1 1276 650 1277 135525 1278 13585000 1279 785729750 1280 29130433800 1281 741647643100 1282 13613494637600 1283 186817354623900 1284 1971231917512000 1285 16355197317001400 1286 108668982367908300 1287 587059168352988175 1288 2611858801401897950 1289 9675295540830277125 1290 30125251423598626000 1291 79491936473224876175 1292 179050021022798000550 1293 346453979159496742075 1294 579134405976038930000 1295 840509347316810663100 1296 1063797910809892505500 1297 1178791236165320719250 1298 1147594110653036886000 1299 984571050375494111950 1300 746415994954294400372 1301 501189077633407170714 1302 298656279467615692084 1303 158201026762308603621 1304 74591729179316406130 1305 31336463289144362203 1306 11737543848325864736 1307 3921151683270055531 1308 1168272216477911934 1309 310303295459938095 1310 73413606484174728 1311 15450759264278750 1312 2887438976154800 1313 477984565038760 1314 69869464701440 1315 8982897143152 1316 1010632997752 1317 98887184452 1318 8344537388 1319 601684095 1320 36477310 1321 1839909 1322 73744 1323 2401 1324 50 1325 1