7557: [CSES Problem Set] Two Sets II
[Creator : ]
Description
Your task is to count the number of ways numbers $1,2,\ldots,n$ can be divided into two sets of equal sum.
For example, if $n=7$, there are four solutions:
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≤n≤500$
Sample 1 Input
7
Sample 1 Output
4