Nhiệm vụ của bạn là đếm số cách chia các số ~1,2,\ldots,n~ thành hai tập có tổng bằng nhau.

Ví dụ, nếu ~n=7~, có bốn nghiệm:

• ~\{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\}~

Dữ liệu vào

Dòng duy nhất chứa một số nguyên ~n~.

Kết quả

In ra đáp án lấy modulo ~10^9+7~.

Giới hạn

• ~1 \le n \le 500~

Ví dụ

Input:

7

Output:

4