MREPLBRC  Counting The Way of Bracket Replacement
English  Vietnamese 
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
~!(*(@*!@^&:
20090417 18:06:21
It is a technique of COI contest, they like it. 

[Trichromatic] XilinX:
20090417 18:06:21
So boring. If the original answer is 15, you must output 15; but if the original answer is 100015, you must output 00015!!! 
Added by:  ~!(*(@*!@^& 
Date:  20090309 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COCI 1th 07 