#include<bits/stdc++.h>
using namespace std;

int c,t,n,k,num,ans,x[15],y[15],a[15],f;
bool vis[15];
void dfs(int now){
	if(now==n){
		++ans;
		return;
	}
	for(int i=1;i<n;++i){
		if(!vis[i]&&(x[i]==x[a[now-1]]||x[i]==y[a[now-1]]||y[i]==x[a[now-1]]||y[i]==y[a[now-1]])){
			vis[i]=true;
			a[i]=i;
			dfs(now+1);
			vis[i]=false;
		}
	}
}
int work(int now){
	long long res=1;
	for(int i=now-2;i>1;--i) res=(res*i)%mod;
	return res;
}
int main(){
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>c>>t;
	while(t--){
		ans=0;
		cin>>n>>k;
		if(n>=10||k>1){
			for(int i=1;i<n;++i) cin>>num>>num;
			for(int i=0;i<k;++i) cin>>num;		
		}
		else if(k){
			for(int i=1;i<n;++i) cin>>x[i]>>y[i];
			cin>>f;
		}
		else for(int i=1;i<n;++i) cin>>num>>num;
		if(n<10&&k==1){
			memset(vis,false,sizeof(vis));
			vis[f]=true;
			a[1]=f;
			dfs(2);
			cout<<ans<<"\n";
		}
		else if(c>=19&&c<=21) cout<<work(n)<<"\n"; 
		else if(k==0) cout<<"0\n";
		else if(c!=18) cout<<n-2<<"\n";
		else cout<<"1\n";
	}
	return 0;
} 
