Problem:


Score : 600 points

Problem Statement

Let us define the oddness of a permutation p = {p_1,\ p_2,\ ...,\ p_n} of {1,\ 2,\ ...,\ n} as \sum_{i = 1}^n |i - p_i|.

Find the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

Constraints

All values in input are integers.

1 \leq n \leq 50

0 \leq k \leq n^2

Input

Input is given from Standard Input in the following format:

n k

Output

Print the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

Sample Input 1

3 2

Sample Output 1

2

There are six permutations of {1,\ 2,\ 3}. Among them, two have oddness of 2:  {2,\ 1,\ 3} and {1,\ 3,\ 2}.

Sample Input 2

39 14

Sample Output 2

74764168



Sample input:
3 2


Sample output:
2

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())
N,K = inpl()

ans = [[] for _ in range(51)]
ans[0]= [1]
ans[1]= [1]
ans[2]= [1, 1]
ans[3]= [1, 2, 3]
ans[4]= [1, 3, 7, 9, 4]
ans[5]= [1, 4, 12, 24, 35, 24, 20]
ans[6]= [1, 5, 18, 46, 93, 137, 148, 136, 100, 36]
ans[7]= [1, 6, 25, 76, 187, 366, 591, 744, 884, 832, 716, 360, 252]
ans[8]= [1, 7, 33, 115, 327, 765, 1523, 2553, 3696, 4852, 5708, 5892, 5452, 4212, 2844, 1764, 576]
ans[9]= [1, 8, 42, 164, 524, 1400, 3226, 6436, 11323, 17640, 25472, 33280, 40520, 44240, 45512, 40608, 35496, 25632, 18108, 8064, 5184]
ans[10]= [1, 9, 52, 224, 790, 2350, 6072, 13768, 27821, 50461, 83420, 127840, 182256, 242272, 301648, 350864, 382576, 389232, 373536, 332640, 273060, 208548, 136512, 81792, 46656, 14400]
ans[11]= [1, 10, 63, 296, 1138, 3708, 10538, 26480, 59673, 121626, 226787, 390144, 628744, 949472, 1355952, 1826464, 2341600, 2833632, 3282464, 3584160, 3765600, 3719664, 3531924, 3093336, 2642364, 2010240, 1508544, 963072, 621504, 259200, 158400]
ans[12]= [1, 11, 75, 381, 1582, 5582, 17222, 47194, 116457, 261163, 537459, 1022981, 1817652, 3040352, 4810720, 7230928, 10360160, 14178912, 18577792, 23327872, 28132048, 32571504, 36310464, 38903904, 40028724, 39552156, 37457388, 33941412, 29314944, 24179904, 18835776, 13777344, 9452736, 5716800, 3211200, 1742400, 518400]
ans[13]= [1, 12, 88, 480, 2137, 8096, 26860, 79376, 211811, 515308, 1153268, 2391936, 4633331, 8438664, 14557048, 23874176, 37407760, 56117824, 80906752, 112162240, 150052400, 193572736, 241706624, 291576384, 341323776, 386160048, 424359540, 450394992, 464545584, 461528208, 446428476, 413557632, 373573440, 321120000, 268449408, 210332160, 162330624, 112550400, 77788800, 46540800, 28497600, 11404800, 6739200]
ans[14]= [1, 13, 102, 594, 2819, 11391, 40344, 127508, 364587, 952559, 2293742, 5126898, 10710633, 21042989, 39117852, 69175664, 116857024, 189256368, 294745440, 442503456, 641759376, 900689616, 225195321, 617201401, 74227554, 586823330, 140227131, 711888699, 274217080, 795069832, 242715461, 585116357, 796764497, 861974465, 769155485, 525176285, 146566301, 650715556, 73773796, 455145195, 828946802, 226153586, 685663993, 216281593, 828705600, 536385600, 309484800, 166924800, 87609600, 25401600]
ans[15]= [1, 14, 117, 724, 3645, 15626, 58741, 197280, 600215, 1671266, 4295107, 10259436, 22922995, 48184950, 95816051, 181136304, 327071752, 566117888, 942525072, 513281017, 349163810, 532145419, 154557773, 309226767, 88509354, 563257605, 789064441, 766807654, 474675580, 795689314, 599134613, 627066840, 658988947, 307608398, 337632800, 295701193, 44870369, 150212311, 705302359, 336038622, 452522163, 797367958, 62674553, 57993322, 777736994, 845298906, 452367755, 90655804, 810196653, 976943895, 564798323, 582118351, 994783972, 869862386, 697759993, 660441600, 381024000]
ans[16]= [1, 15, 133, 871, 4633, 20979, 83313, 295803, 952299, 2809009, 7656027, 19414457, 46086247, 102967901, 217634463, 437195525, 838372452, 540635289, 722168530, 638311860, 640827391, 196046908, 898688562, 478199884, 793020369, 808862771, 562236075, 94791602, 385333320, 237794527, 197694759, 398043392, 504456766, 579736664, 78137089, 793367253, 961295251, 280517488, 179779783, 947563092, 901772777, 859566930, 199212409, 920781370, 362900807, 735004334, 297264154, 482748036, 653703312, 140400674, 623159781, 320434095, 373194802, 13313867, 205909676, 360223815, 570584277, 68075848, 372652149, 961247580, 23084534, 261139053, 151302323, 715359965, 625702393]
ans[17]= [1, 16, 150, 1036, 5802, 27648, 115538, 431844, 1464468, 4554040, 13096378, 35069940, 87969166, 207781760, 464351910, 986188668, 998611836, 879505923, 237509223, 15110629, 621334822, 88677622, 257578542, 963016850, 235638961, 442107823, 429101453, 483004748, 329733855, 718448185, 266304376, 413950543, 256286771, 626720357, 318467482, 59069608, 81901162, 352730851, 104241055, 503595237, 956355036, 534522134, 457799859, 108929893, 887297322, 424614770, 265024591, 876853471, 515703045, 692038809, 210906163, 20070317, 468291405, 145357835, 797577421, 232358134, 747771239, 343859985, 833879609, 78548665, 289896769, 449285934, 313197004, 379603290, 397630660, 609910102, 442642726, 627950853, 722186028, 705163253, 998661511, 771071664, 636940611]
ans[18]= [1, 17, 168, 1220, 7172, 35852, 157132, 616084, 2192506, 7159090, 21631676, 60902460, 160707468, 399489140, 939796228, 101060910, 481320121, 151453550, 952463061, 931694473, 957528293, 554162053, 990142499, 644946993, 651797781, 791594351, 556120466, 271969917, 107619398, 710253075, 280526462, 615698879, 99748930, 775178221, 257586036, 645364809, 806795120, 340635512, 801741075, 790520661, 68328385, 331513794, 351728404, 931812262, 91105169, 176869824, 445724501, 370449983, 359815736, 918724628, 869062973, 659791249, 657727222, 395793733, 32692523, 78858425, 151369211, 628504487, 842750087, 152091477, 889718876, 908002421, 944598446, 656459208, 712920845, 47550280, 92244967, 110652620, 951703750, 217822851, 901098263, 655149074, 861896271, 859184013, 992613245, 768042116, 807916959, 335381553, 909568095, 153171069, 827990317, 681893483]
ans[19]= [1, 18, 187, 1424, 8764, 45832, 210072, 861400, 3206786, 10957868, 34666130, 102239488, 282743580, 736889224, 817936097, 262532028, 534038590, 412279142, 965109380, 86702267, 846482566, 945052509, 644517943, 548776024, 679330947, 152291502, 882910517, 188127435, 636778925, 902059202, 132531208, 193904122, 893705022, 246193070, 652079051, 958060250, 148697872, 504141990, 371410212, 807466717, 514477363, 565424570, 560794838, 11419155, 215137208, 665710713, 791504234, 359367396, 224050172, 509091270, 125989128, 782600310, 957126038, 667219607, 386301613, 605448653, 296557741, 618019404, 194294675, 222923480, 765962783, 743934970, 24324611, 512643153, 214242880, 286900578, 228877964, 91240846, 430467141, 533029377, 904804693, 373207899, 916503101, 83598539, 560288494, 363356684, 68282446, 152683809, 284461190, 124425011, 167972327, 428909487, 373215034, 420008537, 513304383, 874743039, 487193257, 97337408, 532639641, 184378261, 955976093]
ans[20]= [1, 19, 207, 1649, 10600, 57852, 276620, 1183172, 4595034, 16384606, 54107670, 166643130, 481442164, 311240781, 381378831, 288429444, 380463632, 370477330, 171662912, 688513797, 626045604, 789881798, 844990830, 70546834, 230422087, 267733218, 970080423, 75064762, 104073936, 888990608, 393490487, 819401315, 362017415, 197941501, 97730360, 491049732, 790022455, 142301163, 381999002, 81566974, 255547256, 500580164, 503785886, 874661360, 953064009, 357278689, 416715628, 656421867, 311332859, 849655408, 575613107, 850236831, 533549113, 255339339, 611845477, 501164398, 135987981, 672393680, 678611757, 552403430, 470027818, 333312311, 203812034, 929380798, 133842121, 497262544, 839881753, 29703780, 133717366, 249364505, 959337844, 632980495, 72879056, 356819838, 662140760, 182352973, 260787823, 329159184, 423643610, 488600943, 164109163, 8143787, 184454683, 684285006, 693158498, 382122550, 488552031, 777204359, 564238497, 598675373, 603916585, 720234840, 93182262, 238936257, 486420235, 352604922, 958291193, 880928218, 736558676, 163545641, 189347824]
ans[21]= [1, 20, 228, 1896, 12703, 72200, 359348, 1599616, 6465450, 23997032, 82508708, 264654080, 796563486, 260832418, 76986106, 528774007, 854313906, 307546108, 722735109, 61004626, 805619536, 18191861, 511411798, 993782454, 401030744, 633897378, 70862649, 96855526, 314416445, 92910833, 135520920, 492052755, 24334887, 643976444, 574388511, 317610455, 122930943, 637889505, 255461238, 950861369, 48876234, 149504663, 198682481, 942670278, 866921314, 563621302, 960474580, 980132644, 624295523, 399490883, 351714973, 945626033, 827908349, 157456205, 481861323, 472454109, 343580291, 683697065, 95059407, 841332348, 464714941, 596887160, 38681949, 757883329, 590303711, 64921694, 730086270, 15240461, 714742087, 32874447, 175996750, 277466516, 788882909, 11880203, 95097385, 778398376, 531252352, 479554466, 557013590, 609738833, 798714176, 859324339, 721484640, 268442938, 861267595, 806087188, 31691029, 950412807, 580575404, 849451646, 691790951, 264837637, 967322620, 365040170, 622467624, 456436788, 658680316, 60575186, 387550026, 215002020, 31349904, 449373833, 559514745, 640364153, 807042078, 450172023, 562637973, 109112418, 545193132, 195217263, 976304283]
ans[22]= [1, 21, 250, 2166, 15097, 89189, 461164, 2132144, 8950214, 34503182, 123236828, 410729140, 284813823, 790835929, 594736274, 153822108, 374418504, 157537842, 147846917, 133568389, 483576696, 508616649, 656867821, 84463125, 640047601, 955370715, 182167616, 49108700, 229345632, 795610484, 502493987, 857101031, 142485158, 996679960, 742503997, 723858587, 317526153, 365342533, 250775491, 442738912, 408346120, 881242865, 135363327, 231979623, 347291745, 824934645, 995772018, 164592917, 354883487, 450805745, 963969802, 171006181, 92161176, 169883419, 961669090, 26844445, 393784092, 571606470, 464707158, 34144520, 652396373, 745405475, 202923498, 135935314, 703695236, 776259115, 48310283, 874186699, 219390686, 510394758, 751965065, 418424556, 8781061, 736058807, 674014147, 674780706, 590530540, 4352977, 803825827, 167292329, 541083402, 260679638, 665083995, 939990721, 816665296, 886017767, 669822229, 694816125, 643235536, 937314556, 115942268, 261159535, 687177905, 12245758, 694615643, 977706180, 217949106, 118952653, 898868241, 856650616, 42954342, 330321980, 535121720, 982503521, 719423135, 714354007, 18745970, 333448882, 302037622, 935654015, 778423936, 317991952, 284756555, 504736970, 155871365, 118263505, 797065125, 640838446, 258037348, 34344762, 502389803, 911086550]
ans[23]= [1, 22, 273, 2460, 17807, 109158, 585339, 2805752, 12209406, 48792492, 180680070, 624410736, 25734764, 199973794, 977710523, 571365953, 412869707, 328237414, 214863466, 633048751, 257394955, 317735309, 673309005, 193600985, 704135816, 514918834, 650479735, 33606857, 490034801, 698396427, 67986999, 220797055, 218864611, 931163713, 940790978, 675674698, 85542051, 543018292, 61247584, 910803604, 831296179, 923943160, 89478028, 104500393, 161998091, 254912705, 539249258, 547749719, 357852173, 690014841, 206926249, 893887199, 747112232, 382059625, 148865046, 301618706, 260333115, 442306036, 247371284, 782005651, 233300621, 920894203, 317455792, 678639547, 427050277, 482884001, 854060466, 980543322, 860769666, 701293636, 771136168, 670745480, 486701027, 168461356, 848787800, 289825171, 498776317, 33320170, 430165721, 821516580, 115533370, 398776967, 333310602, 563097053, 553134182, 219816464, 216637272, 206027601, 933677337, 925510467, 267639197, 43693887, 486722546, 270929495, 877730912, 261947307, 375318068, 692508932, 989184491, 226696206, 288508969, 739837562, 849035543, 782296408, 273955665, 801085382, 431898190, 935043965, 202752072, 867866169, 151133676, 67940990, 78118516, 742654574, 165553271, 254022475, 668960857, 929973305, 656759571, 877339826, 925206924, 133648890, 623964326, 796176354, 256442424, 844384225, 955053908, 35821657, 33969824, 328610099, 171474448, 265634834, 954990510]
ans[24]= [1, 23, 297, 2779, 20859, 132473, 735535, 3649437, 16435370, 67971642, 260491974, 931772466, 129241853, 915880695, 773220207, 21124907, 663657824, 89235883, 562087424, 395633225, 79602143, 818737728, 503346111, 923762587, 810187543, 71950684, 872552891, 722894374, 788701216, 792043650, 839896539, 577542972, 345484502, 350106805, 159630680, 594479078, 806985602, 451202244, 562057157, 345406448, 404888318, 371479292, 122121086, 196184273, 855722413, 625056343, 209132008, 580725504, 234791519, 683270249, 879431955, 820639155, 890517789, 877206124, 780147370, 943542736, 532169988, 134361777, 389279830, 486085405, 212150153, 60309713, 36144061, 220641769, 167907687, 433032241, 672669299, 4840381, 543970499, 860603358, 920463673, 899153827, 269139419, 99866794, 833550296, 732963165, 649634036, 220976898, 948879986, 81746947, 249278044, 943429751, 227240067, 617290217, 857759442, 317672542, 702411387, 392102340, 598392406, 771484657, 20769431, 772211314, 777981688, 103043307, 336611982, 922346108, 46010568, 620920750, 740298345, 143296430, 127113300, 229361025, 452883985, 298773134, 583669967, 430943791, 878469881, 498554889, 377075156, 399618101, 518539100, 610655946, 762624102, 339746521, 193491143, 582788075, 58498274, 139175929, 439487543, 659039143, 969039085, 205473123, 149794944, 735361805, 144310487, 952281582, 885994682, 290034640, 449859219, 870975475, 717604104, 930837761, 466542500, 510501275, 368063612, 61813298, 959329905, 938922014, 660077190, 12025968, 335011033, 657136343, 351072920, 964781583, 196462283]
ans[25]= [1, 24, 322, 3124, 24280, 159528, 915834, 4696644, 21857553, 93405656, 369882084, 367190881, 745178532, 541448535, 237690972, 408537702, 191376116, 678513161, 493570976, 397907192, 9101765, 658714208, 122356973, 514532531, 911169029, 6916896, 782796, 910119724, 942560918, 62371227, 773940129, 523667340, 669757203, 42568262, 891666384, 467022993, 486796667, 727294526, 413613585, 787453753, 599953158, 417187968, 359849625, 117069116, 879478181, 12380000, 910899870, 838986319, 102687453, 103327364, 376800830, 429223538, 780159138, 706916356, 587575355, 971169352, 36010810, 483798044, 344462034, 787276711, 359714668, 737585540, 514856433, 506547585, 7966248, 935961, 931790046, 725219981, 437246235, 737823353, 539625329, 101294921, 998345360, 158678756, 14552916, 434899855, 58679632, 771567929, 908041362, 370603042, 958461645, 473954165, 329932246, 645017860, 950250115, 632956030, 39737256, 308287817, 593859369, 848980890, 73354610, 67983312, 794665532, 744501399, 571146358, 79777328, 768540650, 301591668, 87146707, 749547055, 542914952, 113807115, 981646049, 443442346, 689844336, 226785366, 664441023, 644644459, 65534356, 186334852, 433121661, 818953887, 687026114, 344822747, 464015963, 110899493, 294091084, 65199948, 37449794, 719226153, 501099656, 413337315, 725255533, 799293560, 259962068, 954615054, 373654234, 764439094, 914044890, 22085466, 539035590, 698634111, 313016212, 98993468, 941478268, 955683335, 902077766, 420565422, 767959775, 128648986, 355285226, 534029655, 104714136, 932643222, 778200211, 56428536, 225880543, 792355687, 449940761, 181471652, 529937629, 325235521, 6575392, 94094707, 441392085, 37264955, 911557047]
ans[26]= [1, 25, 348, 3496, 28098, 190746, 1130768, 5985744, 28747851, 126764795, 517958180, 975500521, 75313899, 914923483, 611051644, 458281681, 932346365, 712529240, 185024083, 463834094, 950836649, 286357381, 871292163, 434939852, 58330077, 629835295, 27932676, 66354549, 10923173, 590226200, 526183672, 176005584, 809584977, 222348292, 260397896, 396327746, 178971085, 774808076, 78650222, 507195902, 144802453, 299847298, 581537053, 724817078, 350425193, 503589319, 654904119, 595937600, 992781673, 82554146, 868891604, 769490422, 119334199, 287573489, 85347169, 118147346, 949694675, 540939467, 927324362, 545027201, 610310429, 769058023, 21423, 262519735, 786795808, 240407039, 428554518, 447092428, 788617633, 367724192, 374279457, 343082569, 856162651, 150954733, 962857235, 700751807, 895999415, 533537747, 537990547, 268357366, 869434038, 633081543, 603452058, 947934680, 987367826, 743179254, 710352935, 835787228, 706586787, 845202323, 238777269, 405136472, 480736674, 155194042, 871452828, 677921910, 616952227, 984554304, 602482844, 894952109, 161534829, 782737895, 850072208, 670793244, 828100052, 222399146, 284700626, 231919567, 306545173, 673216888, 772842480, 314744315, 347738200, 25002680, 730048408, 649455506, 745857274, 196252843, 529935260, 419302767, 276709210, 732855171, 343508231, 624945362, 861002432, 484757974, 367927715, 209929226, 661865936, 531107025, 413469524, 479519565, 741904536, 610072165, 606639245, 934344602, 716197790, 587584177, 185414563, 306822687, 841034662, 971868532, 919896238, 158358640, 773475266, 936203252, 665923149, 911486615, 197651366, 774528535, 82937079, 883806524, 130206852, 774201811, 995994000, 245370199, 842572718, 793423605, 740588350, 687616120, 657690139, 857790226, 37323118, 88399209, 523321086, 117621631, 71036645, 222192424, 788926021, 202125596]
ans[27]= [1, 26, 375, 3896, 32342, 226580, 1385350, 7560544, 37426495, 170077814, 716127109, 814596482, 388283574, 187079164, 480126707, 290089727, 38629756, 54115650, 64891257, 901599546, 718222041, 911275669, 323565019, 817912019, 805459451, 803612364, 201797073, 732830955, 80380678, 23464457, 701195891, 272214917, 913862649, 132026200, 669751010, 759341231, 973676755, 794065196, 967438659, 308299894, 10712690, 949669597, 781686555, 88559004, 727530543, 318751597, 278470531, 434911202, 804701133, 324324750, 981099143, 232682614, 987104568, 776649739, 786487389, 442468777, 569068005, 663709268, 881510700, 203686642, 57967683, 568729400, 236001193, 623959074, 703861418, 908672716, 70204475, 867825588, 827103298, 241630317, 362696969, 415618616, 805038660, 598704556, 10082872, 643477587, 415164213, 703084166, 477367476, 20036406, 629980785, 802614294, 952521645, 17601466, 311433959, 830294700, 548394039, 535645146, 521413012, 929141249, 283365227, 727229980, 443388093, 410708269, 286618040, 319768543, 938841603, 93475597, 394693465, 931196821, 495806189, 902879580, 707905623, 303901454, 576396872, 484544924, 486011674, 564305854, 311518869, 856442237, 372745088, 366968335, 813470622, 720542245, 551543931, 596748971, 778551123, 354920979, 984250497, 691689872, 327423759, 52302396, 920309409, 457393341, 162758194, 401889329, 760192486, 361045291, 58998809, 845800809, 8575285, 649668894, 501939170, 542308042, 574502757, 192463535, 690505425, 204738512, 689813836, 483570629, 525148782, 216925832, 952334594, 68584858, 946061868, 229986068, 113082103, 705545851, 563504064, 430610853, 209937938, 608555345, 578039088, 750439353, 944169681, 417934823, 74422181, 960090808, 568355902, 435674968, 894299009, 15861008, 618713868, 509911155, 168869978, 339481775, 369451744, 600513141, 71634326, 781507214, 857107917, 106564183, 736233715, 362800524, 615467708, 519437498, 342065337, 206666492, 505918934, 308299385, 20927738, 106279730, 457391057]
ans[28]= [1, 27, 403, 4325, 37042, 267514, 1685106, 9470830, 48268511, 225792189, 978561725, 958557158, 38052071, 919433401, 254995547, 546697380, 704487939, 32839999, 508901654, 551556389, 663564198, 695178769, 814009554, 547143595, 371559020, 945387943, 670094820, 616330760, 976064124, 607380120, 8699769, 998280938, 580008436, 958036252, 912203574, 544195790, 396609897, 954428754, 708902921, 801338681, 431017191, 381717232, 344144422, 131861617, 874277396, 830300192, 596462835, 318671397, 244894238, 904557382, 834593756, 283869037, 697514761, 969250693, 509524190, 913260759, 384371901, 692021356, 509945770, 32685910, 505430483, 907189201, 193340383, 693205397, 603006308, 305262013, 925218957, 968092842, 27052064, 47727228, 477199307, 293774777, 98292616, 663047137, 995897620, 288543890, 998081856, 524487172, 892499155, 556044593, 972323813, 578208602, 933674462, 509188659, 985492681, 986901126, 628028841, 519717277, 311965185, 897395442, 829761538, 9680527, 161715155, 343759581, 402616197, 861303980, 911400557, 358697993, 515548395, 553147014, 892738525, 205604013, 762111690, 442223169, 7841804, 517369986, 84729818, 152655938, 700957258, 898706126, 75157861, 271201265, 543855670, 440588279, 204308612, 236683234, 208667572, 404506592, 809547310, 853106482, 518815458, 16491026, 491832633, 360120645, 923872102, 602086347, 641452842, 18221609, 229080666, 428455406, 569262655, 856993308, 230900297, 490066099, 367669571, 96292417, 52365382, 469261002, 374633464, 900617667, 182287939, 49700390, 796588976, 949085023, 222503562, 658471212, 94278399, 66098044, 72459139, 603916441, 257635815, 234793049, 951525459, 549173423, 938321308, 13662267, 288258509, 65326301, 11071916, 364716823, 929353581, 839483911, 199241395, 29486252, 482468148, 829994735, 370892643, 687560607, 531658704, 568187724, 486108828, 475403750, 227529481, 124500798, 228110006, 56292488, 958873404, 963718586, 481659835, 183136868, 593123751, 622015148, 469053734, 211587807, 928091671, 481375722, 612130911, 134707706, 334981252, 784422204, 712253942, 698883770, 390222722, 25478322, 28778175, 349558455, 616616543]
ans[29]= [1, 28, 432, 4784, 42229, 314064, 2036108, 11772944, 61710789, 296841956, 322742117, 501368237, 486564198, 208215103, 787564548, 236938424, 301578523, 866593178, 461034739, 153403692, 741061604, 268366308, 41671958, 999969805, 820629183, 540097933, 348143198, 290585123, 709901036, 830657214, 397773343, 205345230, 80836479, 744283025, 767371096, 13280133, 166091858, 688213267, 405245759, 999129285, 957885801, 125598090, 229197648, 232621259, 771781842, 15692966, 623498734, 209019752, 451480479, 405116698, 905232949, 522429827, 160392239, 911337480, 463779522, 870625842, 997849245, 364479050, 834828, 300785526, 10186705, 265101999, 566806573, 614983712, 685595755, 48653250, 344390997, 673637797, 896886255, 108856368, 31386606, 486989879, 489263782, 517653845, 976993581, 117774221, 829510874, 294191687, 233225993, 831800739, 448583977, 657291524, 649603801, 456575978, 536862581, 855051723, 994222346, 302476269, 502749737, 322446053, 790323255, 357338908, 887312147, 181428924, 536100952, 55330164, 160205355, 190454705, 365581727, 201998030, 826748536, 400273437, 624522779, 849319472, 800147953, 80982274, 447705256, 168185200, 97822479, 309878269, 678607548, 912097410, 927785144, 334246635, 662138658, 715198385, 260363473, 461374975, 89468114, 651175074, 575096135, 130470890, 71518840, 879845193, 486812125, 128678982, 647847215, 49005945, 59417027, 550597313, 85275582, 589669875, 488581288, 579391253, 238935007, 307933774, 801626662, 991248834, 831660242, 2289249, 939337934, 170802252, 112167473, 712496239, 45742853, 482400666, 341362938, 957391891, 147812751, 376451585, 832724562, 418101830, 38563919, 274362964, 819817184, 400041713, 313141267, 806456583, 999307614, 670677205, 585839782, 845991536, 831623045, 109161241, 554327240, 822718306, 173814042, 363700239, 22366070, 479904205, 190929878, 554951008, 774006606, 279182950, 109357938, 401823952, 575672540, 860574847, 593910748, 547825741, 217594637, 989467389, 184852185, 331539318, 325720467, 383229710, 654245987, 146654996, 209385163, 560462909, 965812836, 65583448, 508391947, 709539829, 955465325, 214525022, 394005813, 531700924, 773028650, 417539579, 326670161, 406612199, 165245, 699092510, 550837077, 14964582, 527720684, 440459594, 268905155, 297293091, 881879628]
ans[30]= [1, 29, 462, 5274, 47935, 366779, 2445008, 14530396, 78259797, 386723841, 770080067, 561338901, 331351593, 839635833, 167817400, 497149119, 881282118, 352201610, 471630724, 181160121, 88806794, 987377178, 289689361, 946592969, 656979867, 594487341, 196240769, 948508749, 810784209, 709855728, 576276359, 518417791, 87667236, 667014934, 181628700, 79050911, 337053925, 373883684, 560120551, 458872893, 815731972, 827954345, 771964062, 380463298, 190074568, 335845313, 308369049, 297128477, 730684746, 742600059, 263592454, 96421517, 206168581, 306386280, 238588046, 136275025, 509837233, 285349782, 467079296, 44733505, 132275281, 829959933, 391862643, 62600608, 253168338, 426879146, 365435454, 91732486, 471304236, 543190875, 798110387, 894371900, 696428631, 750022470, 726550236, 936549828, 542410178, 939184541, 791578453, 983635297, 823881369, 150676558, 585328209, 653882077, 963087655, 950795211, 936066317, 71868369, 440124326, 965151462, 175368387, 40663323, 699428294, 108367130, 332044307, 970432796, 572024201, 885659377, 539317691, 132218646, 139253073, 467726930, 45351751, 297376822, 508633325, 703469419, 746467332, 503668629, 112630766, 930570931, 962347630, 576196343, 698904389, 167199167, 333129737, 608922442, 222067115, 688206452, 802821275, 954540394, 911151138, 906746447, 902608727, 890863920, 307268385, 54404696, 104370759, 495676754, 441341576, 829087999, 88911607, 975336543, 381836343, 298727399, 758323163, 709721214, 146811076, 322114121, 909574264, 955852236, 803216000, 511491931, 157225317, 671670053, 367885171, 612666342, 842261160, 508147005, 345029386, 809990068, 981225972, 241279545, 458275632, 172983843, 48836190, 961296645, 538132589, 271432367, 877708377, 386417805, 815731556, 463571419, 404450924, 113136747, 549319603, 219464194, 220054123, 907114544, 328856175, 265047793, 589592614, 328159953, 809008569, 510434161, 420313068, 107873733, 868895119, 895337042, 156863206, 48004547, 666506430, 727609186, 85858741, 59205240, 78940637, 545962715, 139572749, 421355881, 858507471, 952603331, 401020118, 942925111, 296295597, 997986384, 115737481, 677010850, 282276283, 274892540, 163700485, 118592549, 846472792, 136765224, 236032397, 179431589, 539549211, 214067143, 923131121, 999465547, 232088789, 610013691, 896204760, 478686995, 218989077, 91096939, 221616643, 243944261, 454787573, 542927414, 355318220, 147354818, 482630, 675619041, 634351197, 478341164, 574509037, 738721209]
ans[31]= [1, 30, 493, 5796, 54193, 426242, 2919073, 17814512, 98499977, 499582398, 346636279, 286311246, 338970899, 482987014, 740494022, 522312682, 389124982, 438269373, 295660905, 384589942, 269003911, 190728878, 21841107, 394443500, 159301748, 885681179, 869073529, 396029106, 969827087, 16747334, 474716791, 259235367, 753984455, 365768194, 423375006, 957390875, 407261764, 592999097, 928039310, 529328158, 133251022, 533719572, 434981329, 779487889, 212784950, 467080112, 287628298, 91658981, 576061624, 322787361, 682746649, 234833733, 676878118, 220869554, 982232103, 879428014, 742840902, 65876039, 230084790, 68776407, 988541480, 113769367, 288661011, 898604342, 790158821, 811679832, 416532461, 643426286, 357304561, 904850873, 143689492, 643378934, 217587561, 816799579, 741653213, 950522177, 519192837, 195766899, 875531753, 913462122, 931740864, 147485151, 73473743, 881407231, 943949423, 19375017, 95185407, 658198820, 654223830, 78841384, 487272636, 810454297, 156111172, 108214345, 594083015, 721613382, 413639222, 199581479, 219296986, 983776208, 50034813, 434669652, 336761553, 553659069, 443256837, 867959007, 649693919, 829394710, 511124003, 801382432, 809258820, 440312724, 549557631, 57091967, 619973166, 38255131, 989252595, 296849831, 126449228, 992478958, 948085171, 398912012, 308493194, 585304989, 581850817, 704472537, 457658359, 706849064, 974235300, 322942033, 801441410, 806760539, 930211369, 674605925, 140615032, 804334982, 654022727, 747554604, 304695097, 670935186, 973200118, 899755340, 43016718, 33443894, 486649937, 183173093, 28680647, 612676891, 17478829, 208078434, 467131016, 651933212, 464433186, 3993644, 959280435, 310671435, 524438940, 540166082, 143663989, 984026973, 596317769, 299039541, 925611762, 115137245, 238184581, 798462400, 902062936, 499673997, 696053154, 121959061, 376644235, 378356623, 996412950, 115590297, 517087995, 817795384, 731733847, 61225249, 930096903, 292653780, 149516053, 503527083, 233497811, 781589564, 87992011, 514696635, 495015483, 151617728, 478098704, 773499685, 621536652, 787266199, 440325002, 249898342, 747360642, 671517137, 216648293, 686506084, 544204132, 949750238, 249236969, 319054830, 756596931, 233403453, 594672369, 158463779, 809106181, 249481644, 610711719, 262167344, 179138909, 270160113, 278492510, 490828032, 946977816, 803242084, 541036271, 624688984, 204404014, 881539240, 779609382, 561095932, 524976628, 888316278, 139701497, 712146362, 413036824, 810411985, 241441787, 247390036, 695355554, 122993697, 227371919, 399947791, 833892197, 899399938, 781528108, 656359733, 551706967, 845829828, 900357325]
ans[32]= [1, 31, 525, 6351, 61037, 493071, 3466221, 21705119, 123102861, 640304911, 83941000, 859775332, 485271727, 929183599, 393442380, 976105677, 287805815, 238271867, 74391877, 765979021, 335546599, 709265303, 808915958, 907593582, 463983041, 147572225, 888153362, 391439968, 221443415, 801779213, 245226914, 866175931, 810047153, 267980729, 805674759, 955321032, 906824500, 367243333, 486256638, 145115859, 530769671, 290945081, 932311137, 51068986, 807551107, 185085629, 261181005, 959829857, 118218336, 295880881, 506261294, 848742193, 936582961, 153400705, 578662225, 341741810, 161659811, 816049772, 839223846, 559301757, 400427189, 216771109, 207016492, 505237766, 795055758, 945605740, 555992642, 907845643, 982951177, 401043526, 597396374, 84431994, 362552441, 746539639, 303946121, 357484364, 893505269, 526515449, 560103044, 121894895, 445706213, 592793631, 713670463, 810676671, 143889731, 392244416, 73126772, 488568958, 542583029, 752584772, 7383345, 155007498, 994039957, 804821801, 379264833, 525210782, 239847467, 126254398, 219331239, 753237922, 434345445, 635807399, 872366121, 133933893, 590603804, 32230684, 70841222, 840236255, 909722819, 689521789, 529248821, 178846494, 980363222, 548654005, 434479841, 697553680, 35011089, 544881135, 260563063, 695816358, 44173506, 726085055, 671716390, 781464159, 450226987, 146813053, 877951734, 991641337, 221699230, 419417817, 794832550, 810418558, 969705412, 219055178, 274301546, 503413612, 695160244, 74090275, 26176299, 695070748, 341801549, 897892431, 470380437, 3467372, 448525308, 439337134, 724845391, 9187155, 585558376, 372261444, 277930003, 34819054, 431482585, 279947765, 492267585, 818516372, 484582901, 390623889, 856573701, 179325546, 611189228, 688765384, 847931848, 534263758, 557397045, 116495491, 85868985, 610969731, 478650084, 585159686, 14772190, 776211983, 474268574, 460744792, 134988124, 912707317, 105964987, 809266690, 785401545, 161419686, 653370610, 499797235, 534961655, 323936668, 802659551, 370287438, 326963010, 342959476, 313044094, 148582386, 976795271, 120954501, 724957759, 860215558, 270001726, 640931921, 833230238, 701256342, 242231076, 286286219, 13632467, 253663042, 129411109, 603714672, 564008356, 523901279, 216864213, 524434304, 182659511, 983267072, 644616701, 707181007, 618980658, 405751838, 571460922, 136629759, 744395053, 539608518, 963053644, 97893406, 866038338, 265757870, 944699732, 964525924, 892464175, 168006507, 562926324, 742708490, 132927348, 526909479, 79557205, 129052432, 157042523, 659309142, 834183171, 802572815, 517259737, 256356803, 353227137, 87135975, 224995979, 596580540, 402931204, 515099940, 793833445, 691900231, 589149123, 114327507, 887760880, 389703467, 830251700, 783657579, 433484966, 412892473, 432995349, 911076886, 112628181]
ans[33]= [1, 32, 558, 6940, 68502, 567920, 4095058, 26291268, 152836946, 814626856, 19929138, 508014078, 3627542, 383619686, 178749032, 257695016, 714018516, 472708243, 782289684, 785010736, 673452130, 967313791, 416615851, 594708501, 823838568, 374885539, 520875465, 462873691, 866641568, 110422771, 371334024, 597629306, 954905318, 192386746, 711820060, 202869372, 886359460, 670157944, 884126969, 502946720, 582271977, 402610790, 343533084, 511648372, 517557636, 170605372, 597697292, 829559995, 983984749, 601678152, 265076525, 200313780, 586898347, 936910249, 473920775, 97417050, 844866738, 973357211, 106398807, 531568235, 220592830, 72245680, 709223174, 966562898, 364453034, 204299565, 516186616, 388239153, 70201813, 72763421, 794896998, 14537122, 759848271, 370782607, 723372604, 610938893, 161728308, 212501210, 376508968, 271352258, 323852567, 552136716, 801650724, 615740271, 208656790, 224034222, 747809272, 617340476, 153891047, 285642015, 901118362, 123777425, 16228193, 623027527, 937436377, 60747289, 714381298, 882770713, 15381170, 999192137, 197256049, 480638655, 953137460, 883599778, 148656904, 722191509, 39402136, 582147050, 757441169, 260428827, 253172482, 508174417, 834955862, 157349819, 261175551, 247577251, 264652493, 595186522, 812752039, 875384578, 747313263, 224431706, 462673707, 39074204, 237357876, 896371707, 361524710, 10299862, 761952483, 924315000, 304463541, 831385606, 228637562, 845205390, 599099308, 177524018, 209006125, 256908838, 355221513, 792061054, 713446694, 397486564, 756107839, 527866716, 337624854, 575430320, 456754471, 959728018, 921786900, 102983773, 936936381, 473475121, 131588049, 189268154, 863126769, 700571091, 871530822, 832046604, 609629520, 45186676, 853387560, 464311797, 368430192, 151536782, 691919878, 176735598, 972465597, 804610607, 50289062, 722819065, 20410813, 11987321, 648373171, 889715409, 778512390, 280809979, 767453391, 155472064, 275305459, 296611231, 377220752, 229158487, 259857310, 987705391, 873889855, 448418244, 657467052, 301028637, 400332864, 304525446, 853531448, 201469133, 757430782, 288842043, 292821474, 389580374, 148645279, 450672899, 404696472, 399758661, 549392647, 972607841, 459482261, 344863732, 405989209, 14412475, 913865943, 988039851, 302203080, 293916756, 28383491, 502818531, 791480646, 619991127, 151573496, 311251301, 362738947, 457688580, 884177111, 390413172, 889218635, 530910268, 818241216, 542232757, 765042883, 885001834, 10229128, 574524301, 836418812, 984923781, 235783687, 868003012, 379478756, 832878398, 751487743, 496700139, 587857943, 624473538, 510088706, 778144708, 214176553, 953029206, 646822434, 252787767, 281229254, 401166205, 434753895, 343430684, 941989547, 465870277, 861407908, 387687010, 216509894, 375279811, 453878600, 982073623, 677731113, 95924240, 198468867, 861679672, 204003039, 472066136, 228890861, 880462406, 133638984, 924365283, 274136081, 742318625, 898640542, 85174164, 775817726, 982947180, 716729952]
ans[34]= [1, 33, 592, 7564, 76624, 651480, 4814916, 31671996, 188578368, 29248753, 200002145, 508415428, 442411092, 823607844, 339155380, 84465338, 814093820, 347929398, 722645092, 146033429, 312847170, 460125097, 915837300, 530134554, 683613860, 22911398, 950166343, 297700883, 874171812, 779302544, 705201416, 91735442, 764568060, 448540109, 794383951, 50664826, 501387621, 764478731, 392332791, 697065547, 136584719, 904822171, 811342153, 498086442, 66346910, 903864157, 648069920, 294527566, 68277872, 192952288, 465503414, 89641650, 342876181, 975687654, 849073744, 732768838, 299144725, 960087859, 432060633, 521050995, 669642411, 783220798, 964761936, 888496451, 578822675, 774117896, 595815330, 556187991, 328078421, 497539038, 461150544, 593197759, 454579240, 228665398, 675695769, 189021504, 506127036, 683711210, 767254008, 372876392, 950363733, 781425867, 518441353, 618578159, 210702480, 146366158, 211092828, 25645664, 252569415, 768287264, 315751220, 46304131, 875313001, 63062094, 41563387, 521548621, 882111752, 325592507, 674715724, 754661696, 386558110, 154963091, 238088464, 48050421, 639662963, 70331570, 315682289, 290604457, 553625701, 114470501, 286499320, 302628334, 934963054, 90280656, 946037777, 701374947, 21339121, 663053978, 944685826, 452543047, 117230904, 560747251, 199227363, 16627409, 318622953, 147892287, 924956445, 813803967, 785002825, 524657750, 94619872, 228326183, 399365341, 370689535, 675442405, 908504726, 873312142, 624281896, 910865167, 214431914, 356568789, 649815619, 48684312, 203060656, 723151845, 388405201, 798060040, 729614446, 977682164, 533436928, 146813819, 149571082, 895803037, 777214043, 552248021, 204656845, 982800841, 733286978, 63964308, 481147156, 389291330, 76639625, 311176854, 441157810, 671041225, 83215916, 462900391, 792922861, 933493638, 911064426, 640299582, 658369868, 816565473, 95242536, 385493380, 848295064, 737403618, 437312030, 117969370, 718173112, 995019578, 309321859, 756181744, 40101942, 426476878, 702396178, 795715493, 835764511, 743326504, 209546865, 430615231, 826070511, 334341237, 118979238, 371120144, 839568659, 676120384, 72519, 845333099, 357629799, 910834209, 593346831, 104377605, 380654497, 634970517, 115890735, 793059350, 887063630, 651636452, 507749972, 783577804, 143656503, 242083869, 911105370, 970085702, 524972130, 465698950, 325374351, 536364599, 196104291, 139239152, 633851401, 256158579, 919175466, 894613648, 315818683, 5141779, 876022828, 934709255, 681050535, 191918360, 662583345, 207316521, 848780031, 272975543, 702356884, 769886013, 961041057, 6500208, 70262300, 494310602, 739703998, 384177576, 343193798, 693062586, 969762392, 66952659, 685150241, 630304511, 413041585, 515441116, 191001103, 912006289, 473846745, 605301455, 795067847, 856671001, 508821454, 735406667, 258084054, 117733205, 780290039, 23367661, 593944851, 692132515, 4650353, 187487602, 151055135, 898863554, 673507355, 215091232, 603704193, 594167428, 682519378, 496434131, 965159536, 430378180, 248402836, 470772870, 307340881, 347656961, 749714755, 122062081, 558277910, 169666679, 941915597, 277380477, 270070849, 652088255, 549544085]
ans[35]= [1, 34, 627, 8224, 85440, 744480, 5635892, 37957128, 231322416, 291965329, 678229698, 199102832, 733159273, 432255582, 825398987, 945721657, 530531857, 605903605, 198451639, 405128341, 881104650, 95712824, 87475937, 88052462, 854657880, 671362129, 345256719, 279913923, 405600244, 791623773, 184158289, 548244621, 559931899, 811302745, 822463013, 829884052, 612803610, 114370483, 717655175, 250670751, 158660853, 996989593, 922821653, 403693850, 640224917, 726696528, 558324649, 504260316, 457498775, 235424755, 214797729, 595578763, 703649058, 668639597, 273743575, 830864733, 8621856, 152359528, 351252345, 54682531, 631863641, 533130514, 548187372, 212107229, 690348600, 269650465, 644636821, 588449397, 716956418, 569059993, 571818753, 620732748, 238441683, 628780105, 73251606, 77232245, 265685085, 860541096, 181038883, 995121568, 787161997, 984175916, 994855981, 70309595, 279951259, 412871815, 881913054, 268261177, 575207129, 196951994, 610045829, 705950877, 200402175, 179100085, 912730914, 795237101, 264189519, 756871237, 840795855, 477498958, 568161700, 101820158, 478938140, 546807900, 824972458, 320572966, 375535061, 712736750, 146215080, 296045377, 892271196, 198915619, 973312163, 292266224, 766955048, 774760742, 724672108, 189810671, 590576941, 955913056, 705860403, 956268133, 120026477, 977289531, 897970234, 594373646, 802624855, 16139526, 294245189, 661099173, 505327457, 687552139, 570417673, 288750674, 928298666, 124243321, 103493234, 782666425, 810561902, 479140046, 567654010, 66398299, 87173858, 171094018, 401077961, 201022453, 649177770, 751032860, 458665510, 583069945, 3741921, 644139368, 777863779, 427938859, 574083500, 968708036, 5259009, 14753514, 566158894, 428971413, 29779639, 601893398, 934948155, 463945886, 442386091, 787098075, 294593703, 467511028, 998601384, 749411810, 495421040, 283658473, 287441865, 687819162, 964614928, 353638623, 648210867, 238886215, 893364457, 158958124, 29345292, 800368429, 595552294, 572640574, 913495958, 705720935, 850127566, 83220185, 799386246, 848828465, 335228800, 498492912, 819731260, 972790229, 191002130, 289923062, 997108332, 479589354, 13686350, 377632380, 915241611, 38445376, 115515812, 312111610, 862313776, 36444206, 491509332, 899038496, 494299749, 577210085, 925017398, 377889538, 129014425, 544007299, 134491550, 77644047, 150186363, 549177782, 243194000, 889811949, 476414356, 302027816, 934223010, 116351600, 936035078, 728736728, 99057293, 233685532, 715949090, 484999785, 527817757, 40017975, 403976200, 963752121, 230480821, 165554215, 501580240, 480519751, 374582722, 588438105, 13652788, 835399525, 909982574, 63720437, 165170490, 768431894, 385829327, 268804006, 950180874, 398363435, 512876602, 149304949, 858796870, 305796565, 80654592, 209088881, 365995652, 741417209, 580938286, 849913699, 209592153, 430983500, 292682916, 89781822, 346251985, 899920810, 490814818, 319818650, 865676138, 199552930, 49606030, 396988194, 289382805, 394082926, 680976370, 125444750, 312554820, 11884810, 730982055, 36906819, 144996838, 532313029, 339360681, 509568859, 763509787, 79118993, 930179491, 756170211, 627420026, 161269793, 542072728, 498021200, 392693531, 523036960, 919765468, 367278574, 755839168, 466305341, 613534367, 534169086, 166110829, 107021592, 280650539, 268761091, 590645300, 269909358, 234042842]
ans[36]= [1, 35, 663, 8921, 94988, 847688, 6568888, 45268120, 282195928, 611807809, 518705216, 990050297, 271051698, 122408000, 405189613, 94926808, 864141322, 53735275, 24011733, 736554738, 929218491, 904644261, 780020466, 504939462, 734736582, 905177688, 612557341, 964587741, 714487014, 841745335, 939266470, 221175663, 553510265, 427922711, 816845808, 551876447, 104782423, 432788437, 75343637, 98990584, 780296494, 401590023, 184896774, 39759619, 46187357, 134251301, 342702573, 517720, 358976055, 583636644, 962541900, 167548822, 161325057, 550357824, 277594189, 165080443, 231182951, 735855208, 908711807, 571176463, 42569340, 237272417, 790920442, 624258522, 720842250, 768667158, 451444080, 122083868, 366641147, 308868590, 806102171, 616667978, 212552319, 508058403, 321794596, 570313528, 460066496, 737582233, 710064955, 691296552, 63281621, 675218599, 955697061, 110510427, 512018248, 153536802, 745040214, 175960352, 594730127, 864516601, 686994354, 671193730, 758082482, 651219990, 268055455, 209604272, 794711886, 922988292, 233697499, 855180879, 757331520, 952855529, 712373324, 501054908, 610479660, 988305583, 359797155, 981016202, 392046260, 222705767, 339379031, 255395660, 760704862, 824907580, 377018926, 100950434, 568292199, 345612839, 702169410, 76425882, 316244660, 633878521, 345805531, 43908232, 498746978, 171201976, 618174067, 828038701, 451921110, 452033897, 911744318, 64098066, 83924105, 595571257, 147937863, 948006101, 514496555, 77289879, 282007238, 421799065, 804334778, 765393189, 193008022, 263503242, 355816072, 278012511, 227861525, 902054870, 618486736, 979710805, 971590402, 61042704, 664850817, 113175896, 488535341, 617582794, 612947413, 45804546, 259073867, 263038734, 265569066, 162645795, 60875191, 359494871, 979749311, 139358127, 29529290, 309151363, 279422923, 345089768, 87598058, 700337527, 479652910, 994907927, 933976635, 324751070, 167729179, 810904540, 230096199, 33195878, 559883815, 674302503, 158162721, 997344757, 974400760, 476723636, 933671908, 372458552, 487353300, 603836216, 903251923, 461631785, 620155186, 664707969, 139328434, 135802315, 547850780, 544085832, 243757336, 714792500, 277247444, 736724545, 7257213, 104433298, 33077964, 133546300, 658470668, 407613385, 15549086, 409602732, 220607605, 154437658, 434924060, 212726357, 432662346, 953726155, 55947205, 221865215, 896738564, 702917595, 219549259, 784888336, 998968443, 737927890, 111474776, 479544893, 204531672, 722344756, 339644359, 296335713, 172390948, 145219000, 740849986, 175518952, 876047366, 775536223, 909308844, 333180421, 96764559, 528034987, 396799645, 413114766, 622993858, 563074288, 710510893, 900874806, 315196225, 993816000, 623166550, 642968249, 328645521, 844280596, 556521945, 272458659, 580772239, 284457451, 186994948, 909094031, 935768265, 319893231, 114481887, 109302906, 586737223, 466388545, 717893242, 342269015, 164207650, 394855609, 330099455, 836592042, 939058426, 541984626, 852636994, 524042858, 358495217, 921118657, 464191254, 284341637, 363378706, 679058686, 917272314, 562488937, 105215359, 614330571, 404183151, 365378837, 280141835, 594380252, 79371576, 739360814, 210010442, 10232401, 449147207, 97531383, 696215921, 900156881, 51327507, 224992261, 946786023, 685932368, 729503576, 741723150, 479111191, 872812474, 454570174, 217639787, 553029674, 745481673, 194164134, 241094015, 672191097, 520725696, 177728245, 485102929, 511421076, 349030122, 157631252, 431267952, 813510823, 604978728, 799539100, 871169236, 265066919, 191499414, 52282294]
ans[37]= [1, 36, 700, 9656, 105307, 961912, 7625652, 53738944, 342470612, 999200441, 797070294, 375863958, 9523173, 166271514, 481765400, 879554808, 535680694, 467340394, 413500052, 692064693, 580959888, 369347871, 169821810, 621921924, 137911737, 940784828, 741570244, 905517670, 551817302, 657369119, 721648393, 536831850, 500879720, 726253305, 296162041, 891225164, 880747817, 182180719, 544050763, 654393489, 357200480, 356889637, 635049309, 374948412, 486169649, 407475615, 51228607, 535369936, 325305756, 74215114, 944988254, 919680639, 647644667, 526651696, 763479161, 278201627, 103508412, 387580497, 561661113, 38190290, 310583115, 569811056, 351262691, 985051203, 403138813, 643132429, 289980808, 570569544, 550559442, 934893929, 352045239, 810200946, 61218795, 42358563, 89293505, 506603831, 400595820, 117891860, 469015294, 166372283, 320554017, 155147268, 955469333, 896730515, 826039051, 931193995, 36098122, 893366407, 522834450, 917130400, 759016216, 23584371, 48884561, 844352920, 604253909, 886656394, 548946691, 688504947, 972899398, 721435398, 409845929, 399680456, 284950632, 796741351, 217452678, 611033399, 592790059, 219084711, 504058472, 277505825, 120276345, 694287126, 35416589, 305976723, 447309020, 969824889, 565684997, 62139306, 857693940, 901163636, 262850397, 927594387, 721909425, 958991660, 471789360, 260033992, 544270783, 877013007, 153311613, 85679796, 660447085, 213261352, 954007371, 8266647, 75417194, 28241545, 733410215, 579803150, 41901427, 876245480, 900022334, 813145019, 668096269, 73987267, 175135030, 724217744, 139403302, 77167168, 775504145, 397863476, 816272710, 221129133, 242347768, 885383757, 728565085, 947647994, 605379205, 598139075, 269419404, 178994132, 603450690, 652850980, 19254430, 182635911, 57268581, 239936865, 878358438, 515315850, 141611162, 665647032, 700517198, 807335907, 965806030, 897617342, 773532343, 924389029, 419741954, 420757062, 581633294, 179995348, 34733596, 923518220, 731757774, 573741822, 531242380, 813544540, 336821038, 442738016, 551572674, 470067223, 638102335, 989538200, 956007535, 613954394, 401563904, 103519975, 569290006, 144046622, 689996849, 638589501, 358099514, 725282594, 691632053, 702244532, 284031792, 473014945, 465414316, 116886234, 142777936, 342518645, 138051544, 347505254, 57716395, 939744642, 114873890, 359397343, 671360195, 724489266, 683013222, 345781236, 550104449, 877003874, 63443231, 224660360, 658626409, 133687251, 933261032, 273131705, 48202694, 144323990, 559827621, 779609382, 930553156, 35267489, 493151974, 645090534, 517431516, 368634145, 540405134, 215255527, 144656993, 549192120, 659960465, 217236722, 742258783, 538378955, 211409043, 760044403, 389330065, 692548510, 583181570, 627949137, 829194932, 234693932, 651493437, 707321269, 828284674, 652751037, 873736576, 267300299, 729754896, 429920674, 875733754, 60888792, 225478637, 39002446, 407176220, 761384762, 131879783, 661443680, 51638267, 568172852, 186052558, 637968267, 556455031, 313451921, 238551452, 644714578, 449541818, 640800540, 923965193, 38909678, 41940756, 338485997, 888949941, 526610135, 48150535, 778944981, 480892059, 874500608, 900322190, 973783674, 468787609, 618167632, 913754856, 327797543, 845404908, 752246622, 831422464, 484541178, 501948673, 647306990, 882577308, 771072569, 171273117, 620085552, 385025714, 126556571, 472404266, 664907284, 284895728, 860747643, 285481155, 480968189, 426457284, 579997870, 253315436, 264967992, 325506073, 407074927, 289125366, 710111895, 168902913, 39893459, 264014099, 335462311, 284068808, 624620216, 265346008, 330183605, 301153063, 136165951, 223572391, 416076696, 791322793, 440956632, 812128221, 56870528, 529001955, 157225171, 153110824, 659760559, 934444871]
ans[38]= [1, 37, 738, 10430, 116437, 1088001, 8818820, 63517016, 413577336, 466132154, 602224077, 950429493, 571044537, 948550192, 759622519, 360792951, 40404471, 549575252, 331339348, 353289303, 642561133, 959520386, 811439523, 113998222, 306747368, 686402540, 608623079, 625536502, 102898449, 513583096, 310389938, 861964034, 144673299, 459932354, 368865341, 656127608, 909171212, 807159815, 446679967, 582385365, 827063804, 980667706, 264330272, 600794253, 740948802, 906942889, 945728377, 18846332, 985664112, 7701519, 115050801, 870345183, 606442987, 443069595, 817056595, 621418778, 690512206, 255049968, 161633922, 402904753, 372549674, 317848199, 779510849, 454579621, 366999138, 955388684, 940196190, 710141532, 289889641, 400266971, 473006189, 518001144, 203532149, 277752196, 73653399, 957077834, 580796815, 797359407, 33679102, 974181950, 229170666, 221016673, 753153481, 718492334, 480056326, 134801483, 829292600, 87160542, 624566954, 157188714, 912350324, 248797376, 864861712, 311625650, 564724833, 638897879, 211767349, 670618766, 182357348, 406247054, 335828971, 235855014, 766599169, 873180801, 943988159, 797515463, 949064434, 37355164, 366387587, 992037332, 39085136, 457008562, 710738441, 147115812, 245127944, 221285308, 44913339, 750687382, 166494925, 487773254, 2533400, 294773545, 964749926, 838352064, 354747747, 983055334, 906311260, 773970452, 136280712, 732037766, 304757958, 868694356, 9717274, 686595153, 845171773, 715645486, 457517675, 868876321, 257821804, 398717354, 952878758, 459394839, 735151005, 982831573, 597714383, 483469574, 396276440, 147004054, 275175512, 449695021, 280047682, 322443740, 657859781, 236891682, 338855034, 771308208, 208042945, 611383416, 470020781, 959351211, 871193372, 314812327, 417008584, 157794928, 30304137, 772193806, 92880268, 735754383, 725090032, 678769251, 695572650, 713627047, 220917673, 996272940, 711499227, 615337951, 732510553, 265860373, 10346269, 946167168, 327969286, 691646116, 588894836, 556718107, 891256057, 29035235, 193826291, 413628097, 951441661, 812044940, 432676044, 866499015, 139084375, 351784477, 900166473, 781089061, 914118385, 818686834, 857340116, 329139077, 237478891, 284468211, 215304591, 458481845, 227432873, 865995208, 554027168, 463893384, 221077016, 374577314, 119759917, 360383422, 704486222, 404678036, 137104816, 809074680, 755219457, 826569646, 867839827, 768754773, 89100960, 257194726, 724398193, 973188469, 858913715, 18463743, 680309520, 450458743, 140048366, 764912130, 371007014, 456635116, 735728421, 778688084, 152973997, 434969799, 574794869, 212648988, 728361716, 542931287, 302379989, 751579729, 92390154, 220181191, 407743441, 315151252, 520426045, 407908622, 679231575, 395003916, 794034847, 347654216, 68808817, 829211530, 81601558, 162714123, 30761100, 394951130, 268715057, 283612447, 241955302, 623210420, 275963878, 159211117, 252162685, 595441437, 529655660, 437222092, 841111836, 179960886, 135660761, 917237477, 768051317, 444580903, 506791801, 487181239, 875489229, 680194597, 205928376, 680445786, 683783933, 969592088, 132367844, 396994570, 832926454, 630581401, 505495558, 385734337, 641541057, 95095471, 989574773, 911275608, 518514268, 282262989, 419271827, 469001628, 420271862, 947083037, 407529572, 59976989, 434008630, 863717239, 945875935, 75676474, 215313835, 250745830, 87811894, 264747800, 37018493, 98597371, 710706515, 142785594, 391940962, 336466122, 341268838, 21508490, 413865364, 232101532, 92701632, 8053527, 412757119, 757312194, 403681966, 949009531, 880975038, 37050684, 272465075, 678404684, 193438246, 672480427, 700064004, 142628578, 802581416, 279140871, 973655892, 800905741, 598005728, 935768930, 668573394, 207197197, 649003003, 270174246, 76144766, 315632510, 875459369, 359185050, 528086919, 473525359, 758981160, 249109513, 189948776, 344668617, 795917722, 549344159, 348920520, 486734532, 302843834, 285724416, 810790165, 350603652, 574459989, 873908008]
ans[39]= [1, 38, 777, 11244, 128419, 1226846, 10161959, 74764168, 497121432, 26344483, 38234873, 423642505, 376339808, 863392989, 917340710, 353019266, 355701734, 828153534, 204362640, 374924405, 607928554, 963790885, 940721850, 687219775, 764705852, 876861874, 763291630, 981930457, 551085656, 980270580, 505906881, 983294521, 135354674, 135665519, 630173290, 212355830, 143623144, 227056594, 817242891, 163435465, 418550307, 731605596, 289566443, 285968813, 433396374, 290335437, 260134359, 257166798, 296375223, 99595679, 459082068, 507135523, 972388714, 133158519, 975205558, 982374421, 644050428, 996778111, 162109063, 746906113, 514292299, 926426755, 356009260, 196659267, 409916170, 325494529, 655002543, 558511285, 36446396, 471095084, 174722764, 671116976, 160891233, 868903396, 304037581, 23612943, 337881011, 234387037, 370561646, 356075504, 698718914, 535181667, 514726084, 815242029, 608023573, 448544035, 835833664, 991058290, 399256230, 20531824, 669361826, 539724566, 760387110, 830813942, 547045707, 178050500, 929198630, 6813905, 110412371, 858816899, 809729618, 833864785, 232951975, 485491061, 613385270, 553071180, 627954610, 952757220, 692906182, 748961577, 662247263, 52513186, 149763764, 145530822, 33882391, 453364543, 997405166, 992558694, 759602854, 84367345, 100239977, 854081961, 858205595, 486024240, 91555639, 177882871, 949083392, 519037398, 556513157, 228484413, 492836072, 589348909, 196163508, 266626335, 11245627, 157404436, 270481031, 638406640, 490889097, 527976504, 370488458, 823400678, 322868722, 206357234, 647142926, 768625346, 265191551, 148038615, 363341916, 267722164, 893118504, 738977503, 565582757, 762106365, 849369394, 766495732, 13155357, 515888816, 523640060, 647203814, 437352666, 546684558, 961386555, 7614498, 893885274, 936701598, 428062192, 113231261, 402917050, 409965843, 165984892, 799921270, 659405770, 509144023, 774701607, 842603658, 487390464, 251731862, 581859608, 922860080, 258383681, 201597752, 292594441, 460903867, 638298912, 848020590, 765105850, 965506327, 844776867, 575276415, 85481014, 653985938, 197424999, 197600210, 989591463, 112466859, 918937916, 878289962, 30252094, 561367106, 701604983, 794157139, 205106586, 358551581, 218730442, 820317821, 718077344, 742273426, 343977802, 723940137, 91227055, 889419899, 835334285, 445942872, 874169472, 806494972, 841559090, 34902341, 936247116, 742348345, 932764662, 776531786, 136341990, 609226011, 962126351, 692609037, 492230872, 512261831, 61424189, 202712100, 557188069, 23267751, 10862209, 780311892, 698216821, 610626474, 445698906, 548927052, 791636623, 278469086, 802570473, 843652647, 214889050, 950325814, 545811188, 732525066, 799299048, 547938769, 119233118, 836166054, 515368215, 821018309, 703809789, 385697728, 474302192, 326687407, 701322950, 753939342, 860741461, 608860184, 481069405, 497217661, 107822505, 538149776, 65872865, 267685484, 630211463, 833714775, 127007356, 988488267, 704390393, 326686679, 330510067, 968474337, 860095258, 865223840, 3530159, 602833824, 943838253, 510792598, 862215682, 804647558, 57277705, 379631476, 611335785, 827032941, 500396827, 166974973, 950996383, 97277257, 336237474, 527425945, 836169765, 13569792, 45600126, 103702022, 589110361, 158793934, 917834123, 750227633, 450511448, 228174293, 380815071, 984828008, 35225572, 19924799, 316530723, 169463852, 11894443, 83625994, 27918722, 725825514, 510537357, 901592447, 560692763, 386943274, 409576331, 409681305, 19743037, 901841314, 504205848, 287987501, 95070522, 999713439, 52172335, 458657276, 716446234, 960325619, 967217606, 29400294, 323715881, 571473809, 542099425, 838958945, 826022366, 215456133, 111542899, 27057122, 264098733, 414451664, 367598279, 660361161, 317432327, 788309656, 482969647, 453723335, 307123116, 46250346, 156036134, 550671015, 501877998, 918162544, 672414507, 744250791, 519150731, 449335541, 717241257, 798831268, 772517138, 286300330, 910111510, 66350225, 850058429, 996528049, 454249733, 463645138, 33673728, 195487971, 700828817, 25012182, 447505308, 968790402, 312778627, 684898658, 698549052, 965513947, 825161447, 410399245, 428579579, 669192144, 82412074]
ans[40]= [1, 39, 817, 12099, 141295, 1379381, 11669611, 87657665, 594899060, 695536795, 226472285, 640458905, 794561570, 378189352, 472728269, 218438573, 56516519, 255055733, 845027144, 588332091, 652544873, 575593478, 251899261, 421780632, 446749115, 397384403, 967249876, 562965804, 307548860, 910064219, 267557957, 532097834, 694036707, 378870548, 124206593, 109699395, 5415029, 722948552, 875697847, 694452268, 7553293, 132421363, 106964105, 391245927, 870340375, 243365738, 69805673, 199865008, 75486973, 171179760, 109991897, 220793643, 513746719, 106419838, 540171765, 580499245, 759007158, 982900537, 645687882, 590392656, 601803737, 221575615, 697448067, 153409333, 368742411, 593478736, 779784392, 983542304, 533669091, 167997680, 729893362, 841704349, 760614624, 47743042, 998724205, 972938209, 77600320, 536850090, 695359058, 769331095, 966134679, 528777379, 695035445, 387545073, 911151592, 242062595, 521446824, 889535341, 920252167, 112865832, 806555197, 118151259, 625842139, 701618487, 790273468, 694977537, 572862214, 473466414, 246109368, 48621359, 353657541, 554932622, 499105369, 867797665, 487345603, 842033962, 519557065, 245850790, 335288378, 782811146, 892240358, 338051309, 826545456, 41171254, 334148733, 152569170, 144665017, 941279118, 897754414, 89241104, 416864510, 41530804, 299074740, 73588196, 959211062, 109470038, 500259918, 366443802, 403320596, 183957534, 992196343, 652194487, 652679636, 980112362, 896443763, 694053263, 85474084, 793481845, 36502549, 113761902, 13660255, 295744749, 768030597, 559676644, 267907464, 329732897, 34721556, 481917917, 470669881, 496023609, 35319413, 426881953, 436183525, 539581676, 797395436, 949513087, 636400441, 684066319, 283217124, 456809507, 742722246, 708837224, 1825110, 845476655, 721485134, 509524702, 571748192, 313097600, 164720049, 83489702, 463694600, 122519767, 438333196, 350973050, 742760174, 292313656, 699166885, 733491013, 480543050, 245749577, 741817620, 207993307, 244579067, 622422144, 604751887, 899189402, 151409381, 217727618, 880477312, 214663719, 394263729, 196688383, 548030201, 726215545, 464673145, 261250632, 625458514, 838784252, 982491280, 700533618, 585918514, 160625577, 639912412, 329107337, 639996475, 820595096, 822718095, 278815123, 496262265, 918547360, 8027724, 726754416, 823448457, 260321413, 863184482, 650858805, 276099402, 685460415, 954079520, 733965175, 676833996, 368637623, 143549481, 304621819, 472579474, 749596748, 116386311, 410243381, 633945382, 411647917, 177570608, 616578162, 767744928, 61290651, 523112125, 276619822, 15151789, 253528389, 167816966, 891846580, 541892511, 341041750, 391023167, 293092921, 243156326, 622723871, 473135257, 726189187, 379573236, 555335821, 257038714, 482079083, 723871307, 606515981, 65251208, 632383753, 147352575, 594192641, 924833549, 483314326, 808069004, 770319259, 427864560, 25642674, 464671587, 569308215, 637300329, 923466624, 23057035, 86870702, 983746124, 846059215, 574808201, 554549209, 446310553, 959681948, 778636627, 211592095, 516682914, 291911580, 587928798, 427680003, 894209596, 866648165, 679666232, 460484096, 854394115, 982195268, 822495481, 835383529, 431162040, 830468499, 195346596, 57036658, 866149457, 860543178, 818146210, 279107618, 892401239, 225036974, 868558986, 685134666, 744469605, 156127522, 187537334, 788919638, 909025900, 672187019, 217419201, 384265406, 616374282, 378322214, 141913342, 501653295, 461070473, 25985020, 589549638, 109433868, 888240019, 931367280, 762349235, 234613827, 765084315, 611038359, 758764450, 286873014, 382512476, 382119459, 20294058, 943700532, 211933192, 58390954, 180966724, 929698288, 805610393, 509211182, 866583662, 775212548, 88368846, 726939816, 185342247, 229877142, 705155204, 200856219, 36832958, 610458570, 660966337, 749737121, 592806565, 894272325, 480779946, 649154472, 88597955, 74084666, 744113332, 528684751, 282107891, 100372245, 756922141, 58776739, 981772435, 924634098, 951039927, 397719622, 577729727, 762973087, 736969640, 674672356, 297937804, 986319572, 149411109, 496025335, 118765897, 173573997, 13186371, 696131467, 139811703, 497652080, 238358226, 252091863, 126575962, 416549513, 112043953, 769546766, 210139961, 218718185, 975953506, 930028805, 845629302, 57030776, 852433935, 836915594, 400219298, 622051773, 829969111, 114603161, 10751254, 909008878, 579282117, 214070865, 563200757]
ans[41]= [1, 40, 858, 12996, 155108, 1546584, 13357338, 102391268, 708914679, 491589996, 307979410, 602522471, 317222127, 290284759, 54099411, 989042041, 349750818, 106531062, 706143382, 63807262, 819412921, 144007031, 937903432, 671633208, 144280187, 535961584, 391683158, 665684992, 173615217, 173957993, 353557533, 689224661, 70346145, 249590014, 418977958, 826283746, 394602103, 916349862, 513826761, 491750575, 183159109, 757685121, 418341803, 274891227, 642914114, 790796259, 588464975, 740365449, 551222753, 10565934, 35820801, 515689568, 211177017, 828019707, 68961130, 155306993, 295844962, 698696703, 264483577, 967049520, 615265667, 559761896, 719262960, 509462378, 575657367, 591920899, 676732702, 723371825, 327050158, 311506131, 94078284, 608080285, 992236405, 137506625, 399044419, 458634324, 553334522, 801149022, 685520978, 446537546, 993927587, 293142441, 349812890, 364132070, 129851348, 857298051, 877404263, 877505804, 63808796, 43779853, 597054006, 757518688, 847719064, 814336009, 295491019, 566317327, 427355879, 99632937, 271930495, 211594531, 907085661, 370381473, 40651392, 893659649, 363630034, 486697292, 957988008, 762036357, 927839193, 855832860, 336383816, 307639758, 266751066, 682795763, 757933830, 702637096, 416587519, 241670221, 803239702, 991067388, 753770489, 69318095, 379601638, 829408102, 918333643, 833524181, 647446668, 999853061, 600717076, 736359930, 166694847, 912637361, 883248816, 334184966, 360770954, 907814459, 571070899, 760625736, 543003305, 12232839, 27415041, 235755079, 155935992, 895456358, 299525687, 387663753, 430722193, 845849975, 389897647, 157165043, 232374231, 709459451, 819494807, 873294798, 982307907, 723241456, 529916420, 190269000, 832006535, 157577121, 119818595, 751958343, 818604698, 923214476, 455357809, 664208514, 204222119, 358021985, 507909159, 532713722, 447934290, 550255949, 9030523, 204809569, 704696131, 798537153, 779574805, 146334295, 422444856, 763243391, 968318292, 409596303, 730176788, 661449533, 145680243, 291092743, 406566554, 840725280, 859336604, 385485264, 540592314, 491573347, 430591599, 799102625, 349645352, 953856191, 685505744, 968883032, 548153198, 991972402, 298640488, 335784052, 560792641, 200482497, 534424478, 835919822, 256133832, 789502694, 815463653, 367192054, 711296060, 505894941, 749371649, 586599852, 478956964, 771301542, 936596369, 641013477, 895880622, 275251735, 709512313, 675062513, 900057226, 864601515, 604121575, 213439255, 718556713, 352300658, 293209273, 62461535, 212741657, 925233457, 601757735, 357273411, 900952265, 337965737, 654516053, 138964736, 683012438, 388413281, 151113816, 328964247, 191920444, 84786019, 179152386, 346561188, 643354711, 718267295, 169193229, 252223726, 887596939, 657097686, 142103925, 40078284, 150004901, 459569297, 459199105, 789641065, 6481222, 858687076, 375816137, 147145108, 520309635, 748217920, 667457550, 716254093, 186260954, 725808394, 626037945, 743543562, 764478177, 601933842, 797462265, 777370200, 654651513, 156072819, 707272486, 178868661, 27986290, 925976600, 457000898, 540704905, 843382395, 769084631, 760118502, 476552208, 749317409, 710185045, 964800796, 516878606, 266237510, 913933501, 813693982, 336046538, 762072594, 997287607, 756174558, 615699332, 325935068, 478725181, 294206110, 71125626, 862744505, 369229533, 687983312, 908265361, 496504119, 960935105, 69879109, 315010091, 778995602, 757128123, 249975621, 699329744, 984761141, 255696873, 966070938, 214893935, 551564463, 316442626, 532269369, 314110968, 128028415, 969165598, 561496103, 817486578, 282697706, 480617072, 509205119, 834540584, 277705122, 660874354, 778117470, 366056531, 831243822, 903068403, 672944646, 441340373, 340680954, 617276976, 849516577, 560088434, 230800586, 10428026, 372559113, 922230949, 889642650, 244184042, 533938488, 841639506, 817920213, 336934324, 44823033, 565545678, 701086145, 241957483, 114182239, 850726147, 526783422, 115816117, 835376982, 659266467, 815849396, 168028335, 255187925, 748491938, 622185783, 663040863, 743392515, 163408177, 383060357, 31556416, 794030948, 934245344, 258437764, 379321408, 40236316, 660469577, 655665845, 690942361, 375378322, 568352979, 602028119, 317437606, 657543398, 100015852, 252684947, 481051042, 964341166, 522946308, 280791483, 467949044, 475945690, 972019230, 462068105, 580258224, 819125286, 65219413, 675919204, 938373431, 246074242, 416112669, 990084376, 992206586, 174382581, 694468435, 670357482, 52707698, 430228891, 194064984, 374269653, 873105421, 89789806, 360326019, 422866288, 247972613, 990139142, 766813630, 25619403, 929658745, 91230876]
ans[42]= [1, 41, 900, 13936, 169902, 1729478, 15241768, 119176344, 841399673, 434809990, 446105964, 492649140, 758977149, 206041682, 323715565, 660084286, 595902939, 912996958, 734408694, 639760787, 253066665, 208103163, 518638879, 141246298, 316067064, 932295902, 638352197, 835906694, 518593201, 772224592, 710767801, 155069328, 87760296, 888628863, 85616127, 159719113, 852745152, 116208329, 603162784, 598162586, 214665773, 928212607, 364268988, 422947444, 91651894, 294508512, 306449339, 29129368, 721764444, 23720919, 155935808, 134434641, 906918132, 581645037, 673925534, 656820458, 712140580, 940311261, 639783029, 193680127, 625191701, 485391283, 454129733, 912047676, 531795443, 151893083, 16212124, 506754047, 491882623, 143293012, 25311790, 265858487, 730580376, 281408346, 313354998, 904477185, 246774679, 76212745, 790588368, 952519623, 156839403, 194467618, 872887052, 91963369, 534129628, 238356180, 632320800, 58443419, 722943306, 618550091, 33518175, 519583410, 960079192, 538023159, 305123951, 486152058, 294482726, 518323725, 455607677, 182021187, 748135143, 512410493, 35362801, 719659644, 317014598, 528329960, 583008290, 443175574, 659178079, 174647583, 349497845, 577399146, 818913619, 271472027, 656817275, 494680790, 969710982, 229444476, 267631925, 175671131, 35511369, 58752774, 135202754, 944159958, 464206230, 475819996, 314325811, 754861491, 276808552, 810159244, 91192489, 626570800, 590621471, 514780234, 305537247, 801654104, 149383516, 787215362, 114530579, 859617326, 613074050, 468568467, 919259772, 617744284, 340905322, 985953212, 372028816, 217079653, 938494776, 284906842, 769978385, 515786223, 285120775, 375534381, 675385916, 665832700, 133450834, 3874364, 408375526, 770616302, 276273159, 413928636, 723794836, 198571707, 678091222, 296508406, 529916658, 588863591, 413257244, 498474249, 915935032, 120501359, 836927142, 230121084, 774509032, 870826787, 489996192, 917057075, 196187219, 383821852, 922336284, 22274995, 748507616, 607632780, 183109949, 339998525, 507933598, 698781318, 498085612, 803731847, 473820207, 901546035, 302928184, 865394080, 114078163, 2199878, 779942965, 594445523, 91527221, 272107811, 718335802, 365412741, 52329171, 414520032, 494974650, 300177708, 811610962, 146810674, 337728819, 506402762, 403329973, 694340600, 766854981, 757139989, 188368338, 788752320, 918847437, 928046733, 527551285, 479184799, 517252899, 712149490, 791491255, 238449676, 667119615, 757940899, 445679476, 734062646, 326185889, 40504124, 623294475, 807102585, 697275776, 960233124, 90479243, 277423126, 459856976, 523164613, 283246190, 353589088, 214300387, 783487356, 692462518, 267488040, 851918218, 799153667, 810257248, 109085516, 633189413, 670646041, 913414538, 526057886, 701571781, 823895555, 366072317, 141394361, 832809290, 464577360, 305577012, 512815120, 121404516, 195457318, 321946163, 309097012, 239601477, 94799504, 314416433, 43085740, 639634392, 892727867, 559091131, 668748148, 422889784, 711508368, 676630033, 634668710, 364293294, 844937242, 751071408, 322260215, 891789141, 187899827, 511558264, 521391391, 670781806, 509672700, 51147255, 62331255, 681097643, 668432081, 698715101, 46454740, 726474418, 934462337, 72103891, 408373632, 957100449, 670661469, 786800623, 834620545, 287400489, 490496888, 497846381, 189806313, 912940390, 809020495, 703284720, 835793884, 605744360, 923348658, 214377202, 697918809, 343995053, 445012242, 544883273, 475774494, 73159748, 664916820, 945806189, 388033609, 184443581, 891139166, 132967061, 662232592, 630310273, 296941879, 926467100, 732662520, 755030683, 373067237, 200501225, 132039597, 621016442, 864116597, 199168443, 229224627, 19895297, 392227721, 512572983, 888183257, 954225811, 362992884, 408318299, 664465052, 828120392, 703374891, 61248349, 16358204, 241119413, 30565637, 838212406, 921697699, 543334430, 89858526, 273185879, 355471309, 304528048, 507574008, 476038937, 789196651, 57644735, 932966132, 292240565, 284284800, 198355642, 844613937, 375170024, 881957600, 108981244, 644631978, 730251746, 563646094, 15703371, 891969119, 462467018, 842418885, 184776107, 20489508, 525173823, 93913531, 199936707, 49296883, 500271791, 9386940, 42793104, 102301079, 299925062, 242848544, 157270543, 567750735, 512260765, 540910896, 473863432, 123756576, 867793612, 940752336, 189701376, 338838501, 163690216, 120916067, 790468763, 680974009, 939542025, 299064055, 752326705, 668302564, 775312490, 929999123, 713601128, 593704708, 595301628, 539445680, 220384571, 492539730, 572951883, 264745653, 946510661, 751486844, 372815432, 445849920, 481560920, 887629330, 46438187, 433046906, 550746520, 68280122, 549536967, 98170304, 942092421, 657076175, 85959544, 736296914, 244774210, 196059783, 968298850, 183375217, 810099519, 413635020, 636120983, 396309504, 740465895, 371532101]
ans[43]= [1, 42, 943, 14920, 185722, 1929132, 17340642, 138243024, 994832181, 548192008, 829424358, 702470585, 488681655, 275370643, 835638795, 810867407, 286977068, 950047225, 83539435, 44629372, 288790619, 507410843, 264046736, 483012816, 672138691, 875194556, 651203850, 66911617, 918075656, 674825734, 94581776, 415282344, 303997379, 819537616, 622429217, 698967413, 751254549, 420414807, 687830513, 601402264, 434289505, 724948167, 754889253, 808542135, 995391960, 178813332, 724416372, 177739106, 814105099, 753597104, 45856871, 272275296, 786414287, 511285559, 160720229, 317562390, 790336119, 868224061, 359611251, 78736463, 773457035, 927802445, 421722380, 116775238, 364696053, 502866895, 626441652, 490807991, 713262576, 797949369, 598695934, 260170588, 82830001, 494545919, 272206045, 443643728, 598266021, 33015507, 884148700, 307476402, 959867411, 216334812, 800291904, 985570368, 488188448, 107147695, 538136243, 662412600, 979298525, 134498654, 226734918, 727004323, 749341953, 119616289, 344235011, 179701806, 771727176, 867138213, 462181714, 886155872, 120844409, 637609736, 732957723, 950929297, 917858187, 787591285, 658307576, 752393246, 363474545, 410621001, 994736846, 177814531, 780475306, 862888709, 592093607, 579502147, 557845688, 288775481, 603183203, 577960148, 788283409, 673824051, 683888139, 877184660, 633236685, 114600324, 443874806, 243845462, 737247494, 816215602, 301818289, 678209727, 613605938, 858234475, 818583083, 638002191, 955539556, 166659792, 402119583, 136117938, 121601666, 755992562, 47984728, 295575049, 499852111, 307179145, 332974068, 315732357, 716712867, 640162541, 867854182, 934376752, 313718034, 59903781, 946384843, 119557570, 525136020, 151571916, 798992199, 641098837, 260839275, 993458171, 824535499, 355644177, 761912070, 816737774, 16159145, 269418274, 606453921, 360745230, 8968332, 697762673, 987763777, 660889863, 735951723, 644168107, 694447061, 112348183, 530007620, 3042837, 764274326, 848173528, 194620935, 635775962, 259196720, 713828904, 940082694, 457694335, 838811079, 742877821, 825043434, 999682813, 323541591, 50872352, 337477908, 513975090, 485543671, 991738379, 437900643, 771900426, 686428428, 563411325, 914169111, 935692665, 43568184, 490175371, 749564693, 101137943, 245839802, 603981104, 626386341, 386920859, 413292672, 913439917, 70347116, 434898910, 144090153, 824132212, 891175519, 132402569, 347193520, 969072546, 16729602, 608672301, 618817500, 911982521, 688615529, 732174336, 500282116, 497352932, 456415575, 878875953, 316115544, 915703538, 598465482, 596140294, 730305232, 164832432, 897815573, 166896959, 324516472, 764718824, 566396641, 914517008, 874306816, 779763109, 852306547, 611269114, 292511571, 915381300, 758955270, 257373679, 74625589, 121789415, 230596845, 205840454, 916544901, 23902587, 416402779, 293269031, 510816400, 975368660, 955188220, 72244504, 561311434, 137072009, 127537010, 860723336, 883260674, 394382836, 913512596, 497775666, 206616201, 483790701, 11643758, 543373789, 107216374, 536706614, 345207484, 197739695, 416959310, 802020491, 883579389, 155472766, 707726533, 878636875, 137339984, 387604391, 170286771, 862464509, 93116703, 698306089, 277231574, 157624181, 518482505, 545923209, 301838767, 429107456, 65466197, 400869145, 603396151, 201146053, 29560436, 908247428, 740900666, 645622178, 468181946, 182006817, 585006092, 39427009, 901513909, 575103140, 643739693, 969005418, 413112711, 121940507, 949419798, 274176335, 533655948, 73448571, 447893873, 303200166, 406062958, 327948494, 399154885, 680966803, 676784794, 346165530, 118434942, 634041854, 219847494, 927409557, 731595298, 204066166, 484721091, 397391612, 62697528, 613046235, 363210072, 588627148, 359818291, 176675393, 710790103, 31891420, 193284227, 13322649, 80677012, 364175866, 156203486, 303397217, 540753075, 969185318, 762928705, 479974322, 873609278, 714679223, 243389411, 893917661, 730412727, 540295939, 380888528, 199480073, 111615382, 501213077, 699982545, 83674978, 340471893, 589623231, 135448371, 354059110, 416125008, 490338358, 869847423, 644581498, 153365962, 261322947, 680966984, 400282844, 542955010, 604680600, 412088220, 680278649, 139286485, 860834305, 469429775, 280658323, 253030904, 2560916, 10309871, 297479762, 823144855, 871982081, 47058346, 963847165, 382927224, 356584190, 324565827, 306141977, 910279795, 453817674, 601981427, 979339306, 222338413, 904561649, 382529080, 408856660, 854658577, 411827225, 670817056, 827144476, 223389693, 471934610, 930635535, 587441381, 722797748, 95690794, 663628478, 287716698, 646651719, 701670514, 288321331, 90367689, 303151955, 540716833, 449495113, 614473847, 768187147, 779428778, 859329178, 317839203, 24311574, 208713726, 534909824, 569617669, 779723332, 951823587, 262620278, 508684571, 644816282, 124674019, 369884532, 146396384, 993989514, 828097325, 353947367, 356630001, 483119775, 36683277, 829372562, 480348153, 416969202, 237164413, 917166508, 673670902, 955993972, 550159722, 115253791, 571208381, 883450110, 234414978, 338605160, 465632072, 975880238]
ans[44]= [1, 43, 987, 15949, 202614, 2146662, 19672862, 159841410, 171958174, 857707214, 674952199, 863564473, 694487987, 218927913, 150857334, 64522123, 242512102, 726888439, 233627107, 811786714, 114239005, 343074532, 372330107, 720689358, 467711835, 904517093, 48140523, 445520536, 151023837, 477389409, 167654505, 524330326, 826025786, 750662832, 873751815, 63739722, 191556854, 667326112, 50500515, 441625511, 782830742, 400734038, 564497630, 921910383, 845548941, 368028935, 749018447, 103585045, 796556849, 628596101, 868979841, 539520158, 627354569, 90231323, 417433082, 56768496, 355579497, 422451590, 886349503, 72956900, 803725461, 415871073, 683643384, 621063238, 193330057, 325926450, 277754812, 24871409, 448472012, 886190243, 823962291, 441987145, 894908057, 837390023, 862747763, 91512877, 722912649, 93349481, 545810047, 913016979, 515556016, 298546360, 734212089, 844284728, 136068973, 71028614, 122223407, 751306630, 44843394, 423748616, 386401231, 812571458, 811253207, 883210298, 108253088, 777750730, 94398075, 357510258, 341016668, 444595182, 421469474, 846006439, 697364303, 430219357, 145159, 329923811, 555736286, 145037472, 50858159, 758063180, 409311835, 199515197, 849732459, 429458586, 110831608, 601311986, 405029768, 899721594, 362036575, 3616348, 447767827, 718164293, 455022502, 154627334, 632024645, 923207902, 841801838, 418932384, 595460287, 460605434, 188513457, 767682601, 51793196, 194981425, 929803954, 504733978, 22197692, 870666331, 333136663, 819520200, 530915500, 599537526, 53266589, 48676597, 387019415, 413134249, 89916173, 988538195, 741237674, 580557472, 340811443, 13472882, 840030352, 781975641, 296220934, 702357371, 942050407, 935085214, 845987731, 799577627, 872670633, 692587304, 440284632, 702895036, 10589510, 109084537, 901549736, 680965380, 523560865, 14608855, 766098800, 955736031, 229070295, 918139336, 762087315, 15060087, 769624318, 210516326, 269537431, 932448778, 651446512, 367308406, 624037144, 927670291, 415521073, 854675140, 947034643, 395133007, 858104556, 792426709, 918444166, 282314711, 96653546, 423079321, 469451942, 792999037, 308400615, 330587501, 691818222, 53917678, 568461122, 362577365, 775464857, 904714011, 845440210, 795470521, 568880508, 666239878, 183860147, 125507811, 545400921, 401495311, 3467092, 430876347, 332849310, 96436924, 957680475, 836934713, 150232592, 891109199, 995835861, 145792868, 255284669, 853681633, 801676454, 45857933, 127560794, 137690320, 534209092, 436059291, 890838261, 134212816, 302504982, 936257832, 761720727, 269396963, 28197218, 59083210, 947207164, 442972791, 384169121, 488722025, 351406087, 443097712, 82956552, 698141640, 145942108, 188889308, 734290094, 387705377, 912805029, 973822420, 47485510, 507370861, 221674431, 786661915, 91335607, 856760661, 173031704, 864904090, 599152735, 495185408, 938099393, 556362344, 990758140, 995900803, 254599934, 462199704, 5008078, 665636661, 527028350, 642386127, 1829553, 551952980, 424017355, 108488740, 701380336, 806666866, 700141562, 59441909, 362171728, 894757457, 445400929, 773238426, 127546419, 723395394, 338826564, 332919619, 340737249, 850054615, 184058121, 13063831, 278558952, 698063140, 498777528, 72607237, 345269132, 902279995, 183690503, 772520236, 708689187, 233896476, 458831695, 230994551, 41124197, 206351350, 689101399, 262700029, 620939252, 892377787, 428085255, 694339277, 213848040, 916329377, 192795757, 474268014, 561285670, 220016093, 638297144, 193877561, 647642810, 64716523, 5417153, 709160560, 438820650, 471896153, 456049785, 424945489, 102312939, 179871925, 155527933, 66018018, 519349428, 575834851, 366155295, 196027859, 709388961, 444696414, 108229719, 111474967, 169464130, 765045351, 916818004, 674916990, 958919968, 932259128, 849009441, 829390390, 846317162, 253991616, 482990034, 163822353, 775754269, 532037321, 49173712, 212326050, 301906174, 678424573, 534302771, 375782334, 160287870, 855370313, 341617592, 25457804, 708941176, 246832732, 903916100, 546588049, 96029971, 706821232, 940560978, 101534792, 337492719, 856837601, 613769045, 707646199, 812028723, 616833643, 679800396, 535428679, 224426630, 413895724, 784683428, 431644219, 111092914, 661756720, 639659700, 41894591, 68359952, 43802473, 952730000, 823133424, 376059765, 707785553, 822330735, 771301262, 948220958, 908479296, 864547297, 515908783, 27167717, 175015260, 401476125, 721945851, 298498970, 707819205, 838011772, 889483594, 356594984, 693435347, 967781679, 401435494, 355846180, 333596320, 628919505, 303558980, 984974994, 113643042, 89409518, 612893129, 122412730, 114900098, 810658251, 247580260, 945287301, 609126629, 492005778, 772356444, 361927818, 440145503, 858752994, 174471327, 210890472, 769016792, 638211867, 546015263, 377533141, 892710683, 705066724, 412035898, 913706912, 989583745, 102815427, 296051463, 435828877, 627348761, 994079761, 369313875, 909339708, 172995194, 816793393, 474860389, 821690532, 962160124, 246051373, 970475428, 561698902, 165844443, 708639335, 918973613, 861542417, 207950600, 197794802, 563223285, 448456804, 787570186, 926930606, 566070711, 279041721, 162328562, 287318056, 191225488, 14318341, 585550504, 409974535, 697728497, 891226405, 200433586, 381575055, 638337683, 483277973, 755030264, 867834356, 962849947, 821535631]
ans[45]= [1, 44, 1032, 17024, 220625, 2383232, 22258540, 184242832, 375813872, 392612893, 231706087, 882424931, 687132034, 689650073, 577977876, 303878988, 24310937, 406963663, 625468735, 582435950, 41660062, 421950986, 98962940, 938709884, 758565048, 969234571, 703952131, 900436492, 658647225, 285611947, 399326780, 419454732, 205387170, 983950227, 49990302, 189001672, 62673927, 586296391, 184361166, 506353667, 438069708, 256171907, 825943859, 951340167, 368115756, 522855639, 198647246, 263328246, 450011807, 434855284, 725807775, 648411666, 18383140, 128787399, 387148373, 905324825, 158891954, 656234845, 213026076, 490012707, 365468167, 200221292, 298615515, 290107567, 35072337, 317672326, 60118064, 676291945, 898619095, 494511021, 35193707, 681989460, 255539191, 6318676, 181981289, 309123618, 769843578, 942743189, 29734288, 954472400, 463236670, 747980714, 175643037, 260101113, 77874147, 589524374, 710018290, 567729062, 854908844, 767838566, 521233813, 535397022, 395450772, 519565978, 430844324, 691804767, 750969410, 915664434, 335442962, 327801393, 599337662, 151524696, 372580414, 756807473, 202845724, 578628778, 324772867, 495203100, 594805038, 176866440, 134364432, 797477913, 981614510, 128692174, 938852792, 42148884, 122641852, 370944239, 473851910, 935488807, 532851475, 689984371, 438315593, 696398812, 66001022, 428174065, 54501471, 80878480, 666016821, 47295976, 813797397, 317765605, 714997505, 258919731, 82884010, 661027522, 582655484, 361252385, 24311003, 432884688, 368733632, 23821090, 792526029, 846601436, 536812192, 29313630, 382435159, 426147993, 517181759, 645690342, 270896281, 775661220, 283600768, 240876557, 135665693, 104458079, 616729602, 497103691, 828815240, 86098789, 998656307, 754065783, 488969594, 91503702, 52278308, 883359011, 733253122, 448869387, 985543203, 116773170, 582006344, 860482711, 481797421, 498040658, 240829616, 836032529, 195942841, 508465042, 970760583, 262117458, 515914406, 802808161, 784332475, 374122343, 146224696, 841597534, 586439935, 244148601, 788204315, 767547799, 776362337, 510076278, 624681830, 364806405, 36907700, 539421266, 800828005, 512242954, 899834647, 163376162, 50294413, 18654970, 84289561, 55576943, 421249957, 34930346, 752291330, 162276973, 265235612, 648593820, 174309283, 472188614, 715911113, 367773012, 121970433, 269868616, 883985007, 980070897, 514347496, 412293057, 574601560, 116830355, 45453500, 562859501, 189078677, 827602581, 712444490, 316586780, 733065979, 840949184, 60074648, 135398686, 424428452, 321968689, 410040315, 273128858, 471407472, 574966766, 873880166, 875045586, 51088331, 163730111, 878321231, 726127318, 966070068, 992549896, 363335253, 89848987, 723352311, 66759579, 406269326, 227087300, 150259572, 36586234, 121181736, 671327424, 433664784, 948164313, 657988535, 451431758, 352880293, 341991927, 179834471, 17796695, 709446365, 576526708, 534876965, 620591563, 749402589, 628280366, 213414310, 982746106, 780180633, 458647121, 527146575, 210950823, 363805011, 571210392, 912463620, 153315485, 532024632, 427468951, 230879114, 869803861, 964025520, 480715223, 895116735, 766188327, 419338263, 475074013, 158183698, 899486620, 551866464, 830407504, 385674668, 305150124, 25769566, 438519248, 46473036, 427624180, 723264512, 651472006, 264633252, 457374493, 476392005, 982968243, 594462543, 141658727, 489344824, 433530156, 442633667, 193279091, 506366676, 618868695, 731227096, 902261819, 499005142, 38842574, 647293009, 470120821, 963932040, 826530559, 427769181, 52186234, 243569284, 806914289, 77294303, 605077946, 125786816, 193185124, 669741115, 146483601, 421911450, 244025223, 607708016, 920909811, 503255382, 458139691, 962827176, 614853461, 60315827, 350564197, 429760397, 252570002, 854719144, 336843776, 342192419, 596659989, 924243516, 172320579, 980212083, 387574794, 749118912, 796421442, 338721201, 731277700, 423355068, 842226704, 398877706, 643899462, 276311394, 413568057, 530987554, 558156380, 825270018, 71652153, 764304967, 575174245, 41877959, 189656159, 729954858, 472722511, 759829544, 285982254, 921037034, 543320666, 873711613, 829723375, 146980729, 88768980, 242470712, 9284436, 325379730, 426922557, 253585643, 473459335, 496125795, 212116723, 579959160, 525505189, 681915634, 797942363, 691505794, 454823298, 342255990, 994255712, 284908161, 275004161, 935102263, 472107098, 948357256, 856671615, 528973823, 649773881, 963952149, 308388016, 911396221, 251193820, 721175020, 199750213, 907595892, 491208059, 66513541, 911357998, 28185931, 408941602, 745821213, 601730782, 8869191, 260152446, 11616084, 492782894, 282010506, 115926945, 586669273, 760307966, 135350671, 730510115, 701832702, 230080848, 284697593, 182609947, 968668397, 822892958, 20031466, 582030222, 113170973, 44631330, 117449096, 742186715, 393019551, 475653487, 44400405, 854169605, 417464027, 638137059, 767027912, 156446839, 993857936, 340495049, 620457258, 138844665, 409760846, 178352112, 82788960, 388732194, 649306589, 798058368, 662337136, 564354859, 463324080, 651997437, 151329929, 798760314, 140393196, 82249686, 534814725, 624568021, 130746531, 950081340, 74895509, 582830295, 80288213, 896322580, 930247101, 961634195, 343840503, 151542664, 791653321, 891526646, 512046490, 292522561, 321986893, 483787584, 926080170, 410378864, 504638099, 532986681, 138953386, 701001827, 64586773, 800287681, 592917926, 845148767, 612516645, 103437292, 360749745, 802262044, 905182790, 741928176, 827192105, 608668686, 275550867, 759837767, 768468707, 652063776, 969103143]
ans[46]= [1, 45, 1078, 18146, 239803, 2640055, 25119048, 211741156, 609749448, 185787670, 784612981, 979654374, 245960280, 15201333, 958496287, 21110097, 315107827, 742613444, 350112648, 551346765, 22689059, 646342016, 52427180, 113726997, 20972491, 531552248, 493279562, 92962089, 319571072, 658193556, 921146440, 975234478, 32484025, 175484024, 620442122, 566033382, 228886883, 301912152, 137109958, 37427138, 531183271, 684452057, 239066445, 806400806, 345167706, 766401402, 659593100, 342864185, 793254425, 754419464, 829307575, 253460669, 788296808, 455700810, 203460090, 299960617, 672027544, 662169751, 130171479, 226661975, 16040291, 641167104, 11608362, 92735361, 828424038, 151425031, 757058935, 838944903, 705030989, 271605017, 832315720, 525711262, 695893337, 524834613, 616761109, 89325780, 498691877, 390082387, 413410547, 86170624, 733987779, 857386717, 121183471, 378540433, 791481061, 602874536, 895775257, 706223069, 9499, 916233199, 610175789, 305910126, 402086898, 380865911, 987929263, 784720236, 752249361, 533065111, 750214951, 512527924, 120069833, 497034065, 691332267, 542878776, 324018841, 841280375, 368737196, 213532423, 972352910, 856518833, 695976280, 832491001, 482258020, 288928023, 37469870, 669147935, 728824530, 312167670, 98462828, 664815478, 37466991, 488559701, 805407681, 555656112, 449333572, 115257333, 422614443, 217564969, 709154128, 523463461, 73425486, 892488653, 72758100, 139084611, 245397266, 356349189, 258341975, 374070936, 726599734, 907199192, 145474167, 868900328, 80767170, 435742131, 604761267, 550372021, 238314098, 858506407, 406280874, 734533546, 294613351, 569709112, 578499728, 811514468, 971780315, 806793934, 105431100, 109183449, 48863833, 577768093, 679710969, 415227663, 41263734, 575857153, 381654592, 178237376, 962188807, 96401085, 816699360, 379978, 698529453, 815682387, 657011537, 324418972, 693645417, 573047105, 308103161, 882958960, 454854080, 319280881, 638681315, 366562235, 558670399, 767575020, 418970310, 599121706, 533764150, 589341596, 935247125, 342450103, 752510984, 17885861, 270962366, 936052758, 754048953, 578853463, 395299411, 975776432, 660809842, 714104917, 664542262, 888472526, 460099640, 981638523, 92874960, 177231620, 389704303, 815325394, 892076514, 810821143, 435904186, 382196425, 459031152, 355917826, 128881343, 657597142, 768648132, 489510758, 615223177, 785945817, 514595120, 566588750, 607013232, 187911920, 428934627, 690400146, 385480557, 274884476, 214574226, 202705516, 78809920, 768678876, 104566183, 54811645, 783466377, 78714677, 225394661, 571378521, 194681502, 425310485, 768219090, 304793231, 206900396, 615627160, 652872143, 605935098, 888495311, 608958308, 684600222, 150382009, 670451269, 632074742, 29926906, 676412361, 727588975, 541140282, 152873820, 396851079, 644404346, 44361987, 675992732, 795525664, 898044746, 408945421, 518637916, 428148139, 754863856, 398182352, 901207212, 713356422, 978366083, 314876385, 700685480, 450639991, 507197672, 750335365, 694787156, 659670168, 536065922, 58255852, 874808151, 601680063, 300562698, 308983506, 144763409, 291800793, 77526020, 485403753, 904665596, 240987930, 592380858, 131116194, 318805303, 40941643, 253699630, 655235690, 431599614, 508389196, 766960976, 64307752, 83604788, 642165815, 298107337, 143184667, 782909601, 97135064, 800759539, 594114128, 462420032, 946857620, 578998109, 847963761, 556321528, 57391815, 681855904, 181815656, 486333346, 837072759, 524567487, 328595763, 549915998, 810586503, 921107919, 625157836, 520890292, 832156974, 502972509, 844559735, 189855766, 821823028, 625190873, 310510259, 495827691, 683011136, 462720297, 218315456, 558392392, 789434995, 973556645, 730884239, 996176654, 617108310, 869866261, 672230385, 823462275, 454316955, 569646417, 836576125, 486906178, 189726176, 941091111, 447563926, 715506888, 259006307, 152570437, 178255829, 705545293, 756368978, 655390691, 445318929, 656847742, 582354283, 964611397, 757172000, 601301680, 424348696, 51484783, 19240319, 282677827, 308226295, 848392338, 155829926, 371112122, 224524783, 972970693, 890401898, 186586738, 229535528, 744395297, 436751188, 287103606, 767393594, 221149011, 725319915, 148703291, 142739608, 565503173, 66967587, 579759051, 568848401, 146971072, 400042251, 42796974, 930117091, 516575412, 958322295, 49672443, 25502320, 669481138, 837449618, 7837933, 569472200, 125364493, 253977071, 938687542, 347213905, 923213402, 374713215, 103889249, 423021360, 42560340, 446498368, 893011213, 263552847, 473020638, 594960497, 638188472, 306243047, 631678307, 460262893, 114330448, 196301356, 120279822, 408786998, 213927614, 687965452, 221650209, 761159253, 159653422, 237951119, 705996510, 183076481, 962207888, 939920456, 729428244, 527536009, 933629825, 48104537, 426892607, 222940406, 156477133, 294062878, 856995315, 562470362, 935041969, 210948751, 968306167, 842365144, 520781012, 542464204, 753086923, 742421303, 62000597, 644679235, 71406991, 633199433, 272647461, 452692051, 412108892, 971466694, 51102980, 982720545, 17172841, 800141833, 835541670, 112517201, 389287762, 451060806, 667438631, 372888210, 71363616, 925222882, 974951293, 516878304, 717488009, 957226897, 42671831, 558776576, 623171604, 305500795, 631070922, 102790598, 482941055, 578335399, 805101814, 173951677, 379242816, 368922629, 730730546, 873191134, 654555294, 282999571, 122452789, 92227034, 843713012, 807240125, 801145367, 399481174, 81195926, 292593849, 487745170, 77737545, 120468361, 275563695, 294725580, 329691567, 323060707, 128192468, 940264172, 278390124, 237020514, 693096287, 868976326, 357620751, 777387506, 600499325, 283061659, 552760619, 551343042, 374674126, 67456147, 355451755, 309520773, 188033652, 438124708, 963234900, 524570431, 966112342, 609641134, 592345761]
ans[47]= [1, 46, 1125, 19316, 260197, 2918394, 28277069, 242654144, 877454212, 274093151, 658806941, 733787098, 12686768, 373279778, 972151771, 700803085, 323660829, 529034010, 15342046, 14519348, 617205005, 151932388, 986173050, 673700068, 544467810, 964286681, 515278420, 556139518, 340574896, 558301369, 203169010, 995039572, 456888812, 641435231, 165153057, 140522292, 660622205, 195293121, 536816710, 963078287, 7389104, 204944482, 754195920, 468292992, 782743724, 983001140, 866703245, 496885028, 44229335, 385957410, 278539952, 468949573, 420982388, 313452346, 869856814, 98935497, 204399132, 112520568, 660616311, 229799510, 228233497, 492491671, 631417681, 54933646, 149425728, 621332861, 339088208, 164640489, 629238436, 824895721, 154091091, 876001533, 408513031, 998443240, 581987593, 639413342, 564182232, 919538600, 946772636, 882410774, 972663920, 656083562, 92818, 266781815, 775781699, 746031288, 222736672, 245153398, 853395663, 612580130, 998160370, 644539418, 268757618, 522753001, 961290581, 775849265, 167666621, 207332842, 699178165, 754169098, 895892786, 110804927, 209717022, 224332021, 783584762, 168756823, 846734143, 820517435, 567375827, 214226237, 514413130, 94334242, 56417678, 452070622, 302779049, 643793464, 45275321, 465081583, 721848633, 905142006, 304646178, 594655979, 909007937, 734286949, 886228757, 175346016, 613908391, 543890160, 182181133, 880150750, 840065256, 833202286, 948664835, 99995047, 986587901, 143761895, 873393215, 472341142, 369663112, 813013714, 860504625, 731747262, 545041246, 583231233, 427381591, 37913038, 537312918, 219404202, 592801409, 727962123, 878247573, 121527391, 62101177, 856133295, 688561557, 4927109, 639161755, 216890863, 944378755, 396352437, 878653962, 905668778, 386987830, 935008847, 899701147, 100650401, 955831377, 336099358, 325599961, 655390214, 368725260, 410912881, 868037904, 255016544, 51552711, 320078126, 868474642, 332377928, 241406268, 35418479, 170587950, 775390874, 598922434, 616742075, 563583865, 362204509, 606438997, 894815935, 49721736, 43588534, 841088924, 703571407, 258771291, 525460849, 233015242, 491199815, 325653075, 858892862, 519655123, 115437087, 727491564, 149427446, 582972761, 204458210, 871579136, 737982490, 129452738, 424878982, 856725917, 336920826, 730532856, 841738688, 738232572, 913319995, 816486040, 235770118, 427698004, 930569686, 569011751, 212446463, 508105319, 803897811, 496189040, 948372030, 432798655, 784691260, 809769369, 691850475, 577558004, 62715847, 947764060, 196109904, 506172286, 447735266, 980867772, 417186123, 46557919, 986790130, 277584037, 822619391, 621076591, 388367593, 68342324, 236699370, 119970164, 657351210, 878868802, 794459312, 436412351, 290870119, 503296346, 564802634, 58773734, 218770767, 842309450, 694735121, 712067611, 605426442, 634737321, 598847809, 189964014, 104895974, 463967300, 12836011, 374171101, 422839429, 769990513, 562838372, 23465799, 935303296, 758855803, 832260567, 373886738, 362866660, 831747060, 745193763, 842521525, 971131364, 323409153, 328965945, 810807795, 987986960, 514599613, 697337301, 518676386, 255182547, 320862033, 438306682, 656059329, 246817307, 296427451, 518314128, 212813255, 401599307, 322632262, 651271379, 102975853, 978392574, 171788197, 425477753, 865141598, 200230496, 352371432, 128877128, 483645145, 487174027, 207964600, 565016864, 366179929, 769999162, 980709292, 279413092, 778963675, 322935221, 775556840, 152203885, 621120920, 754303914, 144652778, 603456104, 397495432, 911648885, 161631342, 183072379, 436197254, 410415743, 654211646, 998944149, 660332881, 659092994, 407158213, 993390015, 62237745, 342306369, 807083806, 460112259, 598009122, 34231667, 354435262, 237881432, 155417941, 495370397, 996923439, 566380833, 854227389, 702509945, 42544433, 284265702, 294553519, 149363293, 27077251, 84953964, 442875086, 52560456, 900402134, 145229989, 73758817, 191009440, 854994962, 638721915, 122661714, 185868970, 77283521, 869275152, 18655948, 313026284, 709600476, 473812539, 310414874, 881320952, 952459523, 248120422, 525865505, 878780555, 987277088, 840681160, 676792790, 412115993, 140030918, 974129475, 721196483, 656805079, 905290349, 47935904, 451920705, 209356056, 551066765, 377150442, 379611973, 957219941, 151470005, 815021467, 645207971, 427463516, 863082600, 325313522, 124436219, 624577057, 614877838, 455973640, 851822937, 25478672, 694724523, 841056623, 311625157, 733217559, 234679922, 488590424, 672460808, 393534712, 496209755, 929085969, 673429468, 675205481, 477828672, 541309112, 421475544, 478494486, 773959869, 620756099, 817295158, 343366608, 474968096, 138789669, 1261477, 581929663, 193727536, 890932863, 10823177, 566850894, 774883564, 16714666, 326523886, 969386350, 297903394, 330603328, 602435368, 640131734, 422205271, 722651837, 536164302, 931111157, 119137488, 728875089, 985577117, 985476890, 17918009, 917723365, 472997173, 89115107, 916366434, 502538821, 230961609, 303908854, 617061492, 736625515, 131713887, 339453221, 738950163, 633262610, 426758031, 238112917, 779917917, 838020550, 66019448, 650675847, 778117049, 610691432, 213274580, 385410347, 146924004, 364868172, 467790003, 719723336, 134820272, 752419541, 477278067, 249134595, 704095466, 475445405, 736299900, 879265925, 152926089, 845846141, 495967193, 279498385, 571884448, 188818617, 160584873, 477296264, 718325160, 376134972, 29944771, 994040918, 900529668, 502667072, 63109761, 493032874, 781301515, 461834757, 82343644, 481132313, 514447042, 33858163, 779555233, 748165656, 15592733, 72424287, 572256728, 868353288, 210902382, 873738113, 462082508, 116372507, 317994063, 320661573, 43412947, 698165915, 782179405, 544478699, 376533191, 591100852, 669522818, 718785967, 689856669, 868867194, 692259782, 326169003, 372530014, 278822874, 245059471, 536750832, 337386716, 351509954, 600150419, 771930319, 812137400, 268506281, 52663290, 576040882, 250206016, 182636529, 238498760, 83748189, 556944302, 408365242, 877381661, 687598532, 206936328, 93325077, 375585930, 311118119, 840250578]
ans[48]= [1, 47, 1173, 20535, 281857, 3219563, 31756649, 277324867, 182983217, 698763572, 224340727, 130185913, 938338213, 457596872, 500667258, 726272186, 242531386, 490324006, 697265581, 186365736, 123707347, 149163288, 89978475, 985283339, 584841356, 785509005, 693590689, 256394211, 919078587, 671307265, 271140497, 146527772, 508423202, 678732983, 767147115, 418422439, 470469749, 411147184, 246424306, 580998273, 228726677, 964726100, 955513349, 444565758, 668191949, 622619432, 792082487, 929348032, 601983375, 875985614, 424117930, 730694027, 740975250, 920167707, 500437835, 690210005, 493329701, 913508192, 695611331, 515433292, 682059417, 760833644, 299135864, 144219873, 937695856, 872711671, 176916492, 348891212, 334587033, 49595521, 749704350, 806067034, 773327860, 183297942, 590517602, 642228939, 275941227, 305722242, 165986509, 644370063, 71211109, 994092320, 193064301, 728492690, 76982066, 397536959, 240992716, 459846893, 745186728, 715105963, 864528752, 8495685, 753272988, 61740216, 691254120, 133693721, 536597663, 806042634, 964981978, 37162518, 164112239, 637759779, 841824460, 829311498, 573961610, 622092127, 856298148, 23010232, 90428839, 608194623, 46765621, 381935126, 362962166, 452925715, 585602790, 768818647, 88708532, 942042803, 418311021, 521378251, 499003594, 126819649, 281499536, 951375086, 146412815, 883657287, 598780576, 163659546, 959278876, 560517421, 665346319, 929162776, 164983787, 77699826, 451232846, 342897676, 483260356, 399557298, 954841649, 593150358, 617703430, 292815034, 3827776, 631211917, 629217856, 387782790, 117795063, 964508694, 824603912, 347867132, 217932218, 808071571, 466159291, 919428338, 306867765, 310085680, 347929669, 103137973, 445637697, 645585557, 573817817, 596387955, 672995733, 578127218, 402908135, 115353766, 244018895, 365778204, 555835033, 188328988, 247770780, 214263457, 844226086, 575129810, 998900133, 642186262, 886066131, 9933705, 609621463, 398319031, 223920768, 209742125, 519163806, 74615456, 814536291, 217678251, 205417278, 306418059, 464475526, 330591049, 614947407, 841330174, 17421893, 462387593, 572435987, 550253368, 393354277, 125715312, 124567536, 533400012, 599797708, 528236566, 670562226, 867851657, 488086533, 312725786, 238592338, 37063455, 385067665, 487783197, 118051898, 700641656, 71282753, 435781034, 103306472, 894876554, 845215295, 848516, 105817111, 455104275, 971250603, 659938256, 173306291, 702024160, 716038595, 487118454, 170680030, 880373959, 881689085, 153725278, 74926408, 143593976, 537712434, 635112688, 530810156, 750175992, 211491335, 495469862, 938874667, 906814766, 530322450, 654580872, 345961757, 642596517, 63791230, 944154048, 670877958, 937127089, 186748489, 915912734, 209561832, 276486399, 229476817, 558761321, 226557040, 227364465, 312169979, 745218623, 741668605, 732242764, 141121784, 862165956, 612899824, 26577011, 945385273, 251793938, 946782241, 731260038, 244678083, 406380914, 904932224, 539791264, 681567161, 903979395, 522313639, 307479666, 592336384, 274405785, 808155145, 116439879, 610551965, 466693001, 783212908, 356926408, 441684284, 460337698, 929744044, 6376955, 718008169, 946348344, 771828366, 973818233, 895371075, 977137826, 380169268, 772257849, 31334848, 472603919, 411133545, 814229722, 268412684, 269984826, 925865608, 465876593, 90547760, 192297128, 107314233, 564985934, 624177562, 939350415, 164843750, 127698384, 375467125, 733175906, 272735725, 449176665, 148653187, 981408173, 518395662, 539465581, 376426572, 523018009, 244326749, 117372211, 788925566, 998562683, 66998700, 958836224, 912519308, 243826028, 372775429, 817271079, 249393258, 980817911, 290157076, 803249202, 54296904, 967950499, 259586185, 891527285, 197070576, 229312354, 227197980, 799697366, 938796541, 780082061, 90937344, 484280959, 41280132, 365255061, 357940368, 463355056, 931322797, 484716584, 549219150, 927360223, 836260928, 974511964, 168938341, 138740543, 617041490, 552137623, 940491117, 311751083, 797191757, 581186247, 747525174, 464341615, 45074367, 877273095, 118604361, 820377975, 651223472, 330450797, 299712101, 798402816, 155978336, 76119913, 279749437, 94544299, 576902970, 337821847, 762491092, 205421212, 628488971, 912880168, 293200919, 74345429, 106904237, 117214135, 997309646, 440117215, 601730010, 44099662, 275878624, 579837056, 734358196, 740396992, 105320711, 497734455, 593389397, 892951024, 375888233, 469355971, 904918031, 759963217, 159920933, 656339936, 82028185, 635763012, 494109863, 887577439, 747214684, 51704021, 870514178, 310168296, 344440919, 671389360, 63636271, 867520663, 253359253, 809561479, 515218518, 735486509, 595414813, 855063768, 809133514, 296905455, 403829884, 13706060, 521945271, 406722813, 508410711, 177195219, 735377028, 927006199, 631467156, 561281245, 747357347, 2938426, 465345595, 461810717, 851331500, 936133185, 709629669, 764183492, 336958888, 999734612, 886346709, 929391292, 283117585, 489898780, 493902211, 377860665, 233672406, 313970515, 130449778, 925311516, 829665465, 27964512, 47478431, 502231137, 77997958, 450616449, 231073347, 922519036, 577962078, 74763491, 840109600, 825429573, 325716083, 462423227, 684091307, 610980133, 146344297, 230702558, 840583842, 568780809, 837872774, 467777629, 918753619, 868791683, 692922864, 937076083, 487643358, 553595896, 717484731, 882361644, 739294901, 547711612, 781629368, 821302751, 368923697, 499416921, 374122329, 146178192, 867117817, 743635071, 435195107, 43377741, 23687167, 878990481, 99110158, 262344925, 137035868, 292609610, 625408058, 171070693, 281506530, 350758492, 515834894, 237732608, 828774443, 840832942, 431386878, 857791323, 291378943, 894741249, 559570546, 881728336, 216217018, 497590589, 210577047, 706853900, 528807154, 595327246, 243687205, 679896105, 276389715, 520651743, 981854062, 782051052, 628779694, 482906971, 308000266, 98460224, 329039027, 663453182, 866909422, 358447817, 756042580, 103701857, 530184673, 82157052, 864831037, 833622836, 129557279, 680891914, 903510655, 223117879, 584910098, 872789802, 683398377, 818673921, 424793316, 162530200, 461191009, 233747923, 764377859, 866276050, 20068038, 599500015, 419525268, 504837656, 702339633, 161478719, 731429464, 9977417, 955013204, 944736389, 868359658, 303235910, 570685307, 762022093, 973456873, 491776893, 191155949]
ans[49]= [1, 48, 1222, 21804, 304834, 3544928, 35583250, 316123172, 530785426, 505824986, 901343166, 615485588, 789348648, 698747334, 657848248, 964586458, 476943547, 698458295, 801769019, 257736525, 542576587, 933572174, 9542546, 488292838, 779820677, 404677231, 568188493, 931045218, 340825658, 205993974, 185959269, 78058729, 445883053, 431770274, 625502333, 180277174, 804167964, 894493650, 995189957, 934651928, 779076648, 286076285, 196236261, 433504295, 796345349, 46608071, 262327913, 615865530, 569486410, 232121371, 86175778, 154003167, 455565337, 592635041, 449778081, 946011559, 315342730, 523152035, 660192808, 984322053, 918448908, 362530845, 976500024, 826353996, 979299043, 20455239, 106430716, 169990095, 856925551, 339927417, 872925000, 454748405, 844111855, 778706572, 953334777, 367875579, 54603227, 952723870, 746089521, 114899675, 378338080, 515017450, 901556480, 75514717, 118586517, 750778341, 164215503, 398032943, 932771419, 175973529, 371281707, 414155738, 136305212, 176477492, 529591042, 473449712, 104580388, 917944592, 711611694, 275529831, 657391663, 618370464, 182199238, 863262145, 671572410, 926093081, 964697471, 20599847, 886336884, 976845790, 332330830, 936899217, 469444206, 333826539, 382006323, 404644652, 86283892, 711449573, 711524895, 240243757, 137744674, 52585102, 502954368, 568353873, 424768720, 673699213, 453807002, 277591996, 614231800, 858886730, 933633627, 855960053, 795294602, 320736325, 160050137, 741837408, 875372187, 933116510, 439299086, 339530899, 998809886, 988163112, 414204450, 626581582, 425958595, 547450689, 257877182, 25212376, 487090639, 693248108, 736165691, 261048117, 530252319, 667332870, 224234420, 283256778, 493030047, 381167115, 959191937, 567700201, 408470930, 456733167, 877572444, 640070139, 177231251, 53889209, 630925282, 764167042, 903138510, 822950867, 161878067, 741376139, 620673064, 828400388, 989198090, 398235498, 335164252, 650259410, 895482301, 288920533, 986020511, 960531109, 692510577, 743863232, 159848129, 639142915, 658806616, 286815941, 569150064, 996156909, 474086872, 377428234, 108191201, 968576455, 934066962, 520785392, 648351310, 322768543, 500047228, 717012630, 366640002, 617370336, 747113890, 647615517, 420668064, 485924194, 28548015, 242698362, 20265134, 481161073, 780894508, 716872330, 925052871, 809234518, 209608950, 454869307, 42621234, 266915957, 548835092, 11648368, 200676498, 803279760, 609790836, 522043768, 787672824, 264643232, 571421826, 762085826, 854807719, 119023111, 660310435, 945098645, 838260736, 592383406, 728604232, 586121308, 18945549, 62079587, 8000021, 137221342, 936745518, 867913927, 937623778, 183088542, 624248829, 606106136, 815005922, 728188591, 164502140, 885086995, 646575964, 60630781, 250914884, 619961376, 835493684, 1794097, 350786557, 222634027, 605402916, 871984975, 140157610, 784428245, 701028584, 784157139, 199990301, 49282014, 806191394, 544636448, 696393844, 625422532, 306981977, 200109353, 819880255, 622554727, 966234587, 1715755, 884432882, 186517679, 414057470, 559202957, 356291776, 440462056, 76496043, 54502936, 82793754, 693820485, 333532789, 139408482, 538301356, 908601203, 663844984, 277481039, 494620179, 126148065, 101563902, 543304970, 40138848, 255494176, 250466774, 181548534, 183041503, 553027506, 468172977, 571880068, 685135214, 70030015, 431414252, 965377675, 285528459, 577690235, 3039911, 424468115, 149219671, 315258608, 442938842, 340124780, 620577523, 697442435, 606981307, 195766252, 513624332, 160814831, 144529981, 626344971, 929525101, 167384034, 985564306, 757660450, 674490248, 404160553, 218780132, 253152109, 588527766, 276135385, 293545669, 229980166, 406532593, 544661736, 944987368, 74067610, 979465423, 367319108, 691015763, 308068787, 270297211, 892899529, 571121326, 682341094, 508186314, 992592910, 570463576, 551864557, 443417375, 102996223, 180706669, 66278518, 547390018, 97982020, 377733797, 642211092, 809569594, 442856622, 912786312, 563198351, 549331531, 576357131, 891027263, 77805689, 816522985, 731749256, 313952972, 411776160, 795006290, 22615421, 348238413, 716260746, 223962550, 78670864, 47765882, 267128253, 587371111, 927656165, 192469863, 806624234, 136996971, 759497678, 646978177, 833527505, 472805550, 754214240, 960030895, 232746388, 490616131, 420542303, 904038549, 210637836, 74285318, 144447351, 742135765, 244372617, 87595635, 852731251, 594678505, 794681848, 228154101, 363702627, 673985808, 239196945, 836249623, 602064792, 462168907, 430511049, 331217937, 84426505, 529390112, 953694258, 768941491, 296949641, 617567965, 759210871, 554347066, 314959464, 855978152, 459336095, 416019714, 554419893, 643616814, 307318600, 193723511, 342506504, 737708842, 961578294, 644413804, 283651295, 449519877, 262823100, 438065978, 195660179, 15479674, 929627357, 712657286, 867475048, 618979059, 615899609, 290553872, 46585860, 675146342, 899293157, 138576244, 932939832, 413352510, 228638502, 577046541, 52412367, 271101119, 704058715, 716195674, 113738084, 976781966, 417637854, 201849275, 137988263, 703452509, 833173534, 774723430, 98520292, 647910333, 702073064, 101667724, 93613248, 4773372, 993672667, 598539625, 298728331, 547262186, 609550837, 42278975, 203431476, 764589375, 791435299, 273439277, 15186943, 247517820, 332116413, 672582410, 88991345, 573172714, 370502342, 495515460, 486357723, 529038430, 112617630, 9655079, 54905538, 630913486, 94540925, 694069860, 101033114, 601510215, 405093272, 877399916, 606786230, 712700446, 365826653, 440611748, 222502187, 628732942, 260127071, 415183336, 331627148, 603111841, 484627861, 252203062, 603610758, 918118836, 775502591, 558836403, 458735214, 903545723, 229008632, 239177179, 70767308, 751925156, 652119146, 980361868, 450630793, 63075950, 714904102, 795480239, 196855664, 446357279, 343343138, 751184330, 353543327, 265335039, 291055365, 141693974, 952501609, 772988967, 982806649, 295006336, 142133453, 389243658, 551050114, 837354729, 288032982, 926886748, 940810321, 996269340, 544323652, 123254721, 449847916, 164321665, 408440169, 540527971, 235735087, 384560805, 888470688, 711171300, 414716347, 219479361, 559050803, 610845133, 321258507, 296543705, 253557800, 771631909, 466270561, 966519146, 100544233, 474799959, 147649345, 956135303, 808272257, 279282920, 472357219, 422709994, 530025514, 999788009, 64593897, 709199531, 479060735, 311654131, 943520011, 427742758, 799287390, 782392773, 191335024, 830990096, 336010037, 237942831, 237453992, 695887098, 398366572, 529644737, 344086296, 862051533, 684436865, 317549101, 968659087, 366641438]
ans[50]= [1, 49, 1272, 23124, 329180, 3895908, 39783804, 359447204, 925733384, 746545659, 165655001, 158091124, 719304162, 111160209, 171158550, 935012406, 874008903, 988755604, 608336289, 351327718, 211049418, 970686245, 441380023, 920727544, 396494781, 218114186, 934368772, 753990221, 203263446, 488226646, 946324350, 642441651, 816607227, 122420091, 629716118, 498106515, 488881569, 100763230, 814241373, 430998026, 986590664, 188596813, 238499794, 887765759, 719310391, 819612870, 840885905, 584773429, 811468143, 396065785, 368868801, 299761844, 617462619, 308704442, 206242421, 833439007, 106715469, 970135543, 972244832, 66232618, 207050932, 577078708, 955731123, 103929249, 632790957, 297717977, 280927805, 856143814, 140717794, 889342899, 570959166, 553036683, 311778062, 833874032, 321035571, 629235909, 60666525, 19636232, 889773198, 837811568, 283828621, 499062871, 459250525, 468391935, 389843786, 80632526, 462481073, 859711240, 66143264, 831825780, 518914304, 998480225, 496960804, 480385724, 483317701, 923742113, 771054094, 630267330, 478946945, 527928962, 674723787, 882998613, 123711144, 324674723, 964132061, 961988031, 65215295, 858250635, 924300325, 577545014, 241841560, 172586320, 726876085, 210684082, 897202470, 742850020, 161301259, 120853804, 344539574, 836860211, 667275920, 72688787, 930704832, 179668299, 861726583, 168665810, 834696469, 672920894, 419563732, 302874180, 454615268, 934181182, 119694911, 779976833, 216225187, 244379028, 586838513, 942544272, 397970796, 155525782, 435250288, 609294947, 697035870, 790138207, 313089121, 451259481, 904475234, 15500998, 428233316, 352796372, 805867626, 355791012, 191743365, 390372515, 86113794, 224579645, 34292553, 472538607, 244805809, 799547326, 350596592, 550928379, 248605526, 858957317, 809083222, 418025439, 717379009, 843111164, 748566980, 795763411, 344249103, 246799165, 468081584, 533360568, 97839725, 814208152, 370784820, 149643652, 648814350, 586462723, 179226570, 323415874, 413399345, 830824722, 901264775, 785155020, 673315179, 883230707, 320461657, 209574161, 896187167, 641537195, 580708044, 615201169, 907420567, 226969633, 44823693, 653925850, 618905940, 556249274, 683808190, 595045606, 406684866, 817926872, 498013040, 741888764, 255307898, 750076370, 226664326, 45791371, 138249186, 182084615, 925519009, 32002450, 507648904, 36302093, 164244320, 134446595, 176304234, 443232913, 204696272, 377207389, 330407781, 317016375, 255990328, 346121343, 776903928, 865285835, 180645765, 94169320, 523805568, 66571932, 958229276, 706032441, 157122799, 174128102, 265560802, 960871567, 814597354, 840895548, 702037, 848074074, 17426708, 276377856, 55696613, 206160180, 32721003, 453495162, 587538197, 204676036, 610254246, 936113705, 842825687, 202272844, 145230437, 624393323, 739106533, 700708897, 523328161, 691038973, 656087189, 213848962, 927815456, 921255504, 609475698, 113463094, 529085932, 807792149, 579407091, 163833313, 694176222, 471399591, 346973697, 718259544, 297359882, 892552532, 451373341, 120883534, 8029910, 624607649, 606649877, 815313728, 231664869, 673443919, 615486405, 94571095, 110823650, 950289120, 646876432, 928906934, 684469503, 297251947, 919054473, 285157267, 967739040, 274416446, 465229888, 656873003, 825576691, 53305194, 539107135, 609069516, 669008004, 585520763, 526072937, 91836656, 101778461, 538228891, 424599066, 719851020, 234795290, 701214554, 914481398, 497763115, 504286064, 212679726, 409710596, 134500525, 154608785, 554889670, 267547678, 851784437, 749366191, 681515762, 587313005, 604179607, 297539881, 51380469, 30897443, 988568867, 430543091, 168358864, 325894509, 131217074, 122226126, 289735266, 2541560, 697428098, 339809826, 339814711, 568813016, 256466301, 865405619, 710940331, 7424767, 660900037, 729644940, 444, 450105203, 690939247, 459755659, 92556107, 42398758, 782901298, 483436309, 73995240, 784415989, 602791285, 655683750, 744368335, 684929720, 939318197, 1937536, 94209990, 544006669, 195169186, 297173575, 151918090, 559870646, 425964491, 818978660, 571568643, 60393204, 415731654, 547756555, 991386612, 383053326, 997830526, 963081859, 107336308, 898219937, 906988404, 550036125, 981857264, 691293427, 481189647, 501756531, 316529056, 476096058, 168221459, 165690115, 553028411, 960794528, 453386272, 963889156, 71983103, 494867184, 462967097, 635240847, 989817132, 23786457, 968645733, 163475174, 884798755, 971346358, 8231228, 947835970, 751371876, 21594745, 702982989, 997528759, 30899466, 874470660, 839706683, 64336797, 183002010, 415355406, 851375333, 802315034, 662347966, 459017349, 83113197, 807783874, 686211775, 665742332, 548408223, 38712773, 947065654, 224142524, 544199777, 554457822, 161813447, 59932464, 324817969, 826816639, 159675767, 610260222, 802832692, 962264291, 230527850, 654881259, 493134625, 56109407, 491401533, 163680598, 892934948, 889185132, 78662275, 741528574, 616484511, 204394884, 120980232, 4959172, 884202370, 468625389, 987185268, 797914336, 292935354, 542176515, 965256954, 25044127, 701524209, 669825969, 264620823, 983915826, 463815578, 325409981, 142164710, 946513145, 626025918, 890502327, 456729879, 921471703, 889764153, 10834930, 550258959, 888111963, 456661896, 560525119, 254574198, 379302005, 359197537, 748972811, 432885247, 174603143, 495215302, 304225805, 499574, 89067439, 956588800, 479903186, 900293862, 918419160, 874312513, 779518268, 750190343, 34999197, 204187488, 29703716, 310295240, 212734818, 705461990, 880565621, 542764103, 578132976, 871657196, 920555643, 635330221, 603836039, 905337022, 446003049, 531829391, 914627500, 109964459, 793773872, 883594493, 588890899, 761763418, 850946563, 47045637, 406265955, 398330580, 175033998, 98562597, 74022406, 109783010, 888406279, 62923507, 851720727, 920064661, 659715101, 731241623, 740764931, 68490942, 26861674, 832409630, 156628069, 65837301, 277330611, 504531610, 621094682, 513712789, 824543274, 863846088, 522929299, 50674845, 205053841, 391074024, 703020653, 598865065, 977680558, 126857946, 571772915, 596794646, 195429545, 328266420, 36051456, 451216030, 522276964, 948367998, 561406981, 389510759, 585943971, 108053297, 459413669, 288907310, 136029766, 802792879, 520247265, 414339912, 337619243, 597859489, 40005835, 350918, 321070418, 199829979, 141119131, 515535428, 350920730, 314377413, 808898947, 900198037, 799762368, 570476717, 244997759, 402733111, 626061442, 103647198, 938528989, 898060580, 652361018, 641847472, 149112119, 134262079, 887185896, 606038263, 859408453, 950373236, 692335861, 405660442, 565431386, 959094106, 393940636, 423632434, 612413824, 143336067, 663257107, 9730523, 471491852, 112828340, 936303905, 998673093, 55233966, 416039620, 144081002, 565258672, 539355694, 202448366, 14002378, 539019751, 307827209, 288622328, 788194350, 570120788, 965430343, 472467292]

if K%2 == 1 or len(ans[N])*2<=K:
    print(0)
else:
    print(ans[N][K//2]%mod)