Description

For the set of consecutive integers from $1\sim n$, determine the number of ways to partition it into two subsets such that the sum of numbers in each subset is equal. For example, if $n = 3$, the set $\{1, 2, 3\}$ can be partitioned into two subsets with equal sums:

$\{3\}$ and $\{1, 2\}$ is the only way (swapping the two subsets is considered the same partition, so it does not increase the total count).

If $n = 7$, there are four ways to partition the set $\{1, 2, 3, 4, 5, 6, 7\}$ into two subsets with equal sums: $\{1, 6, 7\}$ and $\{2, 3, 4, 5\}$. $\{2, 5, 7\}$ and $\{1, 3, 4, 6\}$. $\{3, 4, 7\}$ and $\{1, 2, 5, 6\}$. $\{1, 2, 4, 7\}$ and $\{3, 5, 6\}$.

Given $n$, your program should output the total number of such partitions.

Input Format

The input contains a single line with one integer $n$.

Output Format

Output the total number of valid partitions.

7

4

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 39$.

Translation from NOCOW.

USACO 2.2.

Translated by ChatGPT 5