Equal Sum Partitioning of Consecutive Integers

Given a set of consecutive integers ({1, 2, \dots, n}), determine the number of ways to partition the set into two subsets such that the sum of the numbers in each subset is equal. Note that swapping the two subsets is considered the same partitioning. For example, when (n=3), the set ({1,2,3}) can be partitioned in exactly one way: ({3}) and ({1,2}). Similarly, when (n=7), there are four valid partitions:

• \(\{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\}\)

If the total sum (S = \frac{n(n+1)}{2}) is odd, it is impossible to divide the set into two subsets of equal sum, and the answer should be 0. Otherwise, let (T = \frac{S}{2}). A dynamic programming approach can be used to count the number of ways to form the sum (T) from the given numbers. Because each valid partition is counted twice (once for each order of subsets), the final answer is (\frac{\text{dp}[T]}{2}).

inputFormat

The input consists of a single integer (n) ((1 \leq n \leq 40)) representing the number of consecutive integers.

outputFormat

Output the number of ways to partition the set ({1, 2, \dots, n}) into two subsets with equal sum.

sample

3

1