题目描述

对于从 $1$ 到 $N$（$1 \le N \le 39$）的连续整数集合，存在若干种方式将其划分为两个子集，使得两个子集的元素之和相等。

例如当 $N=3$ 时，集合 $\{1,2,3\}$ 可以按如下方式划分，使得两个子集的和相同：

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

这算作一种划分方案。交换两个子集的顺序视为同一种方案，不重复计数。

当 $N=7$ 时，集合 $\{1,2,3,\ldots,7\}$ 共有 $4$ 种等和划分方案：

• $\{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,2,\ldots,N\}$ 的等和划分方案数。若不存在任何方案则输出 $0$。

你的程序必须通过计算得到答案，不能查表。

输入格式

一行，一个正整数 $N$。

输出格式

一行，一个整数，表示等和划分的方案数。若无法划分则输出 $0$。

样例

7

4

提示

提示

• 总和 $S = \frac{N(N+1)}{2}$，若 $S$ 为奇数则答案为 $0$。
• 可用背包 DP 统计和为 $S/2$ 的子集个数，最终除以 $2$（因为每种划分被计算了两次）。