#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i) 
#define fd(i,a,b) for(int i=(a);i>=(b);--i) 
#define fu(i,a,b) for(int i=(a);i<(b);++i)
#define ll long long 
using namespace std;
const int N=1e5+5,mo=1e9+7,inv2=5e8+4;
int c,T,n,k,u[N],v[N],e[N],d[N];
ll jc[N];
inline int read()
{
	int num=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	return num;
}
void clear()
{
	fo(i,1,n)d[i]=0;
}
int main()
{
	freopen("traverse.in","r",stdin); 
	freopen("traverse.out","w",stdout); 
	c=read(),T=read();
	if(c==18)
	{
		while(T--)printf("1\n");
	}
	else if(19<=c&&c<=21)
	{
		jc[0]=1;fo(i,1,100000)jc[i]=jc[i-1]*i%mo;
		while(T--)
		{
			n=read();k=read();
			clear();
			fu(i,1,n){u[i]=read();v[i]=read();}
			fo(i,1,k)e[i]=read();
			if(n==2)printf("1\n");
			else printf("%lld\n",(jc[n-2]*k%mo-jc[n-3]*(k-1)%mo*k%mo*inv2%mo+mo)%mo);
		}
	}
	else
	{
		jc[0]=1;fo(i,1,100000)jc[i]=jc[i-1]*i%mo;
		while(T--)
		{
			n=read();k=read();
			clear();ll ans=1;
			fu(i,1,n){u[i]=read();v[i]=read();++d[u[i]];++d[v[i]];}
			fo(i,1,k)e[i]=read();
			fo(i,1,n)ans=ans*jc[d[i]-1]%mo;
			printf("%lld\n",ans);
		}
	}
	return 0;
}
