Yevin Kang possède un arbre avec $N$ sommets étiquetés par des entiers de $1$ à $N$. Un arbre est un graphe connexe non orienté qui ne contient aucun cycle.
Soit $K$ un entier positif. Nous définissons $f(K)$ comme suit.
Pour deux sommets quelconques $1 \le u, v \le N$, soit $d(u, v)$ le nombre d'arêtes sur le chemin simple reliant le sommet $u$ au sommet $v$. En particulier, $d(u, u) = 0$ pour tout $1 \le u \le N$.
Une permutation $p_1, \dots, p_N$ de $1, \dots, N$ est dite bonne si toutes les conditions suivantes sont satisfaites : $d(p_{i-1}, p_i) \le K$ pour tout $i = 2, \dots, N$. $d(1, p_i) \le d(1, p_j)$ pour toutes les paires d'entiers $(i, j)$ avec $1 \le i < j \le N$.
Alors, $f(K)$ est le nombre de bonnes permutations.
Yevin pense que ce problème est trop facile, il vous donne donc $Q$ entiers positifs $K_1, \dots, K_Q$. Il vous demande d'afficher les valeurs de $f(K_1), f(K_2), \dots, f(K_Q)$, modulo $10^9 + 7$.
Il peut également être utile de noter que « mod » correspond à l'opérateur % dans la plupart des langages de programmation, indiquant le reste après la division. Par exemple, $5 \pmod 3 = 2$ et $17 \pmod 4 = 1$.
Entrée
Chaque test contient plusieurs cas de test.
La première ligne du test contient un entier $T$ ($1 \le T \le 5 \times 10^5$) — le nombre de cas de test.
La première ligne de chaque cas de test contient deux entiers séparés par un espace $N, Q$ ($1 \le Q \le N \le 5 \times 10^5$).
Chacune des $N - 1$ lignes suivantes contient deux entiers séparés par un espace $u, v$ — indiquant qu'il existe une arête reliant $u$ et $v$ dans l'arbre. Il est garanti que les $N - 1$ arêtes forment un arbre.
La ligne suivante contient $Q$ entiers, $K_1, \dots, K_Q$ — désignant les $Q$ requêtes.
Il est garanti que la somme de $N$ sur tous les cas de test d'un test (notée $\sum N$) ne dépasse pas $5 \times 10^5$.
Le tableau suivant montre comment les 25 points disponibles sont répartis :
| Points attribués | Bornes sur $\sum N$ | Bornes sur $Q$ | Bornes sur $K_i$ |
|---|---|---|---|
| 2 points | $1 \le \sum N \le 10$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
| 3 points | $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 points | $1 \le \sum N \le 3000$ | $1 \le Q \le \min(5, N)$ | $1 \le K_i \le N$ |
| 7 points | $1 \le \sum N \le 5 \times 10^5$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
| 8 points | $1 \le \sum N \le 5 \times 10^5$ | $1 \le Q \le N$ | $1 \le K_i \le N$ |
Sortie
Pour chaque cas de test, affichez une ligne avec $Q$ entiers séparés par des espaces — les valeurs de $f(K_1), f(K_2), \dots, f(K_Q)$, modulo $10^9 + 7$.
Exemples
Entrée 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
Sortie 1
0 2 2 0 6 12
Remarque
Les deux arbres de l'exemple d'entrée sont illustrés ci-dessous.
Dans le premier cas de test, pour $K = 2$ ou $K = 3$, les deux permutations $[1, 2, 3]$ et $[1, 3, 2]$ sont bonnes. $[2, 1, 3]$ n'est pas une bonne permutation pour toutes les valeurs de $K$ car $d(1, p_1) = 1 \not\le 0 = d(1, p_2)$, ce qui viole la seconde condition.
On peut montrer qu'aucune permutation n'est bonne pour $K = 1$.
Dans le second cas de test, $[1, 3, 2, 4, 5, 6]$ est une bonne permutation pour $K = 3$ mais n'est pas une bonne permutation pour $K = 2$ car $d(2, 4) = 3 \not\le 2$.