# K – Beautiful Permutation Codechef Solution

### We Are Discuss About CODECHEF SOLUTION

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.

K- beautiful permutation is a permutation for which K is the minimum number of good consecutive segments into which the sequence can be partitioned.
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 \leq T \leq 10
• 1 \leq K \leq N \leq 100
• 0 \leq P_i \leq N
• The sum of N over all test cases won’t exceed 100.

### Sample 1:

Input

Output

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.

## K – Beautiful Permutation Codechef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW