Un grafo funcional es un grafo dirigido donde cada nodo tiene grado de salida 1. Por ejemplo, aquí hay un grafo funcional con 9 nodos y 2 componentes:

Dado ~n~, su tarea es calcular, para cada ~k=1 \dots n~, el número de grafos funcionales que tienen ~n~ nodos y ~k~ componentes.

Entrada

La única línea de entrada contiene un entero ~n~: el número de nodos.

Salida

Imprima ~n~ líneas: para cada ~k=1 \dots n~, el número de grafos módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 5000~

Ejemplo de Entrada

3

Ejemplo de Salida

17
9
1