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

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Complete search


Solutions:
from itertools import permutations
for k in range(int(input())):
	(n, k) = map(int, input().split())
	u = 0
	a = list(map(int, input().split()))
	b = [i for i in range(1, n + 1)]
	for i in a:
		if i != 0:
			b.remove(i)
	d = list(permutations(b))
	for j in d:
		s = 0
		t = []
		for i in range(len(a)):
			if a[i] == 0:
				t.append(j[s])
				s += 1
			else:
				t.append(a[i])
		h = 0
		for i in range(0, n - 1):
			if t[i] < t[i + 1]:
				h += 1
		if h == k:
			u += 1
	print(u)


from math import *
from itertools import *
t = int(input())
while t:
	r = 0
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	rem = set(range(1, n + 1)) - set(a)
	totalperm = list(permutations(rem))
	for item in totalperm:
		i = 0
		b = a[:]
		z = 0
		if 1:
			for j in range(n):
				if b[j] == 0:
					b[j] = item[i]
					i += 1
			for j in range(n - 1):
				if b[j + 1] > b[j]:
					z += 1
			if z == k:
				r += 1
	print(r)
	t = t - 1


from itertools import permutations
t = int(input())
for z in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	missing = []
	for i in range(1, n + 1):
		if i not in a:
			missing.append(i)
	if not missing:
		cnt = 0
		for i in range(1, n):
			if a[i] > a[i - 1]:
				cnt += 1
		if cnt == k:
			print(1)
		else:
			print(0)
		continue
	alist = list(permutations(missing))
	ans = 0
	for filler in alist:
		b = a[:]
		idx = 0
		for i in range(n):
			if b[i] == 0:
				b[i] = filler[idx]
				idx += 1
		cm = 0
		for i in range(1, n):
			if b[i] > b[i - 1]:
				cm += 1
		if cm == k:
			ans += 1
	print(ans)


from itertools import permutations
t = int(input())
for i in range(t):
	ip = input().split()
	n = int(ip[0])
	k = int(ip[1])
	arr = [0] * n
	ip = input().split()
	present = [False] * (n + 1)
	for j in range(n):
		arr[j] = int(ip[j])
		present[arr[j]] = True
	permute = []
	for j in range(1, n + 1):
		if not present[j]:
			permute.append(j)
	missingPermutations = list(permutations(permute))
	count = 0
	for permutation in missingPermutations:
		temp = arr.copy()
		ctr = 0
		index = 0
		for j in range(len(temp)):
			if temp[j] == 0:
				temp[j] = permutation[index]
				index += 1
		ctr = 0
		for j in range(1, len(temp)):
			if temp[j - 1] < temp[j]:
				ctr += 1
		if ctr == k:
			count += 1
	print(count)


from itertools import permutations
t = int(input())
while t > 0:
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	res = []
	good = int(0)
	arr = [int(i) for i in input().split()]
	check = [1, 2, 3, 4, 5, 6, 7, 8]
	for num in check:
		if num not in arr and (num >= 1 and num <= n):
			res.append(num)
	index = 0
	missing_index = []
	for num in arr:
		if num == 0:
			missing_index.append(index)
		index = index + 1
	for p in list(permutations(res)):
		final = list(arr)
		g = list(missing_index)
		for num in p:
			for ind in g:
				final[ind] = num
				g.remove(ind)
				break
		count = int(0)
		for i in range(1, len(final)):
			if final[i] > final[i - 1]:
				count = count + 1
			if count > k:
				break
		if count == k:
			good = good + 1
	print(good)
	t = t - 1


from itertools import permutations
itr = int(input())
for i in range(itr):
	l = input().split()
	(n, k) = map(int, l)
	l = input().split()
	fv = list(map(int, l))
	a = set([j for j in range(1, n + 1)])
	ctr = 0
	m = list(permutations(list(a - set(fv))))
	for j in m:
		k_ctr = 0
		j_ctr = 0
		flag = True
		l = fv[:]
		for z in range(n):
			if l[z] == 0:
				l[z] = j[j_ctr]
				j_ctr += 1
			if z > 0:
				if l[z] > l[z - 1]:
					k_ctr += 1
			if k_ctr > k:
				flag = False
				break
		if flag == True and k_ctr == k:
			ctr += 1
	print(ctr)


from itertools import permutations
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = set()
	ans = 0
	for i in range(1, n + 1):
		s.add(i)
	l = s - set(a)
	l = list(l)
	l = list(permutations(l))
	orig = []
	for val in a:
		orig.append(val)
	for tup in l:
		x = list(tup)
		ind = 0
		for i in range(n):
			if a[i] == 0:
				a[i] = x[ind]
				ind += 1
		cn = 0
		for i in range(len(a) - 1):
			if a[i + 1] - a[i] > 0:
				cn += 1
		if cn == k:
			ans += 1
		a = []
		for p1 in orig:
			a.append(p1)
	print(ans)


from itertools import permutations

def checkpermu(po, k):
	gt = len(po)
	co = 0
	for ju in range(gt - 1):
		if po[ju + 1] > po[ju]:
			co += 1
	if co == k:
		return True
	else:
		return False
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = [int(o) for o in input().split()]
	num = []
	for i in range(n):
		num.append(i + 1)
	for ki in l:
		if ki != 0:
			num.remove(ki)
	t = list(permutations(num))
	result = 0
	for ji in t:
		lo = 0
		l1 = l[:]
		for y in range(n):
			if l1[y] == 0:
				l1[y] = ji[lo]
				lo += 1
		if checkpermu(l1, k):
			result += 1
	print(result)


