Hãy đếm số cách mà các số \(1, 2,\ldots,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 \leq n \leq 500\)

Example

Sample input

7

Sample output

4