Chef has a sequence $A_1, A_2, \ldots, A_N$. This sequence has exactly $2^N$ subsequences. Chef considers a subsequence of $A$ interesting if its size is exactly $K$ and the sum of all its elements is minimum possible, i.e. there is no subsequence with size $K$ which has a smaller sum.
Help Chef find the number of interesting subsequences of the sequence $A$.

-----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, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of interesting subsequences.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le K \le N \le 50$
- $1 \le A_i \le 100$ for each valid $i$

-----Subtasks-----
Subtask #1 (30 points): $1 \le N \le 20$
Subtask #2 (70 points): original constraints

-----Example Input-----
1
4 2
1 2 3 4

-----Example Output-----
1

-----Explanation-----
Example case 1: There are six subsequences with length $2$: $(1, 2)$, $(1, 3)$, $(1, 4)$, $(2, 3)$, $(2, 4)$ and $(3, 4)$. The minimum sum is $3$ and the only subsequence with this sum is $(1, 2)$.

Difficulty: MEDIUM_HARD
Tags: Sorting

Combinatorics

Mathematics
Skill types: Sorting

Starter code:

Solutions:
from math import factorial
for x in range(int(input())):
	(k, n) = map(int, input().split(' '))
	ori_arr = [int(x) for x in input().split()]
	ori_arr.sort()
	cut_arr = ori_arr[:n]
	unq = list(set(cut_arr))
	freq_or = []
	freq_cut = []
	for x in unq:
		freq_or.append(ori_arr.count(x))
		freq_cut.append(cut_arr.count(x))
	summ = 1
	for x in range(len(unq)):
		N = factorial(freq_or[x])
		R = factorial(freq_cut[x])
		N_R = factorial(freq_or[x] - freq_cut[x])
		summ = summ * (N / (N_R * R))
	print(int(summ))


from itertools import combinations
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split(maxsplit=n)))
	y = list(combinations(x, k))
	z = []
	for i in range(len(y)):
		z.append(sum(y[i]))
	print(z.count(min(z)))


