MREPLBRC - Counting The Way of Bracket Replacement


Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mreplbrc


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à ([([])]{}).

hide comments
evang12: 2022-01-11 03:29:52

If you are getting wrong answer, it may be due to the unclarity of the problem statement.
If the answer for a specific test case is 12300050, you should print 00050, NOT 50. If, however, the answer for a specific test case is 123, you should print 123, NOT 00123.

Last edit: 2022-01-12 05:41:23

Added by:psetter
Date:2009-03-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COCI 1th 07