#include<cstdio>
#define int long long
const int N=7,M=16,MOD=1e9+7;
int fac[N],ifac[N],s[N],vis[1<<M],f[M+1][M+1];
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int Add(int &a,int b){return(a+=b)>=MOD?a-=MOD:a;}
int vAdd(int a,int b){return(a+=b)>=MOD?a-=MOD:a;}
int Sub(int &a,int b){return(a-=b)<0?a+=MOD:a;}
int vSub(int a,int b){return(a-=b)<0?a+=MOD:a;}
int Mul(int a,int b){return 1ll*a*b%MOD;}
int qpow(int a,int b){
	int ret=1;
	while(b){if(b&1)ret=Mul(ret,a);a=Mul(a,a);b>>=1;}
	return ret;
}
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
bool prework(){
	fac[0]=1;for(int i=1;i<=6;i++)fac[i]=fac[i-1]*i;
	ifac[0]=1;for(int i=1;i<=6;i++)ifac[i]=qpow(fac[i],MOD-2);
	for(int i=1;i<=4;i++){
		int len=(1<<i);
		for(int j=0;j<(1<<len);j++){
			int cnt=0;
			s[0]=s[1]=s[2]=s[3]=0;
			for(int k=0;k<len;k++){
				if(!((j>>k)&1))continue;
				cnt++;
				for(int l=0;l<i;l++)if((k>>l)&1)s[l]|=1<<(cnt-1);
			}
			vis[(1<<cnt)-1]=vis[0]=1;
			for(int k=0;k<i;k++)vis[s[k]]++;
			bool flag=true;
			for(int x=0;x<i;x++){
				for(int y=x;y<i;y++)
					if(vis[s[x]|s[y]]!=1||vis[s[x]&s[y]]!=1){
						flag=false;
						break;
					}
				if(!flag)break;
			}
			vis[(1<<cnt)-1]=vis[0]=0;
			for(int k=0;k<i;k++)vis[s[k]]=0;
			f[cnt][i]+=flag;
		}
	}
	return true;
}
int C(int n,int m){int ret=1;for(int i=0;i<m;i++)ret=Mul(ret,n-i);return Mul(ret,ifac[m]);}
int calc(int n,int m){
	n%=MOD;int ret=0;
	for(int i=0;i<m;i++)
		if(!(i&1))Add(ret,Mul(C(m,m-i),qpow(m-i,n)));
		else Sub(ret,Mul(C(m,m-i),qpow(m-i,n)));
	return ret;
}
bool solve(){
	int n=read();int m=read();int ans=0;
	if(m==2){puts("2");return true;}
	for(int i=1;i<=Min(n,1<<(m-2));i++)Add(ans,Mul(f[i][m-2],calc(n,i)));
	printf("%d\n",Mul(m*(m-1),ans));
	return true;
}
signed main(){
	prework();
	int T=read();
	while(T--)solve();
}