测试数据来自 oistream/1104

背景

• 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\)。