Maheshmati and Sangu are playing a game. First, Maheshmati gives Sangu a sequence of $N$ distinct integers $a_1, a_2, \dots, a_N$ (not necessarily sorted) and an integer $K$. Sangu has to create all subsequences of this sequence with length $K$. For each subsequence, he has to write down the product of $K-2$ integers: all elements of this subsequence except the minimum and maximum element.
Sangu wins the game if he is able to write down all these numbers and tell Maheshmati their product (modulo $10^9+7$, since it can be very large). However, Sangu is a very lazy child and thus wants you to help him win this game. Compute the number Sangu should tell Maheshmati!

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

-----Output-----
For each test case, print a single line containing one integer — the product of all numbers written down by Sangu modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 10$
- $3 \le N \le 5,000$
- $3 \le K \le N$
- $1 \le a_i \le 10,000$ for each valid $i$
- the numbers $a_1, a_2, \dots, a_N$ are pairwise distinct

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

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

-----Example Output-----
36

-----Explanation-----
Example case 1: There are four possible subsequences:
- $[1, 2, 3]$ (Sangu should write down $2$.)
- $[1, 3, 4]$ (Sangu should write down $3$.)
- $[1, 2, 4]$ (Sangu should write down $2$.)
- $[2, 3, 4]$ (Sangu should write down $3$.)
The required product is $2 \cdot 3 \cdot 2 \cdot 3 = 36$.

Difficulty: interview

Starter code:

Solutions:
f = 5003*[0]
modn = 1000000007


def qPow(a, b):
 nonlocal modn
 res = 1
 while b > 0:
  if (b & 1) == 1:
   res = res * a % modn
  a = a * a % modn
  b = b >> 1
 return res


def getF():
 nonlocal f
 f[0] = 1
 for i in range(1, 5001):
  f[i] = f[i-1] * i


def __starting_point():
 getF()
 T = int(input())
 while T > 0:
  T = T - 1
  n, k = list(map(int,input().split()))
  lis = list(map(int, input().split()))
  lis = sorted(lis)
  res = 1
  for i in range(n):
   zhi = f[n-1]//f[k-1]//f[n-k]
   if i >= k-1:
    zhi = zhi - f[i]//f[k-1]//f[i+1-k]
   if n-i-1 >= k-1:
    zhi = zhi - f[n-i-1]//f[k-1]//f[n-i-k]
   zhi = zhi % (modn-1)
   # print(zhi)
   res = res * qPow(lis[i], zhi) % modn
  print(res)

__starting_point()

# cook your dish here
MOD = (10**9) + 7

def ncr(n, r, p): 
 # initialize numerator 
 # and denominator 
 num = den = 1 
 for i in range(r): 
  num = (num * (n - i)) % p 
  den = (den * (i + 1)) % p 
 return (num * pow(den,  
   p - 2, p)) % p 

for _ in range(int(input())):
 
 n , k = list(map( int, input().split()))
 
 arr = list( map( int, input().split()) )
 
 arr = sorted(arr)
 
 value = ncr(n-1,k-1,MOD)
 
 ans = 1
 
 
 
 for x in range(1,n-1):
  
  if (n - x - 1) >= (k-1) :
   
   temp1 = ncr(n-x-1,k-1,MOD)
  else:
   temp1 = 0
   
  if x >= (k-1):
   
   temp2 = ncr(x,k-1,MOD)
  else:
   temp2 = 0 
   
   
  # print(value,ans,temp1,temp2)
  ans = ( ans * (arr[x]**( value - temp2 - temp1 )) )%MOD
  
 print(ans)
   
  
  
 


# cook your dish here
MOD = (10**9) + 7

def ncr(n, r, p): 
 # initialize numerator 
 # and denominator 
 num = den = 1 
 for i in range(r): 
  num = (num * (n - i)) % p 
  den = (den * (i + 1)) % p 
 return (num * pow(den,  
   p - 2, p)) % p 

