Dãy ngoặc

Một dãy ngoặc hợp lệ là một xâu chỉ gồm các ký tự ngoặc mở và ngoặc đóng, được định nghĩa như sau:

1. Xâu rỗng là một dãy ngoặc hợp lệ;
2. Nếu $S$ là một dãy ngoặc hợp lệ thì (S), [S] và {S} cũng là các dãy ngoặc hợp lệ;
3. Nếu $A$ và $B$ là hai dãy ngoặc hợp lệ thì xâu ghép $AB$ cũng là một dãy ngoặc hợp lệ.

Sau khi làm xong một số bài toán về dãy ngoặc, An đã viết một dãy ngoặc hợp lệ ra tờ giấy trên bàn học của mình rồi chạy đi chơi với đám bạn. Trong lúc An không có nhà, Bình, cậu em trai hiếu động của An, đã lấy tờ giấy ra nghịch ngợm và làm dính mực vào một vài ký tự trong dãy. Mỗi ký tự bị lem mực được biểu diễn bởi ký tự '?'. Khi trở về nhà, An không trách em khi biết được điều gì đã xảy ra. Bất chợt trong đầu cậu lóe lên một câu hỏi: có bao nhiêu cách để tạo ra một dãy ngoặc hợp lệ bằng cách thay thế những ký tự bị lem mực?

Mỗi ký tự '?' có thể được thay thế bởi một trong sáu ký tự ngoặc '(', ')', '[', ']', '{', '}'. Hai cách thay thế được coi là khác nhau nếu có ít nhất một vị trí '?' được thay bởi hai ký tự khác nhau.

Yêu cầu: Hãy đếm số cách thay thế các ký tự '?' để thu được một dãy ngoặc hợp lệ. Vì kết quả có thể rất lớn, bạn chỉ cần in ra $5$ chữ số cuối của kết quả, tức là phần dư của kết quả khi chia cho ${10}^5$ (in như một số nguyên bình thường, không thêm chữ số $0$ ở đầu).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $N$ là độ dài của dãy ngoặc.
• Dòng thứ hai chứa một xâu độ dài $N$, chỉ gồm các ký tự '(', ')', '[', ']', '{', '}' và '?' ('?' là ký tự bị lem mực).

Dữ liệu đảm bảo xâu được tạo ra từ một dãy ngoặc hợp lệ (mà An đã viết) bằng cách thay một số ký tự bởi '?', nên luôn có ít nhất một cách thay thế.

Dữ liệu ra

In ra một số nguyên là phần dư khi chia số cách thay thế để thu được dãy ngoặc hợp lệ cho ${10}^5$.

Ràng buộc

• $2\le N\le 200$.
• Có $40\%$ số test ứng với $40\%$ số điểm có $N\le 50$ và số ký tự '?' nhỏ hơn $10$.
• $60\%$ số test còn lại ứng với $60\%$ số điểm có $2\le N\le 200$.

Ví dụ