Yevin Kang tiene un árbol con $N$ vértices etiquetados con números enteros del 1 al $N$. Un árbol es un grafo conexo no dirigido que no contiene ciclos.
Sea $K$ un entero positivo. Definimos $f(K)$ de la siguiente manera.
Para cualesquiera dos vértices $1 \le u, v \le N$, sea $d(u, v)$ el número de aristas en el camino simple que conecta el vértice $u$ y el vértice $v$. En particular, $d(u, u) = 0$ para todo $1 \le u \le N$.
Una permutación $p_1, \dots, p_N$ de $1, \dots, N$ es buena si se cumplen todas las siguientes condiciones:
- $d(p_{i-1}, p_i) \le K$ para todo $i = 2, \dots, N$.
- $d(1, p_i) \le d(1, p_j)$ para todos los pares de enteros $(i, j)$ con $1 \le i < j \le N$.
Entonces, $f(K)$ es el número de permutaciones buenas.
Yevin piensa que este problema es demasiado fácil, por lo que te da $Q$ enteros positivos $K_1, \dots, K_Q$. Te pide que imprimas los valores de $f(K_1), f(K_2), \dots, f(K_Q)$, módulo $10^9 + 7$.
Puede ser útil notar que "mod" corresponde al operador % en la mayoría de los lenguajes de programación, indicando el resto después de la división. Por ejemplo, $5 \pmod 3 = 2$ y $17 \pmod 4 = 1$.
Entrada
Cada prueba tiene múltiples casos de prueba.
La primera línea de la prueba contiene un entero $T$ ($1 \le T \le 5 \times 10^5$) — el número de casos de prueba.
La primera línea de cada caso de prueba contiene dos enteros separados por espacios $N, Q$ ($1 \le Q \le N \le 5 \times 10^5$).
Cada una de las siguientes $N - 1$ líneas contiene dos enteros separados por espacios $u, v$ — indicando que hay una arista que conecta $u$ y $v$ en el árbol. Se garantiza que las $N - 1$ aristas forman un árbol.
La siguiente línea contiene $Q$ enteros, $K_1, \dots, K_Q$ — que denotan las $Q$ consultas.
Se garantiza que la suma de $N$ sobre todos los casos de prueba en una prueba (denotada por $\sum N$) no excede $5 \times 10^5$.
La siguiente tabla muestra cómo se distribuyen las 25 marcas disponibles:
| Marcas otorgadas | Límites en $\sum N$ | Límites en $Q$ | Límites en $K_i$ |
|---|---|---|---|
| 2 marcas | $1 \le \sum N \le 10$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
| 3 marcas | $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 marcas | $1 \le \sum N \le 3000$ | $1 \le Q \le \min(5, N)$ | $1 \le K_i \le N$ |
| 7 marcas | $1 \le \sum N \le 5 \times 10^5$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
| 8 marcas | $1 \le \sum N \le 5 \times 10^5$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
Salida
Para cada caso de prueba, imprime una línea con $Q$ enteros separados por espacios — los valores de $f(K_1), f(K_2), \dots, f(K_Q)$, módulo $10^9 + 7$.
Ejemplos
Entrada 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
Salida 1
0 2 2 0 6 12
Nota
Los dos árboles en la entrada de ejemplo se muestran a continuación.
En el primer caso de prueba, para $K = 2$ o $K = 3$, tanto $[1, 2, 3]$ como $[1, 3, 2]$ son permutaciones buenas. $[2, 1, 3]$ no es una permutación buena para todos los valores de $K$ porque $d(1, p_1) = 1 \not\le 0 = d(1, p_2)$ viola la segunda condición.
Se puede demostrar que ninguna permutación es buena para $K = 1$.
En el segundo caso de prueba, $[1, 3, 2, 4, 5, 6]$ es una permutación buena para $K = 3$ pero no es una permutación buena para $K = 2$ porque $d(2, 4) = 3 \not\le 2$.