Cho một số tự nhiên ~N \le 19~. Giữa các số từ 1 đến N hãy thêm vào các dấu ~+~ và ~–~ sao cho kết quả thu được bằng ~0~. Hãy viết chương trình tìm tất cả các khả năng có thể.

Input

• Một dòng ghi số ~N~,

Output

• Số lượng kết quả tìm được

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

7

Output

6

Giải thích ví dụ

• ~1 - 2 - 3 - 4 -5 + 6 + 7 = 0~
• ~1 - 2 + 3 + 4 5 + 6 - 7 = 0~
• ~1 - 23 - 35 + 67 = 0~
• ~1 - 23 + 4 + 5 + 6 + 7 = 0~
• ~1 + 2 - 3 - 4 + 5 + 6 - 7 = 0~
• ~1 + 2 - 3 + 4 - 5 - 6 + 7 = 0~