在图论中，树是一个连通、无环的无向简单图。一个有 $n$ 个节点的树总是有 $n-1$ 条边。

树中的路径是一系列相连的不同边（路径中每相邻的两条边共享一个顶点）。

考虑一个有 $n$ 个顶点和 $n-1$ 条边的树。你可以用 $k$ 种颜色中的一种为每条边着色。

如果对于树中每一条长度为 2 或 3 的路径，其包含的边的颜色各不相同，则称这种边的着色方案为“彩虹着色”（即：任意两条相邻的边颜色不同，且任意三条连续的边颜色也各不相同）。

给定一棵树和颜色数量 $k$，求彩虹着色的方案数，结果对 $1000000009$ 取模。

输入格式

输入的第一行包含测试用例的数量 $C$。接下来对于每个测试用例：

• 第一行包含两个整数，格式为 "$n \ k$"。$n$ 是树的节点数，$k$ 是可用的颜色数量。
• 接下来 $n-1$ 行，每行包含两个整数 "$x \ y$"，表示节点 $x$ 和节点 $y$ 之间有一条边。节点编号从 1 到 $n$。

输出格式

对于每个测试用例，输出一行。该行应包含 "Case #$X$: $Y$"，其中 $X$ 是从 1 开始的用例编号，$Y$ 是该测试用例的答案。

数据范围

$1 \le k \le 1000000000$

所有节点编号均在 1 到 $n$ 之间（含边界）。

小数据集（测试集 1 - 可见；9 分）

$1 \le C \le 100$

$2 \le n \le 20$

大数据集（测试集 2 - 隐藏；15 分）

$1 \le C \le 40$

$2 \le n \le 500$

样例

样例输入 1

2
4 10
1 2
1 3
1 4
5 3
1 2
2 3
3 4
4 5

样例输出 1

Case #1: 720
Case #2: 6

说明

在第一个用例中，树有四个节点。其中一个节点与其余三个节点各有一条边相连。这些边两两相邻，因此要满足彩虹着色，所有边必须颜色各不相同。因此共有 $10 \times 9 \times 8 = 720$ 种彩虹着色方案。

在第二个用例中，树本身是一条包含 4 条边的路径，且有 3 种颜色。前三条边必须颜色各不相同，因此这三条边有 $3 \times 2 \times 1$ 种着色方案，而第四条边只有一种选择，因此共有 6 种彩虹着色方案。