一个合法的括号序列是指仅由开括号和闭括号组成，并满足以下条件的字符序列：

• 空串是一个合法的括号序列。
• 如果 $A$ 是一个合法的括号序列，那么 $(A)$、$[A]$ 和 $\{A\}$ 也是合法的括号序列。
• 如果 $A$ 和 $B$ 都是合法的括号序列，那么 $AB$ 也是合法的括号序列。

例如，序列 [({})]、[](){} 和 [{}]()[{}] 是合法的，而序列 [({{([、[]({)} 和 [{}])([{}] 则不是。

Ivica 发现了一个看起来可能是合法括号序列的字符串。其中一些字符变得模糊不清、无法辨认，它们原本可以是任何字符。

编写一个程序，计算有多少种方法可以将字符串中无法辨认的字符替换为括号，使得最终得到的字符串是一个合法的括号序列。由于这个数量可能非常大，请仅输出其最后 5 位数字。

输入格式

第一行包含一个偶数 $N$ ($2 \le N \le 200$)，表示字符串的长度。

第二行包含该字符串。无法辨认的字符用 ? 字符表示。

输出格式

输出该字符串可能代表的合法括号序列的总数（仅输出最后 5 位数字）。

样例

输入样例 1

6
()()()

输出样例 1

1

输入样例 2

10
(?([?)]?}?

输出样例 2

3

输入样例 3

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

输出样例 3

92202

说明

在第二个样例中，三种匹配的合法括号序列分别为 ({([()])})、()([()]{}) 和 ([([])]{})。