#1010. BRACKET - Dãy ngoặc

Một dãy ngoặc được hợp lệ là một 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:

1. Là dãy ngoặc rỗng
2. Nếu nó có thể biểu diển dưới dạng , và với là một dãy ngoặc hợp lệ
3. Nếu nó là một chuỗi được tạo ra bằng cách ghép hai dãy ngoặc hợp lệ. Ví dụ và là dãy ngoặc hợp lệ thì cũng được coi là hợp lệ

Long được thầy cho một 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 một 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 ghi ra chữ số cuối của kết quả.

Dữ liệu vào:

• Dòng đầu tiên là số thể hiện độ dài của dãy ngoặc.
• Dòng thứ hai là một xâu ký tự độ dài 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ị dính mực.

Dữ liệu ra:

• In ra 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 dính mực ban đầu.

Ví dụ:

Dữ liệu vào:

8
[{????)]

Dữ liệu ra:

10

Dữ liệu vào:

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

Dữ liệu ra:

15106

Giới hạn:

• số test có và số dấu hỏi bé hơn
• test còn lại có