MREPLBRC - Counting The Way of Bracket Replacement


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
kshubham02: 2017-09-20 07:30:32

Thanks @XilinX
"If the original answer is 15, you must output 15; but if the original answer is 100015, you must output 00015!!!"

s_jindal00: 2017-06-09 13:35:21

O/p must have leading zeroes if actual answer has zero in last 5 digits. Use long long and apply mod with 10^9 at each step!

ameya7: 2016-09-25 10:13:38

Last edit: 2016-09-25 12:36:25
sonu: 2016-08-31 18:42:28

really a nice problem

topke: 2015-11-26 01:12:14

Use long long :D

Ankit: 2015-09-08 09:25:44

really nice que , but printing format is unnecessary

Last edit: 2015-09-08 10:07:15
Pulkit Singhal: 2015-05-18 09:01:32

Problem Statement Not Visible :(

戚圣凯: 2011-12-04 12:33:31

Tell me why?Always runtime error!!!

:D: 2010-07-07 19:46:25

I wouldn't say it was boring. A little diversification is welcome and it's not tiresome if programmed right (at least I feel that way). But the description could underline that you need to output leading zeros. It's very easy to miss that when you're accustomed to mod counting.

Ravi Kiran: 2010-05-31 15:30:41

I agree with Xilinx.
5 Wa's for not having read his post.
That way of outputting is really boring and tiresome :(


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