P1466 [USACO2.2] Subset Sums

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.

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

Output the total number of valid partitions.

Constraints For $100\%$ of the testdata, $1 \le n \le 39$. Translation from NOCOW. USACO 2.2. Translated by ChatGPT 5