def goDownTheRabbitHole(A, indexToFill, numbersLeftToUse, k):
	if indexToFill == N:
		if k == K:
			return 1
		else:
			return 0
	else:
		goodWaysFound = 0
		if A[indexToFill] != 0:
			if indexToFill > 0 and A[indexToFill] > A[indexToFill - 1]:
				goodWaysFound += goDownTheRabbitHole(A[:], indexToFill + 1, numbersLeftToUse, k + 1)
			else:
				goodWaysFound += goDownTheRabbitHole(A[:], indexToFill + 1, numbersLeftToUse, k)
		elif A[indexToFill] == 0:
			for numberLeftToUse in numbersLeftToUse:
				A[indexToFill] = numberLeftToUse
				if indexToFill > 0 and A[indexToFill] > A[indexToFill - 1]:
					goodWaysFound += goDownTheRabbitHole(A[:], indexToFill + 1, numbersLeftToUse - {numberLeftToUse}, k + 1)
				else:
					goodWaysFound += goDownTheRabbitHole(A[:], indexToFill + 1, numbersLeftToUse - {numberLeftToUse}, k)
		return goodWaysFound
T = int(input())
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	numbersLeftToUse = set(range(1, N + 1)) - set(A)
	goodWaysFound = goDownTheRabbitHole(A, 0, numbersLeftToUse, 0)
	print(goodWaysFound)


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)


import sys
import math
import itertools
fileoperation = 0
if fileoperation:
	orig_stdout = sys.stdout
	orig_stdin = sys.stdin
	inputfile = open('W:/Competitive Programming/input.txt', 'r')
	outputfile = open('W:/Competitive Programming/output.txt', 'w')
	sys.stdin = inputfile
	sys.stdout = outputfile
mod = 1000000007

def nospace(l):
	ans = ''.join((str(i) for i in l))
	return ans
t = int(input())
for tt in range(t):
	(n, k) = map(int, sys.stdin.readline().split(' '))
	a = list(map(int, sys.stdin.readline().split(' ')))
	b = []
	for i in range(1, n + 1):
		if i not in a:
			b.append(i)
	l = list(itertools.permutations(b))
	ans = 0
	for i in range(len(l)):
		m = l[i]
		c = a[:]
		kk = 0
		for j in range(n):
			if not a[j]:
				c[j] = m[kk]
				kk += 1
		count = 0
		for j in range(1, n):
			if c[j] > c[j - 1]:
				count += 1
		if count == k:
			ans += 1
	print(ans)
if fileoperation:
	sys.stdout = orig_stdout
	sys.stdin = orig_stdin
	inputfile.close()
	outputfile.close()


def find_perm(s1, n1, k1, index, x1, prev):
	perms = 0
	if n1 == 1:
		return 1
	if k1 < 0:
		return 0
	if index == 0:
		if s1[index] != 0:
			perms += find_perm(s1, n1, k1, index + 1, x1, s1[index])
		else:
			for i in x1:
				perms += find_perm(s1, n1, k1, index + 1, x1 - {i}, i)
	elif index == n1 - 1:
		if s[index] != 0:
			if s[index] > prev:
				k1 -= 1
		else:
			for i in x1:
				if i > prev:
					k1 -= 1
		if k1 == 0:
			return 1
		else:
			return 0
	elif s[index] != 0:
		if s[index] > prev:
			k1 -= 1
		perms += find_perm(s1, n1, k1, index + 1, x1, s1[index])
	else:
		for i in x1:
			if i > prev:
				perms += find_perm(s1, n1, k1 - 1, index + 1, x1 - {i}, i)
			else:
				perms += find_perm(s1, n1, k1, index + 1, x1 - {i}, i)
	return perms
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split())
	s = list(map(int, input().strip().split()))
	x = []
	for i in range(n):
		x.append(i + 1)
	for i in s:
		if i != 0:
			x.remove(i)
	ans = find_perm(s, n, k, 0, set(x), -1)
	print(ans)


t = int(input())
perms = []

def toString(List):
	return ''.join(List)

def permute(a, l, r):
	if l == r:
		perms.append(a[:])
	else:
		for i in range(l, r + 1):
			(a[l], a[i]) = (a[i], a[l])
			permute(a, l + 1, r)
			(a[l], a[i]) = (a[i], a[l])
while t > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	count_zero = 0
	reqd = []
	for i in range(1, n + 1):
		if i in a:
			pass
		else:
			count_zero += 1
			reqd.append(i)
	permute(reqd, 0, count_zero - 1)
	if count_zero == 0:
		cnt = 0
		for i in range(1, n):
			if a[i] > a[i - 1]:
				cnt += 1
		if cnt == k:
			print(1)
		else:
			print(0)
	else:
		for perm in perms:
			count = 0
			temp_a = [0] * n
			z = 0
			for i in range(n):
				if a[i] == 0:
					temp_a[i] = perm[z]
					z += 1
				else:
					temp_a[i] = a[i]
			for i in range(1, n):
				if temp_a[i] > temp_a[i - 1]:
					count += 1
			if count == k:
				ans += 1
		print(ans)
	perms = []
	t -= 1


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) = 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)


import itertools

def isgood(a):
	count = 0
	for i in range(1, len(a)):
		if a[i] > a[i - 1]:
			count += 1
	return count
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	z = a.count(0)
	if z == 0:
		count = isgood(a)
		if count == k:
			print(1)
		else:
			print(0)
	else:
		b = list(range(1, n + 1))
		for l in a:
			if l in b:
				b.remove(l)
		u = []
		for i in range(len(a)):
			if a[i] == 0:
				u.append(i)
		s = 0
		for c in list(itertools.permutations(b)):
			temp = list(a)
			i = 0
			for j in list(c):
				if i < len(u):
					temp[u[i]] = j
					i += 1
			count = isgood(temp)
			if count == k:
				s += 1
		print(s)


