[SCOI2009] 游戏

题目描述

windy 学会了一种游戏。 对于 $1$ 到 $N$ 这 $N$ 个数字,都有唯一且不同的 $1$ 到 $N$ 的数字与之对应。 最开始 windy 把数字按顺序 $1,2,3,\cdots,N$ 写一排在纸上。 然后再在这一排下面写上它们对应的数字。 然后又在新的一排下面写上它们对应的数字。 如此反复,直到序列再次变为 $1,2,3,\cdots,N$。 如:$1\ 2\ 3\ 4\ 5\ 6$ 对应的关系为:$1\to 2$,$2\to 3$,$3\to 1$,$4\to 5$,$5\to 4$,$6\to 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$ 到 $N$ 的排列,上例中有 $7$ 排。 现在 windy 想知道,对于所有可能的对应关系,有多少种可能的排数。

输入输出格式

输入格式


一个整数,N。

输出格式


一个整数,可能的排数。

输入输出样例

输入样例 #1

3

输出样例 #1

3

输入样例 #2

10

输出样例 #2

16

说明

$30\%$ 的数据,满足 $1 \le n\le 10$。 $100\%$ 的数据,满足 $1 \le n\le 1000$。