编程题：动态规划

常规方括号序列是一组字符，仅由开始方括号和结束方括号组成，并满足以下条件：

•空字符串是一个常规的括号序列。
•如果$$A$$是正则括号序列，那么$$(A), [A]$$和$${A}$$也是正则括号序列。
•如果$$A$$和$$B$$是常规括号序列，那么$$AB$$也是常规括号序列。

例如，序列[({})]，[](){}i[{}]()[{}]是规则的，但是序列[({{([,[]({)}和[{}])([{}]不是规则的。
$$Ivica$$发现了一个字符串，看起来可能是一个普通的括号序列。一些字符变得污迹斑斑，难以辨认，可能是任何字符。
编写一个程序，计算用括号替换字符串中难以辨认的字符的方式，从而得到一个规则的括号序列。这个数字可能非常大，所以只输出最后$$5$$位数字。

### 输入格式:
第一行包含偶数整数$$N（2≤N≤200）$$，表示字符串的长度。
第二行包含字符串。难以辨认的字符用“？”表示
### 输出格式:
输出字符串可能的常规括号序列的数量。

### 输入样例1:
in
6
()()()

### 输出样例1:
out
1


### 输入样例2:
in
10
(?([?)]?}?

### 输出样例2:
out
3


### 输入样例3:
in
16
???[???????]????

### 输出样例3:
out
92202


在第二个示例中，三个匹配的正则括号序列可能是({([()])}), ()([()]{}) 和([([])]{})





答案：若无答案欢迎评论