from itertools import permutations
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	b = list(range(1, n + 1))
	a = list(map(int, input().split()))
	remain = list(set(b) - set(a))
	for perm in permutations(remain):
		temp = a[:]
		p = 0
		for i in range(n):
			if temp[i] == 0:
				temp[i] = perm[p]
				p += 1
		k_temp = sum([temp[i] > temp[i - 1] for i in range(1, n)])
		ans += int(k_temp == k)
	print(ans)


def func(arr):
	count = 0
	for i in range(1, len(arr)):
		if arr[i] > arr[i - 1]:
			count += 1
	return count
from itertools import permutations
for z in range(int(input())):
	(n, k) = (int(s) for s in input().split())
	l = [int(x) for x in input().split()]
	miss = []
	present = []
	count = 0
	for i in range(n):
		if l[i] == 0:
			miss.append(i)
		else:
			present.append(l[i])
		if l[i] != 0 and l[i - 1] != 0:
			if l[i] > l[i - 1]:
				count += 1
	if count > k:
		print('0')
	else:
		ar = []
		for v in range(1, n + 1):
			if v not in present:
				ar.append(v)
		per = list(permutations(ar))
		count = 0
		for mm in range(len(per)):
			pos = 0
			for kk in miss:
				l[kk] = per[mm][pos]
				pos += 1
			if func(l) == k:
				count += 1
		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
	mm = list(itertools.permutations(list(left)))
	tot = 0
	for perm in mm:
		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)


from itertools import permutations

def solve():
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	index = []
	for i in range(0, n):
		if a[i] > 0:
			index.append(i)
	per = list(permutations(range(1, n + 1)))
	ans = 0
	for p in per:
		f = False
		l = list(p)
		for i in index:
			if l[i] != a[i]:
				f = True
				break
		if f:
			continue
		c = 0
		for i in range(1, n):
			if l[i - 1] < l[i]:
				c += 1
		if c == k:
			ans += 1
	print(ans, end='\n')
test = int(input())
while test:
	solve()
	test = test - 1


from itertools import permutations
import sys

def permute():
	(n, k) = map(int, sys.stdin.readline().split())
	v = []
	a = list(map(int, sys.stdin.readline().split()))
	for i in range(n):
		if a[i] > 0:
			v.append(i)
	permu = list(permutations(range(1, n + 1)))
	ans = 0
	for p in permu:
		i = list(p)
		c = 0
		flag = 0
		for j in v:
			if i[j] != a[j]:
				flag = 1
				break
		if flag:
			continue
		for j in range(1, n):
			if i[j] > i[j - 1]:
				c += 1
		if c == k:
			ans += 1
	print(ans)
for _ in range(int(input())):
	permute()


from itertools import permutations as perm
t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	global_count = 0
	missing = []
	for i in range(n):
		missing.append(i + 1)
	for i in a:
		if i != 0:
			missing.remove(i)
	per = list(perm(missing))
	t = list(a)
	for i in range(len(per)):
		index = 0
		local_count = 0
		a = list(t)
		for j in range(n):
			if a[j] == 0:
				a[j] = per[i][index]
				index += 1
		for j in range(1, n):
			if a[j] > a[j - 1]:
				local_count += 1
		if local_count == k:
			global_count += 1
	print(global_count)


from itertools import permutations
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	all_elements = [i + 1 for i in range(n)]
	found_elements = []
	missing_indices = []
	missing_elements = []
	for i in range(n):
		elem = ar[i]
		if elem > 0:
			found_elements.append(elem)
		else:
			missing_indices.append(i)
	missing_elements = list(set(all_elements) - set(found_elements))
	perms = permutations(missing_elements)
	all_perms = []
	for perm in perms:
		temp = list(ar)
		perm = list(perm)
		for i in range(len(missing_elements)):
			temp[missing_indices[i]] = perm[i]
		all_perms.append(temp)
	good_perms = 0
	for perm in all_perms:
		count = 0
		for i in range(n - 1):
			if perm[i + 1] > perm[i]:
				count += 1
		if count == k:
			good_perms += 1
	print(good_perms)


from itertools import permutations
R = lambda : map(int, input().split())
t = int(input())
for _ in range(t):
	(n, k) = R()
	a = list(R())
	l = [i for (i, x) in enumerate(a) if not x]
	s = 0
	for c in permutations(set(range(1, n + 1)) - set(a)):
		for (i, x) in zip(l, c):
			a[i] = x
		s += sum((a[i] > a[i - 1] for i in range(1, n))) == k
	print(s)


import itertools
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(range(1, n + 1))
	c = list(itertools.permutations(b, n))
	d = []
	e = []
	for j in range(n):
		if a[j] != 0:
			d.append([j, a[j]])
	m = len(d)
	for j in c:
		r = 0
		for s in d:
			if j[s[0]] == s[1]:
				r += 1
			else:
				break
		if r == m:
			e.append(j)
	ans = 0
	for j in e:
		m = 0
		for s in range(len(j) - 1):
			if j[s] < j[s + 1]:
				m += 1
		if m == k:
			ans += 1
	print(ans)


from itertools import permutations

def count(nums, k):
	res = 0
	for p in permutations(range(1, len(nums) + 1)):
		validPermutation = True
		for (x, y) in zip(nums, p):
			if x != 0 and x != y:
				validPermutation = False
				break
		if validPermutation:
			valid = 0
			for (i, j) in enumerate(p):
				if i == 0:
					continue
				if p[i] > p[i - 1]:
					valid += 1
			if valid == k:
				res += 1
	return res
nTestcases = int(input())
for _ in range(nTestcases):
	(n, k) = [int(i) for i in input().split()]
	numbers = [int(i) for i in input().split()]
	print(count(numbers, k))


