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$.
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$.
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.
|Sample Input 1||Sample Output 1|
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