[SCOI2009]游戏

Windy 学会了一种游戏。对于 $1$ 到 $N$ 这 $N$ 个数字，每个数字都唯一对应另一个 $1$ 到 $N$ 之间的数字，且不同数字对应的数字互不相同。

最开始，Windy 将数字 $1,2,3,\ldots,N$ 依次写成一排。接着，在下一排写出每个数字所对应的数字，再根据新一排中的数字继续写出下一排。如此反复，直到序列再次变为 $1,2,3,\ldots,N$ 。

例如，对于 $N=6$ ，对应关系为：

1\to 2,\quad 2\to 3,\quad 3\to 1,\quad 4\to 5,\quad 5\to 4,\quad 6\to 6。

Windy 的操作过程如下：

\begin{aligned} &1\quad 2\quad 3\quad 4\quad 5\quad 6\\ &2\quad 3\quad 1\quad 5\quad 4\quad 6\\ &3\quad 1\quad 2\quad 4\quad 5\quad 6\\ &1\quad 2\quad 3\quad 5\quad 4\quad 6\\ &2\quad 3\quad 1\quad 4\quad 5\quad 6\\ &3\quad 1\quad 2\quad 5\quad 4\quad 6\\ &1\quad 2\quad 3\quad 4\quad 5\quad 6 \end{aligned}

此时一共写出了 $7$ 排。

对于所有可能的对应关系，Windy 想知道排数共有多少种可能的取值。

输入格式

输入包含一个整数 $N$ 。

输出一个整数，表示可能的排数的种数。

样例 $1$ ：

样例 $2$ ：

样例 $1$ ：

样例 $2$ ：

本题为 SCOI 2009 试题「游戏」，题面与测试数据整理自 BZOJ。