Little Cyan Fish와 Little Kevinfish는 수열 정렬 게임을 하고 있습니다. Little Kevinfish는 $n$개의 정점으로 이루어진 트리 $T$를 가지고 있으며, 정점에는 $1$부터 $n$까지의 정수가 번호로 매겨져 있습니다.

$1$부터 $n$까지의 정수로 구성된 수열 $A$에 대하여, Little Kevinfish는 다음과 같은 교환 연산을 정의합니다:

• $A_i$와 $A_j$라는 번호가 매겨진 정점이 트리 $T$에서 간선으로 직접 연결되도록 하는 인덱스 $i, j$를 선택합니다.
• $A_i$와 $A_j$의 위치를 서로 바꿉니다.

Little Kevinfish는 Little Cyan Fish에게 다음과 같은 질문을 합니다:

• 주어진 상수 $m$에 대하여, 각 $\ell = 1, 2, \dots, m$에 대해 다음 문제를 해결하세요:
  • $1$부터 $n$까지의 정수로 구성된 길이 $\ell$인 수열 $A$를 고려합니다 (총 $n^\ell$개의 수열이 존재합니다). 이 수열 $A$ 중, 위에서 정의한 교환 연산을 임의의 횟수만큼 수행하여 단조 비감소(monotonically non-decreasing) 수열로 변환할 수 있는 수열 $A$는 몇 개인가요?

Little Cyan Fish가 Little Kevinfish의 질문에 답할 수 있도록 도와주세요. 정답이 매우 클 수 있으므로, $10^9 + 7$로 나눈 나머지를 출력하면 됩니다.

입력

입력은 여러 개의 테스트 케이스로 구성됩니다. 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 $n$과 $m$ ($1 \le n \le 200, 1 \le m \le 10^5$)이 주어집니다.

다음 $(n - 1)$개의 줄에는 각각 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)가 주어지며, 이는 정점 $u_i$와 $v_i$를 잇는 간선을 의미합니다. 이 $(n - 1)$개의 간선은 항상 유효한 트리를 형성함이 보장됩니다.

모든 테스트 케이스에 대한 $n$의 합은 $200$을 넘지 않으며, $m$의 합은 $10^5$를 넘지 않습니다.

출력

각 테스트 케이스마다 $m$개의 정수를 한 줄에 출력합니다. $i$번째 ($1 \le i \le m$) 정수는 $\ell = i$일 때의 정답을 $10^9 + 7$로 나눈 나머지입니다.

예제

입력 1

3
3 4
1 2
2 3
4 2
1 2
1 3
3 4
1 10

출력 1

3 8 23 70
4 13
1 1 1 1 1 1 1 1 1 1