Yevin Kang は、$N$ 個の頂点を持つ木を持っており、各頂点には $1$ から $N$ までの整数がラベル付けされています。木とは、閉路を含まない無向連結グラフのことです。

正の整数 $K$ に対して、$f(K)$ を以下のように定義します。

任意の2頂点 $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$) が含まれます。

各テストケースの最初の行には、2つの整数 $N, Q$ ($1 \le Q \le N \le 5 \times 10^5$) がスペース区切りで含まれます。

続く $N - 1$ 行の各行には、木における頂点 $u$ と $v$ を結ぶ辺を表す2つの整数 $u, v$ がスペース区切りで含まれます。$N - 1$ 本の辺が木を形成することが保証されています。

次の行には、$Q$ 個の整数 $K_1, \dots, K_Q$ が含まれ、これらは $Q$ 個のクエリを表します。

すべてのテストケースにおける $N$ の総和（$\sum N$ と表記）は $5 \times 10^5$ を超えないことが保証されています。

以下の表は、25点分の配点の内訳を示しています。

出力

各テストケースについて、$Q$ 個の整数をスペース区切りで1行に出力してください。これらは $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

注記

サンプル入力の2つの木を以下に示します。

最初のテストケースにおいて、$K = 2$ または $K = 3$ のとき、$[1, 2, 3]$ と $[1, 3, 2]$ はどちらも良い順列です。$[2, 1, 3]$ は、 $d(1, p_1) = 1 \not\le 0 = d(1, p_2)$ となり、2番目の条件に違反するため、どのような $K$ の値に対しても良い順列ではありません。

$K = 1$ のとき、良い順列は存在しないことが示せます。

2番目のテストケースにおいて、$[1, 3, 2, 4, 5, 6]$ は $K = 3$ のときは良い順列ですが、$K = 2$ のときは $d(2, 4) = 3 \not\le 2$ となるため、良い順列ではありません。