e-olymp
Competitions

Knapsack - Рюкзак

Subset Sums

For many sets of consecutive integers from 1 to n (1n39), 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 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 (1n39).

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.

Time limit 1 second
Memory limit 64 MiB
Input example
7
Output example
4