You have a sequence $a$ with length $N$ created by removing some elements (possibly zero) from a permutation of numbers $(1, 2, \dots, N)$. When an element is removed, the length of the sequence doesn't change, but there is an empty spot left where the removed element was. You also have an integer $K$.
Let's call a permutation $p_1, p_2, \dots, p_N$ good if:
- it is possible replace empty spots in $a$ by numbers in such a way that we obtain the permutation $p$
- the number of positions $i$ ($1 < i \le N$) such that $p_i > p_{i-1}$ is equal to $K$
Your task is to find the number of good permutations.
-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $a_1, a_2, \dots, a_N$. Each element of this sequence is either $0$ (indicating an empty spot previously occupied by a removed element) or an integer between $1$ and $N$ inclusive.
-----Output-----
For each test case, print a single line containing one integer — the number of good permutations.
-----Constraints-----
- $1 \le T \le 300$
- $0 \le K < N \le 8$
- each integer between $1$ and $N$ inclusive appears in $a$ at most once
-----Example Input-----
1
3 1
2 0 0
-----Example Output-----
2
-----Explanation-----
Example case 1: The two possible good permutations are $(2,3,1)$ and $(2,1,3)$.
from itertools import permutations

for _ in range(int(input())):
 N,K=list(map(int,input().split()))
 arr=list(map(int,input().split()))
 arr1=[]
 arr2=[]
 for i in range(1,len(arr)+1):
  arr1.append(i)
 indexzero=[]
 for i in range(0,len(arr)):
  if(arr[i]==0):
   indexzero.append(i)
  else:
   arr2.append(arr[i])
 # arr3 = [x for x in arr1 if x not in arr2]
 arr3= list(set(arr1)-set(arr2))
 result=permutations(arr3)
 perm=[]
 for i in result:
  perm.append(i)
 step=0
 count=0
 for p in range(0,len(perm)):
  temp=[]
  for q in range(0,len(arr)):
   if(arr[q]==0):
    temp.append(perm[p][step])
    step+=1 
   else:
    temp.append(arr[q])
  k=0
  step=0
  for m in range(0,len(temp)-1):
   if(temp[m]<temp[m+1]):
    k+=1
  if(k==K):
   count+=1 
 print(count)
   
    
  
 
  
 
   

from itertools import permutations

for _ in range(int(input())):
 N,K=list(map(int,input().split()))
 arr=list(map(int,input().split()))
 arr1=[]
 arr2=[]
 for i in range(1,len(arr)+1):
  arr1.append(i)
 indexzero=[]
 for i in range(0,len(arr)):
  if(arr[i]==0):
   indexzero.append(i)
  else:
   arr2.append(arr[i])
 # arr3 = [x for x in arr1 if x not in arr2]
 arr3= list(set(arr1)-set(arr2))
 result=permutations(arr3)
 perm=[]
 for i in result:
  perm.append(i)
 step=0
 count=0
 for p in range(0,len(perm)):
  temp=[]
  for q in range(0,len(arr)):
   if(arr[q]==0):
    temp.append(perm[p][step])
    step+=1 
   else:
    temp.append(arr[q])
  k=0
  step=0
  for m in range(0,len(temp)-1):
   if(temp[m]<temp[m+1]):
    k+=1
  if(k==K):
   count+=1 
 print(count)
   
    
  
 
  
 
   
