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 that are connected: every two consecutive edges of the sequence share a vertex.

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

A coloring of the edges is a rainbow coloring if the edges of every path of 2 edges and of every path of 3 edges all have different colors. That is, any two consecutive edges have different colors, and any three consecutive edges have three different colors.

Given the tree and the number of colors $k$, count the rainbow colorings modulo $1000000009$.

The first line contains the number of test cases $C$. Each of the $C$ cases follows in this format.

• One line with two integers $n$ and $k$. Here $n$ is the number of nodes of the tree and $k$ is the number of available colors.
• $n - 1$ lines, one per edge, each with two integers $x$ and $y$, meaning that an edge joins node $x$ and node $y$. Nodes are numbered from 1 to $n$.

Limits

• $1 \le C \le 100$
• $2 \le n \le 20$
• $1 \le k \le 1000000000$
• Every node number is between 1 and $n$, inclusive.

For each test case print one line in the form Case #X: Y, where $X$ is the 1-based number of the case and $Y$ is the answer for that case.

In the first sample case the tree has four nodes, and its three edges all meet at one node. Each pair of these edges is adjacent, so a rainbow coloring gives them three different colors, which leaves $10 \times 9 \times 8 = 720$ colorings.

In the second sample case the tree is a path of 4 edges and there are 3 colors. The first three edges must all have different colors, so they can be colored in $3 \times 2 \times 1$ ways, and then only one color is left for the fourth edge. That gives 6 rainbow colorings.