题目描述

在一个间谍和密码破译者的神秘国度里，一位被称为“密码师”的天才破译者截获了一段高度机密的敌方密电。这段密电的长度为 $n$，据信是使用一种复杂的括号系统加密的。根据情报，敌方的加密方法遵循以下特定规则，由 $m$ 种不同类型的括号序列组成：

• 长度为 $0$ 的括号序列被认为是合法的。
• 如果 $A$ 是一个合法的序列，$x$ 是某种类型的左括号，$y$ 是相同类型的右括号，那么序列 $xAy$ 也是一种合法的括号序列。
• 如果 $A$ 和 $B$ 都是合法的序列，那么这些序列的连接 $AB$ 也是一个合法的括号序列。

密码师的任务是通过理解和应用这些括号序列的规则来破译这段信息。形势紧迫，因为这条密电可能包含着决定国家命运的关键信息。

你能帮助密码师根据敌方的加密规则，确定给定的序列是否是一个合法的括号序列吗？

输入格式

每个测试点包含多组测试数据。第一行为测试数据组数 $T(1 ≤ T ≤20)$。

每组测试数据格式为(每组测试数据占 $2$ 行)：

第一行包含两个整数，$n(1 ≤ n ≤ 500)$ 为括号序列长度， $m(1 ≤ m < 10^9 + 7)$ 表示括号类型数（每种类型含左右两种括号）。

第二行包含 $n$ 个整数，$a_1, a_2, ..., a_n(|a_i| ≤ m)$，第 $i$ 个整数 $a_i$ 表示序列中的第 $i$ 个字符：

• 如果 $a_i = 0$，表示该位置的字符丢失了。
• 如果 $a_i > 0$，表示该位置是第 $i$ 种左括号。
• 如果 $a_i < 0$，表示该位置是第 $i$ 种右括号。 保证对于所有 $n>100$ 的测试点，最多有 $15$ 组测试数据。

输出格式

对于每组测试数据，输出一个整数，表示满足条件的括号序列个数（输出答案模 $1000000007$ 的值）。

对于部分情况，可能无法形成一个合法的括号序列（结果为 $0$）。

样例

3
4 2
1 0 0 -1
4 2
0 0 0 -1
6 3
0 0 0 0 0 0

3
4
135