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:

• ${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}$

The only input line contains an integer $n$ .

• $1 \le n \le 500$

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