Le $N$ mucche del circo di Farmer John ($1 \leq N \leq 10^5$) stanno preparando i loro prossimi numeri. Tutti i numeri si svolgono su un albero con vertici etichettati $1\ldots N$. Lo "stato iniziale" di un numero è definito da un numero $1 \leq K \leq N$ e da un'assegnazione delle mucche $1\dots K$ ai vertici dell'albero, in modo che nessuna coppia di mucche occupi lo stesso vertice.

Durante un numero, le mucche effettuano un numero arbitrariamente grande di "mosse". In una mossa, una singola mucca si sposta dal vertice che occupa a un vertice adiacente non occupato. Due stati iniziali si dicono equivalenti se uno può essere raggiunto dall'altro mediante una sequenza di mosse.

Per ogni $1 \leq K \leq N$, aiutate le mucche a determinare il numero di classi di equivalenza degli stati iniziali: cioè, il numero massimo di stati iniziali che possono scegliere in modo che nessuna coppia sia equivalente. Poiché questi numeri possono essere molto grandi, stampate i loro resti modulo $10^9 + 7$.

Input

La riga $1$ contiene $N$.

Le righe $2\le i\le N$ contengono ciascuna due interi $a_i$ e $b_i$ che indicano un arco tra $a_i$ e $b_i$ nell'albero.

Output

Per ogni $1\le i\le N,$ la riga $i$-esima dell'output deve contenere la risposta per $K=i$ modulo $10^9+7$.

Esempi

Input 1

5
1 2
2 3
3 4
3 5

Output 1

1
1
3
24
120

Nota

Per $K=1$ e $K=2,$ due stati qualsiasi possono essere trasformati l'uno nell'altro.

Consideriamo ora $K=3$ e indichiamo con $c_i$ la posizione della mucca $i$. Lo stato $(c_1,c_2,c_3)=(1,2,3)$ è equivalente agli stati $(1,2,5)$ e $(1,3,2).$ Tuttavia, non è equivalente allo stato $(2,1,3).$

Input 2

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

Output 2

1
1
1
6
30
180
5040
40320

Sottocompiti

• I casi di test 3-4 soddisfano $N\le 8.$
• I casi di test 5-7 soddisfano $N\le 16.$
• I casi di test 8-10 soddisfano $N\le 100$ e l'albero forma una "stella": al massimo un vertice ha grado maggiore di due.
• I casi di test 11-15 soddisfano $N\le 100$.
• I casi di test 16-20 non hanno vincoli aggiuntivi.

Autore del problema: Dhruv Rohatgi