У Йевина Кана есть дерево с $N$ вершинами, пронумерованными целыми числами от 1 до $N$. Дерево — это неориентированный связный граф, не содержащий циклов.
Пусть $K$ — положительное целое число. Определим $f(K)$ следующим образом.
Для любых двух вершин $1 \le u, v \le N$ пусть $d(u, v)$ обозначает количество ребер на простом пути, соединяющем вершину $u$ и вершину $v$. В частности, $d(u, u) = 0$ для всех $1 \le u \le N$.
Перестановка $p_1, \dots, p_N$ чисел $1, \dots, N$ называется хорошей, если выполнены все следующие условия: $d(p_{i-1}, p_i) \le K$ для всех $i = 2, \dots, N$. $d(1, p_i) \le d(1, p_j)$ для всех пар целых чисел $(i, j)$ таких, что $1 \le i < j \le N$.
Тогда $f(K)$ — это количество хороших перестановок.
Йевин считает эту задачу слишком простой, поэтому он дает вам $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 \cdot 10^5$) — количество наборов входных данных.
Первая строка каждого набора данных содержит два целых числа $N, Q$ ($1 \le Q \le N \le 5 \cdot 10^5$), разделенных пробелом.
Каждая из следующих $N - 1$ строк содержит два целых числа $u, v$, разделенных пробелом, указывающих на наличие ребра между $u$ и $v$ в дереве. Гарантируется, что $N - 1$ ребер образуют дерево.
Следующая строка содержит $Q$ целых чисел $K_1, \dots, K_Q$, обозначающих $Q$ запросов.
Гарантируется, что сумма $N$ по всем наборам входных данных в тесте (обозначается $\sum N$) не превышает $5 \cdot 10^5$.
Подзадачи
| Награда | Ограничения на $\sum N$ | Ограничения на $Q$ | Ограничения на $K_i$ |
|---|---|---|---|
| 2 балла | $1 \le \sum N \le 10$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
| 3 балла | $1 \le \sum N \le 5 \cdot 10^5$ | $1 \le Q \le \min(2, N)$ | $1 \le K_i \le \min(2, N)$ |
| 5 баллов | $1 \le \sum N \le 3000$ | $1 \le Q \le \min(5, N)$ | $1 \le K_i \le N$ |
| 7 баллов | $1 \le \sum N \le 5 \cdot 10^5$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
| 8 баллов | $1 \le \sum N \le 5 \cdot 10^5$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
Выходные данные
Для каждого набора входных данных выведите одну строку с $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$.