#83. 括号序列

括号序列

题目描述

ww 在赛场上遇到了这样一个题:一个长度为 nn 且符合规范的括号序列,其有些位置已经确定了,有些位置尚未确定,求这样的括号序列一共有多少个。 身经百战的小 ww 当然一眼就秒了这题,不仅如此,他还觉得一场正式比赛出这么简单的模板题也太小儿科了,于是他把这题进行了加强之后顺手扔给了小 cc。 具体而言,小 ww 定义“超级括号序列”是由字符 (())* 组成的字符串,并且对于某个给定的常数k ,给出了“符合规范的超级括号序列”的定义如下:

  1. ()()(S)(S) 均是符合规范的超级括号序列,其中 SS 表示任意一个仅由不超过 kk 个字符 * 组成的非空字符串(以下两条规则中的 SS 均为此含义);
  2. 如果字符串 AABB 均为符合规范的超级括号序列,那么字符串 ABABASBASB 均为符合规范的超级括号序列,其中 ABAB 表示把字符串 AA 和字符串 BB 拼接在一起形成的字符串;
  3. 如果字符串 AA 为符合规范的超级括号序列,那么字符串 (A)(A)(SA)(SA)(AS)(AS) 均为符合规范的超级括号序列。
  4. 所有符合规范的超级括号序列均可通过上述3 条规则得到。

例如,若 k=3k = 3 ,则字符串 ((()()))()((**()*(*))*)(***) 是符合规范的超级括号序列,但 字符串 ()*()(())(*()*)(()))((**))*)(())(****(*)) 均不是。特别地,空字符串也不被视为符合规范的超级括号序列。 现在给出一个长度为 nn 的超级括号序列,其中有一些位置的字符已经确定,另外一些位置的字符尚未确定(用 ?? 表示)。小 ww 希望能计算出:有多少种将所有尚未确定的字符一一确定的方法,使得得到的字符串是一个符合规范的超级括号序列? 可怜的小 cc 并不会做这道题,于是只好请求你来帮忙。

输入格式

从文件 bracket.in 中读入数据。 第 11 行,22 个正整数 n,kn, k。 第 22 行,一个长度为 nn 且仅由(())*?? 构成的字符串 SS

输出格式

输出到文件 bracket.out 中。 输出一个非负整数表示答案对 109+710^9 + 7 取模的结果。

7 3
(*??*??
5

样例 1 解释

如下几种方案是符合规范的:

(**)*()
(**(*))
(*(**))
(*)**()
(*)(**)
10 2
???(*??(?)
19

样例 3

见选手目录下的 bracket3.in 与 [bracket3.out](file://bracket3.out)。

样例 4

见选手目录下的 bracket4.in 与 [bracket4.out](file://bracket4.out)。

数据范围与提示

测试点编号 nn\le 特殊性质
131\sim 3 1515
484\sim 8 4040
9139\sim 13 100100
141514\sim 15 500500 SS 串中仅含有字符 ??
162016\sim 20

对于 100%100\% 的数据,1kn5001 \leq k \leq n \leq 500