**Time limit:**1.00 s**Memory limit:**512 MB

*functional graph*is a directed graph where each node has outdegree $1$. For example, here is a functional graph that has $9$ nodes and $2$ components:

**Input**

The only input line has an integer $n$: the number of nodes.

**Output**

Print $n$ lines: for each $k=1 \dots n$ the number of graphs modulo $10^9+7$.

**Constraints**

- $1 \le n \le 5000$

**Example**

Input:

`3`

Output:

`17`

9

1