P40025

connected graph

难度 6 级 组合 动态规划 组合数学
讨论 统计 6通过 10提交 60%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

无向图是由顶点集合 V 和边集合 E \subseteq V \times V 组成的结构。一个无向图是连通的,当且仅当对于任意一对顶点 (u, v),u 都可以从 v到达。

你需要编写一个程序,计算具有 n 个顶点的不同连通无向图的数量。

例如,当 n = 3 时,共有 4 个不同的连通无向图。

输入

输入一个正整数 n。

输出

输出答案对1e9+7取模的值。

样例

样例 1
输入
3
输出
4

提示

1 \leq n \leq 1000

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交