题目描述

定义一个规则括号序列如下：

• 空串是规则括号序列。

• 如果 A 是规则括号序列，那么 (A) [A] {A} 都是规则括号序列。

• 如果 A,B 都是规则括号序列，那个序列 AB 也是规则括号序列。

Ivica 发现了一个长度为 $n$ 的疑似规则括号序列的串。但有一些字符已经模糊不清了，用 ? 表示。

他想请你帮忙计算有多少种可能的情况使得这个疑似的串为规则括号序列。

输入格式

输入第一行为一个整数 $n$，表示这个疑似的串。

第二行为 $n$ 个字符，可能为 ? { } [ ] ( )中的任何字符。

输出格式

输出一行一个整数，表示情况的总数。因为答案可能很大，所以只需输出答案的 后 $5$ 位。（如果不足 $5$ 位不需要补前导 $0$）

6
()()()

1

10
(?([?)]?}?

3

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

92202

提示

样例 $2$ 解释

所有可能的情况： ({([()])}) ()([()]{}) ([([])]{})。

数据规模与约定

对于 $100\%$ 的数据，保证 $2\le n\le 200$。

说明

题目译自 COCI2007-2008 CONTEST #1 T4 ZAPIS