Hãy đếm số cách mà các số ~1,2,…,n~ có thể được chia thành hai tập hợp có tổng bằng nhau.

Ví dụ, với ~n=7~, có 4 cách chia:

• {1,3,4,6} và {2,5,7}
• {1,2,5,6} và {3,4,7}
• {1,2,4,7} và {3,5,6}
• {1,6,7} và {2,3,4,5}

Input

Gồm một dòng duy nhất chứa số nguyên n.

Output

• In đáp án - số cách thoả mãn chia lấy dư cho ~10^9 +7~.

  Constraints

• ~1≤n≤500~

Example

Sample input

7

Sample output

4