Bài toán: Phân chia tập hợp thành hai tập có tổng bằng nhau

Đề bài

Cho một tập hợp các số nguyên từ ~1, 2, \ldots, n~. Nhiệm vụ của bạn là đếm số cách chia tập hợp này thành hai tập con sao cho tổng các phần tử của hai tập 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

• Dòng đầu tiên chứa một số nguyên ~n~: kích thước của tập hợp.

Output

• In ra số cách chia tập hợp thành hai tập con có tổng bằng nhau, kết quả được lấy modulo ~10^9 + 7~.

Ràng buộc

• ~1 \leq n \leq 500~

Ví dụ

Input:

7

Output:

4

Giải thích:

Tổng các số từ 1 đến 7 là ~S = \frac{7 \times 8}{2} = 28~. Do ~S~ là số chẵn, có thể chia thành hai tập con có tổng bằng ~S / 2 = 14~. Có 4 cách chia như trong đề bài.

Input:

4

Output:

1

Giải thích:

Tổng các số từ 1 đến 4 là ~S = \frac{4 \times 5}{2} = 10~. Vì ~S~ là số chẵn, có thể chia thành hai tập con có tổng bằng ~S / 2 = 5~. Có duy nhất 1 cách chia: ~\{1, 4\}, \{2, 3\}~.