列数字

【题目描述】

windy学会了一种游戏。对于$1$到$N$这$N$个数字，都有唯一且互不相同的$1$到$N$的数字与之对应。最开始windy把数字按顺序$1,2,3,…,N$写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。 如此反复，直到序列再次变为$1,2,3,…,N$。 如：

1 2 3 4 5 6

对应的关系为

1→2  2→3  3→1  4→5  5→4  6→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想知道，对于所有可能的对应关系，有多少种可能的排数。

1 2 3 4 5 6

1→2  2→3  3→1  4→5  5→4  6→6

1 2 3 4 5 6 \n2 3 1 5 4 6 \n3 1 2 4 5 6 \n1 2 3 5 4 6 \n2 3 1 4 5 6 \n3 1 2 5 4 6 \n1 2 3 4 5 6

【输入】

一行包含一个整数$N$。

【输出】

一行包含一个整数，表示可能的排数。

【输入样例】

10

【输出样例】

16

【提示】

【数据规模】 对于30%的数据，$1≤N≤10$。 对于100%的数据，$1≤N≤1000$。