Two Sets II

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 \le n \le 500$

Example

Input

7

Output

4