#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

const int N = 1e5 + 5,mod = 1e9 + 7;

vector<int> t[N];

int fac[N],e[N],inv[N],u[N],v[N];

int qmi(int a,int b){

	int res = 1;

	while(b){

		if(b & 1) res = 1ll * res * a % mod;

		b >>= 1;

		a = 1ll * a * a % mod;

	}

	return res;

}

vector<int> g[N];

int C(int a,int b){

	if(a < b) return 0;

	return 1ll * fac[a] * inv[b] % mod * inv[a - b] % mod;

}

int main(){

	ios::sync_with_stdio(false);

	cin.tie(0),cout.tie(0);

	freopen("traverse.in","r",stdin);

	freopen("traverse.out","w",stdout);

	fac[0] = 1;

	for(int i=1;i<N;i++){

		fac[i] = 1ll * fac[i - 1] * i % mod;

//		cout<<fac[i]<<" ";

	}

	inv[N - 1] = qmi(fac[N - 1],mod - 2);

	for(int i=N - 2;i>=0;i--){

		inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;

//		cout<<inv[i]<<" ";

	}

	int c,T;

	cin>>c>>T;

	while(T--){

		

		int n,k;

		cin>>n>>k;

		for(int i=1;i<n;i++){

			cin>>u[i]>>v[i];

		}

		for(int i=1;i<=k;i++){

			cin>>e[i];

		}

//		cout<<n<<" "<<k<<'\n';

		if(c == 18){

			cout<<1<<'\n';

		}else if(c >= 19 && c <= 21){

			if(n == 2 || n == 3){

				cout<<1<<'\n';

				continue;

			}

			int res = 1ll * fac[n - 2] * k % mod;

			for(int i=1;i<=k;i++){

				res = (res + mod - 1ll * C(i - 1,1) * fac[n - 3] % mod) % mod;

			}

			cout<<res<<'\n';

		}else{

			cout<<1<<'\n';

		}

	}

	return 0;

}

/*

1

2 1 2

1 1

*/


