问题描述

您是特别讲座「括号序列和涂色」的讲演者。今天，您决定介绍一种关于仅由(和)构成的字符串$S$的着色方法。保证$S$中的括号匹配没有矛盾。

考虑将$S$中的所有字符涂成红色或蓝色。在这种情况下，如果第$i$个字符是(，第$j$个字符是)且它们是匹配的，则需要对字符串$S[i, j]$中的子串进行涂色，其中红色字符的数目为$R$，蓝色字符的数目为$B$，并且必须满足$|R-B|≦K$。

请计算满足条件的着色方法的总数，将其除以$1,000,000,007$并返回余数。

在此问题中，括号匹配的字符串定义如下：

1. 空字符串是括号匹配的字符串。
2. 如果字符串$A$和$B$都是括号匹配的字符串，则由它们合并而成的字符串$AB$也是括号匹配的字符串。
3. 如果字符串$A$是括号匹配的字符串，则字符串($A$)也是括号匹配的字符串。而且，这两个末端的(和)被称为匹配的。
4. 不满足上述条件的字符串是括号匹配的字符串。

---

输入

输入以以下格式从标准输入中给出。

$S$

$K$

• 第1行包含一个括号序列$S$ $(2≦|S|≦3,000)$。保证$S$中的括号匹配没有矛盾。
• 第2行包含一个表示涂色约束的整数$K (0≦K≦3,000)$。

输出

输出满足条件的着色方法的总数除以$1,000,000,007$的余数。请不要忘记输出换行符。

部分分

此问题有部分分。

• 对于满足$2≦|S|≦8$的数据集，如果答案正确，则得10分。
• 对于满足$2≦|S|≦100$的数据集，如果答案正确，则额外得到10分。
• 如果对于额外限制的数据集，答案正确，则再额外得到50分，共70分。

---

示例输入1

()()
0

示例输出1

4

• 字符串的第1个字符(与第2个字符)，第3个字符(与第4个字符)是匹配的。
• 为方便起见，用红色括号表示<>，用蓝色括号表示[]。
• 可能的着色方法有<]<]、<][>、[><]、[>[>这4个。
• 类似<><]的涂色方法不满足$S[1,2]$中的$|R-B|≦K$约束。
• 此示例满足第1个部分分限制。

---

示例输入2

()()
2

示例输出2

16

• 可能的着色方法有<><>、<><]、<>[]、<>[>、<]<>、<]<]、<][]、<][>、[><>、[><]、[>[]、[>[>、[]<>、[]<]、[][]、[][>共16个。
• 此示例满足第1个部分分限制。

---

示例输入3

(()())
2

示例输出3

50

• 字符串的第1个字符(和第6个字符)，第2个字符(和第3个字符)，第4个字符(和第5个字符)是匹配的。
• 此示例满足第1个部分分限制。

---

示例输入4

()()()()()()()()()()()()()()()()
2

示例输出4

294967268

• 可能的涂色方法总数为$4,294,967,296$，请输出除以$1,000,000,007$的余数$294,967,268$。
• 此示例满足第2个部分分限制。