$N$ krów z cyrku Farmer John ($1 \leq N \leq 10^5$) przygotowuje swoje nadchodzące występy. Wszystkie występy odbywają się na drzewie o wierzchołkach oznaczonych $1\ldots N$. „Stan początkowy” występu jest określony przez liczbę $1 \leq K \leq N$ oraz rozmieszczenie krów $1\dots K$ w wierzchołkach drzewa tak, aby żadne dwie krowy nie znajdowały się w tym samym wierzchołku.

Podczas występu krowy wykonują dowolnie dużą liczbę „ruchów”. W jednym ruchu pojedyncza krowa przechodzi ze swojego obecnego wierzchołka do niezajętego sąsiedniego wierzchołka. Dwa stany początkowe nazywamy równoważnymi, jeśli z jednego można dojść do drugiego za pomocą pewnego ciągu ruchów.

Dla każdego $1 \leq K \leq N$ pomóż krowom wyznaczyć liczbę klas równoważności stanów początkowych, czyli maksymalną liczbę stanów początkowych, które mogą wybrać tak, aby żadne dwa nie były równoważne. Ponieważ liczby te mogą być bardzo duże, wypisz ich reszty modulo $10^9 + 7$.

Wejście

Wiersz $1$ zawiera $N$.

Każdy z wierszy $2\le i\le N$ zawiera dwie liczby całkowite $a_i$ oraz $b_i$, oznaczające krawędź między $a_i$ i $b_i$ w drzewie.

Wyjście

Dla każdego $1\le i\le N,$ w $i$-tym wierszu wyjścia należy wypisać odpowiedź dla $K=i$ modulo $10^9+7$.

Przykład

Wejście 1

5
1 2
2 3
3 4
3 5

Wyjście 1

1
1
3
24
120

Uwagi

Dla $K=1$ i $K=2,$ dowolne dwa stany można przekształcić jeden w drugi.

Rozważmy teraz $K=3$ i niech $c_i$ oznacza położenie krowy $i$. Stan $(c_1,c_2,c_3)=(1,2,3)$ jest równoważny stanom $(1,2,5)$ i $(1,3,2).$ Nie jest jednak równoważny stanowi $(2,1,3).$

Wejście 2

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

Wyjście 2

1
1
1
6
30
180
5040
40320

Podzadania

• Przypadki testowe 3-4 spełniają $N\le 8.$
• Przypadki testowe 5-7 spełniają $N\le 16.$
• Przypadki testowe 8-10 spełniają $N\le 100$, a drzewo ma postać „gwiazdy”; co najwyżej jeden wierzchołek ma stopień większy od dwóch.
• Przypadki testowe 11-15 spełniają $N\le 100$.
• Przypadki testowe 16-20 nie mają dodatkowych ograniczeń.

Autor zadania: Dhruv Rohatgi