For many sets of consecutive integers from through (), one can partition the set into two sets whose sums are identical.
For example, if , one can partition the set in one way so that the sums of both subsets are identical:
and
This counts as a single partitioning. Reversing the order counts as the same partitioning and thus does not increase the count of partitions.
If , there are four ways to partition the set so that each partition has the same sum:
and
and
and
and
Given , print the number of ways a set containing the integers from through can be partitioned into two sets whose sums are identical. Print if there are no such ways.
Your program must calculate the answer, not look it up from a table.
输入格式
A single line with a single integer .
输出格式
A single line with a single integer that tells how many same-sum partitions can be made from the set . The output should be if there are no ways to make a same-sum partition.
