#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MOD = 1e9 + 7;

int n, m;
vector<int> E[1010];
int cnt[1010];
LL fact[1010];
LL dp[1010][1010];

LL POW(LL a, LL b) {
	LL res = 1;
	while (b) {
		if (b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}

void dfs(int u, int fa) {
	cnt[u] = 1;
	for (int &v : E[u]) {
		if (v == fa) continue;
		dfs(v, u);
		cnt[u] += cnt[v];
	}
}

int main()
{
	fact[0] = 1;
	for (int i = 1; i <= 1000; i++) fact[i] = fact[i - 1] * i % MOD;
	int T;
	scanf("%d", &T);
	for (int cas = 1; cas <= T; cas++) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++) {
			E[i].clear();
		}
		for (int i = 1; i < n; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			E[u].push_back(v);
			E[v].push_back(u);
		}
		dfs(1, 0);
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			LL q = POW(cnt[i], MOD - 2);
			LL p = (cnt[i] - 1) * q % MOD;
			dp[i][0] = dp[i - 1][0] * p % MOD;	
			for (int j = 1; j <= m; j++) {
				dp[i][j] = (dp[i - 1][j] * p + dp[i - 1][j - 1] * q) % MOD;
			}
		}
		LL ans = fact[n] * dp[n][m] % MOD;
		printf("Case #%d: %lld\n", cas, ans);
	}
	return 0;
}