Migrated from Lutece 1741 连通图计数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

求出$n$个顶点的联通无向图的个数，顶点有标号，不允许重边和自环.

Input

输入只有一个整数$n$.($1 \leq n \leq 10^5$)

Output

输出$n$行，分别表示从$1$到$n$时的答案，只需输出其在$\text{mod } 10^9 +7$意义下的值即可

Samples

3

1
1
4

Resources

Prepared by xiper