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

Difficulty: interview

Starter code:

Solutions:
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
k=[]
d=[]
def abc(l):
 ans=0
 for i in range(1,len(l)):
  if l[i]>l[i-1]:
   ans+=1
 return ans

for i in range(8):
 k.append(i+1)
 x=list(permutations(k))
 c=[]
 for j in range(8):
  c.append([])
 d.append(c)
 for j in x:
  d[i][abc(j)].append(j)

t=int(input())
for _ in range(t):
 n,k=list(map(int,input().split()))
 l=list(map(int,input().split()))
 ans=0
 c=d[n-1][k]
 for i in c:
  flag=1
  for j in range(n):
   if l[j]!=0 and l[j]!=i[j]:
    flag=0
    break
  if flag:
   ans+=1
 print(ans)
 


from itertools import permutations
k=[]
d=[]
def abc(l):
 ans=0
 for i in range(1,len(l)):
  if l[i]>l[i-1]:
   ans+=1
 return ans

for i in range(8):
 k.append(i+1)
 x=list(permutations(k))
 c=[]
 for j in range(8):
  c.append([])
 d.append(c)
 for j in x:
  d[i][abc(j)].append(j)

t=int(input())
for _ in range(t):
 n,k=list(map(int,input().split()))
 l=list(map(int,input().split()))
 ans=0
 c=d[n-1][k]
 for i in c:
  flag=1
  for j in range(n):
   if l[j]!=0 and l[j]!=i[j]:
    flag=0
    break
  if flag:
   m=0
   for j in range(1,n):
    if i[j]>i[j-1]:
     m+=1
   if m==k:
    ans+=1
 print(ans)
 


from itertools import permutations
for _ in range(int(input())):
 n,k=list(map(int,input().split()))
 a=list(map(int,input().split()))
 b=[False]*(n+1)
 for i in a:
  if i!=0:b[i]=True
 g=[]
 grd=0
 for i in range(1,n+1):
  if not b[i]:g.append(i)
 for i in permutations(g):
  b=a[:]
  f=0
  m=0
  ff=list(i[:])
  for j in range(n):
   if b[j]==0:
    b[j]=ff[-1]
    ff.pop()
  for j in range(1,n):
   if b[j]>b[j-1]:
    f+=1
   if f>k:
    m=1
    break
  if f==k and m==0:grd+=1
 print(grd)


# cook your dish here
from itertools import permutations
for _ in range(int(input())):
 n,k=list(map(int,input().split()))
 a=list(map(int,input().split()))
 b=[False]*(n+1)
 for i in a:
  if i!=0:b[i]=True
 g=[]
 grd=0
 for i in range(1,n+1):
  if not b[i]:g.append(i)
 for i in permutations(g):
  b=a[:]
  f=0
  ff=list(i[:])
  for j in range(n):
   if b[j]==0:
    b[j]=ff[-1]
    ff.pop()
  for j in range(1,n):
   if b[j]>b[j-1]:f+=1
  if f==k:grd+=1
 print(grd)


def cal(a, count, k, poss, ind):
 temp = a.copy()
 if len(poss) == 0:
  #print(a)
  for i in range(1, len(a)):
   if temp[i]>temp[i-1]:
    k -= 1
  if k == 0 and 0 not in temp:
   count += 1
  return count
 if temp[ind] == 0:
  for item in poss:
   temp[ind] = item
   count = cal(temp, count, k, poss-set([item]), ind+1)
 else:
  count = cal(temp, count, k, poss, ind+1)
 return count
t = int(input())
while t>0:
 t -= 1
 n, k = map(int, input().split())
 a = [int(x) for x in input().split()]
 poss = set()
 for i in range(1, len(a)+1):
  if i not in a:
   poss.add(i)
 count = cal(a, 0, k, poss, 0)
 print(count)

t=int(input())
import itertools
for _ in range(t):
 n,kkk=list(map(int,input().split()))
 it=list(map(int,input().split()))
 kk=set(list(range(1,n+1)))
 s=set([i for i in it if i!=0])
 left=kk-s
 #print(left)
 mm=list(itertools.permutations(list(left)))
 tot=0
 #print(mm)
 for perm in mm:
  #print(perm)
  k=0
  mt=it[:]
  ind=0
  for j,i in enumerate(it):
   if i==0:
    mt[j]=perm[ind]
    ind+=1
   if j>0:
    if mt[j]>mt[j-1]:
     k+=1
  if kkk==k:
   tot+=1
 print(tot)
   
   
  
 
 


import itertools
t=int(input())
for _ in range(t):
 n,k=map(int,input().split())
 a=list(map(int,input().split()))
 p=[i for i in range(1,n+1)]
 good=0
 for i in a:
  if(i != 0 ):
   p.remove(i)

 x=list(itertools.permutations(p))
 for i in x:
  j=0
  b=[l for l in a]
  for z in range(n):
   if(b[z]==0):
    b[z]=i[j]
    j+=1
  loc_cnt=0
  for z in range(1,n):
   if(b[z]>b[z-1]):
    loc_cnt+=1
  if(loc_cnt==k):
   good+=1
  
 print(good)