Rainbow Trees

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

A path in a tree is a sequence of distinct edges in which every two consecutive edges share a vertex.

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

A painting is a rainbow coloring if the edges of every path made of 2 edges have different colors and the edges of every path made of 3 edges have different colors. In other words, two consecutive edges always differ in color, and three consecutive edges always use three different colors.

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

The first line contains the number of test cases $C$. Each test case then consists of the following.

• One line with two integers $n$ and $k$ separated by a space. $n$ is the number of vertices of the tree and $k$ is the number of available colors.
• $n-1$ lines, one per edge, each with two integers $x$ and $y$: the endpoints of that edge. Vertices are numbered from 1 to $n$.

Limits

• $1 \le C \le 40$
• $2 \le n \le 500$
• $1 \le k \le 1000000000$
• Every vertex number is between 1 and $n$, inclusive.
• The $n-1$ given edges always form a tree.

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

Take a tree with 4 vertices where one vertex is joined to each of the other three, with 10 colors available. All three edges are pairwise adjacent, so a rainbow coloring must give them three different colors. That leaves $10 \times 9 \times 8 = 720$ colorings.

Now take a tree whose 5 vertices form a single path, with 3 colors available. The first three edges must all differ, which gives $3 \times 2 \times 1$ choices, and the color of the fourth edge is then forced. So there are 6 rainbow colorings.