0 1 1 2 2 1 3 5 4 3 5 1 6 12 7 8 8 4 9 1 10 29 11 20 12 12 13 5 14 1 15 70 16 49 17 32 18 17 19 6 20 1 21 169 22 119 23 81 24 49 25 23 26 7 27 1 28 408 29 288 30 200 31 130 32 72 33 30 34 8 35 1 36 985 37 696 38 488 39 330 40 202 41 102 42 38 43 9 44 1 45 2378 46 1681 47 1184 48 818 49 532 50 304 51 140 52 47 53 10 54 1 55 5741 56 4059 57 2865 58 2002 59 1350 60 836 61 444 62 187 63 57 64 11 65 1 66 13860 67 9800 68 6924 69 4867 70 3352 71 2186 72 1280 73 631 74 244 75 68 76 12 77 1 78 33461 79 23660 80 16724 81 11791 82 8219 83 5538 84 3466 85 1911 86 875 87 312 88 80 89 13 90 1 91 80782 92 57121 93 40384 94 28515 95 20010 96 13757 97 9004 98 5377 99 2786 100 1187 101 392 102 93 103 14 104 1 105 195025 106 137903 107 97505 108 68899 109 48525 110 33767 111 22761 112 14381 113 8163 114 3973 115 1579 116 485 117 107 118 15 119 1 120 470832 121 332928 122 235408 123 166404 124 117424 125 82292 126 56528 127 37142 128 22544 129 12136 130 5552 131 2064 132 592 133 122 134 16 135 1 136 1136689 137 803760 138 568336 139 401812 140 283828 141 199716 142 138820 143 93670 144 59686 145 34680 146 17688 147 7616 148 2656 149 714 150 138 151 17 152 1 153 2744210 154 1940449 155 1372096 156 970148 157 685640 158 483544 159 338536 160 232490 161 153356 162 94366 163 52368 164 25304 165 10272 166 3370 167 852 168 155 169 18 170 1 171 6625109 172 4684659 173 3312545 174 2342244 175 1655788 176 1169184 177 822080 178 571026 179 385846 180 247722 181 146734 182 77672 183 35576 184 13642 185 4222 186 1007 187 173 188 19 189 1 190 15994428 191 11309768 192 7997204 193 5654789 194 3998032 195 2824972 196 1991264 197 1393106 198 956872 199 633568 200 394456 201 224406 202 113248 203 49218 204 17864 205 5229 206 1180 207 192 208 20 209 1 210 38613965 211 27304196 212 19306972 213 13651993 214 9652821 215 6823004 216 4816236 217 3384370 218 2349978 219 1590440 220 1028024 221 618862 222 337654 223 162466 224 67082 225 23093 226 6409 227 1372 228 212 229 21 230 1 231 93222358 232 65918161 233 46611168 234 32958965 235 23304814 236 16475825 237 11639240 238 8200606 239 5734348 240 3940418 241 2618464 242 1646886 243 956516 244 500120 245 229548 246 90175 247 29502 248 7781 249 1584 250 233 251 22 252 1 253 225058681 254 159140519 255 112529329 256 79570133 257 56263779 258 39780639 259 28115065 260 19839846 261 13934954 262 9674766 263 6558882 264 4265350 265 2603402 266 1456636 267 729668 268 319723 269 119677 270 37283 271 9365 272 1817 273 255 274 23 275 1 276 543339720 277 384199200 278 271669848 279 192099462 280 135833912 281 96044418 282 67895704 283 47954911 284 33774800 285 23609720 286 16233648 287 10824232 288 6868752 289 4060038 290 2186304 291 1049391 292 439400 293 156960 294 46648 295 11182 296 2072 297 278 298 24 299 1 300 1311738121 301 927538920 302 655869048 303 463769310 304 327933374 305 231878330 306 163940122 307 115850615 308 81729711 309 57384520 310 39843368 311 27057880 312 17692984 313 10928790 314 6246342 315 3235695 316 1488791 317 596360 318 203608 319 57830 320 13254 321 2350 322 302 323 25 324 1 325 3166815962 326 2239277041 327 1583407968 328 1119638358 329 791702684 330 559811704 331 395818452 332 279790737 333 197580326 334 139114231 335 97227888 336 66901248 337 44750864 338 28621774 339 17175132 340 9482037 341 4724486 342 2085151 343 799968 344 261438 345 71084 346 15604 347 2652 348 327 349 26 350 1 351 7645370045 352 5406093003 353 3822685009 354 2703046326 355 1911341042 356 1351514388 357 955630156 358 675609189 359 477371063 360 336694557 361 236342119 362 164129136 363 111652112 364 73372638 365 45796906 366 26657169 367 14206523 368 6809637 369 2885119 370 1061406 371 332522 372 86688 373 18256 374 2979 375 353 376 27 377 1 378 18457556052 379 13051463048 380 9228778012 381 6525731335 382 4614387368 383 3262855430 384 2307144544 385 1631239345 386 1152980252 387 814065620 388 573036676 389 400471255 390 275781248 391 185024750 392 119169544 393 72454075 394 40863692 395 21016160 396 9694756 397 3946525 398 1393928 399 419210 400 104944 401 21235 402 3332 403 380 404 28 405 1 406 44560482149 407 31509019100 408 22280241060 409 15754509347 410 11140118703 411 7877242798 412 5569999974 413 3938383889 414 2784219597 415 1967045872 416 1387102296 417 973507931 418 676252503 419 460805998 420 304194294 421 191623619 422 113317767 423 61879852 424 30710916 425 13641281 426 5340453 427 1813138 428 524154 429 126179 430 24567 431 3712 432 408 433 29 434 1 435 107578520350 436 76069501249 437 53789260160 438 38034750407 439 26894628050 440 19017361501 441 13447242772 442 9508383863 443 6722603486 444 4751265469 445 3354148168 446 2360610227 447 1649760434 448 1137058501 449 765000292 450 495817913 451 304941386 452 175197619 453 92590768 454 44352197 455 18981734 456 7153591 457 2337292 458 650333 459 150746 460 28279 461 4120 462 437 463 30 464 1 465 259717522849 466 183648021599 467 129858761409 468 91824010567 469 64929378457 470 45911989551 471 32464604273 472 22955626635 473 16230987349 474 11473868955 475 8105413637 476 5714758395 477 4010370661 478 2786818935 479 1902058793 480 1260818205 481 800759299 482 480139005 483 267788387 484 136942965 485 63333931 486 26135325 487 9490883 488 2987625 489 801079 490 179025 491 32399 492 4557 493 467 494 31 495 1 496 627013566048 497 443365544448 498 313506783008 499 221682771976 500 156753389024 501 110841368008 502 78376593824 503 55420230908 504 39186613984 505 27704856304 506 19579282592 507 13820172032 508 9725129056 509 6797189596 510 4688877728 511 3162876998 512 2061577504 513 1280898304 514 747927392 515 404731352 516 200276896 517 89469256 518 35626208 519 12478508 520 3788704 521 980104 522 211424 523 36956 524 5024 525 498 526 32 527 1 528 1513744654945 529 1070379110496 530 756872327456 531 535189554984 532 378436161000 533 267594757032 534 189217961832 535 133796824732 536 94606844892 537 66891470288 538 47284138896 539 33399454624 540 23545301088 541 16522318652 542 11486067324 543 7851754726 544 5224454502 545 3342475808 546 2028825696 547 1152658744 548 605008248 549 289746152 550 125095464 551 48104716 552 16267212 553 4768808 554 1191528 555 248380 556 41980 557 5522 558 530 559 33 560 1 561 3654502875938 562 2584123765441 563 1827251437952 564 1292061882440 565 913625715984 566 646030918032 567 456812718864 568 323014786564 569 228403669624 570 161498315180 571 114175609184 572 80683593520 573 56944755712 574 40067619740 575 28008385976 576 19337822050 577 13076209228 578 8566930310 579 5371301504 580 3181484440 581 1757666992 582 894754400 583 414841616 584 173200180 585 64371928 586 21036020 587 5960336 588 1439908 589 290360 590 47502 591 6052 592 563 593 34 594 1 595 8822750406821 596 6238626641379 597 4411375203393 598 3119313320392 599 2205687598424 600 1559656634016 601 1102843636896 602 779827505428 603 551418456188 604 389901984804 605 275673924364 606 194859202704 607 137628349232 608 97012375452 609 68076005716 610 47346208026 611 32414031278 612 21643139538 613 13938231814 614 8552785944 615 4939151432 616 2652421392 617 1309596016 618 588041796 619 237572108 620 85407948 621 26996356 622 7400244 623 1730268 624 337862 625 53554 626 6615 627 597 628 35 629 1 630 21300003689580 631 15061377048200 632 10650001844772 633 7530688523785 634 5325000918816 635 3765344232440 636 2662500270912 637 1882671142324 638 1331245961616 639 941320440992 640 665575909168 641 470533127068 642 332487551936 643 234640724684 644 165088381168 645 115422213742 646 79760239304 647 54057170816 648 35581371352 649 22491017758 650 13491937376 651 7591572824 652 3962017408 653 1897637812 654 825613904 655 322980056 656 112404304 657 34396600 658 9130512 659 2068130 660 391416 661 60169 662 7212 663 632 664 36 665 1 666 51422757785981 667 36361380737780 668 25711378892972 669 18180690368557 670 12855689442601 671 9090345151256 672 6427844503352 673 4545171413236 674 3213917103940 675 2272566402608 676 1606896350160 677 1136109036236 678 803020679004 679 567128276620 680 399729105852 681 280510594910 682 195182453046 683 133817410120 684 89638542168 685 58072389110 686 35982955134 687 21083510200 688 11553590232 689 5859655220 690 2723251716 691 1148593960 692 435384360 693 146800904 694 43527112 695 11198642 696 2459546 697 451585 698 67381 699 7844 700 668 701 37 702 1 703 124145519261542 704 87784138523761 705 62072759630752 706 43892069261529 707 31036379811158 708 21946034593857 709 15518189654608 710 10973015916588 711 7759088517176 712 5486483506548 713 3879462752768 714 2743005386396 715 1939129715240 716 1370148955624 717 966857382472 718 680239700762 719 475693047956 720 328999863166 721 223455952288 722 147710931278 723 94055344244 724 57066465334 725 32637100432 726 17413245452 727 8582906936 728 3871845676 729 1583978320 730 582185264 731 190328016 732 54725754 733 13658188 734 2911131 735 518966 736 75225 737 8512 738 705 739 38 740 1 741 299713796309065 742 211929657785303 743 149856898154513 744 105964828892281 745 74928449072687 746 52982414405015 747 37464224248465 748 26491205571196 749 18732104433764 750 13245572023724 751 9365946259316 752 6622468139164 753 4682135101636 754 3309278670864 755 2337006338096 756 1647097083234 757 1155932748718 758 804692911122 759 552455815454 760 371166883566 761 241766275522 762 151121809578 763 89703565766 764 50050345884 765 25996152388 766 12454752612 767 5455823996 768 2166163584 769 772513280 770 245053770 771 68383942 772 16569319 773 3430097 774 594191 775 83737 776 9217 777 743 778 39 779 1 780 723573111879672 781 511643454094368 782 361786555939816 783 255821727046794 784 180893277964968 785 127910863477702 786 90446638653480 787 63955429819661 788 45223310004960 789 31977676457488 790 22611518283040 791 15988414398480 792 11304603240800 793 7991413772500 794 5646285008960 795 3984103421330 796 2803029831952 797 1960625659840 798 1357148726576 799 923622699020 800 612933159088 801 392888085100 802 240825375344 803 139753911650 804 76046498272 805 38450905000 806 17910576608 807 7621987580 808 2938676864 809 1017567050 810 313437712 811 84953261 812 19999416 813 4024288 814 677928 815 92954 816 9960 817 782 818 40 819 1 820 1746860020068409 821 1235216565974040 822 873430010034184 823 617608282986610 824 436715005011762 825 308804141442670 826 218357502131182 827 154402068473141 828 109178739824621 829 77200986462448 830 54589194740528 831 38599932681520 832 27293017639280 833 19296017013300 834 13637698781460 835 9630388430290 836 6787133253282 837 4763655491792 838 3317774386416 839 2280771425596 840 1536555858108 841 1005821244188 842 633713460444 843 380579286994 844 215800409922 845 114497403272 846 56361481608 847 25532564188 848 10560664444 849 3956243914 850 1331004762 851 398390973 852 104952677 853 24023704 854 4702216 855 770882 856 102914 857 10742 858 822 859 41 860 1 861 4217293152016490 862 2982076586042449 863 2108646576008224 864 1491038293020794 865 1054323287998372 866 745519146454432 867 527161643573852 868 372759570604323 869 263580808297762 870 186379726287069 871 131790181202976 872 93189127422048 873 65892950320800 874 46589034652580 875 32933715794760 876 23268087211750 877 16417521683572 878 11550788745074 879 8081429878208 880 5598545812012 881 3817327283704 882 2542377102296 883 1639534704632 884 1014292747438 885 596379696916 886 330297813194 887 170858884880 888 81894045796 889 36093228632 890 14516908358 891 5287248676 892 1729395735 893 503343650 894 128976381 895 28725920 896 5473098 897 873796 898 113656 899 11564 900 863 901 42 902 1 903 10181446324101389 904 7199369738058939 905 5090723162050673 906 3599684869029018 907 2545361581019166 908 1799842434452804 909 1272680790028284 910 899921214178175 911 636340378902085 912 449960534584831 913 318169907490045 914 224979308625024 915 159082077742848 916 112481984973380 917 79522750447340 918 56201803006510 919 39685608895322 920 27968310428646 921 19632218623282 922 13679975690220 923 9415873095716 924 6359704386000 925 4181911806928 926 2653827452070 927 1610672444354 928 926677510110 929 501156698074 930 252752930676 931 117987274428 932 50610136990 933 19804157034 934 7016644411 935 2232739385 936 632320031 937 157702301 938 34199018 939 6346894 940 987452 941 125220 942 12427 943 905 944 43 945 1 946 24580185800219268 947 17380816062160328 948 12290092900109612 949 8690408031079691 950 6145046450048184 951 4345204015471970 952 3072523224481088 953 2172602004206459 954 1536261593080260 955 1086300913486916 956 768130442074876 957 543149216115069 958 384061386367872 959 271564062716228 960 192004735420720 961 135724553453850 962 95887411901832 963 67653919323968 964 47600529051928 965 33312194313502 966 23095848785936 967 15775577481716 968 10541616192928 969 6835739258998 970 4264499896424 971 2537349954464 972 1427834208184 973 753909628750 974 370740205104 975 168597411418 976 70414294024 977 26820801445 978 9249383796 979 2865059416 980 790022332 981 191901319 982 40545912 983 7334346 984 1112672 985 137647 986 13332 987 948 988 44 989 1 990 59341817924539925 991 41961001862379596 992 29670908962269940 993 20980500931189303 994 14835454481127875 995 10490250465520154 996 7417727239953058 997 5245125228687547 998 3708863597286719 999 2622562506567176 1000 1854431355561792 1001 1311279658189945 1002 927210602482941 1003 655625449084100 1004 463568798136948 1005 327729288874570 1006 231611965355682 1007 163541331225800 1008 115254448375896 1009 80912723365430 1010 56408043099438 1011 38871426267652 1012 26317193674644 1013 17377355451926 1014 11100239155422 1015 6801849850888 1016 3965184162648 1017 2181743836934 1018 1124649833854 1019 539337616522 1020 239011705442 1021 97235095469 1022 36070185241 1023 12114443212 1024 3655081748 1025 981923651 1026 232447231 1027 47880258 1028 8447018 1029 1250319 1030 150979 1031 14280 1032 992 1033 45 1034 1 1035 143263821649299118 1036 101302819786919521 1037 71631910824649536 1038 50651409893459243 1039 35815955412317178 1040 25325704946648029 1041 17907977705473212 1042 12662852468640605 1043 8953988825974266 1044 6331426103853895 1045 4476993862128968 1046 3165711013751737 1047 2238490260672886 1048 1582836051567041 1049 1119194247221048 1050 791298087011518 1051 559341254230252 1052 395153296581482 1053 278795779601696 1054 196167171741326 1055 137320766464868 1056 95279469367090 1057 65188619942296 1058 43694549126570 1059 28477594607348 1060 17902089006310 1061 10767034013536 1062 6146927999582 1063 3306393670788 1064 1663987450376 1065 778349321964 1066 336246800911 1067 133305280710 1068 48184628453 1069 15769524960 1070 4637005399 1071 1214370882 1072 280327489 1073 56327276 1074 9697337 1075 1401298 1076 165259 1077 15272 1078 1037 1079 46 1080 1 1081 345869461223138161 1082 244566641436218639 1083 172934730611569057 1084 122283320718108779 1085 86467365305776421 1086 61141660358965207 1087 43233682652121241 1088 30570830174113817 1089 21616841294614871 1090 15285414929828161 1091 10808419965982863 1092 7642704875880705 1093 5404201274424623 1094 3821326312239927 1095 2702030298788089 1096 1910492334232566 1097 1350639341241770 1098 954494550811734 1099 673949076183178 1100 474962951343022 1101 333487938206194 1102 232600235831958 1103 160468089309386 1104 108883169068866 1105 72172143733918 1106 46379683613658 1107 28669123019846 1108 16913962013118 1109 9453321670370 1110 4970381121164 1111 2442336772340 1112 1114596122875 1113 469552081621 1114 181489909163 1115 63954153413 1116 20406530359 1117 5851376281 1118 1494698371 1119 336654765 1120 66024613 1121 11098635 1122 1566557 1123 180531 1124 16309 1125 1083 1126 47 1127 1 1128 835002744095575440 1129 590436102659356800 1130 417501372047787696 1131 295218051329677836 1132 208750686023885200 1133 147609025664741628 1134 104375343011086448 1135 73804512826235058 1136 52187671468728688 1137 36902256224443032 1138 26093834895811024 1139 18451124841863568 1140 13046906150305328 1141 9225527586664550 1142 6523356611028016 1143 4612522633020655 1144 3261131675474336 1145 2305133892053504 1146 1628443626994912 1147 1148912027526200 1148 808450889549216 1149 566088174038152 1150 393068325141344 1151 269351258378252 1152 181055312802784 1153 118551827347576 1154 75048806633504 1155 45583085032964 1156 26367283683488 1157 14423702791534 1158 7412717893504 1159 3556932895215 1160 1584148204496 1161 651041990784 1162 245444062576 1163 84360683772 1164 26257906640 1165 7346074652 1166 1831353136 1167 402679378 1168 77123248 1169 12665192 1170 1747088 1171 196840 1172 17392 1173 1130 1174 48 1175 1 1176 2015874949414289041 1177 1425438846754932240 1178 1007937474707144496 1179 712719423377465532 1180 503968737353563036 1181 356359711688626828 1182 251984368675828076 1183 178179855837321506 1184 125992184294963746 1185 89089927693171720 1186 62996091120254056 1187 44544959737674592 1188 31498030992168896 1189 22272433736969878 1190 15748884197692566 1191 11135879244048671 1192 7873654308494991 1193 5566265567527840 1194 3933577519048416 1195 2777355654521112 1196 1957362917075416 1197 1374539063587368 1198 959156499179496 1199 662419583519596 1200 450406571181036 1201 299607140150360 1202 193600633981080 1203 120631891666468 1204 71950368716452 1205 40790986475022 1206 21836420685038 1207 10969650788719 1208 5141081099711 1209 2235190195280 1210 896486053360 1211 329804746348 1212 110618590412 1213 33603981292 1214 9177427788 1215 2234032514 1216 479802626 1217 89788440 1218 14412280 1219 1943928 1220 214232 1221 18522 1222 1178 1223 49 1224 1 1225 4866752642924153522 1226 3441313796169221281 1227 2433376321462076736 1228 1720656898084610028 1229 1216688160731028568 1230 860328449042189864 1231 608344080364454904 1232 430164224513149582 1233 304172040132285252 1234 215082111988135466 1235 152086018813425776 1236 107541050857928648 1237 76042990729843488 1238 53770464729138774 1239 38021317934662444 1240 26884763441741237 1241 19009533552543662 1242 13439919876022831 1243 9499843086576256 1244 6710933173569528 1245 4734718571596528 1246 3331901980662784 1247 2333695562766864 1248 1621576082699092 1249 1112826154700632 1250 750013711331396 1251 493207774131440 1252 314232525647548 1253 192582260382920 1254 112741355191474 1255 62627407160060 1256 32806071473757 1257 16110731888430 1258 7376271294991 1259 3131676248640 1260 1226290799708 1261 440423336760 1262 144222571704 1263 42781409080 1264 11411460302 1265 2713835140 1266 569591066 1267 104200720 1268 16356208 1269 2158160 1270 232754 1271 19700 1272 1227 1273 50 1274 1 1275 11749380235262596085 1276 8308066439093374803 1277 5874690117631298017 1278 4154033219546686764 1279 2937345058815638596 1280 2077016609773218432 1281 1468672529406644768 1282 1038508304877604486 1283 734336264645434834 1284 519254152120420718 1285 367168130801561242 1286 259627069671354424 1287 183584041587772136 1288 129813455458982262 1289 91791782663801218 1290 64906081376403681 1291 45894296994284899 1292 32449453428566493 1293 22939762962599087 1294 16210776260145784 1295 11445651745166056 1296 8066620552259312 1297 5665597543429648 1298 3955271645465956 1299 2734402237399724 1300 1862839866032028 1301 1243221485462836 1302 807440299778988 1303 506814786030468 1304 305323615574394 1305 175368762351534 1306 95433478633817 1307 48916803362187 1308 23487003183421 1309 10507947543631 1310 4357967048348 1311 1666714136468 1312 584645908464 1313 187003980784 1314 54192869382 1315 14125295442 1316 3283426206 1317 673791786 1318 120556928 1319 18514368 1320 2390914 1321 252454 1322 20927 1323 1277 1324 51 1325 1