愤怒的元首

时间限制:10s      空间限制:128MB

题目描述

       Pty生活在一个奇葩的国家,这个国家有n个城市,编号为1~n
       每个城市到达其他城市的路径都是有向的。
       不存在两个城市可以互相到达。
这个国家的元首现在很愤怒,他大喊一声“气死偶咧!”,然后决定把所有的路径都毁掉再重建。
元首想知道有多少种重建的方案使得这个国家仍然奇葩。


输入格式

第一行一个整数:n


输出格式

 
       输出n个城市的重建方案数mod(10^9+7)的结果
Hint图不连通也是合法方案


样例输入

3

样例输出

25

提示

n <= 3000


题目来源

没有写明来源