import itertools
T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	alist = list(map(int, input().split()))
	num0 = alist.count(0)
	missing = []
	for j in range(1, N + 1):
		if j not in alist:
			missing.append(j)
	perm = list(itertools.permutations(missing))
	it = 1
	for j in range(1, num0 + 1):
		it *= j
	ans = 0
	for j in range(it):
		x = 0
		newa = list(alist)
		for k in range(N):
			if newa[k] == 0:
				newa[k] = perm[j][x]
				x += 1
		count = 0
		for k in range(N - 1):
			if newa[k] < newa[k + 1]:
				count += 1
		if count == K:
			ans += 1
	print(ans)


from itertools import *
for t in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	x = [int(i) for i in range(1, n + 1)]
	missing = list(set(x) - set(a))
	per = list(permutations(missing))
	ans = 0
	for i in per:
		b = a[:]
		c = 0
		for j in range(n):
			if a[j] == 0:
				b[j] = i[c]
				c += 1
		d = 0
		for j in range(1, n):
			if b[j] > b[j - 1]:
				d += 1
		if d == k:
			ans += 1
	print(ans)


import itertools
d = {}
t = int(input())
d[1] = [[1]]
d[2] = [(1, 2), (2, 1)]
d[3] = [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
d[4] = [(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]
d[5] = [(1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 4, 3, 5), (1, 2, 4, 5, 3), (1, 2, 5, 3, 4), (1, 2, 5, 4, 3), (1, 3, 2, 4, 5), (1, 3, 2, 5, 4), (1, 3, 4, 2, 5), (1, 3, 4, 5, 2), (1, 3, 5, 2, 4), (1, 3, 5, 4, 2), (1, 4, 2, 3, 5), (1, 4, 2, 5, 3), (1, 4, 3, 2, 5), (1, 4, 3, 5, 2), (1, 4, 5, 2, 3), (1, 4, 5, 3, 2), (1, 5, 2, 3, 4), (1, 5, 2, 4, 3), (1, 5, 3, 2, 4), (1, 5, 3, 4, 2), (1, 5, 4, 2, 3), (1, 5, 4, 3, 2), (2, 1, 3, 4, 5), (2, 1, 3, 5, 4), (2, 1, 4, 3, 5), (2, 1, 4, 5, 3), (2, 1, 5, 3, 4), (2, 1, 5, 4, 3), (2, 3, 1, 4, 5), (2, 3, 1, 5, 4), (2, 3, 4, 1, 5), (2, 3, 4, 5, 1), (2, 3, 5, 1, 4), (2, 3, 5, 4, 1), (2, 4, 1, 3, 5), (2, 4, 1, 5, 3), (2, 4, 3, 1, 5), (2, 4, 3, 5, 1), (2, 4, 5, 1, 3), (2, 4, 5, 3, 1), (2, 5, 1, 3, 4), (2, 5, 1, 4, 3), (2, 5, 3, 1, 4), (2, 5, 3, 4, 1), (2, 5, 4, 1, 3), (2, 5, 4, 3, 1), (3, 1, 2, 4, 5), (3, 1, 2, 5, 4), (3, 1, 4, 2, 5), (3, 1, 4, 5, 2), (3, 1, 5, 2, 4), (3, 1, 5, 4, 2), (3, 2, 1, 4, 5), (3, 2, 1, 5, 4), (3, 2, 4, 1, 5), (3, 2, 4, 5, 1), (3, 2, 5, 1, 4), (3, 2, 5, 4, 1), (3, 4, 1, 2, 5), (3, 4, 1, 5, 2), (3, 4, 2, 1, 5), (3, 4, 2, 5, 1), (3, 4, 5, 1, 2), (3, 4, 5, 2, 1), (3, 5, 1, 2, 4), (3, 5, 1, 4, 2), (3, 5, 2, 1, 4), (3, 5, 2, 4, 1), (3, 5, 4, 1, 2), (3, 5, 4, 2, 1), (4, 1, 2, 3, 5), (4, 1, 2, 5, 3), (4, 1, 3, 2, 5), (4, 1, 3, 5, 2), (4, 1, 5, 2, 3), (4, 1, 5, 3, 2), (4, 2, 1, 3, 5), (4, 2, 1, 5, 3), (4, 2, 3, 1, 5), (4, 2, 3, 5, 1), (4, 2, 5, 1, 3), (4, 2, 5, 3, 1), (4, 3, 1, 2, 5), (4, 3, 1, 5, 2), (4, 3, 2, 1, 5), (4, 3, 2, 5, 1), (4, 3, 5, 1, 2), (4, 3, 5, 2, 1), (4, 5, 1, 2, 3), (4, 5, 1, 3, 2), (4, 5, 2, 1, 3), (4, 5, 2, 3, 1), (4, 5, 3, 1, 2), (4, 5, 3, 2, 1), (5, 1, 2, 3, 4), (5, 1, 2, 4, 3), (5, 1, 3, 2, 4), (5, 1, 3, 4, 2), (5, 1, 4, 2, 3), (5, 1, 4, 3, 2), (5, 2, 1, 3, 4), (5, 2, 1, 4, 3), (5, 2, 3, 1, 4), (5, 2, 3, 4, 1), (5, 2, 4, 1, 3), (5, 2, 4, 3, 1), (5, 3, 1, 2, 4), (5, 3, 1, 4, 2), (5, 3, 2, 1, 4), (5, 3, 2, 4, 1), (5, 3, 4, 1, 2), (5, 3, 4, 2, 1), (5, 4, 1, 2, 3), (5, 4, 1, 3, 2), (5, 4, 2, 1, 3), (5, 4, 2, 3, 1), (5, 4, 3, 1, 2), (5, 4, 3, 2, 1)]
a6 = []
a7 = []
a8 = []
c6 = [1, 2, 3, 4, 5, 6]
c7 = [1, 2, 3, 4, 5, 6, 7]
c8 = [1, 2, 3, 4, 5, 6, 7, 8]
d[7] = list(itertools.permutations(c7))
d[8] = list(itertools.permutations(c8))
d[6] = list(itertools.permutations(c6))
ch = {}
for i in range(9):
	dd = {}
	for j in range(i):
		dd[j] = []
	ch[i] = dd
for i in d:
	kk = d[i]
	for j in kk:
		pp = j
		ll = len(pp)
		c = 0
		for ji in range(ll - 1):
			if pp[ji] < pp[ji + 1]:
				c += 1
		ch[i][c].append(j)
for edi in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	kk = d[n]
	co = 0
	pt = []
	if n == 1 and k == 0:
		print(1)
		continue
	for j in range(n):
		if a[j] != 0:
			pt.append(j)
	kt = ch[n][k]
	for i in kt:
		kk = 1
		for j in pt:
			if i[j] != a[j]:
				kk = 0
				break
		if kk == 1:
			co += 1
	print(co)


from itertools import permutations
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	br = []
	cr = []
	brc = []
	for i in range(n):
		cr.append(i + 1)
		if ar[i] != 0:
			br.append([ar[i], i])
			brc.append(ar[i])
	brc = set(brc)
	cr = set(cr)
	cr = list(cr - brc)
	perm = permutations(cr)
	pem = []
	for p in perm:
		temp = list(p)
		for b in br:
			temp = temp[:b[1]] + [b[0]] + temp[b[1]:]
		pem.append(temp)
	c = 0
	for p in pem:
		ck = 0
		for i in range(1, n):
			if p[i - 1] < p[i]:
				ck += 1
		if ck == k:
			c += 1
	print(c)


import itertools
t = int(input())
while t > 0:
	t -= 1
	(n, K) = map(int, input().split())
	arr = list(map(int, input().split()))
	cc = []
	global_count = 0
	for i in range(n):
		cc.append(i + 1)
	for i in arr:
		if i != 0:
			cc.remove(i)
	l = list(itertools.permutations(cc))
	tt = list(arr)
	for i in range(len(l)):
		index = 0
		local_count = 0
		arr = list(tt)
		for j in range(n):
			if arr[j] == 0:
				arr[j] = l[i][index]
				index += 1
		for j in range(1, n):
			if arr[j] > arr[j - 1]:
				local_count += 1
		if local_count == K:
			global_count += 1
	print(global_count)


def check(arr, k):
	count1 = 0
	for i in range(len(arr) - 1):
		if arr[i + 1] > arr[i]:
			count1 += 1
	if count1 == k:
		return True
	else:
		return False
import itertools
for i in range(int(input())):
	count = 0
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = []
	missin = []
	for i in range(n):
		b.append(i + 1)
	for i in range(n):
		if a[i] == 0:
			missin.append(i)
		elif a[i] in b:
			b.remove(a[i])
	per = list(itertools.permutations(b, len(b)))
	e = []
	copya = []
	for i in per:
		d = list(i)
		copya = a[:]
		index = 0
		for j in missin:
			copya[j] = d[index]
			index += 1
		if check(copya, k):
			count += 1
	print(count)


from itertools import permutations
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	s1 = set([i for i in range(1, n + 1)])
	s = list(s1 - set(a))
	m = len(s)
	d = permutations(s, m)
	ans = 0
	for i in d:
		e = list(i)
		x = 0
		y = 0
		for j in range(1, n):
			temp1 = a[j - 1]
			temp2 = a[j]
			if temp1 == 0:
				temp1 = e[x]
				x += 1
			if temp2 == 0:
				temp2 = e[x]
			if temp2 > temp1:
				y += 1
		if y == k:
			ans += 1
	print(ans)


def cal(a, count, k, poss, ind):
	temp = a.copy()
	if len(poss) == 0:
		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)


from itertools import permutations
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = []
	for i in range(n + 1):
		b.append(0)
	for i in range(n):
		if a[i] != 0:
			b[a[i]] = 1
	fn = []
	for i in range(1, n + 1):
		if b[i] == 0:
			fn.append(i)
	ans = [0]
	perm = permutations(fn)
	for p in perm:
		tmp = []
		gand = 0
		total = 0
		for i in a:
			if i == 0:
				tmp.append(p[gand])
				gand += 1
			else:
				tmp.append(i)
		for i in range(1, n):
			if tmp[i] > tmp[i - 1]:
				total += 1
		if total == k:
			ans[0] += 1
	print(ans[0])


import itertools
t = int(input())
while t > 0:
	t -= 1
	(n, k) = list(map(int, input().split()))
	a = [int(i) for i in input().split()]
	global_count = 0
	missing = []
	for i in range(0, n):
		missing.append(i + 1)
	for i in a:
		if i != 0:
			missing.remove(i)
	permutation_list = list(itertools.permutations(missing))
	temp_a = list(a)
	for i in range(0, len(permutation_list)):
		index = 0
		local_count = 0
		a = list(temp_a)
		for j in range(0, n):
			if a[j] == 0:
				a[j] = permutation_list[i][index]
				index += 1
		for j in range(1, n):
			if a[j] > a[j - 1]:
				local_count += 1
		if local_count == k:
			global_count += 1
	print(global_count)


import numpy as np

def allPerms(x):

	def ap(x):
		ret = []
		if len(x) == 1:
			return [[x[0]]]
		for i in range(len(x)):
			for a in ap(x[:i] + x[i + 1:]):
				ret += [[x[i]] + a]
		return ret
	return np.array(ap(list(range(1, x + 1))), dtype=np.int64)
AA = [[]]
SS = [[]]
for i in range(1, 9):
	AA += [allPerms(i)]
	x = AA[-1]
	y = np.sum(x[:, 1:] > x[:, :-1], 1)
	SS += [y]

def solve(x, k):
	x = np.array(x, dtype=np.int64)
	w = np.where(x > 0)[0]
	if len(w) == 0:
		b = SS[len(x)]
		return np.sum(b == k)
	a = AA[len(x)]
	w0 = np.where(np.sum(a[:, w] == x[np.newaxis, w], 1) == len(w))[0]
	b = SS[len(x)]
	return np.sum(b[w0] == k)
n = int(input())
for i in range(n):
	(x, k) = map(int, input().split())
	x = list(map(int, input().split()))
	print(solve(x, k))


from itertools import permutations
t = int(input())
while t:
	t -= 1
	(n, k) = [int(satish) for satish in input().split()]
	given = [int(satish) for satish in input().split()]
	arr = set()
	for i in range(1, n + 1):
		arr.add(i)
	for i in given:
		if i != 0:
			arr.discard(i)
	per = list(permutations(arr))
	cnt = 0
	for l in per:
		temp = list()
		(i, j, count) = (0, 0, 0)
		while i < len(given):
			if given[i] == 0:
				temp.append(l[j])
				j += 1
			else:
				temp.append(given[i])
			i += 1
		for i in range(1, len(temp)):
			if temp[i] > temp[i - 1]:
				count += 1
		if count == k:
			cnt += 1
	print(cnt)


import itertools
t = int(input())
while t != 0:
	t -= 1
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	numbers = []
	for i in range(1, n + 1):
		numbers.append(i)
	missing_indices = []
	index = 0
	for ele in a:
		if ele != 0:
			numbers.remove(ele)
		else:
			missing_indices.append(index)
		index += 1
	r = len(numbers)
	permu = list(itertools.permutations(numbers, r))
	times = len(permu)
	index = 0
	goods = []
	for i in range(times):
		complete_permu = list(a)
		p = permu[i]
		inside_index = 0
		for m in missing_indices:
			complete_permu[m] = p[inside_index]
			inside_index += 1
		goods.append(complete_permu)
	g = goods[0]
	lg = len(g)
	answer = 0
	for g in goods:
		good = 0
		for i in range(lg - 1):
			if g[i + 1] > g[i]:
				good += 1
		if good == k:
			answer += 1
	print(answer)


def solve(l):
	ans = 0
	for i in range(1, n):
		if l[i] > l[i - 1]:
			ans += 1
	return ans
from itertools import permutations
for i in range(int(input())):
	(n, k) = (int(s) for s in input().split())
	l = [int(s) for s in input().split()]
	l1 = []
	l2 = []
	count = 0
	for j in range(n):
		if l[j] != 0:
			l1.append(l[j])
		else:
			l2.append(j)
		if l[j] != 0 and l[j - 1] != 0:
			if l[j] - l[j - 1] > 0:
				count += 1
	if count > k:
		print(0)
	else:
		lw = []
		for v1 in range(1, n + 1):
			if v1 not in l1:
				lw.append(v1)
		x = list(permutations(lw))
		ans = 0
		for j in range(len(x)):
			v1 = 0
			for v in l2:
				l[v] = x[j][v1]
				v1 += 1
			if solve(l) == k:
				ans += 1
		print(ans)


import sys

def next_permutation(L):
	n = len(L)
	if n == 0:
		return False
	i = n - 2
	while i >= 0 and L[i] >= L[i + 1]:
		i -= 1
	if i == -1:
		return False
	j = i + 1
	while j < n and L[j] > L[i]:
		j += 1
	j -= 1
	(L[i], L[j]) = (L[j], L[i])
	left = i + 1
	right = n - 1
	while left < right:
		(L[left], L[right]) = (L[right], L[left])
		left += 1
		right -= 1
	return True

def check(a, ind, L, K):
	for (i, v) in zip(ind, L):
		a[i] = v
	count = 0
	for i in range(len(a) - 1):
		if a[i] < a[i + 1]:
			count += 1
	return count == K
T = int(sys.stdin.readline().strip())
for _ in range(T):
	(N, K) = sys.stdin.readline().split()
	K = int(K)
	N = int(N)
	found = set()
	ind = list()
	L = list()
	a = list()
	for (i, e) in enumerate(sys.stdin.readline().split()):
		e = int(e)
		if e == 0:
			ind.append(i)
		a.append(e)
		found.add(e)
	for i in range(N):
		if i + 1 in found:
			continue
		L.append(i + 1)
	count = 0
	while True:
		if check(a, ind, L, K):
			count += 1
		if not next_permutation(L):
			break
	print(count)


from itertools import permutations

def okay_or_not(l, n):
	ctr = 0
	for x in range(0, len(l) - 1):
		if l[x + 1] > l[x]:
			ctr += 1
	if ctr == n:
		return True
	else:
		return False
tc = int(input())
while tc:
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	d = list(map(int, input().strip().split(' ')))
	c = []
	for x in range(1, n + 1):
		c.append(x)
	for x in d:
		if x != 0:
			c.remove(x)
	ans = 0
	t = list(permutations(c))
	for x in t:
		counter = 0
		e = d[:]
		for y in range(0, n):
			if e[y] == 0:
				e[y] = x[counter]
				counter += 1
		if okay_or_not(e, k):
			ans += 1
	print(ans)
	tc -= 1


import itertools

def genperm(a, p, n):
	ip = 0
	for i in range(n):
		if a[i] == 0:
			a[i] = p[ip]
			ip += 1
	return a

def cans(a, n):
	c = 0
	for i in range(1, n):
		if a[i] > a[i - 1]:
			c += 1
	return c
for _ in range(int(input())):
	(N, K) = [int(j) for j in input().split()]
	A = [int(j) for j in input().split()]
	NZA = []
	ck = 0
	for nm in range(1, N + 1):
		if nm not in A:
			NZA.append(nm)
	for perm in itertools.permutations(NZA):
		BP = A[:]
		if cans(genperm(BP, perm, N), N) == K:
			ck += 1
	print(ck)


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 = 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)


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)


