在图论中，图 $G = (V, E)$ 的匹配（matching）或独立边集（independent edge set）是指一个边集 $M \subseteq E$，使得 $M$ 中的任意两条边都不共享同一个顶点。

最近你在新闻中看到，2012 年的“瑞典国家银行纪念阿尔弗雷德·诺贝尔经济学奖”（通称诺贝尔经济学奖）授予了 Alvin E. Roth 和 Lloyd S. Shapley，以表彰他们在二分图中寻找满足特定条件的匹配算法等方面的贡献。既然你也听说过循环图（cycle graph）中的匹配在化学领域有应用，你的思绪便集中在一个美好的未来计划上，届时你的圣诞购物将比以往任何时候都更加奢华！

循环图 $C_n$（$n \ge 3$）是一个简单的无向图，其顶点集为 $\{1, \dots, n\}$，边集为 $E(C_n) = \{\{a, b\} \mid |a - b| \equiv 1 \pmod n\}$。它是 2-正则图，包含 $n$ 条边。图 $C_3, C_4, C_5$ 和 $C_6$ 如图 1 所示。

图 1：图 $C_3, C_4, C_5$ 和 $C_6$。

你迈向诺贝尔奖名声的第一步是能够计算循环图 $C_n$ 中的匹配数量。图 2 展示了图 $C_4$ 的七种匹配。

图 2：$C_4$ 的匹配。属于相应匹配的边用绿色标出，而未被匹配的边用虚线表示。$M_1 = \emptyset, M_2 = \{\{2, 1\}\}, M_3 = \{\{3, 2\}\}, M_4 = \{\{4, 3\}\}, M_5 = \{\{1, 4\}\}, M_6 = \{\{2, 1\}, \{4, 3\}\}$ 以及 $M_7 = \{\{3, 2\}, \{1, 4\}\}$。

输入格式

对于每个测试用例，输入包含一行，为一个正整数：$n$，其中 $3 \le n \le 10000$。

输出格式

对于每个测试用例，输出一行，包含 $C_n$ 中的匹配数量。

样例

输入 1

3
4
100

输出 1

4
7
792070839848372253127