Problem Description

A regular bracket sequence is defined as follows:

• 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 both A and B are regular bracket sequences, then the sequence AB is also a regular bracket sequence.

Ivica has found a string of length $n$ that might be a regular bracket sequence. However, some characters in the string are unclear and are represented by ?.

He would like you to help calculate how many possible ways there are to make this疑似串 a regular bracket sequence.

Input Format

The first line of input contains an integer $n$, representing the length of the疑似串.

The second line contains $n$ characters, which can be any of ?, {, }, [, ], (, or ).

Output Format

Output a single integer on one line, representing the total number of possible cases. Since the answer may be very large, output only the last 5 digits of the answer. (If the answer has fewer than 5 digits, do not pad with leading zeros.)

Sample Input and Output

Sample Input #1

6
()()()

Sample Output #1

1

Sample Input #2

10
(?([?)]?}?

Sample Output #2

3

Sample Input #3

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

Sample Output #3

92202

Notes/Hints

Sample #2 Explanation

All possible cases: ({([()])}), ()([()]{}), ([([])]{}).

Data Size and Constraints

For 100% of the data, it is guaranteed that $2 \le n \le 200$.

Notes

The problem is translated from COCI2007-2008 CONTEST #1 T4 ZAPIS

见题面 Input 部分

见题面 Output 部分