import numpy as np
import itertools
d = {i: 0 for i in range(8)}

def check(l):
	ct = 0
	for i in range(len(l) - 1):
		if l[i] < l[i + 1]:
			ct += 1
	d[ct] += 1
t = int(input())
while t:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	x = l.count(0)
	ll = []
	for i in range(1, n + 1):
		if i not in l:
			ll.append(i)
	ll = list(itertools.permutations(ll))
	for i in ll:
		lx = np.array(l)
		lx[lx == 0] = i
		check(lx)
	print(d[k])
	for i in d:
		d[i] = 0
	t -= 1


import itertools
for _ in range(int(input())):
	(a, b) = [int(j) for j in input().split()]
	l = [int(j) for j in input().split()]
	l1 = [int(j) for j in range(1, a + 1)]
	for i in l:
		if i != 0:
			l1.remove(i)
	l2 = list(itertools.permutations(l1, len(l1)))
	p = 0
	for i in l2:
		c = 0
		p1 = []
		for j in range(a):
			if l[j] == 0:
				p1.append(i[c])
				c += 1
			else:
				p1.append(l[j])
		u = 0
		for j in range(1, a):
			if p1[j] > p1[j - 1]:
				u += 1
		if u == b:
			p += 1
	print(p)


import itertools
t = int(input())
for test in range(t):
	(n, f) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	if n != 1:
		ind = [i for i in range(len(arr)) if arr[i] == 0]
		z = [i for i in range(1, n + 1) if i not in arr]
		z = list(itertools.permutations(z))
		x = []
		for i in z:
			k = 0
			for j in ind:
				arr[j] = i[k]
				k = k + 1
			x.append(arr[:])
		for i in x:
			s = 0
			for j in range(1, n):
				if i[j] > i[j - 1]:
					s += 1
			if s == f:
				ans += 1
		print(ans)
	else:
		print(1)


