Migrated from Lutece 1744 基环树的计数

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$个顶点,$n$条边的连通无向图有多少种，顶点有标号，不允许重边和自环.

Input

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

Output

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

Samples

6

0
0
1
15
222
3660

Resources

Prepared by xiper