Hai tập hợp II

Trong một buổi làm việc, lãnh đạo cấp trên đã đưa cho FullHouse Dev một bài toán thú vị về tập hợp. V

Bài toán

FullHouse Dev cần đếm số cách để chia các số từ \(1\) đến \(n\) thành hai tập hợp có tổng bằng nhau. Ví dụ với \(n = 7\), có bốn cách chia như sau:

• {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 FORMAT:

• Dòng duy nhất chứa một số nguyên \(n\).

OUTPUT FORMAT:

• In ra số cách chia có thể theo modulo \(10^9+7\).

Ràng buộc:

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

Ví dụ

INPUT

7

OUTPUT

4

Giải thích

Với \(n = 7\), có đúng 4 cách chia các số từ 1 đến 7 thành hai tập hợp có tổng bằng nhau như đã liệt kê trong phần mô tả bài toán.