#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7,N=1e5+5;
ll jc[N];
set<set<pair<int,int> > >trees;
vector<int>g2[10];
bool vis[10];
set<pair<int,int> >nset;
int cnt;
int nn;
void dfs(int x){
	vis[x]=1;
	cnt++;
	if(cnt==nn-1){
		trees.insert(nset);
//		for(auto tt:nset){
//			cout<<tt.first<<" "<<tt.second<<endl;
//		}cout<<endl;
		cnt--;
		vis[x]=0;
		return;
	}
	for(int y:g2[x])if(!vis[y]){
		nset.insert({x,y});
		nset.insert({y,x});
		dfs(y);
		nset.erase({x,y});
		nset.erase({y,x});
	}
	cnt--;
	vis[x]=0;
}
int main(){
//	system("FC traverse10.out traverse10.ans");
	ios::sync_with_stdio(0);cin.tie(0);
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	//真的不会了
	//好多阳历啊 
	
	//特殊性质 A 答案是 1
	int c,t;cin>>c>>t;
	if(c==18){
		while(t--)cout<<"1\n";
		return 0;
	} 
	//特殊性质 B 在 n-1 点的团里面找一个 k 开始的长度n-2的路径方案 
	/*
	(n-3)!*(k*(k-1)/2+k*(n-1-k))
	*/
	if(c>=19&&c<=21){
		jc[0]=1;
		for(ll i=1;i<=N-3;i++){
			jc[i]=jc[i-1]*i;
			jc[i]%=mod;
		}
		while(t--){
			ll n,k;cin>>n>>k;
			if(n==2){
				cout<<"1\n";continue;
			}
			int x;
			for(int i=1;i<n;i++)cin>>x>>x;
			for(int i=1;i<=k;i++)cin>>x;
			ll ans=k*(k-1)/2;//12:23 bbzl zhelixiecheng + tiaowufnzhong
			ans%=mod;
			ans+=k*(n-1-k);
			ans%=mod;
			ans*=jc[n-3];
			ans%=mod;
			cout<<ans<<"\n";
		}
		return 0;
	}
	if(c<=3){
		while(t--){
			trees.clear();
			memset(vis,0,sizeof vis);
			for(int i=1;i<=10;i++)g2[i].clear();
			map<pair<int,int>,int>mp;
			vector<int>g[10];
			int k;cin>>nn>>k;
			for(int i=1;i<nn;i++){
				int u,v;cin>>u>>v;
				mp[{u,v}]=mp[{v,u}]=i;
				g[u].emplace_back(v);g[v].emplace_back(u);
			}
			int x;cin>>x;
			for(int i=1;i<=nn;i++){
				for(int j:g[i]){
					for(int k:g[i])if(j!=k){
						g2[mp[{i,j}]].emplace_back(mp[{i,k}]);
					}
				}
			}
			dfs(x);
			cout<<trees.size()<<"\n";
		}
	}
	else{
		while(t--)cout<<"1\n";
	}
	//28 pts
	//TAT
	//luogu uid 542457 (& 1377777)
	return 0;
}
