Một dãy ngoặc được hợp lệ là 1 chuỗi các kí tự chỉ bao gồm những kí tự ngoặc đóng, ngoặc mở và thỏa mãn một trong những điều kiện sau:

• Là dãy ngoặc rỗng
• Nếu nó có thể biểu diển dưới dạng ~(S)~, ~[S]~ và ~{S}~ với ~S~ là một dãy ngoặc hợp lệ
• Nếu nó là một chuỗi được tạo ra bằng cách ghép 2 dãy ngoặc hợp lệ. Ví dụ ~A~ và ~B~ là dãy ngoặc hợp lệ thì ~AB~ cũng được coi là hợp lệ

Long được thầy cho 1 dãy ngoặc hợp lệ để học thuộc, nhưng vì quậy phá nên đã lở làm dính mực 1 vài kí tự trong dãy. Để phạt Long, thầy bắt Long phải đếm số cách có thể để tạo ra dãy ngoặc hợp lệ bằng cách thay thế những kí tự bị dính mực.

Bạn hãy giúp Long trả lời thầy nhé. Vì kết quả có thể rất lớn, nên bạn chỉ cần output ra 5 chữ số cuối của kết quả.

Dữ liệu vào

• Dòng đầu tiên là ~ n ~ thể hiện độ dài của dãy ngoặc.
• Dòng thứ 2 thể hiện dãy ngoặc với các kí tự ngoặc (, ), [, ], {, } và dấu ? thể hiện những kí tự bị lem mực.

Kết quả

• In ra 5 chữ số cuối của số cách có thể để tạo ra những dãy ngoặc hợp lệ từ dãy ngoặc lem mực ban đầu.

Ràng buộc

• 40% số test có ~ n ≤ 50 ~ và số dấu hỏi bé hơn 10
• 60% test còn lại ~ 2 ≤ n ≤ 200 ~

Ví dụ:

Input 1

8
[{????)] 

Output 1

10 

Input 2

24
{[????[??????]})???????? 

Output 2

15106