0 1 1 1 2 1 3 2 4 2 5 1 6 4 7 5 8 3 9 1 10 9 11 12 12 9 13 4 14 1 15 21 16 30 17 25 18 14 19 5 20 1 21 51 22 76 23 69 24 44 25 20 26 6 27 1 28 127 29 196 30 189 31 133 32 70 33 27 34 7 35 1 36 323 37 512 38 518 39 392 40 230 41 104 42 35 43 8 44 1 45 835 46 1353 47 1422 48 1140 49 726 50 369 51 147 52 44 53 9 54 1 55 2188 56 3610 57 3915 58 3288 59 2235 60 1242 61 560 62 200 63 54 64 10 65 1 66 5798 67 9713 68 10813 69 9438 70 6765 71 4037 72 2002 73 814 74 264 75 65 76 11 77 1 78 15511 79 26324 80 29964 81 27016 82 20240 83 12804 84 6853 85 3080 86 1143 87 340 88 77 89 12 90 1 91 41835 92 71799 93 83304 94 77220 95 60060 96 39897 97 22737 98 11076 99 4563 100 1560 101 429 102 90 103 13 104 1 105 113634 106 196938 107 232323 108 220584 109 177177 110 122694 111 73710 112 38376 113 17199 114 6552 115 2079 116 532 117 104 118 14 119 1 120 310572 121 542895 122 649845 123 630084 124 520455 125 373581 126 234780 127 129285 128 62127 129 25830 130 9163 131 2715 132 650 133 119 134 15 135 1 136 853467 137 1503312 138 1822824 139 1800384 140 1524120 141 1128816 142 737646 143 426192 144 217242 145 97120 146 37708 147 12528 148 3484 149 784 150 135 151 16 152 1 153 2356779 154 4179603 155 5126520 156 5147328 157 4453320 158 3390582 159 2292654 160 1381080 161 740554 162 352070 163 147356 164 53720 165 16796 166 4403 167 935 168 152 169 17 170 1 171 6536382 172 11662902 173 14453451 174 14727168 175 12991230 176 10136556 177 7064316 178 4414288 179 2473704 180 1239980 181 553146 182 217872 183 74919 184 22134 185 5490 186 1104 187 170 188 18 189 1 190 18199284 191 32652735 192 40843521 193 42171849 194 37854954 195 30192102 196 21615160 197 13952308 198 8127972 199 4266830 200 2010998 201 845937 202 314925 203 102543 204 28728 205 6764 206 1292 207 189 208 19 209 1 210 50852019 211 91695540 212 115668105 213 120870324 214 110218905 215 89662216 216 65759570 217 43695440 218 26347110 219 14405800 220 7123765 221 3171860 222 1263405 223 446196 224 138035 225 36784 226 8245 227 1500 228 209 229 20 230 1 231 142547559 232 258215664 233 328233969 234 346757334 235 320751445 236 265640691 237 199117226 238 135802120 239 84448350 240 47876675 241 24701425 242 11559030 243 4881461 244 1847636 245 621015 246 183064 247 46529 248 9954 249 1729 250 230 251 21 252 1 253 400763223 254 728997192 255 933206967 256 995742748 257 933149470 258 785509362 259 600560037 260 419367696 261 268127145 262 157026450 263 84137130 264 41141916 265 18288127 266 7350112 267 2651715 268 850608 269 239547 270 58212 271 11913 272 1980 273 252 274 22 275 1 276 1129760415 277 2062967382 278 2657946907 279 2862099185 280 2714401580 281 2319218869 282 1805437095 283 1288054878 284 844521291 285 509290725 286 282305496 287 143567173 288 66780155 289 28289954 290 10852435 291 3741870 292 1148367 293 309672 294 72105 295 14145 296 2254 297 275 298 23 299 1 300 3192727797 301 5850674704 302 7583013474 303 8234447672 304 7895719634 305 6839057544 306 5412710842 307 3938013264 308 2641866894 309 1636117512 310 935163394 311 492652824 312 238637282 313 105922544 314 42884259 315 15742672 316 5199909 317 1530144 318 395922 319 88504 320 16674 321 2552 322 299 323 24 324 1 325 9043402501 326 16626415975 327 21668135850 328 23713180780 329 22969224850 330 20147488020 331 16189781650 332 11992591000 333 8215997670 334 5213147800 335 3063933730 336 1666453500 337 837212650 338 387444085 339 164549475 340 63826840 341 22472725 342 7125975 343 2014570 344 501100 345 107730 346 19525 347 2875 348 324 349 25 350 1 351 25669818476 352 47337954326 353 62007732605 354 68350541480 355 66829893650 356 59306494520 357 48329860670 358 36398370320 359 25421736470 360 16493079200 361 9943535030 362 5567599880 363 2891110235 364 1389206210 365 615820400 366 250849040 367 93425540 368 31613270 369 9641645 370 2623400 371 628355 372 130130 373 22724 374 3224 375 350 376 26 377 1 378 73007772802 379 135015505407 380 177696228411 381 197188167735 382 194486929650 383 174466248840 384 144034725510 385 110149967460 386 78313185990 387 51858350700 388 32004214110 389 18402245145 390 9847916325 391 4896136845 392 2255875650 393 960094980 394 375887850 395 134680455 396 43878315 397 12893400 398 3381885 399 781209 400 156078 401 26298 402 3600 403 377 404 27 405 1 406 208023278209 407 385719506620 408 509899901553 409 569371325796 410 566141346225 411 512987904000 412 428650941810 413 332497878960 414 240321504150 415 162175750800 416 102264809955 417 60254375580 418 33146298315 419 16999928820 420 8112107475 421 3591858480 422 1470663285 423 554446620 424 191452170 425 60153600 426 17056494 427 4319172 428 963585 429 185976 430 30275 431 4004 432 405 433 28 434 1 435 593742784829 436 1103642686382 437 1464990733969 438 1645412573574 439 1648500576021 440 1507780192035 441 1274136724770 442 1001470324920 443 734995133910 444 504762064905 445 324694936335 446 195665483850 447 110400602715 448 58258334610 449 28703894775 450 13174629240 451 5616968385 452 2216562075 453 806052390 454 268662264 455 81529266 456 22339251 457 5468733 458 1179836 459 220255 460 34684 461 4437 462 434 463 29 464 1 465 1697385471211 466 3162376205180 467 4214045993925 468 4758903883564 469 4801693341630 470 4430417492826 471 3783387241725 472 3010602183600 473 2241227523735 474 1564452135150 475 1025122485090 476 630761022900 477 364324421175 478 197362832100 479 100136858625 480 47495492400 481 21008159700 482 8639582850 483 3291276729 484 1156243920 485 372530781 486 109337250 487 28987820 488 6868824 489 1434775 490 259376 491 39555 492 4900 493 464 494 30 495 1 496 4859761676391 497 9073807670316 498 12135326082669 499 13774643219119 500 13991014718020 501 13015498076181 502 11224406918151 503 9035216949060 504 6816281842485 505 4830802143975 506 3220335643140 507 2020207929165 508 1192448276175 509 661824111900 510 344995183125 511 168640510725 512 77143234950 513 32939019279 514 13087103499 515 4820051430 516 1638111951 517 510855851 518 145193894 519 37291419 520 8562975 521 1733706 522 303831 523 44919 524 5394 525 495 526 31 527 1 528 13933569346707 529 26068895429376 530 34983776972104 531 39900984019808 532 40781156013320 533 38230919712352 534 33275121943392 535 27075905709696 536 20682300935520 537 14867419629600 538 10071345716280 539 6432991848480 540 3874480317240 541 2199267571200 542 1175459805750 543 590778928800 544 278722764954 545 123169357728 546 50846174208 547 19545266880 548 6969019232 549 2294161696 550 693341164 551 191048288 552 47588100 553 10600512 554 2082456 555 354144 556 50808 557 5920 558 527 559 32 560 1 561 40002464776083 562 74986241748187 563 100953656421288 564 115665917005232 565 118913059745480 566 112287197669064 567 98581947365440 568 81033328588608 569 62625626274816 570 45621066281400 571 31371757194360 572 20378817882000 573 12506739736920 574 7249207694190 575 3965506305750 576 2044961499504 577 992671051482 578 452738296890 579 193560798816 580 77360460320 581 28808447808 582 9956522092 583 3178551148 584 931977552 585 249236900 586 60271068 587 13037112 588 2487408 589 410872 590 57255 591 6479 592 560 593 33 594 1 595 114988706524270 596 215942362945558 597 291605815174707 598 335532633172000 599 346866174419776 600 329782204779984 601 291902473623112 602 242240902228864 603 189280021144824 604 139618449750576 605 97371641357760 606 64257314813280 607 40134765313110 608 23721453736860 609 13259675499444 610 7003138856736 611 3490370847876 612 1638970147188 613 723659556026 614 299729706944 615 116125430220 616 41943521048 617 14067050792 618 4359765600 619 1241485520 620 322545080 621 75795588 622 15935392 623 2955535 624 474606 625 64294 626 7072 627 594 628 34 629 1 630 330931069469828 631 622536884644535 632 843080811292265 633 974004622766483 634 1012181012371760 635 968550852822872 636 863925580631960 637 723423396996800 638 571139373124264 639 426270112253160 640 301247405921616 641 201763721484150 642 128113533863250 643 77115894549414 644 43984268093040 645 23753185204056 646 12132479851800 647 5853000551090 648 2662359410158 649 1139514693190 650 457798658212 651 172136002060 652 60370337440 653 19668301912 654 5923796200 655 1639826188 656 414276060 657 94686515 658 19365533 659 3494435 660 545972 661 71960 662 7700 663 629 664 35 665 1 666 953467954114363 667 1796548765406628 668 2439622318703283 669 2829266446430508 670 2954736487961115 671 2844657445826592 672 2555899830451632 673 2158488350753024 674 1720832882374224 675 1298656891299040 676 929281239658926 677 631124661269016 678 406993149896814 679 249213696505704 680 144853347846510 681 79869933148896 682 41738665606946 683 20647839813048 684 9654874654438 685 4259672761560 686 1769449353462 687 690304997712 688 252174641412 689 85962435552 690 27231924300 691 7977898448 692 2148788763 693 528328108 694 117546483 695 23405940 696 4112367 697 625632 698 80289 699 8364 700 665 701 36 702 1 703 2750016719520991 704 5189639038224274 705 7065437530540419 706 8223625253094906 707 8628660380218215 708 8355293764239339 709 7559045627031248 710 6435221063578880 711 5177978124426288 712 3948771013332190 713 2859062792226982 714 1967399050824756 715 1287331507671534 716 801060194249028 717 473936977501110 718 266461946602352 719 142256438568890 720 72041380074432 721 34562387229046 722 15683996769460 723 6719427112734 724 2711928992586 725 1028442074676 726 365369001264 727 121172258300 728 37358611511 729 10655015319 730 2794663354 731 669280531 732 145064790 733 28143939 734 4818288 735 714285 736 89318 737 9065 738 702 739 37 740 1 741 7939655757745265 742 15005093288285684 743 20478701821859599 744 23917723163853540 745 25207579397552460 746 24542999771488802 747 22349560454849467 748 19172244815036416 749 15561970201337358 750 11985811929985460 751 8775232856383928 752 6113793350723272 753 4055790752745318 754 2562328679421672 755 1541459118352490 756 882655362672352 757 480759765245674 758 248860205872368 759 122287764072938 760 56965811111240 761 25115352874780 762 10459798179996 763 4105740068526 764 1514983334240 765 523899871075 766 169185885130 767 50808290184 768 14118959204 769 3609008675 770 842489260 771 178027017 772 33676512 773 5621891 774 812668 775 99085 776 9804 777 740 778 38 779 1 780 22944749046030949 781 43423450867890548 782 59401518273998823 783 69604004383265599 784 73668302332894802 785 72100139623890729 786 66064805041374685 787 57083775471223241 788 46720026946359234 789 36323014987706746 790 26874838137092660 791 18944816959852518 792 12731912782890262 793 8159578550519480 794 4986443160446514 795 2904874246270516 796 1612275333790394 797 851907735190980 798 428113781056546 799 204368928058958 800 92540962166016 801 39680891123302 802 16080521582762 803 6144623273841 804 2208069090445 805 743894046389 806 234113134518 807 68536258063 808 18570457139 809 4629524952 810 1054192789 811 217325420 812 40111071 813 6533644 814 921557 815 109629 816 10582 817 779 818 39 819 1 820 66368199913921497 821 125769718187920320 822 172428973525154970 823 202673824990159224 824 215372446340051130 825 211833246998160216 826 195248720136488655 827 169868607458957160 828 140126817405289221 829 109917880071158640 830 82142670084651924 831 58551567879835440 832 39836308293262260 833 25877934493856256 834 16050895957236510 835 9503592740507424 836 5369057315251890 837 2892296850037920 838 1484390444306484 839 725023671281520 840 336590781348276 841 148302374872080 842 61906035979905 843 24433213947048 844 9096586410675 845 3186076271352 846 1046543438970 847 321219849720 848 91736240154 849 24254174880 850 5901043161 851 1311629280 852 263970135 853 47566272 854 7564830 855 1041768 856 120990 857 11400 858 819 859 40 860 1 861 192137918101841817 862 364566891626996787 863 500872516703234514 864 590475244855365324 865 629879518328370570 866 622454413474700001 867 576950574593606031 868 505244145000735036 869 419913304935405021 870 332187367561099785 871 250612118035646004 872 180530546257749624 873 124265810666953956 874 81765138744355026 875 51432423191600190 876 30923546012995824 877 17764946905797234 878 9745744609596294 879 5101710965625924 880 2546004896936280 881 1209916827501876 882 546799192200261 883 234641624799033 884 95435836337628 885 36715876629075 886 13329206120997 887 4553839560042 888 1459499528844 889 437210264754 890 121891458195 891 31466847321 892 7476642576 893 1623165687 894 319101237 895 56172870 896 8727588 897 1174158 898 133209 899 12259 900 860 901 41 902 1 903 556704809728838604 904 1057577326432073118 905 1455914653185596625 906 1721227279886970408 907 1842809176658435895 908 1829284506396676602 909 1704649133069041068 910 1502108024529746088 911 1257344817497239842 912 1002712790532150810 913 763330031854495413 914 555408474960349584 915 386561495669058606 916 257463372602909172 917 164121107948951040 918 100120916110393248 919 58434237528389352 920 32612402481019452 921 17393460472158498 922 8857632690064080 923 4302720916638417 924 1991357644501170 925 876876653336922 926 366793337765736 927 145480919087700 928 54598922310114 929 19342545209883 930 6450549353640 931 2018601251793 932 590568570270 933 160834948092 934 40566655584 935 9418909500 936 1998439794 937 384001695 938 66074616 939 10034955 940 1319626 941 146328 942 13160 943 902 944 42 945 1 946 1614282136160911722 947 3070196789346508347 948 4234719259504640151 949 5019951109731002928 950 5393320962942082905 951 5376742816124153565 952 5036041663995463758 953 4464101975096026998 954 3762165632559136740 955 3023387639883886065 956 2321451297346995807 957 1705300002483903603 958 1199433343232317362 959 808145976220918818 960 521705396662253460 961 322676261587733640 962 191167556119802052 963 108440100481567302 964 58863495643242030 965 30553814078860995 966 15151711251203667 967 7170955214476509 968 3235027635603828 969 1389150910190358 970 566873179163550 971 219422386607697 972 80392016873637 973 27811695815316 974 9059719175703 975 2770004770155 976 791970173946 977 210820513176 978 51984004878 979 11801350989 980 2448516105 981 460111266 982 77429197 983 11500909 984 1479114 985 160390 986 14104 987 945 988 43 989 1 990 4684478925507420069 991 8919198185012060220 992 12324867158582151426 993 14647991332177725984 994 15790014888797239398 995 15806105443061700228 996 14876886455215644321 997 13262309271650627496 998 11249655247539049803 999 9107004569790018612 1000 7050138939714785475 1001 5226184643063216772 1002 3712879321937139783 1003 2529284716115489640 1004 1652527634470905918 1005 1035549214369789152 1006 622283918189102994 1007 358471152244611384 1008 197857410203670327 1009 104569020973306692 1010 52876480544541171 1011 25557694101284004 1012 11795133760270695 1013 5191051724957736 1014 2175446475961605 1015 866687582644884 1016 327626099296650 1017 117263431864656 1018 39641419761174 1019 12621694119804 1020 3772795457277 1021 1054774692000 1022 274605869043 1023 66233871972 1024 14709978360 1025 2986056568 1026 549041372 1027 90409220 1028 13140413 1029 1653608 1030 175439 1031 15092 1032 989 1033 44 1034 1 1035 13603677110519480289 1036 25928544269101631715 1037 35892056675771937630 1038 42762873379557116808 1039 46244111664036665610 1040 46473006787074583947 1041 43945301169927972045 1042 39388850974405321620 1043 33618969088979695911 1044 27406798757043853890 1045 21383328152568020859 1046 15989202904715142030 1047 11468348681115846195 1048 7894691672523535341 1049 5217361564956184710 1050 3310360767029798064 1051 2016304284803503530 1052 1178612480637384705 1053 660897583421588403 1054 355302911721518190 1055 183003195619131867 1056 90229308406095870 1057 42543879586512435 1058 19161631961190036 1059 8233185783564225 1060 3369760157903139 1061 1311577113806190 1062 484530950922480 1063 169526545745634 1064 56035909338255 1065 17449264269081 1066 5102176018320 1067 1395614433015 1068 355549719375 1069 83929906900 1070 18245076300 1071 3625507160 1072 652591005 1073 105203241 1074 14969460 1075 1844139 1076 191520 1077 16125 1078 1034 1079 45 1080 1 1081 39532221379621112004 1082 75424278055393049634 1083 104583474324430686153 1084 124899041719365720048 1085 135479991830668366365 1086 136662419621039221602 1087 129807158931407877612 1088 116953121233312989576 1089 100414618820428871421 1090 82409095998591570660 1091 64779329814327016779 1092 48840879738399009084 1093 35352243258354523566 1094 24580401918595566246 1095 16422414004509518115 1096 10544026616789486304 1097 6505277532470686299 1098 3855814348862476638 1099 2194812975780491298 1100 1199203690762238460 1101 628535415746745927 1102 315776383611740172 1103 151934819953798341 1104 69938697331266696 1105 30764577902657400 1106 12914523055273554 1107 5165868222631809 1108 1965634610474304 1109 710093406006369 1110 243011719352970 1111 78587349625656 1112 23947054720416 1113 6853340170710 1114 1835094059290 1115 457724702575 1116 105800490360 1117 22523174465 1118 4383301406 1119 772763706 1120 122016840 1121 17005119 1122 2051784 1123 208679 1124 17204 1125 1080 1126 46 1127 1 1128 114956499435014161638 1129 219539973759444847791 1130 304906794099189455835 1131 364962507874464772566 1132 397041453171073308015 1133 401949570383115465579 1134 383422699785760088790 1135 347174898985149738609 1136 299776836052333431657 1137 247603044633347458860 1138 196029305551317596523 1139 148972452811080549429 1140 108773524915349098896 1141 76355059181459607927 1142 51546842539894570665 1143 33471718153769690718 1144 20905118498122649241 1145 12555904857113654235 1146 7249831015405206396 1147 4022552082289475685 1148 2143515490120724559 1149 1096246619312284440 1150 537649900896805209 1151 252638095187722437 1152 113617798289197650 1153 48844969180562763 1154 20046025888379667 1155 7841596239112482 1156 2918739735833643 1157 1031692474984995 1158 345546123699042 1159 109387744516782 1160 32635488950416 1161 9146158932575 1162 2398619252225 1163 586048367400 1164 132706966231 1165 27679239577 1166 5278081952 1167 911785665 1168 141073743 1169 19265582 1170 2277667 1171 226963 1172 18330 1173 1127 1174 47 1175 1 1176 334496473194459009429 1177 639403267293648465264 1178 889409275733099076192 1179 1066910755144727536416 1180 1163953531428653546160 1181 1182413723339948862384 1182 1132547169154025292978 1183 1030374434823243259056 1184 894554779670830629126 1185 743409186236998487040 1186 592604802995745604812 1187 453775283277747244848 1188 334101036907889256252 1189 236675426636703277488 1190 161373619875123869310 1191 105923679191786910624 1192 66932741509005994194 1193 40710854370641509872 1194 23828287954808336316 1195 13415898587815406640 1196 7262314191722484684 1197 3777412010329814208 1198 1886534615396812086 1199 903905794373725296 1200 415100862657482850 1201 182508793358140080 1202 76732591308054912 1203 30806361863325792 1204 11792028449931120 1205 4295978334517680 1206 1486626343200819 1207 487569357166240 1208 151169392399773 1209 44180267135216 1210 12130826552200 1211 3117374585856 1212 746434573208 1213 165664287760 1214 33869107194 1215 6330941360 1216 1072124990 1217 162616992 1218 21770212 1219 2522960 1220 246420 1221 19504 1222 1175 1223 48 1224 1 1225 973899740488107474693 1226 1863309016221206550885 1227 2595723298171475077872 1228 3120273562306480158768 1229 3413278009913329944960 1230 3478914423922627701522 1231 3345335327317217414418 1232 3057476383648099181160 1233 2668338400731072375222 1234 2230568768903574720978 1235 1789789272510491336700 1236 1380481123181382105912 1237 1024551746822339778588 1238 732150083419716403050 1239 503972725703614057422 1240 334230040575916774128 1241 213567275071434414690 1242 131471883834455840382 1243 77955040913265252828 1244 44506500734346227640 1245 24455624789867705532 1246 12926260817449110978 1247 6567852420100351590 1248 3205541272428020232 1249 1501515450389348226 1250 674342247323677842 1251 290047746529520784 1252 119330981621311824 1253 46894368647774592 1254 17574633127649619 1255 6270174034884739 1256 2125365092766832 1257 682919016701229 1258 207480486087189 1259 59428468273272 1260 15994635711264 1261 4029473446824 1262 945967968162 1263 205864336314 1264 41272173544 1265 7565683342 1266 1256512194 1267 186910164 1268 24539592 1269 2788884 1270 267099 1271 20727 1272 1224 1273 49 1274 1