Les $N$ vaches du cirque de Farmer John ($1 \leq N \leq 10^5$) préparent leurs prochains numéros. Tous les numéros se déroulent sur un arbre dont les sommets sont numérotés $1\ldots N$. L'« état initial » d'un numéro est défini par un nombre $1 \leq K \leq N$ et une affectation des vaches $1\dots K$ aux sommets de l'arbre, de sorte que deux vaches ne se trouvent jamais au même sommet.

Au cours d'un numéro, les vaches effectuent un nombre arbitrairement grand de « déplacements ». Lors d'un déplacement, une seule vache passe de son sommet actuel à un sommet adjacent inoccupé. Deux états initiaux sont dits équivalents si l'on peut passer de l'un à l'autre par une suite de déplacements.

Pour chaque $1 \leq K \leq N$, aidez les vaches à déterminer le nombre de classes d'équivalence des états initiaux : c'est-à-dire le nombre maximal d'états initiaux qu'elles peuvent choisir de sorte qu'aucun couple de ces états ne soit équivalent. Ces nombres pouvant être très grands, affichez leurs restes modulo $10^9 + 7$.

Entrée

La ligne $1$ contient $N$.

Chaque ligne $2\le i\le N$ contient deux entiers $a_i$ et $b_i$ indiquant une arête entre $a_i$ et $b_i$ dans l'arbre.

Sortie

Pour chaque $1\le i\le N,$ la $i$-ème ligne de la sortie doit contenir la réponse pour $K=i$ modulo $10^9+7$.

Exemples

Entrée 1

5
1 2
2 3
3 4
3 5

Sortie 1

1
1
3
24
120

Remarque

Pour $K=1$ et $K=2,$ deux états quelconques peuvent être transformés l'un en l'autre.

Considérons maintenant $K=3$, et notons $c_i$ l'emplacement de la vache $i$. L'état $(c_1,c_2,c_3)=(1,2,3)$ est équivalent aux états $(1,2,5)$ et $(1,3,2).$ Cependant, il n'est pas équivalent à l'état $(2,1,3).$

Entrée 2

8
1 3
2 3
3 4
4 5
5 6
6 7
6 8

Sortie 2

1
1
1
6
30
180
5040
40320

Sous-tâches

• Les tests 3–4 vérifient $N\le 8.$
• Les tests 5–7 vérifient $N\le 16.$
• Les tests 8–10 vérifient $N\le 100$ et l'arbre forme une « étoile » ; au plus un sommet a un degré supérieur à deux.
• Les tests 11–15 vérifient $N\le 100$.
• Les tests 16–20 n'ont aucune contrainte supplémentaire.

Auteur du problème : Dhruv Rohatgi