「SCOI2009」游戏
暂无测试数据。
背景
- Idea: SCOI
- Data: SCOI
- Solution: SCOI
- 题面: SCOI + noip(上传至洛谷) + oistream
声明:本题题面来自洛谷 OJ 相应题目,并经本人略改格式。如侵权则删除。
缺失数据:上传至本 OJ 者未找到本题官方数据,现诚邀有数据者贡献。如您可以造具有合适难度的此题数据,也欢迎提供。
描述
windy 学会了一种游戏。
对于 \(1\sim N\) 这 \(N\) 个数字,都有唯一且不同的 \(1\sim N\) 的数字与之对应,最开始 windy 把数字按顺序 \(1,2,3,\cdots ,N\) 写一排在纸上,然后再在这一排下面写上它们对应的数字,然后又在新的一排下面写上它们对应的数字,如此反复,直到序列再次变为 \(1,2,3,\cdots ,N\) 。
如: \(1,2,3,4,5,6\),对应的关系为 \(1\rightarrow 2,2\rightarrow 3,3\rightarrow 1,4\rightarrow 5,5\rightarrow 4,6\rightarrow 6\),windy 的操作如下。
1 2 3 4 5 6
2 3 1 5 4 6
3 1 2 4 5 6
1 2 3 5 4 6
2 3 1 4 5 6
3 1 2 5 4 6
1 2 3 4 5 6
这时,我们就有若干排 \(1\sim N\) 的排列,上例中有 \(7\) 排。
现在 windy 想知道,对于所有可能的对应关系,有多少种可能的排数。
输入格式
一个整数,\(N\) 。
输出格式
一个整数,可能的排数。
样例
输入样例1
3
输出样例1
3
输入样例2
10
输出样例2
16
数据规模与约定
\(30\%\) 的数据满足 \(1 \leq N \leq 10\) 。
\(100\%\) 的数据满足 \(1 \leq N \leq 1000\) 。
时限 \(1s\),空间限制 \(128MB\)。