题目描述

对于 1～n 的连续整数集合，能划分成两个数字和相等的子集。例如 n=3 时，{1,2,3} 能划分成 2 个子集，{{3} 和 {1,2}，并且这是唯一一种方法。

又例如 n=7，有 4 种方法能划分集合 {1,2,3,4,5,6,7}：

{1,6,7} 和 {2,3,4,5}

{2,5,7} 和 {1,3,4,6}

{3,4,7} 和 {1,2,5,6}

{1,2,4,7} 和 {3,5,6}

根据输入的 n，输出划分子集的方案总数。

输入格式

一行，一个整数 n。

输出格式

一行，一个整数 n，为划分方案数。

输入样例 #1

7

输出样例 #1

4

输入样例 #2

15

输出样例 #2

361

输入样例 #3

24

输出样例 #3

93846

数据范围与约定

对于 100% 的数据，1≤n≤39。