/*
[templates]: 
duipai
spjdp
compre
addhis
floor_sum
treedfs
matrix
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(time(0)); 
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
    string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; } 
    reverse(s.begin(), s.end()); cerr << s << endl; 
    return;
}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍！
//use std::array.
vector<int> t[100100]; int ans = 1, leaf, root; int k;  const int mod = 1000000009; 
void dfs(int now, int fa, int un) {
    if(fa != 0) un ++;
    if(fa != 0 && fa != root) un ++;
    // cerr << now << " " << fa << " " << un << endl; 
    ans *= k - un; 
    ans %= mod; 
    int cnt = 0;  
    for(int i : t[now]) {
        if(i != fa && i != leaf) {
            dfs(i, now, cnt++); 
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen();
    //freopen();
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int T; cin >> T; int TT = 0; 
    while(T--) {
        TT ++; 
        int n; cin >> n; cin >> k; ans = 1; 
        f(i, 1, n) t[i].clear(); 
        f(i, 1, n - 1) {
            int u, v; cin >> u >> v; 
            t[u].push_back(v); t[v].push_back(u); 
        }
        f(i, 1, n) if(t[i].size() == 1) leaf = i; 
        root = t[leaf][0]; 
        // cerr << root << " " << leaf << endl; 
        dfs(root, 0, 0); 
        cout << "Case #" << TT << ": " <<  ans << endl;
    }
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}