A cricket team consists of 11 players and some are good at batting, others are good at bowling and some of them are good at both batting and bowling. The batting coach wants to select exactly K players having maximum possible sum of scores. Given the batting score of each of the 11 players, find the number of ways in which we can select exactly K players such that the sum of their scores is the maximum possible. Two ways are different if there is a player who is selected in one of them is not in the other. See explanation of sample cases for more clarity.

------ Input ------ 

First line contains T, number of test cases ( 1 ≤ T ≤ 100 ). T cases follow, each having 2 lines. First line of each case contains scores of 11 players ( 1 ≤ score ≤ 100 ) and the second line contains K (1 ≤ K ≤ 11)

------ Output ------ 

For each test case, output the answer in a new line.

----- Sample Input 1 ------ 
2
1 2 3 4 5 6 7 8 9 10 11
3
2 5 1 2 4 1 6 5 2 2 1
6
----- Sample Output 1 ------ 
1
6
----- explanation 1 ------ 
Case 1 : Maximum possible sum of scores = 11 + 10 + 9 = 30 and can be achieved only by selecting the last 3 players. Only one possible way.
Case 2 : Maximum possible sum of scores = 6 + 5 + 5 + 4 + 2 + 2 = 24 and considering the players as p1 p2 p3 ... p11 in that order, the ones with maximum possible sum of scores is as follows
{p1, p2, p4, p5, p7, p8 }
{p10, p2, p4, p5, p7, p8 }
{p1, p2, p10, p5, p7, p8 }
{p9, p2, p4, p5, p7, p8 }
{p1, p2, p9, p5, p7, p8 }
{p10, p2, p9, p5, p7, p8 }

Difficulty: EASY

Starter code:

Solutions:
import math
for _ in range(int(input())):
	m = list(map(int, input().split()))
	n = int(input())
	m.sort()
	k = m[11 - n]
	l = m.count(k)
	c = 0
	for i in range(11 - n, 11):
		if m[i] == k:
			c += 1
		else:
			break
	print(math.comb(l, c))


import math
for _ in range(int(input())):
	L = sorted(list(map(int, input().split())), reverse=True)
	K = int(input())
	max_L = L[:K]
	res = 1
	buf_L = []
	for i in range(len(max_L)):
		if max_L[i] not in buf_L:
			res *= math.comb(L.count(max_L[i]), max_L.count(max_L[i]))
			buf_L.append(max_L[i])
	print(res)


from math import comb
for _ in range(int(input())):
	score = list(map(int, input().split()))
	k = int(input())
	score.sort(reverse=True)
	list_before_k = score[:k]
	temp = list_before_k[-1]
	(m, n) = (score.count(temp), list_before_k.count(temp))
	print(comb(m, n))


import math
for _ in range(int(input())):
	n = list(map(int, input().split()))
	k = int(input())
	n.sort()
	max_lst = n[-k:]
	min_ = max_lst[0]
	total_comb = math.comb(n.count(min_), max_lst.count(min_))
	print(total_comb)


facto_list = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000]

def combination(n, k):
	return facto_list[n] // (facto_list[k] * facto_list[n - k])
for _ in range(int(input())):
	a = sorted([int(x) for x in input().split()], reverse=True)
	k = int(input())
	d_bat = {}
	for i in a:
		d_bat[i] = d_bat.get(i, 0) + 1
	ans = 1
	d_bat = list(d_bat.values())
	i = 0
	while k > 0:
		if d_bat[i] > k:
			ans = combination(d_bat[i], k)
			break
		else:
			k -= d_bat[i]
			i += 1
	print(ans)


import math
for _ in range(int(input())):
	l = list(map(int, input().split()))
	x = int(input())
	l.sort()
	l1 = l[::-1]
	l2 = []
	for i in range(x):
		l2.append(l1[i])
	a = l1.count(min(l2)) - l2.count(min(l2))
	print(int(math.factorial(l1.count(min(l2))) / (math.factorial(a) * math.factorial(l2.count(min(l2))))))


