← 返回比赛

已结束 GESP巅峰赛#25

← 上一题下一题 →

A5156 | $括号序列$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为 $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$ 即可。

输入输出样例

输入 #1

3
2 2
()
2 4
)(
2 4
()

输出 #1

1
1
2

C++ 编辑器

输入

输出