#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50,mod=1e9+7;
int c,T,n,k,rt[N],u[N],v[N],ans,ans1;
vector<int> e[N];
namespace subtask1
{
	void solve()
	{
		while(T--)
		{
			scanf("%d %d",&n,&k);
			for(int i=1;i<n;i++) scanf("%d %d",&u[i],&v[i]);
			for(int i=1;i<=k;i++) scanf("%d",&rt[i]);
			puts("1");
		}
	}
}
namespace subtask2
{
	int ksm(int ds,int zs)
	{
		int re=1;
		while(zs)
		{
			if(zs&1) re=1ll*re*ds%mod;
			ds=1ll*ds*ds%mod;
			zs=zs/2; 
		}
		return re;
	}
	void solve()
	{
		while(T--)
		{
			scanf("%d %d",&n,&k);
			for(int i=1;i<n;i++) scanf("%d %d",&u[i],&v[i]);
			for(int i=1;i<=k;i++) scanf("%d",&rt[i]);
			ans=k,ans1=1ll*k*(k-1)%mod;
			for(int i=1;i<n-1;i++) ans=1ll*ans*i%mod;
			for(int i=1;i<n-2;i++) ans1=1ll*ans1*i%mod;
			ans1=1ll*ans1*ksm(2,mod-2)%mod;
			printf("%d\n",(ans-ans1+mod)%mod);
		}
	}
}
int main()
{
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	scanf("%d %d",&c,&T);
	if(c==18) subtask1::solve();
	if(c>=19&&c<=21) subtask2::solve();
	return 0;
}
