#include <cstdio>
#include <iostream>

using namespace std;

const int Max=100005;
const long long Mod=1000000007;

int n,k,e[Max];

#define Solve_Lian() cout<<"1\n"

long long qpow(long long x,long long y) {
	if(y==0)
		return 1;
	if(y==1)
		return x;
	long long r=qpow(x*x%Mod,y/2);
	if(y&1)
		return r*r%Mod*x%Mod;
	return r*r%Mod;
}

void Solve_JuHua() {
	if(n==2) {
		cout<<"1\n";
		return;
	}
	auto jc=[Mod](int x) -> long long {
		long long res=1;
		for(;x;x--)
			res=res*x%Mod;
		return res;
	};
	
	if(k==1)
		cout<<jc(n-2)%Mod<<'\n';
	else
		cout<<(k*jc(n-2)%Mod-(long long)k*(k-1)/2%Mod*jc(n-3)%Mod+Mod)%Mod<<'\n';
}

int main() {
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	ios::sync_with_stdio(false);

	int T,c;
	cin>>c>>T;
	while(T--) {
		cin>>n>>k;
		for(int i=1,uselessVariableWithAnExceedinglyLongName;i<=n*2-2;i++)
			cin>>uselessVariableWithAnExceedinglyLongName;
		for(int i=1;i<=k;i++)
			cin>>e[i];
		if(c==18)
			Solve_Lian();
		else
			Solve_JuHua();
	}
}
