Link 有一个长度为 $n$ 的括号序列。今天，Link 发现序列中的一些括号丢失了。

他希望你计算有多少种填充序列的方法，使得该序列成为一个合法的括号序列。

注意，在 Link 的世界里共有 $m$ 种括号。

以下是合法括号序列的定义： 长度为 0 的序列是合法的括号序列。 如果 $A$ 是一个合法的括号序列，$x$ 是某种类型的左括号，$y$ 是相同类型的右括号，则 $xAy$ 是一个合法的括号序列。 * 如果 $A$ 和 $B$ 都是合法的括号序列，则 $AB$ 也是一个合法的括号序列。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $T(1 \le T \le 20)$。

接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n(1 \le n \le 500)$ 和 $m(1 \le m < 10^9 + 7)$，分别表示 Link 的括号序列长度和括号的种类数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n(|a_i| \le m)$。第 $i$ 个整数 $a_i$ 描述了序列中的第 $i$ 个字符： 如果 $a_i = 0$，表示该位置的括号丢失。 如果 $a_i > 0$，表示序列中的第 $i$ 个字符是第 $a_i$ 种类型的左括号。 * 如果 $a_i < 0$，表示序列中的第 $i$ 个字符是第 $-a_i$ 种类型的右括号。

保证 $n > 100$ 的测试用例不超过 15 个。

输出格式

对于每个测试用例，输出一行一个整数，表示填充括号序列使其成为合法括号序列的方法数。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

在某些情况下，可能无法将其变为合法的括号序列。

样例

样例输入 1

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

样例输出 1

3
4
135