A74560.括号序列

给定一个长度为 $n$ 的括号序列 $a$ ，这个序列 $a$ 是长度为 $m$ 的合法括号序列 $b$ 的子序列。

午枫想知道序列 $b$ 有多少种可能。

一个括号序列是合法的，那它满足以下任意一个条件：

• 它的长度是 $0$ 。
• 它可以用 $(A)$ 来表示，其中 $A$ 是一个合法括号序列。
• 它可以用 $AB$ 来表示，其中 $A$ 和 $B$ 都是合法括号序列。

如果序列 B 可以通过删除任意个（可能是零个或全部）元素得到序列 $A$ ，那么序列 $A$ 为 序列 $B$ 的子序列。

每一个测试点包含多组数据，第一行输入一个正整数 $t$ $(1\leq t\leq 100)$ ，表示数据组数。

对于每一组数据：

第一行输入两个正整数 $n,m$ $(1\leq n\leq m\leq 300)$ ，分别表示序列 $a$ 的长度和序列 $b$ 的长度。

第二行输入一个长度为 $n$ 的括号序列 $a$ ，不保证序列 $a$ 是合法括号序列。

保证所有数据 $m$ 的总和不超过 $10^3$ 。

对于每一组数据，输出一个正整数表示序列 $b$ 的数量，由于答案可能很大，输出答案模 $10^9+7$ 即可。

样例一解释

满足条件的序列 $b$ 只有 () ，因此答案为 $1$ 。

样例二解释

满足条件的序列 $b$ 只有 ()() ，因此答案为 $1$ 。

样例三解释

满足条件的序列 $b$ 有 ()() 和 (()) ，因此答案为 $2$ 。