K – Beautiful Permutation Codechef Solution

Problem

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)(109+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_nP1​,P2​,…,Pn​ — the elements of the $K-$ beautiful permutation. Here, P_i = 0Pi​=0 means Chef forgot the element at i^{th}ith 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)(109+7).

Constraints

Sample 1:

2
5 2
1 0 0 0 4
5 3
2 0 0 0 4

2
6

Explanation:

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