愤怒的元首

Pty 生活在一个奇葩的国家，这个国家有 $n$ 个城市，编号为 $1\sim n$，并且满足：

• 每个城市到达其他城市的路径都是有向的；
• 不存在两个城市可以互相到达。

这个国家的元首现在很愤怒，他大喊一声「气死偶咧！」，然后决定把所有的路径都毁掉再重建。元首想知道有多少种重建的方案使得这个国家仍然奇葩。

提示：基图不连通也是合法方案。

输入格式

第一行一个整数 $n$。

输出格式

输出 $n$ 个城市的重建方案数对 $10^9+7$ 取模的结果。

样例输入

3

样例输出

25

数据范围

• $n\le 3000$。

来源与许可

本题题面与测试数据整理自 BZOJ 2863。

样例 1

输入

3

输出

25