As $N$ vacas do circo de Farmer John ($1 \leq N \leq 10^5$) estão preparando seus próximos números. Todos os números acontecem em uma árvore cujos vértices são numerados de $1\ldots N$. O «estado inicial» de um número é definido por um número $1 \leq K \leq N$ e uma atribuição das vacas $1\dots K$ aos vértices da árvore, de modo que duas vacas nunca estejam no mesmo vértice.

Durante um número, as vacas realizam uma quantidade arbitrariamente grande de «movimentos». Em um movimento, uma única vaca sai de seu vértice atual e vai para um vértice adjacente desocupado. Dois estados iniciais são considerados equivalentes se um puder ser alcançado a partir do outro por alguma sequência de movimentos.

Para cada $1 \leq K \leq N$, ajude as vacas a determinar o número de classes de equivalência de estados iniciais: isto é, o número máximo de estados iniciais que podem escolher de modo que nenhum par seja equivalente. Como esses números podem ser muito grandes, imprima seus restos módulo $10^9 + 7$.

Entrada

A linha $1$ contém $N$.

Cada linha $2\le i\le N$ contém dois inteiros $a_i$ e $b_i$ que representam uma aresta entre $a_i$ e $b_i$ na árvore.

Saída

Para cada $1\le i\le N,$ a $i$-ésima linha da saída deve conter a resposta para $K=i$ módulo $10^9+7$.

Exemplos

Entrada 1

5
1 2
2 3
3 4
3 5

Saída 1

1
1
3
24
120

Observação

Para $K=1$ e $K=2,$ quaisquer dois estados podem ser transformados um no outro.

Agora considere $K=3$ e seja $c_i$ a posição da vaca $i$. O estado $(c_1,c_2,c_3)=(1,2,3)$ é equivalente aos estados $(1,2,5)$ e $(1,3,2).$ No entanto, ele não é equivalente ao estado $(2,1,3).$

Entrada 2

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

Saída 2

1
1
1
6
30
180
5040
40320

Subtarefas

• Os casos de teste 3–4 satisfazem $N\le 8.$
• Os casos de teste 5–7 satisfazem $N\le 16.$
• Os casos de teste 8–10 satisfazem $N\le 100$ e a árvore tem a forma de uma «estrela»; no máximo um vértice tem grau maior que dois.
• Os casos de teste 11–15 satisfazem $N\le 100$.
• Os casos de teste 16–20 não têm restrições adicionais.

Autor do problema: Dhruv Rohatgi