括号序列

时间限制：2000MS 512MB

题目描述

linlic 终于学会了如何判断一个括号序列是否合法，并且成功找到了一个合法的长度为 $n$ 的合法括号序列，但是这个括号序列发生了一些奇妙的反应使得有至多$k$ 个（$0 \leq k \leq 50$）位置发生了反转。例如，第 $i$ 个位置发生反转的话就会导致左括号变成右括号，或者右括号变成左括号。万幸的是，这个括号序列在经过至多$k$ 次反转之后仍然是合法的括号序列。

现在 linlic 想知道在至多反转 $k$ 个位置的情况下，会得到多少种不同的括号序列（对于两个长度为 $n$ 的合法的括号序列 $a，b$，只要存在一个位置 $i$，使得 $1 \leq i \leq n 且 a_i \neq b_i$ 我们就认为两个括号序列是不同的。），由于答案可能很大你只要输出对 $10^9+7$ 取模后的结果。

形式化的说，给定一个长度为 $n$ 的括号序列 $s$（仅由 '(' 和 ')' 组成），你可以执行至多 $k$ 次反转操作：每次操作选择序列中的一个位置，将该位置的括号反转'(' 变 ')'，')' 变 '('。求经过操作后不同的合法的括号序列数目对 $10^9+7$ 取模后的结果。

一个合法的括号序列需要满足以下条件：

• 序列仅由左括号 '(' 和右括号 ')' 组成，且左括号 '(' 和右括号 ')' 的数量相等。
• 对于序列的任意前缀，左括号的数量不少于右括号的数量。

输入描述

第一行一个整数 $T$，表示测试用例数目。

对于每个测试用例：

• 第一行两个整数 $n, k$，表示括号序列的长度和最多可执行的反转操作次数。
• 第二行一个字符串 $s$，表示初始的合法括号序列。

输出描述

对于每个测试用例，输出一行一个整数，为满足条件的不同的括号序列数目对 $10^9+7$ 取模后的结果。

输入样例

1
4 2
()()

输出样例

2