for _ in range(int(input())):
 
 n , k = list(map( int, input().split()))
 
 arr = list( map( int, input().split()) )
 
 arr = sorted(arr)
 
 value = ncr(n-1,k-1,MOD)
 
 ans = 1
 
 
 
 for x in range(1,n-1):
  
  if (n - x - 1) >= (k-1) :
   
   temp1 = ncr(n-x-1,k-1,MOD)
  else:
   temp1 = 0
   
  if x >= (k-1):
   
   temp2 = ncr(x,k-1,MOD)
  else:
   temp2 = 0 
   
   
  # print(value,ans,temp1,temp2)
  ans = ( ans * (arr[x]**( value - temp2 - temp1 )) )%MOD
  
 print(ans)
   
  
  
 


# cook your dish here
MOD = (10**9) + 7

def nCrModpDP(n, r, p): 
  
 # The array C is going to store 
 # last row of pascal triangle 
 # at the end. And last entry  
 # of last row is nCr 
 C = [0] * (n + 1); 
 
 # Top row of Pascal Triangle 
 C[0] = 1;  
 
 # One by constructs remaining  
 # rows of Pascal Triangle from  
 # top to bottom 
 for i in range(1, (n + 1)): 
   
  # Fill entries of current  
  # row using previous row 
  # values 
  j = min(i, r);  
  while(j > 0): 
   C[j] = (C[j] + C[j - 1]) % p; 
   j -= 1; 
 return C[r]; 
 
# Lucas Theorem based function that   
# returns nCr % p. This function 
# works like decimal to binary  
# conversion recursive function. 
# First we compute last digits of  
# n and r in base p, then recur 
# for remaining digits 
def nCrModpLucas(n, r, p): 
  
 # Base case 
 if (r == 0): 
  return 1; 
   
 # Compute last digits of n 
 # and r in base p 
 ni = int(n % p); 
 ri = int(r % p); 
   
 # Compute result for last digits  
 # computed above, and for remaining  
 # digits. Multiply the two results  
 # and compute the result of  
 # multiplication in modulo p. 
 # Last digits of n and r 
 return (nCrModpLucas(int(n / p), int(r / p), p) * 
   nCrModpDP(ni, ri, p)) % p;

for _ in range(int(input())):
 
 n , k = list(map( int, input().split()))
 
 arr = list( map( int, input().split()) )
 
 arr = sorted(arr)
 
 value = nCrModpLucas(n-1,k-1,MOD)
 
 ans = 1
 
 
 
 for x in range(1,n-1):
  
  if (n - x - 1) >= (k-1) :
   
   temp1 = nCrModpLucas(n-x-1,k-1,MOD)
  else:
   temp1 = 0
   
  if x >= (k-1):
   
   temp2 = nCrModpLucas(x,k-1,MOD)
  else:
   temp2 = 0 
   
   
  # print(value,ans,temp1,temp2)
  ans = ( ans * (arr[x]**( value - temp2 - temp1 )) )%MOD
  
 print(ans)
   
  
  
 


# cook your dish here
MOD = (10**9) + 7

def binomialCoefficient(n, r, p): 

 # The array C is going to store last row of 
 # pascal triangle at the end. And last entry 
 # of last row is nCr. 
 C = [0 for i in range(r+1)] 
 
 C[0] = 1 # Top row of Pascal Triangle 
 
 # One by constructs remaining rows of Pascal 
 # Triangle from top to bottom 
 for i in range(1, n+1): 
 
  # Fill entries of current row  
  # using previous row values 
  for j in range(min(i, r), 0, -1): 
 
   # nCj = (n - 1)Cj + (n - 1)C(j - 1) 
   C[j] = (C[j] + C[j-1]) % p 
 
 return int(C[r])

for _ in range(int(input())):
 
 n , k = list(map( int, input().split()))
 
 arr = list( map( int, input().split()) )
 
 arr = sorted(arr)
 
 value = binomialCoefficient(n-1,k-1,MOD)
 
 ans = 1
 
 
 
 for x in range(1,n-1):
  
  if (n - x - 1) >= (k-1) :
   
   temp1 = binomialCoefficient(n-x-1,k-1,MOD)
  else:
   temp1 = 0
   
  if x >= (k-1):
   
   temp2 = binomialCoefficient(x,k-1,MOD)
  else:
   temp2 = 0 
   
   
  # print(value,ans,temp1,temp2)
  ans = ( ans * (arr[x]**( value - temp2 - temp1 )) )%MOD
  
 print(ans)
   
  
  
 


# cook your dish here
MOD = (10**9) + 7

def binomialCoefficient(n, k): 
 # since C(n, k) = C(n, n - k) 
  # Declaring an empty array 
 C = [0 for i in range(k+1)] 
 C[0] = 1 #since nC0 is 1 
 
 for i in range(1,n+1): 
 
  # Compute next row of pascal triangle using 
  # the previous row 
  j = min(i ,k) 
  while (j>0): 
   C[j] = C[j] + C[j-1] 
   j -= 1
 
 return int(C[k] )

for _ in range(int(input())):
 
 n , k = list(map( int, input().split()))
 
 arr = list( map( int, input().split()) )
 
 arr = sorted(arr)
 
 value = binomialCoefficient(n-1,k-1)
 
 ans = 1
 
 
 
 for x in range(1,n-1):
  
  if (n - x - 1) >= (k-1) :
   
   temp1 = binomialCoefficient(n-x-1,k-1)
  else:
   temp1 = 0
   
  if x >= (k-1):
   
   temp2 = binomialCoefficient(x,k-1)
  else:
   temp2 = 0 
   
   
  # print(value,ans,temp1,temp2)
  ans = ( ans * (arr[x]**( value - temp2 - temp1 )) )%MOD
  
 print(ans)
   
  
  
 


# cook your dish here
MOD = (10**9) + 7

def binomialCoefficient(n, k): 
 # since C(n, k) = C(n, n - k) 
 if(k > n - k): 
  k = n - k 
 # initialize result 
 res = 1
 # Calculate value of  
 # [n * (n-1) *---* (n-k + 1)] / [k * (k-1) *----* 1] 
 for i in range(k): 
  res = res * (n - i) 
  res = res / (i + 1) 
 return int(res) 

for _ in range(int(input())):
 
 n , k = list(map( int, input().split()))
 
 arr = list( map( int, input().split()) )
 
 arr = sorted(arr)
 
 value = binomialCoefficient(n-1,k-1)
 
 ans = 1
 
 
 
 for x in range(1,n-1):
  
  if (n - x - 1) >= (k-1) :
   
   temp1 = binomialCoefficient(n-x-1,k-1)
  else:
   temp1 = 0
   
  if x >= (k-1):
   
   temp2 = binomialCoefficient(x,k-1)
  else:
   temp2 = 0 
   
   
  # print(value,ans,temp1,temp2)
  ans = ( ans * (arr[x]**( value - temp2 - temp1 )) )%MOD
  
 print(ans)
   
  
  
 


# cook your dish here

from itertools import combinations


for i in range(int(input())) :
 
 n , k = list(map(int,input().split()))
 
 arr = list(map(int,input().split()))
 
 arr.sort()
 
 sub = [arr[i] for i in range(1,n-1)]
 
 comb = combinations(sub,k-2) 
 
 prod = 1
 
 #print(list(comb))
 
 for i in list(comb) :
  
  maximum = max(i)
  
  minimum = min(i)
  
  
  ind_max , ind_min = arr.index(maximum) , arr.index(minimum) 
  
  
  
  aftermax = n - ind_max - 1 
  
  beforemin = ind_min 
  
  
  
  temp = aftermax * beforemin
  
  for j in i :
   
   
   
   prod = prod * (j**temp)
   
 print(prod % (10**9 + 7))
   
   
   
   
   
   
  
  
  
  
  
  
  
  
  
  
  
 
 
 
 
 
 


MOD=10**9+7
p=100000
fact=[0]*p 
fact[0]=1 
for i in range(1,p):
 fact[i]=(fact[i-1]*i)%MOD
def MI(a,MOD):
 return pow(a,MOD-2,MOD)
def nck(n, k,MOD):
 if n==k or k==0:
  return 1 
 if n<k:
  return 0 
 return (fact[n]*MI(fact[k],MOD)%MOD*MI(fact[n-k],MOD)%MOD)%MOD
