Dãy ngoặc đúng

Chào mừng các bạn đến với UIT Algo Bootcamp 2025 - Kỳ huấn luyện mùa thu!

Trong một buổi học chuyên đề về cấu trúc dữ liệu, các bạn học viên được làm quen với một bài toán kinh điển: dãy ngoặc đúng. Một dãy ngoặc đúng là một xâu ký tự chỉ chứa các loại ngoặc \((, ), \{, \}, [, ]\) tuân theo các quy tắc sau:

• Xâu rỗng là một dãy ngoặc đúng.
• Nếu \(S\) là một dãy ngoặc đúng, thì các xâu \((S)\), \([S]\) và \(\{S\}\) cũng là các dãy ngoặc đúng.
• Nếu \(S\) và \(T\) là hai dãy ngoặc đúng, thì xâu \(ST\) cũng là một dãy ngoặc đúng.

Để tăng thêm tính thử thách, giảng viên đưa ra một bài tập biến thể. Các bạn sẽ được cho một dãy ngoặc đã bị khuyết một số vị trí. Các vị trí khuyết này được ký hiệu bởi ký tự '?'. Nhiệm vụ của bạn là tìm số cách để thay thế các ký tự '?' bằng các loại ngoặc sao cho xâu kết quả là một dãy ngoặc đúng.

Bài toán này không chỉ là một thử thách về thuật toán, mà còn là cơ hội để các trại sinh rèn luyện tư duy, chiến lược giải quyết vấn đề dưới áp lực thời gian, chuẩn bị cho không khí sôi động của các kỳ thi lập trình quốc tế như ICPC.

Hãy chứng tỏ bản thân tại UIT Algo Bootcamp 2025 và chinh phục bài toán này nhé!

Yêu cầu: Cho một xâu ký tự chỉ chứa các loại ngoặc \((, [, \{, ), ], \}\) và ký tự '?'. Hãy đếm số cách thay thế các ký tự '?' để tạo thành một dãy ngoặc đúng.

Input

• Dòng đầu tiên chứa một số nguyên chẵn \(n\) (\(2 \le n \le 200\)), là độ dài của xâu.
• Dòng thứ hai chứa một xâu ký tự độ dài \(n\), chỉ gồm các ký tự \((, [, \{, ), ], \}\) và '?'.

Output

• In ra một dòng duy nhất là \(5\) chữ số cuối cùng của số cách hoàn thành dãy ngoặc đúng.

Example

2
??

3

4
{??}

4

6
(){}[]

1

6
()))))

0

Scoring

• Subtask 1 (\(20\%\) số điểm) : không xuất hiện ký tự '?' trong xâu.
• Subtask 2 (\(30\%\) số điểm) : \(n \leq 8\).
• Subtask 3 (\(30\%\) số điểm) : \(n \leq 50\).
• Subtask 4 (\(20\%\) số điểm) : không có ràng buộc gì thêm.