Little Cyan Fish et Little Kevinfish jouent à un jeu de tri de séquences. Little Kevinfish possède un arbre $T$ à $n$ sommets, où les sommets sont numérotés par des entiers de $1$ à $n$.
Pour une séquence $A$ composée d'entiers de $1$ à $n$, Little Kevinfish définit une opération d'échange comme suit :
- Choisir des indices $i, j$ tels que les sommets numérotés $A_i$ et $A_j$ soient directement reliés par une arête dans $T$.
- Échanger les positions de $A_i$ et $A_j$.
Little Kevinfish pose la question suivante à Little Cyan Fish :
- Pour une constante $m$ donnée, pour chaque $\ell = 1, 2, \dots, m$, résoudre le problème suivant :
- Considérer une séquence $A$ de longueur $\ell$ composée d'entiers de $1$ à $n$ (il y a $n^\ell$ telles séquences au total), combien de séquences $A$ peuvent être transformées en une séquence monotoniquement non décroissante par un certain nombre d'opérations d'échange ci-dessus ?
Veuillez aider Little Cyan Fish à répondre à la question de Little Kevinfish. Comme la réponse peut être très grande, vous devez seulement afficher la réponse modulo $10^9 + 7$.
Entrée
Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier unique $T$ ($1 \le T$), indiquant le nombre de cas de test.
Pour chaque cas de test, la première ligne de l'entrée contient deux entiers $n$ et $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$).
Les $(n - 1)$ lignes suivantes contiennent chacune deux entiers $u_i$ et $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$), indiquant une arête reliant les sommets $u_i$ et $v_i$. Il est garanti que ces $(n - 1)$ arêtes forment un arbre valide.
Il est garanti que la somme de $n$ sur tous les cas de test n'excède pas $200$, et que la somme de $m$ sur tous les cas de test n'excède pas $10^5$.
Sortie
Pour chaque cas de test, affichez une seule ligne contenant $m$ entiers. Le $i$-ième entier ($1 \le i \le m$) représente la réponse pour $\ell = i$, modulo $10^9 + 7$.
Exemples
Entrée 1
3 3 4 1 2 2 3 4 2 1 2 1 3 3 4 1 10
Sortie 1
3 8 23 70 4 13 1 1 1 1 1 1 1 1 1 1