子任务1：测试点$1\sim 3$

$1\leq k\leq n\leq15$，显然可以使用搜索法。

枚举所有括号序列，判断其是否合法。

  1、连续的*不能超过k个。

  2、括号要匹配。

  3、SAS类型是非法括号序列。

时间复杂度O($N\times 3^N$),预计得分15分。

ps:可直接跳到子任务4。

子任务2：测试点$1\sim 13$

显然是一道区间DP问题。

首先明确，合法的括号序列应该是(),(S),(A),(SA),(AS),AA,ASA。

定义$d(l,r)$表示区间$[l,r]$的子串是合法括号序列的方案数。通过观察可以发现，$d(l,r)$可以由S序列转移得到，因此需要定义额外的状态，定义$s(l,r)$表示区间$[l,r]$能否构成合法的S型。

那么对于(),(S),(A),(SA),(AS)型，显然有：

 $d(l,r)=1$, ()型

 $d(l,r)+=1$, (S)型,$s(l+1,r-1)=1$

 $d(l,r)+=d(l+1,r-1)$, (A)型

 $d(l,r)+=d(l+tk+1,r-1)$, (SA)型,$1\leq tk\leq k,s(l+1,l+tk)=1$

 $d(l,r)+=d(l+1,r-tk-1)$, (AS)型,$1\leq tk\leq k,s(r-tk,r-1)=1$

对于AA、ASA型，需要枚举中间的分隔点$j(l\leq j\leq r)$：

 $d(l,r)+=d(l,j)*d(j+1,r)$, (AA)型

 $d(l,r)+=d(l,j)*d(j+tk+1,r)$, (ASA)型,$1\leq tk\leq k,s(j+1,j+tk)=1$

但是，对于部分括号序列，会出现重复计数，例如()()()会被识别成A|AA或者AA|A，()*()*()会被识别成AS|ASA或ASA|S|A。

为了避免重复计数，要求在合并时只能合并一次，因此定义状态$a(l,r)$表示单独的A类型，也即(),(S),(A),(SA),(AS)型，这些类型的特点是不能拆分。因此，状态转移方程需要做出如下修改：

 $a(l,r)=d(l,r)$,(),(S),(A),(SA),(AS)型

对于AA,ASA型，这是出现重复计数的类型：

 $d(l,r)+=a(l,j)*d(j+1,r)$, (AA)型

 $d(l,r)+=a(l,j)*d(j+tk+1,r)$, (ASA)型,$1\leq tk\leq k,s(j+1,j+tk)=1$

综上，算法的流程如下：

 1、预处理得出所有的$s(l,r)$。

 2、从小到大依次枚举每个区间$[l,r]$，求出相应的$d(l,r)$。

 3、最终的答案即为$d(1,n)$。

注意：在运算过程中需要不断对$10^9+7$取余。

注意：通过观察可以得出，首字符必是(，尾字符必是)，可以进行特殊处理。

时间复杂度O($N^4$)，预计得分65分。

子任务3：测试点$1\sim 15$

对于测试点$14\sim 15$,字符串中仅含？。那么状态$d(l_1,r_1+k)$和$d(l_2,r_2+k)$虽然表示的区间不同，但是结果必然是相同的。

因此，定义状态$f(i)$表示$i$个？构成的合法的序列的方案数。那么，状态转移方程修改为：

$f(1)=0$,一个?

$f(2)=1$,()型

$f(i)+=1$,(S)型

$f(i)+=f(i-2)$,(A)型

$f(i)=f(i-2-tk)$,(AS),(SA)型,$1\leq tk\leq k$

$f(i)=f(j)*f(i-j)$,AA型，$2\leq j\leq i - 2$

$f(i)=f(j)*f(i-j-tk)$,ASA型，$2\leq j\leq i-2,1\leq tk\leq k$

同样，也需要考虑重复计数的问题，定义$g(i)$表示单独的A类型的方案数。

那么状态转移方程需要做出部分修改：

$g(i)=f(i)$,()(S)(A)(SA)(AS)型

$f(i)=g(j)*f(i-j)$,AA型，$2\leq j\leq i - 2$

$f(i)=g(j)*f(i-j-tk)$,ASA型，$2\leq j\leq i-2,1\leq tk\leq k$

时间复杂度：O($N^3$),预计得分75分。

子任务4：测试点$1\sim 20$

显然是一道区间DP问题。

首先明确，合法的括号序列应该是(),(S),(A),(SA),(AS),AA,ASA。

定义$d(l,r)$表示区间$[l,r]$的子串是合法括号序列的方案数。通过观察可以发现，$d(l,r)$可以由非法括号序列转移得到，因此需要定义额外的状态。

  定义$s(l,r)$表示区间$[l,r]$能否构成合法的S型。

  定义$sa(l,r)$表示区间$[l,r]$的子串是SA型的方案数。

  定义$as(l,r)$表示区间$[l,r]$的子串是AS型的方案数。

那么对于(),(S),(A),(SA),(AS)型，显然有：

  $d(l,r)=1$, ()型

  $d(l,r)+=s(l+1,r-1)$, (S)型

  $d(l,r)+=d(l+1,r-1)$, (A)型

  $d(l,r)+=sa(l+1,r-1)$, (SA)型

  $d(l,r)+=as(l+1,r-1)$, (AS)型

对于AA、ASA型，需要枚举中间的分隔点$j(l\leq j\leq r)$：

  $d(l,r)+=d(l,j)*d(j+1,r)$, (AA)型

  $d(l,r)+=d(l,j)*sa(j+1,r)$, (ASA)型

同时需要维护AS,SA型，同样需要枚举中间的分隔点$j(l\leq j\leq r)$：

  $as(l,r)+=d(l,j)*s(j+1,r)$, (AS)型

  $sa(l,r)+=s(l,j)*d(j+1,r)$, (SA)型

但是，对于部分括号序列，会出现重复计数，例如()()()会被识别成A|AA或者AA|A，()*()*()会被识别成AS|ASA或ASA|S|A。

为了避免重复计数，要求在合并时只能合并一次，因此定义状态$a(l,r)$表示单独的A类型，也即(),(S),(A),(SA),(AS)型，这些类型的特点是不能拆分。

因此，状态转移方程需要做出如下修改：

  $a(l,r)=d(l,r)$,(),(S),(A),(SA),(AS)型

对于AA,ASA型，这是出现重复计数的类型：

  $d(l,r)+=a(l,j)*d(j+1,r)$, (AA)型

  $d(l,r)+=a(l,j)*sa(j+1,r)$, (ASA)型

综上，算法的流程如下：

  1、预处理得出所有的$s(l,r)$。

  2、从小到大依次枚举每个区间$[l,r]$，求出相应的$d(l,r),a(l,r),sa(l,r),sa(l,r)$。

  3、最终的答案即为$d(1,n)$。

注意：在运算过程中需要不断对$10^9+7$取余。

注意：通过观察可以得出，首字符必是(，尾字符必是)，可以进行特殊处理。

时间复杂度O($N^3$)，预计得分100分。