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。

一个整数，可能的排数。

30\% 的数据，满足 1 \le n\le 10。

100\% 的数据，满足 1 \le n\le 1000。

四川省选