题目描述

给定一个整数 $n$，请问有多少种不同的无向图，用 $n$ 条边连通 $n$ 个点，且不出现重边与自环。

由于答案可能很大，输出方案数模 $1,000,000,007$ 的余数。

输入格式

• 单个整数 $n$。

输出格式

• 单个整数：表示所求答案。

3

1

4

15

数据范围

• $30\%$ 的分数，$1\leq n\leq 12$
• $60\%$ 的分数，$1\leq n\leq 5000$
• $100\%$ 的分数，$1\leq n\leq 1,000,000$