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: \()(, ((((, ()((, )))), )()(\)

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 \le n \le 30)\)

Output

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

Example

4

2

2

1