题目描述

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 $1000000009$.

输入格式

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 in the format "$n$ $k$". $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$.

输出格式

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

提示

Sample Explanation

In the first case, the tree has four nodes. There are edges from one node to each of the other three. Each pair of these edges are adjacent, so for there to be a rainbow coloring, all the edges must have different colors. There are therefore $10 \times 9 \times 8 = 720$ rainbow colorings.

In the second case, the tree itself is a path of $4$ edges, and there are $3$ colors. The first three edges must all have different colors, so there are $3 \times 2 \times 1$ colorings for these, and then there is only one choice for the fourth edge, so there are $6$ rainbow colorings.

Limits

• $1 \leq k \leq 1000000000$
• All the node numbers are between $1$ and $n$, inclusive.

Small dataset (9 Pts, Test set 1 - Visible)

• $1 \leq C \leq 100$
• $2 \leq n \leq 20$

Large dataset (15 Pts, Test set 2 - Hidden)

• $1 \leq C \leq 40$
• $2 \leq n \leq 500$