Frankfurt UAS Exercises Week 4 DUPLICATE

#### Start

2018-05-10 18:00 UTC

## Frankfurt UAS Exercises Week 4 DUPLICATE

#### End

2018-05-17 18:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -313 days 11:05:49

168:00:00

0:00:00

# Problem BZapis

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 bracket-sequence, 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 “[({})]”, “[](){}” and “[{}]()[{}]” 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 \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 bracket-sequences 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