给定一个由(),[],{},? 组成的字符串，问有多少种可能的合法括号序列。

其中： (),[],{},的任意一个字符。

输入 输入的第一行给出一个整数n——表示字符串的大小。

输入的第二行给出一行大小为n的字符串。

2≤n≤200

输出 输出整一个整数——表示合法括号序列的种类。由于结果可能很大，因此只需要输出答案的后五位即可。若不足五位，不需要补前导0。

特别提示:

若答案为1000004,则需要输出00004;

若答案为4，则仅需输出4即可。

样例 输入 1复制 10 (?([?)]?}? 输出 1复制 3 输入 2复制 16 ???[???????]???? 输出 2复制 92202 提示 样例一解释；

({([()])})

()([()]{})

([([])]{})