We know that a sequence of N integers is called a permutation if it contains all integers from 1 to N exactly once.

A K- beautiful permutation is a permutation for which K is the minimum number of good consecutive segments into which the sequence can be partitioned.
A good consecutive segment is a non-empty continuous segment where all elements of the segment have the same [parity].

For example, the permutation [1, 2, 4, 3] can be divided into minimum 3 segments {[1], [2, 4], [3] } where in each segment, all elements have same parity. Thus, this is a 3- beautiful permutation. Note that you can not divide [1, 2, 4, 3] into less than 3 consecutive segments which satisfy the given condition.

Chef had a permutation of size N which was K- beautiful but he forgot the elements at some of the positions of the permutation. Find the number of distinct permutations of length N that are K- beautiful and can be generated by filling the remaining positions of Chef's permutation.

Since the answer can be huge, print it modulo (10^{9} + 7).

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases. The description of test cases follows.
• The first line of each test case contains two space-separated integers N and K.
• The second line of each test case contains $N integers P_{1},P_{2},\ldots,P_{n}$ — the elements of the K- beautiful permutation. Here, P_{i} = 0 means Chef forgot the element at i^{th} position.

------ Output Format ------

For each test case, print the number of distinct permutations of length N that are K- beautiful and can be generated by filling the remaining positions of Chef's permutation.

Since the answer can be huge, print it modulo (10^{9} + 7).

------ Constraints ------

$1 ≤ T ≤ 10$
$1 ≤ K ≤ N ≤ 100$
$0 ≤ P_{i} ≤ N$
- The sum of $N$ over all test cases won't exceed $100$.

----- Sample Input 1 ------
2
5 2
1 0 0 0 4
5 3
2 0 0 0 4
----- Sample Output 1 ------
2
6
----- explanation 1 ------
Test case $1$ : Following are the distinct $2-$ beautiful permutations which satisfy $[1, 0, 0, 0, 4]$ :
- $[1, 3, 5, 2, 4]$ : Divided into $\{ [1, 3, 5], [2, 4]\}$
- $[1, 5, 3, 2, 4]$ : Divided into $\{ [1, 5, 3], [2, 4]\}$

Test case $2$ : The permutations which are $3-$ beautiful and satisfy given permutation are $[2, 1, 3, 5, 4]$, $[2, 1, 5, 3, 4]$, $[2, 3, 1, 5, 4]$, $[2, 5, 1, 3, 4]$, $[2, 3, 5, 1, 4]$, and $[2, 5, 3, 1, 4]$. So, our answer is $6$.

见题面

见题面