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: interview

Starter code:

Solutions:
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)))


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


import math
def fact(n):
 return math.factorial(n)
t=int(input())
for _ in range(t):
 n,k=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 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

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

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

# cook your dish here
# cook your dish here
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)))


# cook your dish here
# cook your dish here
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)))
  
  
 


# cook your dish here
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 itertools import combinations
for i in range(int(input())):
 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 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)))

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

# cook your dish here
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)))

# cook your dish here
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)))

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

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

# cook your dish here
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()
 x=0
 y=0
 if k>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-1]:
    break
  s=int((factorial(x+y))//((factorial(x))*factorial(y)))
  print(s)
 else:
  print(1)

# cook your dish here
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)


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


# cook your dish here
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))