#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long t,c,n,k;
vector<long long>G[100005];
long long C(long long n,long long k)
{
	long long res1=1,res2=1;
	for(int i=k;i>=2;i--)res1=res1*i%mod;
	//cout<<res1<<' ';
	for(int i=n;i>=2;i--)res2=res2*i%mod;
	//cout<<res2<<endl;
	return (res2/res1)/res1%mod;
}
int main()
{
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	cin>>c>>t;
	while(t--)
	{
		//cout<<C(4,2)<<endl;
		cin>>n>>k;
	//	cout<<C(n,k)<<endl;
		for(int i=1;i<n;i++)
		{
			long long u,v;
			cin>>u>>v;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		if(c==16 or c==17 or c==18)
		{
			cout<<1<<endl;
			continue;
		}
		else if(c==19 or c==20 or c==21)
		{
			cout<<(1+k)*k/2%mod*C(n,k)<<endl;
		}
	}
	return 0;
}
