题意分析
给定一个字符串中的一些字符和一些未知字符，求有多少种可能使其成为“符合规范的超级括号序列”，答案对109+710^9+7109+7取模。
“符合规范的超级括号序列”的定义如下：
1、()、(S) 均是符合规范的超级括号序列，其中 S 表示任意一个仅由不超过 k 个字符 * 组成的非空字符串（以下两条规则中的 S 均为此含义。
2、如果字符串 A 和 B 均为符合规范的超级括号序列，那么字符串 AB、ASB 均为符合规范的超级括号序列，其中 AB 表示把字符串 A 和字符串 B 拼接在一起形成的字符串；
3、如果字符串 A 为符合规范的超级括号序列，那么字符串 (A)、(SA)、(AS) 均为符合规范的超级括号序列。
4、所有符合规范的超级括号序列均可通过上述 3 条规则得到。
关键观察
因为是括号序列，且字符串长度n<=500n<=500n<=500，所以睁眼法可得这是一道区间dp问题。但是题目中给定的星号大大加大了该题难度，直接进行转移方程设计极其困难，而且基本不可能不算重，于是我们想到可以多加一维，空间紧张，再开一维只能是小数字了，这一维要表示什么呢？
通过观察“符合规范的超级括号序列”的定义我们可知，可形成新“符合规范的超级括号序列”的方式较少，我们依次建立动规数组：
dp[l][r][s]dp[l][r][s]dp[l][r][s]表示区间[l,r][l, r][l,r]中sss状态的数量，
状态0表示全为*，
状态1表示定义中的()、(S) ，
状态2表示所有的合法序列（状态1加上枚举分割求出的AB、ASB），
状态3表示AS（通过状态2和状态0数量计算），
状态4表示SA（通过状态2和状态0数量计算），
（状态不一定需要合法，因为这其中的状态都是为状态2的计算服务的。）
根据这些状态，我们一步步推出正确答案dp[1][n][2]dp[1][n][2]dp[1][n][2]，即区间[1,n][1, n][1,n]中的“符合规范的超级括号序列”数量。
（下标做了+1处理方便烧烤，记得取模）
AC代码
时间复杂度
O(n3)O(n^3)O(n3)，但循环中操作仅仅是几行简单的数学运算，常数因子较小，加上acgo神机一秒跑完1e9的神力，该代码实际并不会TLE。
（这已经是不死凹常数因子的最快方法了吧，目前没有任何已知的O(n2)O(n^2)O(n2)或O(n2logn)O(n^2 \log n)O(n2logn)解法）
