P6333 [COCI 2007/2008 #1] ZAPIS

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.

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 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$.)

#### 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](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #1](https://hsin.hr/coci/archive/2007_2008/contest1_tasks.pdf) *T4 ZAPIS*** Translated by ChatGPT 5