CSES Problem Set

# Two Sets II

CSES - Two Sets IICSES - Two Sets II

 Time limit: 1.00 s Memory limit: 512 MB

Your task is to count the number of ways numbers $1,2,\ldots,n$ can be divided into two sets so that the sums of the sets are equal.

For example, if $n=7$, there are four solutions:
• $\{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$.

Output

Print the answer modulo $10^9+7$.

Constraints
• $1 \le n \le 500$
Example

Input:
7

Output:
4