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$.

Difficulty: VERY_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
from functools import lru_cache
mod = 10 ** 9 + 7

@lru_cache(maxsize=None)
def f(i, odds, evens, K, prev):
	if i >= n:
		return int(K == 1)
	if p[i] != 0:
		return f(i + 1, odds, evens, K - (prev != p[i] % 2), p[i] % 2) % mod
	ans = 0
	if evens > 0:
		ans += evens * f(i + 1, odds, evens - 1, K - (prev != 0), 0) % mod
	if odds > 0:
		ans += odds * f(i + 1, odds - 1, evens, K - (prev != 1), 1) % mod
	return ans % mod
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	f.cache_clear()
	odds = (n + 1) // 2
	evens = n // 2
	for v in p:
		if v != 0:
			if v % 2:
				odds -= 1
			else:
				evens -= 1
	if p[0] != 0:
		print(f(1, odds, evens, k, p[0] % 2))
	else:
		ans = evens * f(1, odds, evens - 1, k, 0) % mod
		f.cache_clear()
		ans = ans + odds * f(1, odds - 1, evens, k, 1) % mod
		print(ans % mod)