Yevin Kang có một cây với $N$ đỉnh được đánh số từ $1$ đến $N$. Cây là một đồ thị vô hướng liên thông không chứa chu trình.
Cho $K$ là một số nguyên dương. Ta định nghĩa $f(K)$ như sau:
Với hai đỉnh bất kỳ $1 \le u, v \le N$, gọi $d(u, v)$ là số lượng cạnh trên đường đi đơn nối giữa đỉnh $u$ và đỉnh $v$. Đặc biệt, $d(u, u) = 0$ với mọi $1 \le u \le N$.
Một hoán vị $p_1, \dots, p_N$ của $1, \dots, N$ được gọi là tốt nếu tất cả các điều kiện sau được thỏa mãn: $d(p_{i-1}, p_i) \le K$ với mọi $i = 2, \dots, N$. $d(1, p_i) \le d(1, p_j)$ với mọi cặp số nguyên $(i, j)$ thỏa mãn $1 \le i < j \le N$.
Khi đó, $f(K)$ là số lượng các hoán vị tốt.
Yevin cho rằng bài toán này quá dễ, vì vậy anh ấy đưa cho bạn $Q$ số nguyên dương $K_1, \dots, K_Q$. Anh ấy yêu cầu bạn in ra các giá trị $f(K_1), f(K_2), \dots, f(K_Q)$ theo modulo $10^9 + 7$.
Lưu ý rằng "mod" tương ứng với toán tử % trong hầu hết các ngôn ngữ lập trình, biểu thị phần dư sau phép chia. Ví dụ, $5 \pmod 3 = 2$ và $17 \pmod 4 = 1$.
Dữ liệu vào
Mỗi bài kiểm tra có nhiều bộ dữ liệu.
Dòng đầu tiên của dữ liệu chứa một số nguyên $T$ ($1 \le T \le 5 \times 10^5$) — số lượng bộ dữ liệu.
Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên cách nhau bởi dấu cách $N, Q$ ($1 \le Q \le N \le 5 \times 10^5$).
Mỗi dòng trong $N - 1$ dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách $u, v$ — cho biết có một cạnh nối giữa $u$ và $v$ trong cây. Đảm bảo rằng $N - 1$ cạnh này tạo thành một cây.
Dòng tiếp theo chứa $Q$ số nguyên $K_1, \dots, K_Q$ — biểu thị $Q$ truy vấn.
Đảm bảo rằng tổng của $N$ trên tất cả các bộ dữ liệu trong một bài kiểm tra (ký hiệu là $\sum N$) không vượt quá $5 \times 10^5$.
Bảng sau đây cho biết cách phân bổ 25 điểm có sẵn:
| Điểm | Giới hạn $\sum N$ | Giới hạn $Q$ | Giới hạn $K_i$ |
|---|---|---|---|
| 2 điểm | $1 \le \sum N \le 10$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
| 3 điểm | $1 \le \sum N \le 5 \times 10^5$ | $1 \le Q \le \min(2, N)$ | $1 \le K_i \le \min(2, N)$ |
| 5 điểm | $1 \le \sum N \le 3000$ | $1 \le Q \le \min(5, N)$ | $1 \le K_i \le N$ |
| 7 điểm | $1 \le \sum N \le 5 \times 10^5$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
| 8 điểm | $1 \le \sum N \le 5 \times 10^5$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng chứa $Q$ số nguyên cách nhau bởi dấu cách — các giá trị của $f(K_1), f(K_2), \dots, f(K_Q)$ theo modulo $10^9 + 7$.
Ví dụ
Ví dụ 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
Ví dụ 2
0 2 2 0 6 12
Ghi chú
Hai cái cây trong ví dụ đầu vào được hiển thị dưới đây:
Trong bộ dữ liệu đầu tiên, với $K = 2$ hoặc $K = 3$, cả hai hoán vị $[1, 2, 3]$ và $[1, 3, 2]$ đều là hoán vị tốt. $[2, 1, 3]$ không phải là hoán vị tốt với mọi giá trị của $K$ vì $d(1, p_1) = 1 \not\le 0 = d(1, p_2)$ vi phạm điều kiện thứ hai.
Có thể thấy rằng không có hoán vị nào là tốt với $K = 1$.
Trong bộ dữ liệu thứ hai, $[1, 3, 2, 4, 5, 6]$ là một hoán vị tốt với $K = 3$ nhưng không phải là hoán vị tốt với $K = 2$ vì $d(2, 4) = 3 \not\le 2$.