子集求和

题目描述

对于很多由1∼N构成的连续整数集合，我们都可以将其划分为两个子集，并使得两个子集的和相等。

例如，当N=3时，我们可以将集合{1,2,3}划分为子集{1,2}和{3}，这也是唯一的一种满足条件的划分方式。

当N=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，请你计算将1∼N构成的连续整数集合划分为和相等的两个子集，共有多少种划分方式。

将一种划分方式的某个子集内部的元素之间进行顺序调整仍看作是同一种划分方式。

输入描述

共一行包含整数N

数据范围

1≤N≤39

输出描述

输出格式

输出一个整数，表示划分方案数。

如果无法划分，则输出 0。