题目描述

对于从$1$到$N$ ($1 <= N <= 39$) 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。

举个例子，如果$N=3$，对于{$1，2，3$}能划分成两个子集合，他们每个的所有数字和是相等的：

{$3$} 和 {$1,2$}

这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）

如果$N=7$，有四种方法能划分集合{$1，2，3，4，5，6，7$}，每一种分法的子集合各数字和是相等的:

{$1,6,7$} 和 {$2,3,4,5$} {注 $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$，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出$0$。程序不能预存结果直接输出（不能打表）。

输入格式

输入文件只有一行，且只有一个整数$N$

输出格式

输出划分方案总数，如果不存在则输出$0$。

样例数据

input

7

output

4

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$