题目描述

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

输入

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

输出

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

输入样例

10

输出样例

16

提示

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

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。