#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=55,p=1e9+7;
int T,n,k,ans,pwk[N],fac[N],C[N][N],S[N][N];
vector<int> vs;
int mp[1<<26];
void dfs(int i,int s,int st){
	mp[st]=vs.size();vs.push_back(st);
	for(++i;s+i+i<=n;i++)dfs(i,s+i,st|(1<<i));
	//i+i的原因是最长的border对T的贡献至少是两次 
}
int fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void add(int &x,int y){x+=y;if(x>=p)x-=p;}
namespace DP1{
	int f[N][4100],g[4100];
	int calc(int len,int s){
		for(int i=1;i<=len;i++)fa[i]=i;
		int cnt=len;
		for(int i=1;i<=len&&i<=n-len;i++)if(s>>i&1){
			for(int j=1;i+j<=len;j++){
				int x=find(j),y=find(i+j);
				if(x!=y)fa[x]=y,--cnt;
			}
		}
		return pwk[cnt];
	}
	void work(){
		int res=0;
		for(int len=1;len<=n;len++){
			memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
			for(int i=len;i<=n;i++){
				f[i][0]=pwk[i-len];
				for(int j=len;j<i;j++)for(int s=0;s<vs.size();s++)if(f[j][s]){
					if(i-j<len)add(f[i][mp[vs[s]|(1<<i-j)]],p-f[j][s]);
					else add(f[i][s],p-1ll*f[j][s]*pwk[i-j-len]%p);
				}
				for(int s=0;s<vs.size();s++)add(g[s],1ll*f[i][s]*pwk[n-i]%p);
			}
			for(int s=0;s<vs.size();s++)if(g[s])add(res,1ll*calc(len,vs[s])*g[s]%p);
		}
		add(ans,res);
	}
}
namespace DP2{
	int f[N][N][4100],g[N][4100];
	int calc(int len,int t,int s){
		for(int i=0;i<=len;i++)fa[i]=i;
		int cnt=len;
		for(int i=1;i<=len&&i<=n-len;i++)if(s>>i&1){
			for(int j=1;i+j<=len;j++){
				int x=find(j),y=find(i+j);
				if(x!=y)fa[x]=y,--cnt;
			}
		}
		for(int i=1;i<=len&&i<=n-len;i++)if(s>>i&1){
			int x=find(0),y=find(i);
			if(x!=y)fa[x]=y,--cnt,++t;
		}
		int res=0;
		for(int j=1;j<=t&&j<=k;j++){
			add(res,1ll*C[k][j]*S[t][j]%p*fac[j]%p*j%p);
		}
		res=1ll*res*pwk[cnt]%p;
		return res;
	}
	void work(){
		int res=0;
		for(int len=1;len<=n;len++){
			memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
			f[len][0][0]=1;
			g[0][0]=pwk[n-len];
			for(int i=len+1;i<=n;i++){
				f[i][1][0]=pwk[i-len-1];
				for(int j=len;j<i;j++)for(int t=0;t*(len+1)<=j;t++)for(int s=0;s<vs.size();s++)if(f[j][t][s]){
					if(i-j<=len)add(f[i][t][mp[vs[s]|(1<<i-j)]],p-f[j][t][s]);
					else add(f[i][t+1][s],p-1ll*f[j][t][s]*pwk[i-j-len-1]%p);
				}
				for(int t=0;t*(len+1)<=i;t++)for(int s=0;s<vs.size();s++)add(g[t][s],1ll*f[i][t][s]*pwk[n-i]%p);
			}
			for(int t=0;t<=n;t++)for(int s=0;s<vs.size();s++)if(g[t][s])add(res,1ll*calc(len,t,vs[s])*g[t][s]%p);
		}
		add(ans,p-res);
	}
}
int Ans[44][44]={{},{0,2},{0,3,12},{0,4,34,114},{0,5,88,447,1400},{0,6,220,1674,6984,21070},{0,7,532,6063,33688,126895,374412},{0,8,1258,21408,158348,745000,2635878,7665728},{0,9,2912,74085,729384,4287065,18195384,61711797,177672560},{0,10,6644,252378,3306160,24277010,123629220,489139714,609172281,598716382},{0,11,14972,848793,14792504,135693575,829188996,827800256,392257870,269781697,482008183},{0,12,33376,2824488,65481408,750319780,501974717,637531973,377631239,748644328,807412382,517945587},{0,13,73724,9315747,287298016,111788397,179963136,424398810,369593493,965060912,119548994,384077129,516744371},{0,14,161592,30494394,251107545,362654116,101961812,862181525,483450055,413951297,849887397,441796098,911318483,418408761},{0,15,351820,99177177,413605757,840474235,714151590,48716491,495960555,170210665,149938363,86402823,380985937,874497762,278456933},{0,16,761530,320750760,296743467,370237457,322562530,406312927,697134597,55824301,39905500,3660223,572443455,292012328,70275648,316743345},{0,17,1639888,32269762,777705731,840854681,573328029,228543891,233640719,602688535,858496718,427786703,490517044,284321215,772880807,381172830,423287689},{0,18,3515276,307810395,556935881,9678485,262631246,738020914,31991237,951124219,792682351,695168198,280373199,248649139,270525445,613757511,618365086,463430442},{0,19,7504856,558945757,336667488,313377417,765494881,569837173,886121577,730227568,423984525,267356237,213066734,179897763,429843466,896011905,218487385,801709897,381833031},{0,20,15964156,590042559,47113211,831340887,553387555,710881237,534606655,81883675,809310550,603209695,699136112,983719273,40373441,627504095,79330553,79888348,374469789,996846157},{0,21,33847676,527460331,897957855,941259642,245886177,923477164,697917987,821495830,484819969,994710220,805947002,382626009,219242323,824968611,776933477,877517402,143838016,759270348,360621111},{0,22,71552900,901611834,348320081,874604493,58728205,207240625,837973853,899441253,901272161,202304170,723775797,563002282,85225437,203555465,237391671,497100697,223454876,722039074,474704378,902299306},{0,23,150854688,788776785,789965380,137555163,447211742,710464873,908118514,298595401,505985328,378405701,645381543,313645282,576025867,126003574,670142908,781532981,194751797,163361961,730787045,153209932,43760355},{0,24,317268364,956649428,365583731,76215959,581742252,721824863,753189636,241831172,264958615,318039493,258187636,279267640,141706417,739954454,428333821,577395249,660891714,688016673,696089580,959646143,536593176,670489459},{0,25,665766112,551729744,895591383,778433268,706968320,917476532,773321159,610940477,455702250,891458378,885108494,430583183,952290030,888368685,340042651,844981344,646627004,360279895,731671013,79569097,390027196,224257104,243408503},{0,26,394194305,161513199,409417428,309970057,126149523,679139999,941157374,582128081,651227106,263963941,146273184,695682765,98191025,226225300,805142747,84846094,445140405,128357316,67328673,357734514,127930084,15416974,533875705,175238538},{0,27,914085410,684237296,128271892,955320979,296862426,418847941,664720612,734030329,752379977,39490709,783552020,19788318,47177478,19737379,421219298,791611588,711489211,282338415,407727624,923970436,210939068,306079382,846631852,206147807,318601768},{0,28,80250002,882503933,242964277,817461848,883118333,480384287,951620937,411191925,664945340,195653843,368581183,769756268,774805601,429962372,109641667,570838981,499477707,766736507,723672983,389791181,500320824,210665907,427285388,353971430,732373702,389299467},{0,29,665923480,167040949,350860153,892939169,363044076,142633972,725369386,765497686,503287939,912389233,476140439,595055005,722354235,949130200,32989434,709211779,781870182,891870232,342877076,160698764,681258605,71695657,96122023,791096258,594060112,694853645,936998328},{0,30,345036154,176112404,871529916,296348988,921976183,393433606,990173619,862861058,317600949,203791345,766040980,548378970,879432840,927912887,333174615,644091164,64870987,137234343,72321929,284371049,716127482,586860028,366619006,145379735,500704511,258421194,561407986,460471130},{0,31,720801994,187965530,989632079,659451972,106861426,886365822,946134378,477755213,619436162,484961854,381226069,905925505,716935650,641568509,423314574,196977561,24653042,288662182,110926905,238791390,985441318,116676990,582049008,618465915,607395226,443222108,195353727,257619731,857545478},{0,32,511166763,699562779,395192392,77559848,998703777,807842046,956485025,990321776,468585727,526983261,823706817,871460617,533187879,225171396,758131412,990700385,441538989,608677119,470493881,884153566,689501423,924063860,414763425,877318283,36438530,962527688,877870193,436139707,351441066,555024758},{0,33,176590647,974746456,529677423,31333581,311459792,286709136,344627368,901826429,110027467,696183347,370391008,51234188,654426504,590714825,623653689,418798531,518496159,438999745,603016111,736538860,141636014,747398056,326652641,114772787,769134114,436723968,91233124,495644641,290480781,8041004,557804631},{0,34,690021262,870113928,863743465,46992417,737062622,188233333,303655233,491856979,619922859,435928827,572298921,131923948,8601844,600936202,6449969,677075076,222500576,532151464,310627425,884510969,968552655,58702231,842730700,965646571,81648075,809670800,440089113,383151517,673912298,209365429,211616570,425518720},{0,35,106862030,172964877,415311520,55085246,995703061,167601067,406683774,583901548,89702410,912754322,142893402,280563803,873000834,82050878,44560057,134066882,438250687,482367365,244272963,303540170,880675411,202622724,329907587,827171390,464713186,695372771,858904457,924196705,110207701,470899348,167145046,722575091,40895253},{0,36,767263701,560218802,902867643,357203920,609068516,105907507,194682771,724920414,76753861,488336182,156172508,580833405,44386160,815432249,120132063,290863799,68421044,299512581,138133719,421943935,50755579,300784130,535688035,956489850,963821068,737484830,787385796,285724340,98720571,181107450,203438060,982518780,49738652,65605139},{0,37,829781402,720422505,737894427,963468044,652797129,413443423,946960081,394028101,79505348,735221918,696620369,900632307,657610969,425792443,448876828,374505087,545162252,982596839,127048460,618596680,224791945,932180807,982079329,805110350,626770693,411897004,41095218,847837110,490370271,958084759,216385425,99000738,615277739,112713457,41643285},{0,38,605148524,301909548,749870334,870003722,800097406,114253221,113812411,139931799,863411142,405229023,397895390,218654216,780355871,78708799,469257089,20907544,353101816,638372977,291379340,801372857,526773517,223542510,353810152,442651066,742807977,133729524,845904490,269371162,609285610,916209623,65745383,766935000,688112419,275323756,286114945,599602066},{0,39,772613719,919406954,328270599,47125084,598773732,251687908,472009858,197112292,492605985,69847212,149742828,88933584,170838910,905304620,249869770,448916231,270836872,414456606,294119284,266246613,948352497,668668434,154229715,40054059,556293935,889091278,652752032,707742019,879270448,571593822,159195738,152265511,56949605,733273638,412843779,279595048,708112212},{0,40,940399369,688733272,123263614,139208513,533723618,351933885,465842987,327339525,300113131,697259722,816741,989106303,346128080,449182920,50310021,858414400,384856144,526703329,204935379,112750660,961108288,515185928,454201563,830541258,500125383,203588490,422120884,178656572,786225720,59734019,536715178,646761905,755193028,68910020,269207468,175078978,565606282,754398817},{0,41,79878199,645368937,474398937,775592230,18938811,270204132,250180744,429774968,748617476,60707038,357605808,782840496,141690416,25493035,654549439,109292402,309620909,511984653,561220430,288345159,822970356,541455391,363335827,339535687,673974192,665253383,743148920,217158271,956419255,389555483,56936571,224827721,841964143,43091991,791706437,289679663,46824963,945500464,361724072}};
signed main(){
	int T,n,k;
	scanf("%d",&T);
	for(;T--;){
		scanf("%d%d",&n,&k);
		printf("%d\n",Ans[n][k]);
	}
	return 0;
	freopen("db.txt","w",stdout);
	printf("int Ans[44][44]={{}");
	for(n=1;n<=40;n++){
		printf(",{0");
		for(k=1;k<=n;k++){
//			scanf("%d%d",&n,&k);
			vs.clear();
			fac[0]=pwk[0]=1;
			for(int i=1;i<N;i++)fac[i]=1ll*fac[i-1]*i%p,pwk[i]=1ll*pwk[i-1]*k%p;
			C[0][0]=S[0][0]=1;
			for(int i=1;i<N;i++){
				C[i][0]=1;
				for(int j=1;j<=i;j++){
					C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
					S[i][j]=(S[i-1][j-1]+1ll*j*S[i-1][j])%p;
				}
			}
			ans=pwk[n];dfs(0,0,0);
			DP1::work(),DP2::work();
			printf(",%d",ans);
			cerr<<n<<' '<<k<<'\n';
		}
		printf("}");
	}
	printf("};\n");
}