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\}\)

Input

• The only input line contains an integer \(n\).

Output

• Print the answer modulo \(10^9+7\).

Constraints

• \(1 \leq n \leq 500\)

Example

Sample input

7 

Sample output

4