Las $N$ vacas del circo de Farmer John ($1 \leq N \leq 10^5$) están preparando sus próximas actuaciones. Todas las actuaciones tienen lugar en un árbol cuyos vértices están etiquetados con $1\ldots N$. El «estado inicial» de una actuación se define mediante un número $1 \leq K \leq N$ y una asignación de las vacas $1\dots K$ a los vértices del árbol, de modo que no haya dos vacas en el mismo vértice.

Durante una actuación, las vacas realizan un número arbitrariamente grande de «movimientos». En un movimiento, una sola vaca se desplaza desde su vértice actual a un vértice adyacente desocupado. Se dice que dos estados iniciales son equivalentes si se puede llegar de uno al otro mediante alguna secuencia de movimientos.

Para cada $1 \leq K \leq N$, ayuda a las vacas a determinar el número de clases de equivalencia de estados iniciales: es decir, el máximo número de estados iniciales que pueden elegir de manera que ningún par sea equivalente. Como estos números pueden ser muy grandes, imprime sus restos módulo $10^9 + 7$.

Entrada

La línea $1$ contiene $N$.

Cada línea $2\le i\le N$ contiene dos enteros $a_i$ y $b_i$ que indican una arista entre $a_i$ y $b_i$ en el árbol.

Salida

Para cada $1\le i\le N,$ la línea $i$ de la salida debe contener la respuesta para $K=i$ módulo $10^9+7$.

Ejemplos

Entrada 1

5
1 2
2 3
3 4
3 5

Salida 1

1
1
3
24
120

Nota

Para $K=1$ y $K=2,$ cualesquiera dos estados pueden transformarse el uno en el otro.

Considera ahora $K=3$ y sea $c_i$ la ubicación de la vaca $i$. El estado $(c_1,c_2,c_3)=(1,2,3)$ es equivalente a los estados $(1,2,5)$ y $(1,3,2).$ Sin embargo, no es equivalente al estado $(2,1,3).$

Entrada 2

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

Salida 2

1
1
1
6
30
180
5040
40320

Subtareas

• Los casos de prueba 3–4 satisfacen $N\le 8.$
• Los casos de prueba 5–7 satisfacen $N\le 16.$
• Los casos de prueba 8–10 satisfacen $N\le 100$ y el árbol tiene forma de «estrella»; como máximo un vértice tiene grado mayor que dos.
• Los casos de prueba 11–15 satisfacen $N\le 100$.
• Los casos de prueba 16–20 no tienen restricciones adicionales.

Autor del problema: Dhruv Rohatgi