def fac1(t):
	r = 1
	for i in range(2, t + 1):
		r = r * i
	return r
for _ in range(int(input())):
	l = list(map(int, input().split()))
	k = int(input())
	l.sort()
	p = l[11 - k]
	c = l[11 - k:].count(p)
	d = l.count(p)
	f = int(fac1(d) / (fac1(d - c) * fac1(c)))
	print(f)


import math
t = int(input())
for _ in range(t):
	l = [int(i) for i in input().split()]
	n = len(l)
	k = int(input())
	l.sort()
	m = l[11 - k]
	c1 = l.count(m)
	c = 0
	for i in range(11 - k, 11):
		if l[i] == m:
			c += 1
		else:
			break
	ans = math.comb(c1, c)
	print(ans)


from itertools import combinations
for _ in range(int(input())):
	r = []
	r = [sum(i) for i in combinations(map(int, input().split()), int(input()))]
	print(r.count(max(r)))


import math
t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	m = int(input())
	l.sort()
	k = l[11 - m]
	c1 = l.count(k)
	c = 0
	for i in range(11 - m, 11):
		if l[i] == k:
			c += 1
		else:
			break
	ans = math.comb(c1, c)
	print(ans)


import math
for tc in range(int(input())):
	l = list(map(int, input().split()))
	n = int(input())
	l.sort()
	x = l.count(l[-n])
	y = l[-n:].count(l[-n])
	print(math.comb(x, y))


import math
n = int(input())
for i in range(n):
	l = list(map(int, input().split()))
	k = int(input())
	l.sort(reverse=True)
	m = l[0:k]
	w = m[k - 1]
	k = l.count(w)
	s = m.count(w)
	print(math.comb(k, s))


def factorial(num):
	fact = 1
	while num > 1:
		fact = fact * num
		num = num - 1
	return fact
nTest = int(input())
for i in range(nTest):
	scores = list(map(int, input().split()))
	k = int(input())
	scores.sort(reverse=True)
	n = scores.count(scores[k - 1])
	r = scores[0:k].count(scores[k - 1])
	print(int(factorial(n) / (factorial(r) * factorial(n - r))))


for i in range(int(input())):
	list1 = list(map(int, input().split()))
	list1.sort(reverse=True)
	n = int(input())
	dict1 = {}
	for x in list1:
		if x not in dict1.keys():
			dict1[x] = 1
		else:
			dict1[x] += 1

	def factorial(x):
		product = 1
		while x > 0:
			product *= x
			x = x - 1
		return product
	total = 0
	list1 = list1[:n]
	for z in list1:
		count1 = dict1[z]
		count2 = list1.count(z)
		if count1 != count2:
			a = factorial(count1)
			b = factorial(count1 - count2)
			c = factorial(count2)
			total = a // (b * c)
	if total == 0:
		print(1)
	else:
		print(total)


import math
for _ in range(int(input())):
	lst = [int(x) for x in input().split()]
	k = int(input())
	lst.sort(reverse=True)
	n = lst[:k].count(lst[k - 1])
	m = lst.count(lst[k - 1])
	print(math.comb(m, n))


import math
t = int(input())
for _ in range(t):
	p = list(map(int, input().split()))
	n = int(input())
	p = sorted(p)
	mi = p[11 - n]
	c1 = p.count(mi)
	c = 0
	for i in range(11 - n, 11):
		if p[i] == mi:
			c += 1
		else:
			break
	print(math.comb(c1, c))


from collections import Counter

def c(n, r):
	return fact(n) / (fact(n - r) * fact(r))

def fact(m):
	if m == 0 or m == 1:
		return 1
	res = 1
	for i in range(2, m + 1):
		res *= i
	return res