from itertools import permutations
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = set()
	ans1 = set()
	count2 = 0
	for i in range(n):
		ans.add(i + 1)
		if l[i] != 0:
			ans1.add(l[i])
	ans -= ans1
	need = list(permutations(list(ans)))
	for i in range(len(need)):
		cal = l[:]
		w = 0
		for j in range(len(cal)):
			if cal[j] == 0:
				cal[j] = need[i][w]
				w += 1
		count = 0
		for q in range(1, n):
			if cal[q] > cal[q - 1]:
				count += 1
		if count == k:
			count2 += 1
	print(count2)


from itertools import permutations

def main():
	T = int(input())

	def helper(s, k):
		ret = 0
		ind = 1
		l = len(s)
		while l - ind and l - ind >= k - ret:
			if s[ind - 1] < s[ind]:
				ret += 1
				if ret > k:
					return 0
			ind += 1
		if ret == k:
			return 1
		return 0

	def test(n, k, s):
		ret = 0
		e = []
		lst = [i + 1 for i in range(n)]
		for i in range(n):
			if s[i] == 0:
				e.append(i)
			else:
				lst.remove(s[i])
		lst = list(permutations(lst))
		for i in range(len(lst)):
			tem = lst[i]
			temp = s + []
			for j in range(len(e)):
				temp[e[j]] = tem[j]
			ret += helper(temp, k)
		return ret
	for i in range(T):
		(N, K) = list(map(int, input().split()))
		seq = list(map(int, input().split()))
		print(test(N, K, seq))
