Yevin Kang 擁有一棵包含 $N$ 個頂點的樹，頂點標號為 $1$ 到 $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$ 若滿足以下所有條件，則稱為「好的」： 對於所有 $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$，表示樹中有一條連接 $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

說明 1

範例輸入中的兩棵樹如下所示：

在第一個測試案例中，對於 $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$。