Yevin Kang은 $1$부터 $N$까지의 정수로 레이블이 지정된 $N$개의 정점을 가진 트리를 가지고 있습니다. 트리는 사이클이 없는 무방향 연결 그래프입니다.

양의 정수 $K$에 대하여 $f(K)$를 다음과 같이 정의합니다.

임의의 두 정점 $1 \le u, v \le N$에 대하여, $d(u, v)$를 정점 $u$와 정점 $v$를 연결하는 단순 경로상의 간선 개수라고 합니다. 특히, 모든 $1 \le u \le N$에 대하여 $d(u, u) = 0$입니다.

$1, \dots, N$의 순열 $p_1, \dots, p_N$이 다음 조건을 모두 만족하면 좋은(good) 순열이라고 합니다. 모든 $i = 2, \dots, N$에 대하여 $d(p_{i-1}, p_i) \le K$입니다. $1 \le i < j \le N$인 모든 정수 쌍 $(i, j)$에 대하여 $d(1, p_i) \le d(1, p_j)$입니다.

이때, $f(K)$는 좋은 순열의 개수입니다.

Yevin은 이 문제가 너무 쉽다고 생각하여, $Q$개의 양의 정수 $K_1, \dots, K_Q$를 줍니다. $f(K_1), f(K_2), \dots, f(K_Q)$의 값을 각각 $10^9 + 7$로 나눈 나머지를 출력하세요.

"mod"는 대부분의 프로그래밍 언어에서 나눗셈 후의 나머지를 나타내는 % 연산자에 해당합니다. 예를 들어, $5 \pmod 3 = 2$이고 $17 \pmod 4 = 1$입니다.

입력

각 테스트는 여러 개의 테스트 케이스를 포함합니다.

첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 5 \times 10^5$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 두 개의 정수 $N, Q$ ($1 \le Q \le N \le 5 \times 10^5$)가 공백으로 구분되어 주어집니다.

다음 $N - 1$개의 줄에는 트리의 간선을 나타내는 두 정수 $u, v$가 공백으로 구분되어 주어집니다. $N - 1$개의 간선은 트리를 형성함이 보장됩니다.

다음 줄에는 $Q$개의 정수 $K_1, \dots, K_Q$가 주어지며, 이는 $Q$개의 쿼리를 나타냅니다.

모든 테스트 케이스에 대한 $N$의 합($\sum N$)은 $5 \times 10^5$를 넘지 않음이 보장됩니다.

다음 표는 25점의 배점 분포를 나타냅니다.

출력

각 테스트 케이스마다 $Q$개의 정수를 공백으로 구분하여 한 줄에 출력하세요. 이는 $f(K_1), f(K_2), \dots, f(K_Q)$를 $10^9 + 7$로 나눈 값입니다.

예제

입력 1

2
3 3
1 2
1 3
1 2 3
6 3
1 2
1 3
3 4
3 5
3 6
1 2 3

출력 1

0 2 2
0 6 12

참고

예제 입력의 두 트리는 아래와 같습니다.

첫 번째 테스트 케이스에서 $K=2$ 또는 $K=3$일 때, $[1, 2, 3]$과 $[1, 3, 2]$는 모두 좋은 순열입니다. $[2, 1, 3]$은 모든 $K$ 값에 대해 좋은 순열이 아닌데, 그 이유는 다음과 같이 두 번째 조건을 위반하기 때문입니다. $d(1, p_1) = 1 \not\le 0 = d(1, p_2)$

$K=1$인 경우 좋은 순열은 존재하지 않음을 보일 수 있습니다.

두 번째 테스트 케이스에서 $[1, 3, 2, 4, 5, 6]$은 $K=3$일 때는 좋은 순열이지만, $K=2$일 때는 $d(2, 4) = 3 \not\le 2$이므로 좋은 순열이 아닙니다.