for _ in range(int(input())):
 n,k=map(int,input().split())
 prod=1
 l=[int(i) for i in input().split()]
 l.sort()
 for i in range(n):
  tot=nck(n-1,k-1,MOD)
  x=n-i
  asmin=nck(x-1,k-1,MOD)
  y=i+1
  asmax=nck(y-1,k-1,MOD)
  req=tot-asmin-asmax
  prod=(prod*pow(l[i],req,MOD))%MOD
 print(prod%MOD)

MOD=10**9+7
p=100000
fact=[0]*p 
fact[0]=1 
for i in range(1,p):
 fact[i]=(fact[i-1]*i)%MOD
def MI(a,MOD):
 return pow(a,MOD-2,MOD)
def nck(n, k):
 if n==k or k==0:
  return 1 
 if n<k:
  return 0 
 return (fact[n]*MI(fact[k],MOD)%MOD*MI(fact[n-k],MOD)%MOD)%MOD
for _ in range(int(input())):
 n,k=map(int,input().split())
 prod=1
 l=[int(i) for i in input().split()]
 l.sort()
 for i in range(n):
  tot=nck(n-1,k-1)
  x=n-i
  asmin=nck(x-1,k-1)
  y=i+1
  asmax=nck(y-1,k-1)
  req=tot-asmin-asmax
  prod=(prod*pow(l[i],req,MOD))%MOD
 print(prod%MOD)

MOD=10**9+7
p=1000000
fact=[0]*p 
fact[0]=1 
for i in range(1,p):
 fact[i]=(fact[i-1]*i)%MOD
def MI(a,MOD):
 return pow(a,MOD-2,MOD)
def nck(n, k):
 if n==k or k==0:
  return 1 
 if n<k:
  return 0 
 return (fact[n]*MI(fact[k],MOD)%MOD*MI(fact[n-k],MOD)%MOD)%MOD
for _ in range(int(input())):
 n,k=map(int,input().split())
 prod=1
 l=[int(i) for i in input().split()]
 l.sort()
 for i in range(n):
  tot=nck(n-1,k-1)
  x=n-i
  asmin=nck(x-1,k-1)
  y=i+1
  asmax=nck(y-1,k-1)
  req=tot-asmin-asmax
  prod*=pow(l[i],req,MOD)
 print(prod%MOD)

MOD=10**9+7
p=1000000
fact=[0]*p 
fact[0]=1 
for i in range(1,p):
 fact[i]=(fact[i-1]*i)%MOD
def MI(a,MOD):
 return pow(a,MOD-2,MOD)
def nck(n, k):
 if n==k or k==0:
  return 1 
 if n<k:
  return 0 
 return fact[n]*MI(fact[k],MOD)*MI(fact[n-k],MOD)%MOD
for _ in range(int(input())):
 n,k=map(int,input().split())
 prod=1
 l=[int(i) for i in input().split()]
 l.sort()
 for i in range(n):
  tot=nck(n-1,k-1)
  x=n-i
  asmin=nck(x-1,k-1)
  y=i+1
  asmax=nck(y-1,k-1)
  req=tot-asmin-asmax
  prod*=pow(l[i],req,MOD)
 print(prod%MOD)

MOD=10**9+7
p=6000
fact=[0]*p 
fact[0]=1 
for i in range(1,p):
 fact[i]=(fact[i-1]*i)%MOD
def MI(a,MOD):
 return pow(a,MOD-2,MOD)
def nck(n, k):
 if n==k or k==0:
  return 1 
 if n<k:
  return 0 
 return fact[n]*MI(fact[k],MOD)*MI(fact[n-k],MOD)%MOD
for _ in range(int(input())):
 n,k=map(int,input().split())
 prod=1
 l=[int(i) for i in input().split()]
 l.sort()
 #nck=combo_nck(n,k)
 for i in range(n):
  tot=nck(n-1,k-1)
  # print(tot)
  x=n-i
  if x>=k-1:
   asmin=nck(x-1,k-1)
  else:
   asmin=0
  y=i+1
  if y>=k-1:
   asmax=nck(y-1,k-1)
  else:
   asmax=0
  #print(asmin)
  #print(asmin,asmax)
  prod*=pow(l[i],tot-asmin-asmax,MOD)
  # print(prod)
 print(prod%MOD)