Problem F
Zapis
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
is a regular bracket-sequence, then ( ), [ ] and { } are also regular bracket-sequences. -
If
and are regular bracket-sequences, then 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
Input
The first line contains an even integer
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 |