Median

Yaawn... you really shouldn't have played on ByteStation till 3 AM. You begin to slowly drift away, immersed by the monotone voice of your algorithms professor...

Wait. What happened? It seems that you fell asleep during online classes, and slept through the entire afternoon, night, and the next morning. But that means... the exam! Barely catching your breath, you burst into the classroom precisely when the professor is beginning to explain the problem statement.

The task at the exam is to compute the median of a sequence, defined as the middle element in the sorted order (if the length of the sequence is even, the median is the smaller of the two middle values). You are supposed to write down the pseudocode of a solution, and then simulate it on an example sequence provided by the professor.

Reaching into the depths of your memory, you seem to recall something like that appearing during the lecture. Some sort of magic algorithm... magic threes? The memory makes you sleepy again. You somehow split the sequence into parts, solve them recursively, and then combine...?

Based on the bits and pieces you remembered, you came up with the following algorithm:

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]

where splitIntoThreeParts divides the sequence into three connected fragments, with lengths as close to each other as possible. Concretely, the fragments have lengths $[s, s, s]$, $[s + 1, s, s]$ or $[s + 1, s + 1, s]$, depending on the length of the original sequence. For example, the sequence [8, 2, 6, 6, 3, 5, 7, 1] is divided into [8, 2, 6], [6, 3, 5] and [7, 1].

After leaving the exam, you realized that your algorithm is not so magical after all, as it does not always work. Maybe, at least, it has worked on the example sequence from the exam... Unfortunately, your memory of that sequence is as fuzzy as your memory of the algorithm. You remember almost all elements of the sequence, but you are not sure about a few of the values. You do remember the overall bounds on all values in the sequence: all elements were supposed to lie in the closed interval $[0, m-1]$.

Calculate the number of ways to choose the values you do not know, such that magicThrees executed on the resulting sequence returns the correct median (as defined above). As the answer may be very large, output it modulo $10^9 + 7$.

The first line of input contains the number of test cases $z$. The descriptions of the test cases follow.

The first line of a test case contains two integers $n$, $m$ ($n \ge 1$, $1 \le m \le 10^9$), denoting the length of the test sequence and the bound on the values of its elements.

The second line contains the test sequence, described as $n$ integers from the range $[-1, m-1]$, where elements with unknown values are denoted by $-1$.

If we denote the number of unknown values by $q$, then every test case belongs to one of the following groups:

• $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 = 6\,561$

For every test case, output a single integer $r$ ($0 \le r < 10^9 + 7$), the answer to the question posed in the problem statement.

In the first test case, magicThrees returns the correct median irrespective of the two unknown values, so the answer is $10^2 = 100$.

In the second test case, magicThrees returns the correct median if and only if the unknown value is not larger than $20$, which gives $21$ ways.

In the third test case, magicThrees returns an incorrect median if both unknown values are smaller than $10$, or both are larger, which gives $100^2 - (10^2 + 89^2) = 1979$ ways.