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 5 digits.
The first line contains an even integer , the length of the string.
The second line contains the string. Illegible characters are represented by the
Output the number of regular bracket-sequences the string could have read.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Explanation for Sample Output 2
In the second example, the three matching regular bracket-sequences are , and .
Sample Input 3
Sample Output 3