Problem G
Rainbow Trees

In graph theory, a tree is a connected, undirected simple graph with no cycles. A tree with $n$ nodes always has $n - 1$ edges.

A path in a tree is a sequence of distinct edges which are connected (each pair of consecutive edges in the path share a vertex).

Consider a tree with $n$ vertices and $n-1$ edges. You can color each edge in one of $k$ colors.

An assignment of colors to edges is a rainbow coloring if in every path of 2 or 3 edges, the colors of the edges are different. (i.e., every two consecutive edges have different colors, and every three consecutive edges have different colors).

Given a tree and the number of colors $k$, find the number of rainbow colorings modulo $1\, 000\, 000\, 009$.

Input

The first line of input gives the number of test cases, $C$. Then for each of the $C$ cases, there will be:

• One line containing two integers $n$ and $k$, where $n$ is the number of nodes in the tree, and $k$ is the number of colors available.

• $n - 1$ lines, one for each edge, containing two integers $x, y$, indicating that the edge is between node $x$ and node $y$. Nodes are numbered from 1 to $n$.

You may assume that $1 \leq k \leq 1\, 000\, 000\, 000$ and all the node numbers are between 1 and $n$, inclusive. Furthermore, $2 \leq n \leq 500$.

Output

For each test case, output one line. That line should contain "Case #$X$: $Y$", where $X$ is 1-based number of the case, and $Y$ is the answer for that test case.

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

Case #1: 720
Case #2: 6