Baltic Olympiad in Informatics: 2012 Day 1, Problem 1
Let's define a correct string of brackets as follows:
()
and[]
are correct strings of brackets;- if
A
is a correct string of brackets, then(A)
and[A]
are also correct strings of brackets; - if
A
andB
are both correct strings of brackets, then the concatenationAB
is also a correct string of brackets;
In a correct string of brackets which contains at least one pair of square brackets:
[
and corresponding ]
, each square bracket (both opening and closing) was replaced
by the opening round bracket, therefore obtaining a broken string of brackets.
For example, ((
and ((((()))
both are broken strings of brackets. First string
is obtained from the correct strings of brackets []
. Second string may be obtained
only from the following four correct strings of brackets: []((()))
,([](()))
,(([]()))
or ((([])))
.
Your task is for a given broken string of brackets calculate the number of possible correct strings of brackets from which the given broken string may have been obtained.
Constraints
is even.
Subtask 1 [20%]
Subtask 2 [45%]
Subtask 3 [35%]
No additional constraints.
Input Specification
The first line of input contains an even integer - the length of the given broken string of brackets. The second line contains characters (
and )
- the given broken string of brackets.
Output Specification
Output a single integer - the required number of correct strings of brackets. Because the number of correct strings of brackets may be quite large, you should output the answer modulo .
Sample Input 1
4
((()
Sample Output 1
2
Explanation for Sample 1
The correct string of brackets are:
[]()
([])
Sample Input 2
8
((((((((
Sample Output 2
14
Explanation for Sample 2
The correct string of brackets are:
[][][][]
[[]][][]
[[]][[]]
[][][[]]
[[[]]][]
[[][]][]
[][[][]]
[][[[]]]
[[[[]]]]
[[][[]]]
[[[]][]]
[[][][]]
[[[][]]]
[][[]][]
Comments