Given an integer ~n~. Count the number of ways numbers ~1~, ~2~…, ~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~}

Input

• The only input line contains an integer ~n~ (~1 \leq n \leq 500~)

Output

• Print the answer modulo ~10^9+7~.

Example Input 1

7

Example Output 1

4