Problem F
Zapis
A regular bracketsequence is a string of characters consisting only of opening and closing brackets, and satisfying the following conditions:

An empty string is a regular bracketsequence.

If $A$ is a regular bracketsequence, then ($A$), [$A$] and {$A$} are also regular bracketsequences.

If $A$ and $B$ are regular bracketsequences, then $AB$ is also a regular bracketsequence.
For example, the sequences “[({})]”, “[](){}” and “[{}]()[{}]” are regular, but the sequences “[({{([”, “[]({)}” and “[{}])([{}]” are not.
Ivica has found a string which looks like it could be a regular bracketsequence. 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 bracketsequence. This number can be very large, so output only its last $5$ digits.
Input
The first line contains an even integer $N$ ($2 \le N \le 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 bracketsequences the string could have read.
Sample Input 1  Sample Output 1 

6 ()()() 
1 
Sample Input 2  Sample Output 2 

10 (?([?)]?}? 
3 
Sample Input 3  Sample Output 3 

16 ???[???????]???? 
92202 