Problem Description

A regular bracket sequence is defined as follows:

• The empty string is a regular bracket sequence.

• If $A$ is a regular bracket sequence, then (A), [A], and {A} are all regular bracket sequences.

• If $A$ and $B$ are both regular bracket sequences, then the sequence $AB$ is also a regular bracket sequence.

Ivica found a string of length $n$ that seems to be a regular bracket sequence. However, some characters have become unclear and are represented by ?.

He wants you to help compute how many possible replacements make this string a regular bracket sequence.

Input Format

The first line contains an integer $n$, which represents the length of this string.

The second line contains $n$ characters. Each character may be any of ? { } [ ] ( ).

Output Format

Output one integer on a single line, representing the total number of valid possibilities. Because the answer may be very large, you only need to output the last $5$ digits of the answer. (If it has fewer than $5$ digits, do not pad with leading $0$.)

6
()()()

1

10
(?([?)]?}?

3

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

92202

Hint

Explanation of Sample $2$

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

Constraints

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

Note

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

Translated by ChatGPT 5