Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EI2122Q3ADAF2 - SUBSET 3

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 ≤ n ≤ 500)

Output

Print the answer modulo 109+7.

Sample

 

Input

Output

7

4


Added by:Ha Minh Ngoc
Date:2022-06-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.