무지개 트리

그래프 이론에서 트리는 사이클이 없는 연결 무향 단순 그래프다. 정점이 $n$개인 트리에는 항상 간선이 $n-1$개 있다.

트리에서 경로는 서로 다른 간선을 이어 붙인 수열이고, 경로 안에서 연속한 두 간선은 정점을 하나 공유한다.

정점이 $n$개, 간선이 $n-1$개인 트리가 있다. 각 간선을 $k$가지 색 중 하나로 칠한다.

간선 2개로 이루어진 모든 경로와 간선 3개로 이루어진 모든 경로에서 간선의 색이 서로 다르면 그 색칠을 무지개 색칠이라고 한다. 즉 연속한 두 간선의 색이 다르고, 연속한 세 간선의 색도 모두 다르다.

트리와 색의 개수 $k$가 주어진다. 무지개 색칠의 개수를 $1000000009$로 나눈 나머지를 구하라.

첫 줄에 테스트 케이스의 개수 $C$가 주어진다. 이어서 각 테스트 케이스마다 다음이 주어진다.

• 첫 줄에 정수 두 개 $n$과 $k$가 공백으로 구분되어 주어진다. $n$은 트리의 정점 수이고 $k$는 쓸 수 있는 색의 개수다.
• 다음 $n-1$개 줄에 간선 하나씩, 그 간선이 잇는 두 정점의 번호 $x$와 $y$가 주어진다. 정점 번호는 1부터 $n$까지다.

제한

• $1 \le C \le 40$
• $2 \le n \le 500$
• $1 \le k \le 1000000000$
• 모든 정점 번호는 1 이상 $n$ 이하다.
• 주어지는 간선 $n-1$개는 항상 트리를 이룬다.

각 테스트 케이스마다 한 줄씩, Case #X: Y 형식으로 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호이고 $Y$는 그 케이스의 답이다.

정점 4개짜리 트리에서 한 정점이 나머지 세 정점과 각각 이어져 있고 색이 10가지라고 하자. 세 간선은 서로 모두 인접하므로 무지개 색칠에서는 색이 셋 다 달라야 한다. 따라서 색칠은 $10 \times 9 \times 8 = 720$가지다.

정점 5개가 한 줄로 이어진 트리에서 색이 3가지라고 하자. 앞의 세 간선은 색이 모두 달라야 해서 $3 \times 2 \times 1$가지이고, 네 번째 간선의 색은 하나로 정해진다. 그러므로 무지개 색칠은 6가지다.