Problem Description

Yevin Kang has a tree with $N$ vertices that are labelled with integers from $1$ to $N$. A tree is an undirected connected graph that does not contain a cycle.

Let $K$ be a positive integer. We define $f(K)$ as follows.

For any two vertices $1 \le u, v \le N$, let $d(u, v)$ denote the number of edges on the simple path connecting vertex $u$ and vertex $v$. In particular, $d(u, u) = 0$ for all $1 \le u \le N$.

A permutation $p_1, \ldots, p_N$ of $1, \ldots, N$ is good if all of the following conditions are satisfied.

• $d(p_{i-1}, p_i) \le K$ for all $i = 2, \ldots, N$.
• $d(1, p_i) \le d(1, p_j)$ for all pairs of integers $(i, j)$ with $1 \le i < j \le N$.

Then, $f(K)$ is the number of good permutations.

Yevin thinks this problem is too easy, so he gives you $Q$ positive integers $K_1, \ldots, K_Q$. He asks you to print the values of $f(K_1), f(K_2), \ldots, f(K_Q)$, mod $10^9 + 7$.

It may also be useful to note that “mod” corresponds to the $\%$ operator in most programming languages, indicating the remainder after division. For example, $5 \bmod 3 = 2$ and $17 \bmod 4 = 1$.

Input Format

Each test has multiple test cases.

The first line of the test contains one integer $T$ ($1 \le T \le 5 \times 10^5$) — the number of test cases.

The first line of each test case contains two space-separated integers $N, Q$ ($1 \le Q \le N \le 5 \times 10^5$).

Each of the next $N - 1$ lines contains two space-separated integers $u, v$ — indicating that there is an edge connecting $u$ and $v$ in the tree. It is guaranteed that the $N - 1$ edges form a tree.

The next line contains $Q$ integers, $K_1, \ldots, K_Q$ — denoting the $Q$ queries.

It is guaranteed that the sum of $N$ over all test cases in a test (denoted by $\sum N$) does not exceed $5 \times 10^5$.

Output Format

For each test case, output one line with $Q$ space-separated integers — the values of $f(K_1), f(K_2), \ldots, f(K_Q)$, mod $10^9 + 7$.

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

0 2 2
0 6 12

Hint

Explanation of Output for Sample Input

The two trees in the sample input are shown below.

:::align{center} :::

In the first test case, for $K = 2$ or $K = 3$, both $[1, 2, 3]$ and $[1, 3, 2]$ are good permutations. $[2, 1, 3]$ is not a good permutation for all values of $K$ because

violates the second condition.

It can be shown that no permutation is good for $K = 1$.

In the second test case, $[1, 3, 2, 4, 5, 6]$ is a good permutation for $K = 3$ but not a good permutation for $K = 2$ because $d(2, 4) = 3 \nleq 2$.

The following table shows how the $25$ available marks are distributed: