Yevin Kang posiada drzewo o $N$ wierzchołkach, ponumerowanych liczbami całkowitymi od $1$ do $N$. Drzewo to nieskierowany graf spójny, który nie zawiera cykli.
Niech $K$ będzie dodatnią liczbą całkowitą. Definiujemy $f(K)$ w następujący sposób.
Dla dowolnych dwóch wierzchołków $1 \le u, v \le N$, niech $d(u, v)$ oznacza liczbę krawędzi na ścieżce prostej łączącej wierzchołek $u$ z wierzchołkiem $v$. W szczególności $d(u, u) = 0$ dla wszystkich $1 \le u \le N$.
Permutacja $p_1, \dots, p_N$ zbioru $1, \dots, N$ jest dobra, jeśli spełnione są wszystkie poniższe warunki: $d(p_{i-1}, p_i) \le K$ dla wszystkich $i = 2, \dots, N$. $d(1, p_i) \le d(1, p_j)$ dla wszystkich par liczb całkowitych $(i, j)$ takich, że $1 \le i < j \le N$.
Wtedy $f(K)$ jest liczbą dobrych permutacji.
Yevin uważa, że to zadanie jest zbyt łatwe, więc daje Ci $Q$ dodatnich liczb całkowitych $K_1, \dots, K_Q$. Prosi Cię o wypisanie wartości $f(K_1), f(K_2), \dots, f(K_Q)$ modulo $10^9 + 7$.
Warto zauważyć, że „mod” odpowiada operatorowi % w większości języków programowania, oznaczając resztę z dzielenia. Na przykład $5 \pmod 3 = 2$ oraz $17 \pmod 4 = 1$.
Wejście
Każdy test zawiera wiele przypadków testowych.
Pierwsza linia testu zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 5 \cdot 10^5$) — liczbę przypadków testowych.
Pierwsza linia każdego przypadku testowego zawiera dwie liczby całkowite $N, Q$ ($1 \le Q \le N \le 5 \cdot 10^5$).
Każda z kolejnych $N - 1$ linii zawiera dwie liczby całkowite $u, v$ — oznaczające, że istnieje krawędź łącząca $u$ i $v$ w drzewie. Gwarantuje się, że $N - 1$ krawędzi tworzy drzewo.
Następna linia zawiera $Q$ liczb całkowitych $K_1, \dots, K_Q$ — oznaczających $Q$ zapytań.
Gwarantuje się, że suma $N$ we wszystkich przypadkach testowych w teście (oznaczana jako $\sum N$) nie przekracza $5 \cdot 10^5$.
Poniższa tabela przedstawia rozkład 25 dostępnych punktów:
| Przyznane punkty | Ograniczenia na $\sum N$ | Ograniczenia na $Q$ | Ograniczenia na $K_i$ |
|---|---|---|---|
| 2 punkty | $1 \le \sum N \le 10$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
| 3 punkty | $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 punktów | $1 \le \sum N \le 3000$ | $1 \le Q \le \min(5, N)$ | $1 \le K_i \le N$ |
| 7 punktów | $1 \le \sum N \le 5 \cdot 10^5$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
| 8 punktów | $1 \le \sum N \le 5 \cdot 10^5$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
Wyjście
Dla każdego przypadku testowego wypisz jedną linię zawierającą $Q$ liczb całkowitych oddzielonych spacjami — wartości $f(K_1), f(K_2), \dots, f(K_Q)$ modulo $10^9 + 7$.
Przykład
Wejście 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
Wyjście 1
0 2 2 0 6 12
Uwagi
Dwa drzewa z przykładowego wejścia przedstawiono poniżej.
W pierwszym przypadku testowym, dla $K = 2$ lub $K = 3$, zarówno $[1, 2, 3]$, jak i $[1, 3, 2]$ są dobrymi permutacjami. $[2, 1, 3]$ nie jest dobrą permutacją dla żadnej wartości $K$, ponieważ $d(1, p_1) = 1 \not\le 0 = d(1, p_2)$ narusza drugi warunek.
Można wykazać, że żadna permutacja nie jest dobra dla $K = 1$.
W drugim przypadku testowym, $[1, 3, 2, 4, 5, 6]$ jest dobrą permutacją dla $K = 3$, ale nie jest dobrą permutacją dla $K = 2$, ponieważ $d(2, 4) = 3 \not\le 2$.