for _ in range(int(input())):
	a = list(map(int, input().split()))
	k = int(input())
	a.sort()
	s = Counter(a)
	a = a[-k:]
	s2 = Counter(a)
	ans = 0
	for i in s2:
		if s[i] != s2[i]:
			ans += c(s[i], s2[i])
	if ans == 0:
		print(1)
	else:
		print(int(ans))


import math
for i in range(int(input())):
	li = list(map(int, input().split()))
	k = int(input())
	li.sort()
	m = li[11 - k]
	count = li.count(m)
	c = 0
	for j in range(11 - k, 11):
		if li[j] == m:
			c = c + 1
		else:
			break
	print(math.comb(count, c))


import math
n = int(input())
for _ in range(n):
	lis = list(map(int, input().split()))
	k = int(input())
	dic = {}
	for i in lis:
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	lis.sort(reverse=True)
	lis2 = lis[0:k]
	mainelement = lis2[k - 1]
	occurances = lis2.count(mainelement)
	print(math.comb(dic[mainelement], occurances))


for _ in range(int(input())):
	a = [int(x) for x in input().split()]
	k = int(input())
	a.sort(reverse=True)
	n = a.count(a[k - 1])
	c = 0
	cnt = 1
	j = 1
	for i in range(k):
		if a[i] == a[k - 1]:
			c += 1
	for i in range(c):
		cnt = cnt * (n - i) // j
		j += 1
	print(cnt)


from math import comb
for t in range(int(input())):
	pi = [int(i) for i in input().split()]
	n = int(input())
	pi.sort(reverse=True)
	l = pi.count(pi[:n][-1])
	r = pi[:n].count(pi[:n][-1])
	print(comb(l, r))


import math
t = int(input())
for tc in range(t):
	a = sorted(list(map(int, input().split())))
	b = int(input())
	s = []
	c = a[11 - b]
	for j in range(10, 10 - b, -1):
		s.append(a[j])
	print(math.comb(a.count(c), s.count(c)))


import math
t = int(input())
for _ in range(t):
	s = list(map(int, input().split()))
	k = int(input())
	if k == 11:
		print(1)
	else:
		s.sort()
		s1 = s[:11 - k]
		s2 = s[-k:]
		border = s2[0]
		c1 = s1.count(border)
		c2 = s2.count(border)
		print(math.comb(c1 + c2, c2))


factorial = [0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800]
for _ in range(int(input())):
	p = list(map(int, input().split()))
	k = int(input())
	p = sorted(p)
	a = p[-k:]
	n = p.count(a[0])
	r = a.count(a[0])
	if n - r == 0:
		output = 1
	else:
		output = factorial[n] // (factorial[r] * factorial[n - r])
	print(output)


def fact(n):
	if n == 0 or n == 1:
		return 1
	return n * fact(n - 1)
for _ in range(int(input())):
	lst = [int(x) for x in input().split()]
	k = int(input())
	lst.sort(reverse=True)
	n = lst[:k].count(lst[k - 1])
	m = lst.count(lst[k - 1])
	ans = int(fact(m) / (fact(n) * fact(m - n)))
	print(ans)


import math
for _ in range(int(input())):
	scoreList = list(map(int, input().split()))
	K = int(input())
	scoreList.sort(reverse=True)
	lowRun = scoreList[K - 1]
	countLow = scoreList.count(lowRun)
	end = K - 1
	while end < len(scoreList) and scoreList[end] == lowRun:
		end = end + 1
	print(math.comb(countLow, end - K))


import math
for i in range(int(input())):
	l = [int(i) for i in input().split()]
	n = len(l)
	k = int(input())
	l.sort()
	m = l[11 - k]
	x = l.count(m)
	c = 0
	for i in range(11 - k, 11):
		if l[i] == m:
			c += 1
		else:
			break
	print(math.comb(x, c))


import math

