# Huseyn and knapsack

# 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.

7

4