考试中，你的任务是计算一个序列的中位数。中位数定义为序列排序后的中间元素（如果序列长度为偶数，则中位数为两个中间值中较小的一个）。你需要写出该算法的伪代码，并在教授提供的示例序列上进行模拟。

你似乎回想起了讲座中出现过的内容。某种神奇的算法……“魔法三数”（magic threes）？你回忆起了一些片段，将序列分成几部分，递归求解，然后合并……？

基于你回忆起的片段，你得出了以下算法：

function magicThrees(sequence)
if the length of the sequence is no more than 2 then
return the smallest value in sequence
otherwise
part_1, part_2, part_3 = splitIntoThreeParts(sequence)
median_i = magicThrees(part_i) dla i = 1, 2, 3
return the median of [median_1, median_2, median_3]

其中 splitIntoThreeParts 将序列分成三个相连的片段，且长度尽可能接近。具体来说，根据原序列的长度，片段的长度将为 $[s, s, s]$、$[s + 1, s, s]$ 或 $[s + 1, s + 1, s]$。例如，序列 $[8, 2, 6, 6, 3, 5, 7, 1]$ 将被分为 $[8, 2, 6]$、$[6, 3, 5]$ 和 $[7, 1]$。

考试结束后，你意识到你的算法并不那么神奇，因为它并不总是有效。也许，至少它在考试的示例序列上是有效的……不幸的是，你对该序列的记忆和对算法的记忆一样模糊：虽然你确实记得考试序列中几乎所有的元素，但你不确定其中几个值。不过，你确实记得序列中出现的所有值的总体范围：所有元素都应该位于（闭）区间 $[0, m - 1]$ 内。

计算有多少种方式可以填补你不知道的值，使得在结果序列上执行 magicThrees 后返回正确的中位数（定义如上）。由于答案可能非常大，你只需要求出其对 $10^9 + 7$ 取模的结果。

输入格式

输入的第一行包含测试用例的数量 $z$。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$ ($n \ge 1, 1 \le m \le 10^9$)，分别表示测试序列的长度和元素值的范围。

第二行包含测试序列，描述为 $n$ 个范围在 $[-1, m-1]$ 内的整数，其中未知值用 $-1$ 表示。

子任务

如果我们用 $q$ 表示未知值的数量，则每个测试用例属于以下组别之一：

• $1 \le z \le 100, 1 \le q \le 10, n \le 3^4 = 81$
• $z = 15, 1 \le q \le 20, n \le 3^5 = 243$
• $z = 3, q = 30, n \le 3^8 = 6561$

输出格式

对于每个测试用例，输出一个整数 $r$ ($0 \le r < 10^9 + 7$)，即题目所求的答案。

样例

样例输入 1

3
3 10
-1 -1 3
4 50
10 20 -1 40
5 100
-1 10 10 -1 20

样例输出 1

100
21
1979

说明

在第一个测试用例中，无论两个未知值是多少，magicThrees 都会返回正确的中位数；因此答案为 $10^2 = 100$。

在第二个测试用例中，当且仅当未知值不大于 $20$ 时，magicThrees 返回正确的中位数，这有 $21$ 种方式。

在第三个测试用例中，如果两个未知值都小于 $10$，或者都大于 $10$，magicThrees 会返回错误的中位数，这有 $100^2 - (10^2 + 89^2) = 1979$ 种方式。