MREPLBRC - Counting The Way of Bracket Replacement

Giới hạn

• Thời gian: 0.168s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Dãy ngoặc hợp lệ gồm:

• Xâu rỗng.
• A hợp lệ thì (A), [A] và {A} cũng thế.
• A, B hợp lệ thì AB cũng thế.

Ví dụ : [({})], [](){} và [{}]()[{}] là hợp lệ, [({{([, []({)} và [{}])([{}] không hợp lệ.

Cho một xâu chỉ gồm ( ) { } [ ] và ?. Dấu ? có thể thay thế bằng ngoặc bất kỳ. Tính số cách thay thế mà thu được 1 dẫy ngoặc hợp lệ. Chỉ hiện 5 chữ số cuối cùng.

Input

Dòng đầu là N, độ dài xâu (2 <= N <= 200), Dòng thứ hai là xâu mô tả.

Output

5 chữ số cuối cùng của dẫy ngoặc hợp lệ thu được. (<= 5 chữ số thì in ra hết cả kết quả).

Sample

input 

6 
()()() 
 
output 
 
1 

input 
 
10 
(?([?)]?}? 
 
output 
 
3

input 
 
16 
???[???????]???? 
 
output 
 
92202

Ví dụ thứ hai, 3 dãy ngoặc hợp lệ là  ({([()])}), ()([()]{}) và ([([])]{}).

---

• Người up: vdmedragon
• Nguồn bài: COCI 1th 07