def ncr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
t = int(input())
while t != 0:
	players = list(map(int, input().split()))
	k = int(input())
	players.sort()
	n = 0
	r = 0
	idx = 11 - k
	for x in range(idx, 11):
		if players[x] == players[idx]:
			r += 1
	n = players.count(players[idx])
	print(ncr(n, r))
	t -= 1


import math as m
for _ in range(int(input())):
	lst = [int(x) for x in input().split()]
	k = int(input())
	lst.sort(reverse=True)
	lst2 = lst[:k]
	x = lst2[-1]
	(lstc, lst2c) = (lst.count(x), lst2.count(x))
	print(m.comb(lstc, lst2c))


def f(n):
	s = 1
	for i in range(n, 0, -1):
		s *= i
	return s
for _ in range(int(input())):
	l = list(map(int, input().split()))
	n = int(input())
	l.sort(reverse=True)
	l1 = l[:n]
	a = l.count(min(l1))
	b = l1.count(min(l1))
	re = f(a) // (f(a - b) * f(b))
	print(re)


import math
for _ in range(int(input())):
	scores = sorted(list(map(int, input().split())), reverse=True)
	k = int(input())
	a = scores[k - 1]
	b = scores.count(a)
	c = scores[:k].count(a)
	print(math.comb(b, c))


import math
for _ in range(int(input())):
	lis = [int(i) for i in input().split()]
	n = len(lis)
	x = int(input())
	lis.sort()
	m = lis[11 - x]
	c1 = lis.count(m)
	c = 0
	for i in range(11 - x, 11):
		if lis[i] == m:
			c += 1
		else:
			break
	print(math.comb(c1, c))


import math
for _ in range(int(input())):
	a = list(map(int, input().split()))
	k = int(input())
	a.sort(reverse=True)
	f1 = a.count(a[k - 1])
	f2 = a[:k].count(a[k - 1])
	print(math.factorial(f1) // (math.factorial(f2) * math.factorial(f1 - f2)))


import math
tc = int(input())
for _ in range(tc):
	a = list(map(int, input().split()))
	k = int(input())
	b = sorted(a)
	last = b[11 - k]
	c = []
	for i in range(10, 10 - k, -1):
		c.append(b[i])
	print(math.comb(b.count(last), c.count(last)))


import math
for _ in range(int(input())):
	a = sorted(list(map(int, input().split())))
	n = int(input())
	l = [a[i] for i in range(11 - n, 11)]
	m = l[0]
	print(math.comb(a.count(m), l.count(m)))


import math
for tc in range(int(input())):
	arr = list(map(int, input().split()))
	k = int(input())
	arr.sort(reverse=True)
	kmap = {}
	for ele in arr:
		if ele not in kmap:
			if len(kmap) < k:
				kmap[ele] = 1
			else:
				break
		else:
			kmap[ele] += 1
	chose = 0
	for ele in kmap:
		if chose + kmap[ele] < k:
			chose += kmap[ele]
		else:
			unsel = k - chose
			print(math.comb(kmap[ele], unsel))
			break


from itertools import permutations

def fac(n):
	if n < 2:
		return 1
	else:
		return n * fac(n - 1)
for i in range(int(input())):
	a = sorted(list(map(int, input().split())))
	n = int(input())
	a.reverse()
	count = 0
	count1 = 0
	for i in range(0, len(a)):
		if a[n - 1] == a[i]:
			count += 1
	for i in range(0, n):
		if a[n - 1] == a[i]:
			count1 += 1
	if count >= 2:
		print(int(fac(count) / (fac(count - count1) * fac(count1))))
	else:
		print(1)


import math
for _ in range(int(input())):
	n = list(map(int, input().split()))
	k = int(input())
	n.sort()
	max_lst = n[-k:]
	total_comb = 0
	for i in set(max_lst):
		comb = math.comb(n.count(i), max_lst.count(i))
		if comb > 1:
			total_comb += comb
	print(total_comb if total_comb != 0 else 1)