main()


import itertools
for i in range(int(input())):
	(n, f) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	ans = 0
	if n != 1:
		ind = [i for i in range(len(l)) if l[i] == 0]
		z = [i for i in range(1, n + 1) if i not in l]
		z = list(itertools.permutations(z))
		t = []
		for i in z:
			k = 0
			for j in ind:
				l[j] = i[k]
				k = k + 1
			t.append(l[:])
		for i in t:
			x = 0
			for j in range(1, n):
				if i[j] > i[j - 1]:
					x += 1
			if x == f:
				ans += 1
		print(ans)
	else:
		print(1)


import itertools

def f(nums, k):
	res = 0
	allpermutations = itertools.permutations(range(1, len(nums) + 1))
	for p in allpermutations:
		flag = True
		for (x, y) in zip(nums, p):
			if x != 0 and x != y:
				flag = False
				break
		if not flag:
			continue
		cnt = 0
		for i in range(1, len(p)):
			if p[i] > p[i - 1]:
				cnt += 1
		if cnt == k:
			res += 1
	return res

def main():
	T = int(input())
	for i in range(T):
		(n, k) = [int(i) for i in input().split()]
		numbers = [int(i) for i in input().split()]
		print(f(numbers, k))
main()


from itertools import permutations

def check(x, n):
	c = 0
	for i in range(n - 1):
		if x[i + 1] > x[i]:
			c += 1
	return c
t = int(input())
for i in range(t):
	x = input().split()
	n = int(x[0])
	k = int(x[1])
	x = input().split()
	count = 0
	A = [j for j in range(1, n + 1)]
	for j in range(n):
		x[j] = int(x[j])
		if x[j] != 0:
			A.remove(x[j])
	B = list(permutations(A))
	for j in B:
		a = 0
		pk = []
		for p in range(n):
			if x[p] == 0:
				pk.append(j[a])
				a += 1
			else:
				pk.append(x[p])
		if check(pk, n) == k:
			count += 1
	print(count)


from itertools import permutations as p

def validate(array, k, n):
	count = 0
	for z in range(1, n):
		if array[z] > array[z - 1]:
			count += 1
	if count == k:
		return True
	return False
