Một dãy ngoặc đúng là một xâu thỏa mãn tính chất sau:

• Xâu đó là một xâu rỗng, hoặc
• Xâu đó có dạng $(A)$, với $A$ là một dãy ngoặc đúng, hoặc
• Xâu đó có thể được tách thành hai xâu $AB$, với $A, B$ là các dãy ngoặc đúng khác xâu rỗng.

Với định nghĩa trên, giả sử dãy ngoặc đúng có độ dài $2n$ thì nó sẽ có $n$ ngoặc mở và $n$ ngoặc đóng.

Một cách phân tích một dãy ngoặc đúng $a$ có độ dài $2n$ được định nghĩa là một cách đặt các số $1, 2, ..., 2n$ thành $n$ cặp $(x_1, x_2), (x_3, x_4), ..., (x_{2n-1}, x_{2n})$ sao cho thỏa mãn các điều kiện sau:

• $x_{2i-1} < x_{2i}$ với mọi $1 \le i \le n$.
• $x_{2i-1} < x_{2i+1}$ với mọi $1 \le i < n$.
• $a_{2i-1}$ là ngoặc mở và $a_{2i}$ là ngoặc đóng với mọi $1 \le i \le n$.
• Nếu bỏ đi hai ký tự ở vị trí thuộc cùng một cặp $(x_{2i-1}, x_{2i})$ bất kỳ thì dãy ngoặc thu được vẫn là dãy ngoặc đúng.

Ví dụ: Một cách phân tích dãy ngoặc $(()())$ đó là phân tích thành các cặp $(1, 3), (2, 6), (4, 5)$, vì

• $1 < 2 < 4$, $1 < 3$, $2 < 6$ và $4 < 5$.
• Nếu bỏ đi cặp $(1, 3)$ hoặc cặp $(4, 5)$ thì dãy ngoặc còn lại sẽ là $(())$, vẫn là dãy ngoặc đúng.
• Nếu bỏ đi cặp $(2, 6)$ thì dãy ngoặc còn lại sẽ là $()()$.

Cho một dãy ngoặc đúng $a$. Bạn hãy đếm số cách phân tích dãy ngoặc đúng $a$ theo định nghĩa như trên.

(()())

4

(())

2