from math import factorial
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	num = l[k - 1]
	t = l.count(l[k - 1])
	r = l[:k].count(num)
	print(factorial(t) // (factorial(r) * factorial(t - r)))


from math import factorial
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.sort()
	x = 0
	y = 0
	for j in range(n):
		if l[j] == l[k - 1] and j < k:
			x += 1
		elif l[j] == l[k - 1] and j >= k:
			y += 1
		elif l[j] > l[k]:
			break
	s = int(factorial(x + y) // (factorial(x) * factorial(y)))
	print(s)


def fact(n):
	if n < 2:
		return 1
	return n * fact(n - 1)

def ncr(n, r):
	return fact(n) // (fact(r) * fact(n - r))
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	count_z = a.count(a[k - 1])
	count_z_seq = a[:k].count(a[k - 1])
	print(ncr(count_z, count_z_seq))


import math
t = int(input())

def t_min(li, k):
	x = 0
	for i in range(k):
		x += li[i]
	return x

def cnt(li, x):
	n = 0
	for i in li:
		if x == i:
			n += 1
	return n

def num_of_occur(li, k):
	z = li[k - 1]
	y = 0
	for i in range(k):
		if li[i] == z:
			y += 1
	return y

def factorials(z, y):
	return math.factorial(z) / (math.factorial(y) * math.factorial(z - y))
for a in range(t):
	(n, k) = [int(x) for x in input().split()]
	lis = [int(x) for x in input().split()]
	lis.sort()
	sumn = t_min(lis, k)
	y = num_of_occur(lis, k)
	z = cnt(lis, lis[k - 1])
	print(int(factorials(z, y)))


try:
	from math import factorial
	n = int(input())
	for _ in range(n):
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		l.sort()
		seq = l[:k]
		num = seq.count(seq[-1])
		c = l.count(seq[-1])
		answer = factorial(c) // (factorial(num) * factorial(c - num))
		print(answer)
except Exception as e:
	pass


def fact(n):
	res = 1
	for i in range(1, n + 1):
		res *= i
	return res
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	tot = 0
	for i in range(k):
		tot += arr[i]
	count = 0
	for i in range(n):
		if arr[i] == arr[k - 1]:
			count += 1
	orig_count = 0
	for i in range(k):
		if arr[i] == arr[k - 1]:
			orig_count += 1
	print(fact(count) // (fact(orig_count) * fact(count - orig_count)))


from collections import Counter
import operator as op
from functools import reduce

def nCr(n, r):
	r = min(n - r, r)
	num = reduce(op.mul, range(n, n - r, -1))
	den = reduce(op.mul, range(1, r + 1))
	return num // den
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = Counter(list(map(int, input().split())))
	(b, c) = (sorted(a), 1)
	i = 0
	while k > 0:
		k -= a[b[i]]
		i += 1
	if k == 0:
		print(1)
	else:
		print(nCr(a[b[i - 1]], abs(k)))


import math as m
for i in range(int(input())):
	(y, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	count = x
	x -= 1
	while x > 0 and l[x - 1] == l[x]:
		x = x - 1
	box = count - x
	upper = m.factorial(l.count(l[count - 1]))
	lower = m.factorial(box)
	mid = m.factorial(abs(l.count(l[count - 1]) - box))
	print(upper // (lower * mid))


from math import factorial as fact
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	y = list(map(int, input().split()))
	y.sort()
	k1 = []
	for i in range(len(y)):
		if i > k - 1:
			if y[i] != k1[-1]:
				break
			else:
				k1.append(y[i])
		else:
			k1.append(y[i])
	c = k1[k - 1]
	ans = 0
	for i in range(k):
		if k1[i] == c:
			ans += 1
	ans2 = k1.count(c)
	print(fact(ans2) // (fact(ans) * fact(ans2 - ans)))
	t -= 1


import itertools
t = int(input())
for i in range(t):

	def subset(num, k):
		return list(itertools.combinations(num, k))
	(n, k) = list(map(int, input().split()))
	num = list(map(int, input().split()))
	y = subset(num, k)
	num1 = []
	for i in range(len(y)):
		num1.append(sum(y[i]))
	x = min(num1)
	print(num1.count(x))


import math

def nCr(n, r):
	return int(math.factorial(n) / (math.factorial(r) * math.factorial(n - r)))
t = int(input())
while t:
	(n, k) = map(int, input().split())
	ele = input().split()
	arr = [int(j) for j in ele]
	set_arr = set(arr)
	count = []
	for i in sorted(set_arr):
		count.append(arr.count(i))
	if k < count[0]:
		print(nCr(count[0], k))
	elif k == count[0]:
		print(1)
	else:
		ind = -1
		summ = 0
		while summ < k:
			ind += 1
			summ += count[ind]
		req = summ - k
		print(nCr(count[ind], req))
	t -= 1


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	x = l.count(l[k - 1])
	y = l[:k].count(l[k - 1])
	a = 1
	b = 1
	for j in range(x - y + 1, x + 1):
		a *= j
	for z in range(1, y + 1):
		b *= z
	print(a // b)


from math import factorial
t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	l.sort()
	s = l[k - 1]
	a = l.count(s)
	b = l[:k].count(s)
	print(factorial(a) // (factorial(a - b) * factorial(b)))


from math import factorial
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	num = a[k - 1]
	t = a.count(a[k - 1])
	r = a[:k].count(num)
	print(factorial(t) // (factorial(r) * factorial(t - r)))


def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
import sys
from collections import Counter
fact = [0] * 51
fact[0] = 1
for i in range(1, 51):
	fact[i] = fact[i - 1] * i

def main():
	lst.sort()
	seq = lst[:k]
	dct2 = Counter(seq)
	dct = Counter(lst)
	ans = 1
	for ele in dct2:
		ele_req = dct2[ele]
		ele_av = dct[ele]
		ans *= fact[ele_av] // (fact[ele_req] * fact[ele_av - ele_req])
	print(ans)
t = int(input())
for _ in range(t):
	(n, k) = integer_list()
	lst = integer_list()
	main()


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = sorted(arr)
	l = arr[:k].count(arr[k - 1])
	m = arr.count(arr[k - 1])
	print(math.factorial(m) // (math.factorial(l) * math.factorial(m - l)))


from math import factorial as fact
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	hash_arr = [0 for i in range(101)]
	for i in l:
		hash_arr[i] += 1
	r = 1
	for j in hash_arr:
		if j <= k:
			k -= j
		else:
			r *= fact(j) / (fact(k) * fact(j - k))
			k -= j
		if k < 0:
			break
	print(int(r))


from math import factorial
from typing import List
ncr = lambda n, r: factorial(n) // (factorial(r) * factorial(n - r))

def soln(n: int, k: int, arr: List[int]) -> int:
	arr.sort()
	return ncr(arr.count(arr[k - 1]), arr[:k].count(arr[k - 1]))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(soln(n, k, arr))


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	I = a[:k]
	b = I.count(a[k - 1])
	c = a.count(a[k - 1])
	res = math.factorial(c) // (math.factorial(b) * math.factorial(c - b))
	print(res)


from math import factorial
for t in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	q = l[:k]
	a = q.count(q[-1])
	b = l.count(q[-1])
	print(factorial(b) // (factorial(a) * factorial(b - a)))


import math
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	arr.sort()
	a = arr[:k]
	temp = arr[k - 1]
	s1 = arr.count(temp)
	s2 = a.count(temp)
	ans = math.factorial(s1)
	ans = ans // (math.factorial(s1 - s2) * math.factorial(s2))
	print(ans)


from math import factorial as fact
for _ in range(0, int(input())):
	(N, K) = list(map(int, input().split()))
	Amain = list(map(int, input().split()))
	Amain.sort()
	Asub = Amain[:K]
	n = Amain.count(Amain[K - 1])
	r = Asub.count(Amain[K - 1])
	Ans = fact(n) // (fact(r) * fact(n - r))
	print(Ans)


def sort(array):
	new_list = []
	for num in array:
		start = 0
		end = len(new_list)
		while start < end:
			mid = (start + end) // 2
			if new_list[mid] > num:
				end = mid
			else:
				start = mid + 1
		new_list.insert(start, num)
	return new_list
tests = int(input())
for _ in range(tests):
	(n, k) = [int(j) for j in input().split()]
	nums = [int(j) for j in input().split()]
	sorted_nums = sort(nums)
	value = sorted_nums[k - 1]
	repeats = 0
	for i in range(k):
		if sorted_nums[i] == value:
			repeats += 1
	size = repeats
	for i in range(k, n):
		if sorted_nums[i] == value:
			size += 1
	fact = [1 for _ in range(size + 1)]
	for i in range(1, size + 1):
		fact[i] = i * fact[i - 1]
	print(fact[size] // (fact[repeats] * fact[size - repeats]))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def factorial(n, r):
	p = 1
	k = 1
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			p *= n
			k *= r
			y = gcd(p, k)
			p //= y
			k //= y
			n -= 1
			r -= 1
	return p
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	num = l[k - 1]
	t = l.count(num)
	r = l[:k].count(num)
	print(factorial(t, r))


comb = [[0 for i in range(51)] for j in range(51)]
for i in range(51):
	comb[i][0] = 1
for i in range(1, 51):
	for j in range(1, 51):
		comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1]
test = int(input())
while test > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	b = a[:k]
	print(comb[a.count(b[-1])][b.count(b[-1])])
	test -= 1


from math import factorial
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	nli = sorted(list(map(int, input().split())))
	inq_lst = nli[:k]
	nm = inq_lst[-1]
	cnt = inq_lst.count(nm)
	cnt2 = nli.count(nm)
	a = factorial(cnt2)
	b = factorial(cnt) * factorial(cnt2 - cnt)
	print(a // b)


def fact(n):
	if n == 0 or n == 1:
		return 1
	ans = 1
	for i in range(2, n + 1):
		ans *= i
	return ans

def nCr(n, r):
	return int(fact(n) / (fact(r) * fact(n - r)))
for t in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	a = A[:k]
	if a[-1] == a[0]:
		temp = A.count(a[0])
		if temp > k:
			print(nCr(temp, k))
		else:
			print(1)
	else:
		temp = A.count(a[-1])
		if temp > a.count(a[-1]):
			print(nCr(temp, a.count(a[-1])))
		else:
			print(1)


import math as m
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k == n:
		print(1)
	elif n == 1:
		print(1)
	elif k == 1:
		print(arr.count(min(arr)))
	else:
		arr = sorted(arr)
		arr1 = arr[:k]
		c = max(arr1)
		a = arr1.count(c)
		b = arr.count(c)
		ans = m.factorial(b) // (m.factorial(a) * m.factorial(b - a))
		print(ans)


def fact(n):
	factsum = 1
	for i in range(1, n + 1):
		factsum *= i
	return factsum
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	lst = sorted(list(map(int, input().split())))
	s = 0
	ke = 0
	for i in range(k):
		s += lst[i]
		if lst[i] == lst[k - 1]:
			ke += 1
	kt = 0
	for i in range(n):
		if lst[i] == lst[k - 1]:
			kt += 1
	print(fact(kt) // (fact(ke) * fact(kt - ke)))


tests = int(input())
for _ in range(tests):
	(n, k) = [int(j) for j in input().split()]
	nums = [int(j) for j in input().split()]
	sorted_nums = list(nums)
	sorted_nums.sort()
	value = sorted_nums[k - 1]
	repeats = 0
	for i in range(k):
		if sorted_nums[i] == value:
			repeats += 1
	size = repeats
	for i in range(k, n):
		if sorted_nums[i] == value:
			size += 1
	fact = [1 for _ in range(size + 1)]
	for i in range(1, size + 1):
		fact[i] = i * fact[i - 1]
	print(fact[size] // (fact[repeats] * fact[size - repeats]))


import itertools
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	num = list(map(int, input().split(maxsplit=n)))
	y = list(itertools.combinations(num, k))
	num1 = []
	for i in range(len(y)):
		num1.append(sum(y[i]))
	print(num1.count(min(num1)))


import math as m
for i in range(int(input())):
	(y, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	if len(set(l)) == 1:
		upper = m.factorial(l.count(l[0]))
		lower = m.factorial(x)
		mid = m.factorial(abs(l.count(l[0]) - x))
		print(upper // (lower * mid))
	else:
		count = x
		x -= 1
		while l[x - 1] == l[x]:
			x = x - 1
		box = count - x
		upper = m.factorial(l.count(l[count - 1]))
		lower = m.factorial(box)
		mid = m.factorial(abs(l.count(l[count - 1]) - box))
		print(upper // (lower * mid))


def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = sorted(arr)
	last_index_of_k = arr[k - 1]
	count = 0
	for i in range(n):
		if arr[i] == last_index_of_k:
			count += 1
	num = 0
	for i in range(k):
		if arr[i] == last_index_of_k:
			num += 1
	print(int(nCr(count, num)))


import math as m
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	lst1 = lst[:k]
	n = lst.count(max(lst1))
	r = lst1.count(max(lst1))
	print(int(m.factorial(n) / (m.factorial(n - r) * m.factorial(r))))


from math import factorial
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	l = arr[k - 1]
	x = 0
	for i in range(k - 1, -1, -1):
		if arr[i] == l:
			x += 1
	num = arr.count(l)
	print(int(factorial(num) / (factorial(x) * factorial(num - x))))


C = [1, 1]
for i in range(2, 51):
	C += [C[-1] * i]
for _ in range(int(input())):
	(N, K) = [int(i) for i in input().split(' ')]
	A = [int(i) for i in input().split(' ')]
	A.sort()
	B = {}
	for i in range(N):
		if A[i] in B:
			B[A[i]] += 1
		else:
			B[A[i]] = 1
	count = 1
	for i in B:
		if K < B[i]:
			count = C[B[i]] // (C[B[i] - K] * C[K])
			break
		K -= B[i]
	print(count)


from math import factorial as fact
t = int(input())
for _ in range(0, t):
	(n, k) = map(int, input().split())
	fg = list(map(int, input().split()))
	fg.sort()
	f = fg[:k]
	a = f.count(f[-1])
	b = fg.count(f[-1])
	lp = fact(b) // (fact(a) * fact(b - a))
	print(lp)


from math import factorial
try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		l.sort()
		num = l[k - 1]
		t = l.count(l[k - 1])
		r = l[:k].count(num)
		print(factorial(t) // (factorial(r) * factorial(t - r)))
except:
	pass


from math import factorial
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	l = arr[k - 1]
	p = arr[:k].count(l)
	num = arr.count(l)
	print(int(factorial(num) / (factorial(p) * factorial(num - p))))


from math import factorial
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	num = a[k - 1]
	r = a[:k].count(num)
	t = a.count(num)
	print(int(factorial(t) / (factorial(r) * factorial(t - r))))


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	y = list(map(int, input().split()))
	y.sort()
	k1 = []
	for i in range(len(y)):
		if i > k - 1:
			if y[i] != k1[-1]:
				break
			else:
				k1.append(y[i])
		else:
			k1.append(y[i])
	from itertools import combinations
	ans = list(combinations(k1, k))
	l = []
	for i in ans:
		l.append(sum(i))
	print(l.count(min(l)))
	t -= 1


import math
y = lambda x: math.factorial(x)

def combinations(n, r):
	return y(n) // (y(r) * y(n - r))
for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	good = arr[:k]
	last = good[-1]
	count_total = arr.count(last)
	count_mini = good.count(last)
	print(combinations(count_total, count_mini))


def fact(n):
	if n == 0 or n == 1:
		return 1
	ans = 1
	for i in range(2, n + 1):
		ans *= i
	return ans

def nCr(n, r):
	return int(fact(n) / (fact(r) * fact(n - r)))
t = int(input())
while t:
	(n, k) = map(int, input().split())
	ele = input().split()
	arr = [int(j) for j in ele]
	set_arr = set(arr)
	count = []
	for i in sorted(set_arr):
		count.append(arr.count(i))
	if k < count[0]:
		print(nCr(count[0], k))
	elif k == count[0]:
		print(1)
	else:
		ind = -1
		summ = 0
		while summ < k:
			ind += 1
			summ += count[ind]
		req = summ - k
		print(nCr(count[ind], req))
	t -= 1


def fattoriale(n):
	p = 1
	for i in range(2, n + 1):
		p *= i
	return p
tests = int(input())
for _ in range(tests):
	(N, K) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))[:N]
	Q = [0] * 100
	for elem in arr:
		Q[elem - 1] += 1
	i = -1
	while K > 0:
		i += 1
		K -= Q[i]
	coeff = int(fattoriale(Q[i]) / (fattoriale(K + Q[i]) * fattoriale(-K)))
	print(coeff)


from math import factorial
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	b = a[:k]
	c1 = b.count(b[-1])
	c2 = a.count(b[-1])
	print(factorial(c2) // (factorial(c1) * factorial(c2 - c1)))


from math import factorial

def nCr(a, b):
	res = factorial(a) / (factorial(b) * factorial(a - b))
	return res
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	alist = list(map(int, input().split()))
	slist = sorted(alist)
	reps = 0
	count = 0
	maxm = 0
	for i in range(k):
		maxm = max(maxm, slist[i])
	for i in range(n):
		if slist[i] == maxm:
			count += 1
	for i in range(k):
		if slist[i] == maxm:
			reps += 1
	print(int(nCr(count, reps)))


def ncr(n, r):
	c = list()
	for i in range(0, n + 1):
		l = list()
		for j in range(0, r + 1):
			l.append(0)
		c.append(l)
	for i in range(0, n + 1):
		for j in range(0, min(i, r) + 1):
			if j == 0 or j == i:
				c[i][j] = 1
			elif j == 1 or j == i - 1:
				c[i][j] = i
			else:
				c[i][j] = c[i - 1][j] + c[i - 1][j - 1]
	return c[n][r]
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l = sorted(l)
	m = max(l[:k])
	m_count = l[:k].count(m)
	total_count = l.count(m)
	print(ncr(total_count, m_count))


import math
t = int(input())
while t > 0:
	t -= 1
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	if k <= n:
		c = a.count(a[k - 1])
		d = a[:k].count(a[k - 1])
		e = math.factorial(c) // (math.factorial(d) * math.factorial(c - d))
		print(e)
	else:
		print(0)


import math
y = lambda x: math.factorial(x)

def combinations(n, r):
	return y(n) // (y(r) * y(n - r))
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	good = A[:K]
	last = good[-1]
	count_total = A.count(last)
	count_mini = good.count(last)
	print(combinations(count_total, count_mini))


from functools import reduce
from math import factorial as f
comb = lambda n, r: f(n) // (f(r) * f(n - r))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	xs = sorted(map(int, input().split()))
	us = list(set(xs[:k]))
	total = (xs.count(u) for u in us)
	required = (xs[:k].count(u) for u in us)
	print(reduce(lambda x, y: x * y, (comb(t, r) for (t, r) in zip(total, required))))


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
inf = 10 ** 19

def ncr(a, b):
	ans = 1
	if b == 0:
		return 1
	if b == 1:
		return a
	for i in range(b):
		ans *= a - i
	for i in range(b):
		ans //= i + 1
	return ans
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.sort()
	lst = l[:k]
	last = lst[-1]
	n1 = l.count(last)
	n2 = lst.count(last)
	print(int(ncr(n1, n2)))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	kl = arr[:k].count(arr[k - 1])
	kler = arr.count(arr[k - 1])
	print(math.factorial(kler) // (math.factorial(kl) * math.factorial(kler - kl)))


from math import factorial
i = int(input())
for _ in range(i):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	c.sort()
	p = c[b - 1]
	f = c.count(p)
	e = c[:b].count(p)
	print(factorial(f) // (factorial(e) * factorial(f - e)))


t = int(input())
while t:
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	nis = 1
	while k:
		nm = a.count(min(a))
		if nm >= k:
			for i in range(k):
				nis *= nm - i
			kf = 1
			for i in range(2, k + 1):
				kf *= i
			nis /= kf
			break
		else:
			k -= nm
			a = [x for x in a if x != min(a)]
	print(int(nis))
	t -= 1


from math import factorial as fact
for x in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	num = a[k - 1]
	t = a.count(a[k - 1])
	r = a[:k].count(num)
	print(fact(t) // (fact(r) * fact(t - r)))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = sorted(list(map(int, input().split())))
	i = x.count(x[k - 1])
	j = x[:k].count(x[k - 1])
	a = b = 1
	for i in range(i - j + 1, i + 1):
		a *= i
	for j in range(1, j + 1):
		b *= j
	print(a // b)