Two Equal Sets
Given a positive integer
n, count the number of ways to divide the numbers 1, 2, ..., n into two sets of equal sum.
For example, if
n = 7, there are four ways to divide the numbers into two sets with equal sum
{1, 3, 4, 6} and {2, 5, 7}
{1, 2, 5, 6} and {3, 4, 7}
{1, 2, 4, 7} and {3, 5, 6}
{1, 6, 7} and {2, 3, 4, 5}Input
The only input line contains an integer
n (1 ≤ n ≤ 500).Output
Print the answer modulo .
Examples
Input | Output |
7 | 4 |
10 | 0 |
Constraints
Time limit: 20 seconds
Memory limit: 512 MB
Output limit: 1 MB