括号序列是一个只有 ( 和 ) 组成的序列，我们称一个括号序列 合法，当且仅当:
(
)
()
定义 表示从左往右数第 个左括号所对应的是第几个右括号。
现有一个一个长度为 的括号序列，你得到了 条信息，第 个信息形如 ，表示 。
请输出满足条件的括号序列的数量对 取模后的结果。
第一行一个正整数 ，表示数据组数。
对于每组数据，第一行两个整数 ， 表示有几个左括号， 表示信息数。
接下来 行，每行两个数 。
对于每组数据，输出一个数表示答案。
5 1 0 5 0 3 2 1 2 2 3 3 2 2 1 2 3 3 3 1 2 2 3 3 1
1 42 1 2 0
对于 的数据，满足 ，，。 没有写明来源