t = int(input())
for ij in range(0, t):
	(n, k) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	count = 0
	has = [0] * (n + 1)
	ans = 0
	ind = []
	leng = 0
	for i in range(0, n):
		if a[i] == 0:
			ind.append(i)
			leng += 1
		if has[a[i]] == 1 and a[i] != 0:
			ans = -1
		else:
			has[a[i]] += 1
	if ans == -1:
		print(0)
	else:
		req = []
		for j in range(1, n + 1):
			if has[j] == 0:
				req.append(j)
		for f in p(req):
			m = list(f)
			e = list(a)
			for d in range(0, leng):
				e[ind[d]] = m[d]
			if validate(e, k, n):
				ans += 1
		print(ans)


def permute(elements):
	permutations = []
	if len(elements) == 1:
		return [elements]
	for i in range(len(elements)):
		m = elements[i]
		rlist = elements[:i] + elements[i + 1:]
		for p in permute(rlist):
			permutations.append([m] + p)
	return permutations
t = int(input())
for _ in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	arr = [int(x) for x in input().split()]
	if n == 1 and k == 0:
		print(1)
		continue
	elif n == 1 and k != 0:
		print(0)
		continue
	noz = 0
	ioz = [-1] * n
	yarr = [0] * n
	for x in range(n):
		if arr[x] == 0:
			ioz[noz] = x
			noz += 1
		else:
			yarr[arr[x] - 1] = 1
	missd = [i + 1 for i in range(n) if yarr[i] == 0]
	gp = 0
	if len(missd) == 0:
		cnt = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				cnt += 1
		if cnt == k:
			gp += 1
	else:
		pns = permute(missd)
		for p in pns:
			x = 0
			cnt = 0
			if ioz[x] == 0:
				arr[0] = p[x]
				x += 1
			for i in range(1, n):
				if ioz[x] == i:
					arr[i] = p[x]
					x += 1
				if arr[i] > arr[i - 1]:
					cnt += 1
			if cnt == k:
				gp += 1
	print(gp)


def permutation(lst):
	if len(lst) == 0:
		return []
	if len(lst) == 1:
		return [lst]
	l = []
	for i in range(len(lst)):
		m = lst[i]
		remLst = lst[:i] + lst[i + 1:]
		for p in permutation(remLst):
			l.append([m] + p)
	return l
t = int(input())
for i in range(0, t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	zero = 0
	zr = [-1] * n
	num = [0] * (n + 1)
	a = [int(j) for j in input().split()]
	for j in range(n):
		if a[j] == 0:
			zero += 1
			zr[zero - 1] = j
		else:
			num[a[j]] = 1
	miss = [-1] * zero
	tmp = 0
	for j in range(1, n + 1):
		if num[j] == 0:
			miss[tmp] = j
			tmp += 1
	if zero == 0:
		ctr = 0
		for j in range(1, n):
			if a[j] > a[j - 1]:
				ctr += 1
		if ctr == k:
			gp = 1
		else:
			gp = 0
	else:
		l = permutation(miss)
		gp = 0
		for lst in l:
			ctr = 0
			x = 0
			for m in lst:
				a[zr[x]] = m
				x += 1
			for j in range(1, n):
				if a[j] > a[j - 1]:
					ctr += 1
			if ctr == k:
				gp += 1
	print(gp)


import itertools as it
import collections

def construct(perm, a):
	perm = collections.deque(perm)
	ret = list(a)
	for i in range(len(ret)):
		if ret[i] == 0:
			ret[i] = perm.popleft()
	return ret

def inv(perm):
	ret = 0
	for i in range(1, len(perm)):
		if perm[i] > perm[i - 1]:
			ret += 1
	return ret
t = int(input())
for test in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for perm in it.permutations(set(range(1, n + 1)) - set(a)):
		if inv(construct(perm, a)) == k:
			ans += 1
	print(ans)


from itertools import permutations
t = int(input())
for _ in range(t):
	ans = 0
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ninv = [i for i in range(1, n + 1) if i not in arr]
	for i in permutations(ninv):
		(narr, c) = ([], 0)
		for j in range(0, n):
			if arr[j] != 0:
				narr += [arr[j]]
			else:
				narr += [i[c]]
				c += 1
		c = 0
		for j in range(0, n - 1):
			if narr[j] < narr[j + 1]:
				c += 1
		if k == c:
			ans += 1
	print(ans)


def isExactlyK(blanks, K):
	inv = 0
	for i in range(len(blanks) - 1):
		pi_1 = blanks[i]
		pi = blanks[i + 1]
		if pi_1 < pi:
			inv += 1
		if inv > K:
			return False
	return inv == K

def isLessThanEqualToK(blanks, K):
	inv = 0
	for i in range(len(blanks) - 1):
		pi_1 = blanks[i]
		pi = blanks[i + 1]
		if pi_1 == 0 or p_i == 0:
			continue
		if pi_1 < pi:
			inv += 1
		if inv > K:
			return False
	return inv <= K

def findp(blanks, letters, k):
	if letters == [] and isExactlyK(blanks, k):
		return 1
	elif letters == []:
		return 0
	perms = 0
	for i in range(len(letters)):
		letter = letters[i]
		letters = letters[:i] + letters[i + 1:]
		index = blanks.index(0)
		blanks[index] = letter
		perms += findp(blanks, letters, k)
		blanks[index] = 0
		letters = letters[:i] + [letter] + letters[i:]
	return perms

def Main():
	t = int(input())
	while t != 0:
		t -= 1
		(n, k) = [int(x) for x in input().split(' ')]
		blanks = [int(x) for x in input(' ').split(' ')]
		letters = [y for y in range(1, n + 1) if y not in blanks]
		good_perms = findp(blanks, letters, k)
		print(good_perms)
Main()