MREPLBRC - Counting The Way of Bracket Replacement


A regular bracket sequence is a string of characters consisting only of opening and closing brackets, and satisfying the following conditions:

• An empty string is a regular bracket sequence.

• If A is a regular bracket0sequence, then (A), [A] and {A} are also regular bracket sequences.

• If A and B are regular bracket sequences, then AB is also a regular bracket sequence.

For example, the sequences [({})], [](){} i [{}]()[{}] are regular, but the sequences [({{([, []({)} and [{}])([{}] are not.

Ivica has found a string which looks like it could be a regular bracket sequence. Some of the characters have become smudged and illegible, and could have been any character.

Write a program that calculates how many ways the illegible characters in the string can be replaced by brackets so that the result is a regular bracket sequence. This number can be very large, so output only its last 5 digits.

Input

The first line contains an even integer N (2 <= N <= 200), the length of the string.

The second line contains the string. Illegible characters are represented by the '?' character.

Output

Output the number of regular bracket sequences the string could have read.

Sample

input 

6 
()()() 
 
output 
 
1 

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

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

In  the  second example,  the  three matching  regular bracket sequences
are ({([()])}), ()([()]{}) and ([([])]{}).

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