Subset Sums
For many sets of consecutive integers from 1 to n, one can partition it into two subsets with identical sums.
For example, if n = 3, one can partition the set {1, 2, 3} only in one way so that the sums of both subsets are identical:
{3} and {1, 2}
This is considered as a single partitioning (reversing the order is considered as the same partitioning and thus does not increase the number of partitions).
If n = 7, there are four ways to partition the set {1, 2, 3, ..., 7} so that each partition has the same sum:
{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 the vale of n, print the number of ways a set of all integers from 1 to n can be partitioned into two subsets with equal sums. Print 0 if there are no such ways.
Input
One integer n (1 ≤ n ≤ 39).
Output
Print the number of same - sum partitions that can be made from the set {1, 2, ..., n}. Print 0 if the partition does not exist.