Die $N$ Kühe von Farmer Johns Zirkus ($1 \leq N \leq 10^5$) bereiten ihre kommenden Darbietungen vor. Alle Darbietungen finden auf einem Baum statt, dessen Knoten mit $1\ldots N$ beschriftet sind. Der „Anfangszustand“ einer Darbietung wird durch eine Zahl $1 \leq K \leq N$ und eine Zuordnung der Kühe $1\dots K$ zu den Knoten des Baums festgelegt, wobei sich keine zwei Kühe am selben Knoten befinden.

Während einer Darbietung führen die Kühe beliebig viele „Züge“ aus. Bei einem Zug bewegt sich eine einzelne Kuh von ihrem aktuellen Knoten zu einem unbesetzten benachbarten Knoten. Zwei Anfangszustände heißen äquivalent, wenn der eine durch eine Folge von Zügen aus dem anderen erreicht werden kann.

Hilf den Kühen, für jedes $1 \leq K \leq N$ die Anzahl der Äquivalenzklassen von Anfangszuständen zu bestimmen: also die größte Anzahl von Anfangszuständen, die sie auswählen können, sodass keine zwei davon äquivalent sind. Da diese Zahlen sehr groß sein können, gib ihre Reste modulo $10^9 + 7$ aus.

Eingabe

Zeile $1$ enthält $N$.

Jede der Zeilen $2\le i\le N$ enthält zwei ganze Zahlen $a_i$ und $b_i$, die eine Kante zwischen $a_i$ und $b_i$ im Baum angeben.

Ausgabe

Für jedes $1\le i\le N,$ soll die $i$-te Ausgabezeile die Antwort für $K=i$ modulo $10^9+7$ enthalten.

Beispiele

Eingabe 1

5
1 2
2 3
3 4
3 5

Ausgabe 1

1
1
3
24
120

Hinweis

Für $K=1$ und $K=2,$ können je zwei Zustände ineinander überführt werden.

Betrachte nun $K=3$, und sei $c_i$ der Standort der Kuh $i$. Der Zustand $(c_1,c_2,c_3)=(1,2,3)$ ist äquivalent zu den Zuständen $(1,2,5)$ und $(1,3,2).$ Er ist jedoch nicht äquivalent zum Zustand $(2,1,3).$

Eingabe 2

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

Ausgabe 2

1
1
1
6
30
180
5040
40320

Teilaufgaben

• Die Testfälle 3-4 erfüllen $N\le 8.$
• Die Testfälle 5-7 erfüllen $N\le 16.$
• Die Testfälle 8-10 erfüllen $N\le 100$, und der Baum bildet einen „Stern“; höchstens ein Knoten hat einen Grad größer als zwei.
• Die Testfälle 11-15 erfüllen $N\le 100$.
• Für die Testfälle 16-20 gelten keine weiteren Beschränkungen.

Aufgabenautor: Dhruv Rohatgi