Pty 生活在一个奇葩的国家，这个国家有 个城市，编号为 。
每个城市到达其他城市的路径都是有向的。
不存在两个城市可以互相到达。
这个国家的元首现在很愤怒，他大喊一声"气死偶咧！"，然后决定把所有的路径都毁掉再重建。
元首想知道有多少种重建的方案使得这个国家仍然奇葩。
第一行一个整数 。
输出 个城市的重建方案数 的结果
3
25
Hint：基图不连通也是合法方案
