Migrated from Lutece 1747 带标号的边双连通图计数

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

输出一行表示答案，只需输出其在$\text{mod } 10^9 +7$意义下的值即可

Samples

1

1

Resources

Prepared by xiper