Xiao W encountered a question on the field: How many parentheses in a sequence of length n that meets the specifications, with some positions already determined and some positions yet to be determined.
Xiao W, who has been through many battles, was able to solve this question in a blink of an eye. Not only that, he also felt that it was too childish to come up with such a simple template question for a formal competition. So he strengthened the question and casually threw it to Xiao C.
Specifically, Xiao W defines a "super bracket sequence" as a string composed of characters (,) and *, and for a given constant k, provides the following definition of a "compliant super bracket sequence":
1. () and (S) are both standard super bracket sequences, where S represents any non empty string consisting of no more than k characters * (S in the following two rules has this meaning);
2. If both strings A and B are standard super bracket sequences, then strings AB and ASB are standard super bracket sequences, where AB represents the string formed by concatenating strings A and B together;
3. If string A is a standard sequence of super brackets, then strings (A), (SA), and (AS) are all standard sequences of super brackets.
4. All super bracket sequences that meet the specifications can be obtained through the above three rules.
For example, if k=3, then the string (* * () * (*)) * (* *) is a standard sequence of super parentheses, but the strings * (), (* () *), ((* *)) *), and (* * * * (*)) are not. Specifically, empty strings are not considered as compliant super bracket sequences.
Now provide a super bracket sequence of length n, where some characters at certain positions have been determined, while others at other positions have not yet been determined (represented by?). Xiao W hopes to calculate: How many methods are there to determine all the undetermined characters one by one, so that the resulting string is a standardized sequence of super parentheses?
Poor little C doesn't know how to solve this problem, so I have to ask for your help.
小 w 在赛场上遇到了这样一个题：一个长度为 n 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。
身经百战的小 w 当然一眼就秒了这题，不仅如此，他还觉得一场正式比赛出这么简单的模板题也太小儿科了，于是他把这题进行了加强之后顺手扔给了小 c。
具体而言，小 w 定义“超级括号序列”是由字符 ( 、)、* 组成的字符串，并且对于某个给定的常数k ，给出了“符合规范的超级括号序列”的定义如下：
1、() 、(S) 均是符合规范的超级括号序列，其中 S 表示任意一个仅由不超过 k 个字符 * 组成的非空字符串（以下两条规则中的 S 均为此含义）；
2、如果字符串 A 和 B 均为符合规范的超级括号序列，那么字符串 AB 、ASB 均为符合规范的超级括号序列，其中 AB 表示把字符串 A 和字符串 B 拼接在一起形成的字符串；
3、如果字符串 A 为符合规范的超级括号序列，那么字符串 (A) 、(SA) 、(AS) 均为符合规范的超级括号序列。
4、所有符合规范的超级括号序列均可通过上述 3 条规则得到。
例如，若 k=3 ，则字符串 ((**()*(*))*)(***) 是符合规范的超级括号序列，但字符串 *() 、(*()*) 、((**))*) 、(****(*)) 均不是。特别地，空字符串也不被视为符合规范的超级括号序列。
现在给出一个长度为 n 的超级括号序列，其中有一些位置的字符已经确定，另外一些位置的字符尚未确定（用 ? 表示）。小 w 希望能计算出：有多少种将所有尚未确定的字符一一确定的方法，使得得到的字符串是一个符合规范的超级括号序列？
可怜的小 c 并不会做这道题，于是只好请求你来帮忙。