16002 | 무지개 트리

그래프 이론에서 트리는 사이클이 없는 연결된 무방향 단순 그래프이다. 노드가 n개인 트리는 항상 n - 1개의 간선을 가진다.

트리에서 경로는 서로 다르면서 연결된 간선들의 수열이다(경로에서 연속한 각 간선 쌍은 하나의 정점을 공유한다).

정점이 n개이고 간선이 n-1개인 트리를 생각하자. 각 간선을 k가지 색 중 하나로 칠할 수 있다.

모든 2개 또는 3개의 간선으로 이루어진 경로에서 간선들의 색이 서로 다르면, 간선에 색을 배정한 것을 무지개 색칠이라고 한다. (즉, 연속한 모든 두 간선의 색이 서로 다르고, 연속한 모든 세 간선의 색이 서로 다르다.)

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

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ k ≤ 1000000000 모든 노드 번호는 1 이상 n 이하이다.

1 ≤ C ≤ 100 2 ≤ n ≤ 20

1 ≤ C ≤ 40 2 ≤ n ≤ 500

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

"n k" 형식의 두 정수를 포함하는 한 줄. n은 트리의 노드 수이고, k는 사용할 수 있는 색의 수이다.
각 간선마다 하나씩 주어지는 n - 1개의 줄. 각 줄에는 두 정수 "x y"가 주어지며, 노드 x와 노드 y 사이에 간선이 있음을 나타낸다. 노드에는 1부터 n까지 번호가 매겨져 있다.

각 테스트 케이스마다 한 줄을 출력한다. 이 줄에는 "Case #X: Y"을 출력해야 하며, 여기서 X는 1부터 세는 케이스 번호이고 Y는 해당 테스트 케이스의 답이다.

Case #1: 720
Case #2: 6

첫 번째 케이스에서 트리는 네 개의 노드를 가진다. 한 노드에서 나머지 세 노드 각각으로 이어지는 간선이 있다. 이 간선들은 각 쌍이 인접하므로, 무지개 색칠이 되려면 모든 간선의 색이 서로 달라야 한다. 따라서 무지개 색칠은 10 x 9 x 8 = 720가지이다.

두 번째 케이스에서 트리 자체는 4개의 간선으로 이루어진 경로이고, 색은 3가지이다. 처음 세 간선은 모두 서로 다른 색이어야 하므로 이 간선들을 칠하는 방법은 3 x 2 x 1가지이고, 그다음 네 번째 간선에는 선택지가 하나뿐이므로 무지개 색칠은 6가지이다.