6863: BZOJ2863：愤怒的元首
Memory Limit：128 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Pty生活在一个奇葩的国家，这个国家有n个城市，编号为1~n。 每个城市到达其他城市的路径都是有向的。 不存在两个城市可以互相到达。 这个国家的元首现在很愤怒，他大喊一声“气死偶咧！”，然后决定把所有的路径都毁掉再重建。 元首想知道有多少种重建的方案使得这个国家仍然奇葩。
输入格式
第一行一个整数：n
输出格式
输出n个城市的重建方案数mod(10^9+7)的结果 Hint：基图不连通也是合法方案
样例输入
3
样例输出
25
提示
n <= 3000
题目来源
没有写明来源