Có thể định nghĩa khái niệm dãy ngoặc đúng dưới dạng đệ quy như sau:

1. "()" là dãy ngoặc đúng

2. C là dãy ngoặc đúng nếu ~C=(A)~ hay ~C=AB~ với ~A~,~B~ là các dãy ngoặc đúng.

Ví dụ dãy ngoặc đúng: (),(()),()(),(())()

Ví dụ dãy ngoặc sai: )(,((((,()((,)))),)()(

Yêu cầu: Bạn hãy viết chương trình liệt kê tất cả các dãy ngoặc đúng có chiều dài ~n~(~n~ chẵn)

Input

• Là số nguyên ~n~ (~n~ chẵn, ~2 ≤ n ≤ 20~)

Output

• In số ~m~ là số lượng các dãy ngoặc đúng có chiều dài ~n~

Example

Test 1

Input 1

4

Output 1

2

Test 2

Input 2

2

Output 2

1