Link with Bracket Sequence II

Link has a bracket sequence of length $n$. Today, Link finds out that some brackets of the sequence were lost.

Of course, he wants you to calculate how many ways are there to fill the sequence so that it will be a valid bracket sequence.

Note that there are $m$ types of brackets in Link's world.

Here's the definition of a valid bracket sequence:

· A sequence of length $0$ is a valid bracket sequence.
· If $A$ is a valid bracket sequence, $x$ is some type of left bracket, $y$ is the same type of right bracket, $xAy$ is a valid bracket sequence.
· If $A,B$ are both valid bracket sequences, then $AB$ is also a valid bracket sequence.

Each test contains multiple test cases. The first line contains the number of test cases $T(1 \le T \le 20)$. Description of the test cases follows.

The first line contains two integers $n(1 \leq n \leq 500),m(1 \leq m < 10^9+7)$, which is the length of Link's bracket sequence and the types of brackets.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n(|a_i| \leq m)$. The $i$-th integer $a_i$ describes the $i$-th character in the sequence:

· If $a_i=0$, it means the bracket in this position is lost.
· $a_i>0$, it means the $i$-th character in the sequence is the $a_i$-th type of left bracket.
· $a_i<0$, it means the $i$-th character in the sequence is the $-a_i$-th type of right bracket.

It is guaranteed that there are at most 15 test cases with $n>100$.

For each test case, output one integer in a line, which is the number of ways to fill the bracket sequence so that it is a valid bracket sequence. Since the answer can be huge, just print it modulo $10^9+7$.

For some reason, there could be no way to make it a valid bracket sequence.

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

3
4
135

2022“杭电杯”中国大学生算法设计超级联赛（4）