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: MEDIUM_HARD
Tags: Number theory

Combinatorics

Mathematics

Starter code:

Solutions:
import math

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def modInverse(n, p):
	return power(n, p - 2, p)

def Combi(n, r, p):
	if r == 0:
		return 1
	if r > n:
		return 0
	return f[n] * modInverse(f[r], p) % p * modInverse(f[n - r], p) % p % p

def chinese_remainder(n, a, len):
	prod = 1
	sum = 0
	i = 0
	while i < len:
		prod *= n[i]
		i = i + 1
	i = 0
	while i < len:
		p = prod // n[i]
		sum += a[i] * modInverse(p, n[i]) * p
		i = i + 1
	return sum % prod

def calpower(t):
	sum = 0
	i = 1
	while i < 30:
		sum += t // pow(2, i)
		i = i + 1
	return sum

def remainder(n, r):
	if r > n:
		return 0
	if calpower(n) - calpower(n - r) - calpower(r) >= 1:
		return 0
	else:
		return 1
t = int(input())
mod1 = 500000003
mod2 = 1000000007
f = [None] * 5010
f[0] = 1
i = 1
while i <= 5005:
	f[i] = f[i - 1] * i % mod1
	i = i + 1
i = 1
while i <= t:
	(n, k) = map(int, input().split())
	s = input()
	a = list(map(int, s.split()))
	a.sort()
	prod = 1
	j = 1
	while j < n - 1:
		power1 = (Combi(n - 1, k - 1, mod1) % mod1 - (Combi(n - j - 1, k - 1, mod1) % mod1 + Combi(j, k - 1, mod1) % mod1) % mod1) % mod1
		power2 = (remainder(n - 1, k - 1) % 2 - (remainder(n - j - 1, k - 1) % 2 + remainder(j, k - 1) % 2) % 2) % 2
		if power1 < 0:
			power1 += mod1
		if power2 < 0:
			power2 += 2
		b = [None] * 2
		c = [None] * 2
		b[0] = 2
		c[0] = power2
		b[1] = mod1
		c[1] = power1
		ans = chinese_remainder(b, c, 2)
		prod *= power(a[j], ans, mod2)
		prod %= mod2
		j = j + 1
	print(prod)
	i = i + 1


def makeTri():
	triangle[0][0] = 1
	for i in range(1, 5000):
		triangle[i][0] = 1
		triangle[i][i] = 1
		for j in range(1, int(i / 2) + 1):
			triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
			triangle[i][i - j] = triangle[i][j]
(w, h) = (5000, 5000)
triangle = [[0 for x in range(w)] for y in range(h)]
makeTri()
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = list(map(int, input().split()))
	a.sort()
	pp = triangle[n - 1][k - 1]
	ans = 1
	for i in range(int(n / 2) + 1):
		if n - i - 1 < i:
			break
		x = 0
		y = 0
		u = 0
		if n - i - 1 >= k - 1:
			x = triangle[n - i - 1][k - 1]
		if i >= k - 1:
			u = triangle[i][k - 1]
		y = pp - x - u
		if i != n - i - 1:
			ans = ans * pow(a[n - i - 1] * a[i], y, 1000000007) % 1000000007
		else:
			ans = ans * pow(a[i], y, 1000000007) % 1000000007
	print(ans)


MOD = 10 ** 9 + 7
fac = [1]
for i in range(1, 5001):
	fac.append(i * fac[i - 1])

def NCK(n, k):
	if k > n:
		return 0
	return fac[n] // (fac[k] * fac[n - k]) % (MOD - 1)
t = int(input())
for _ in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	a = [int(x) for x in input().split()]
	a.sort()
	res = 1
	tot = NCK(n - 1, k - 1)
	p = []
	if n % 2 == 0:
		for i in range(n // 2):
			p.append((tot % (MOD - 1) - NCK(i, k - 1) % (MOD - 1) - NCK(n - i - 1, k - 1) % (MOD - 1)) % (MOD - 1))
		p = p + p[::-1]
	else:
		for i in range(n // 2 + 1):
			p.append((tot % (MOD - 1) - NCK(i, k - 1) % (MOD - 1) - NCK(n - i - 1, k - 1) % (MOD - 1)) % (MOD - 1))
		p = p + list(reversed(p[:-1]))
	for i in range(n):
		res = res * pow(a[i] % MOD, p[i] % (MOD - 1), MOD) % MOD
	print(res % MOD)


from sys import stdin
MOD = 10 ** 9 + 7
MAX = 5000

class Combination:
	mem = None

	def __init__(self):
		if Combination.mem is None:
			mem = [[0] * (MAX + 1) for _ in range(MAX + 1)]
			for i in range(1, MAX + 1):
				mem[i][0] = mem[i][i] = 1
			for i in range(2, MAX + 1):
				a = mem[i]
				b = mem[i - 1]
				for j in range(1, (i >> 1) + 1):
					a[j] = a[i - j] = (b[j] + b[j - 1]) % (MOD - 1)
			Combination.mem = mem

	def choose(self, n, k):
		return Combination.mem[n][k]

class Power:

	def of(base, exponent):
		result = 1
		while exponent > 0:
			if exponent & 1 == 1:
				result = result * base % MOD
				exponent -= 1
			else:
				base = base * base % MOD
				exponent >>= 1
		return result

class Solver:

	def solve(N, K, a):
		a.sort()
		result = 1
		if N == 3:
			result = a[1]
		else:
			C = Combination()
			for i in range(1, N + 1 >> 1):
				j = N - i - 1
				appear_times = C.choose(N - 1, K - 1)
				appear_times -= C.choose(i, K - 1) + C.choose(j, K - 1)
				appear_times %= MOD - 1
				if N & 1 == 1 and i == N >> 1:
					result = result * Power.of(a[i], appear_times) % MOD
				else:
					result = result * Power.of(a[i] * a[j], appear_times) % MOD
		return result
T = int(stdin.readline().rstrip())
for _ in range(T):
	(N, K) = [int(x) for x in stdin.readline().rstrip().split()]
	a = [int(x) for x in stdin.readline().rstrip().split()]
	result = Solver.solve(N, K, a)
	print(result)


mod = 10 ** 9 + 7

def c(n, r):
	ans = 1
	if n - r < r:
		r = n - r
	for i in range(r):
		ans = ans * (n - i) // (i + 1)
	return ans
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a.sort()
	ansf = 1
	nck = c(n - 1, k - 1)
	nck1 = 1
	nck2 = nck * (n - k) // (n - 1)
	for i in range(1, int(n / 2)):
		if i < k - 1:
			if i <= n - k:
				ans = nck - nck2
				nck2 = nck2 * (n - i - k) // (n - i - 1)
			else:
				ans = nck
		elif i <= n - k:
			ans = nck - nck1 - nck2
			nck1 = nck1 * (i + 1) // (i + 2 - k)
			nck2 = nck2 * (n - i - k) // (n - i - 1)
		else:
			ans = nck - nck1
			nck1 = nck1 * (i + 1) // (i + 2 - k)
		ansf = ansf * pow(a[i] * a[n - i - 1], ans, mod) % mod
	print(ansf)


MOD = 10 ** 9 + 7

def binomialCoefficient(n, k):
	C = [0 for i in range(k + 1)]
	C[0] = 1
	for i in range(1, n + 1):
		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
		ans = ans * arr[x] ** (value - temp2 - temp1) % MOD
	print(ans)


from math import factorial as fact
mod = int(10 ** 9 + 7)

def C(n, r):
	if n < r:
		return 0
	else:
		return fact(n) // (fact(r) * fact(n - r))
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().strip().split()]
	a = list(map(int, input().split()))
	a = sorted(a)
	minCount = []
	(tot, ans) = (C(n - 1, k - 1), 1)
	x = tot
	for i in range(n - k + 1):
		minCount.append(x)
		x = x * (n - k - i) // (n - i - 1)
	for i in range(n - k + 1, n):
		minCount.append(0)
	for i in range(n // 2):
		power = tot - (minCount[i] + minCount[n - 1 - i])
		ans = ans * pow(a[i] * a[n - i - 1], power, mod) % mod
	if n % 2 != 0:
		power = tot - 2 * minCount[n // 2]
		ans = ans * pow(a[n // 2], power, mod) % mod
	print(ans % mod)


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
temp = 1000000006
hell = 1000000007
C = []
tse = []
tse.append(1)
C.append(tse)
for i in range(1, 5002):
	td = []
	td.append(1)
	for j in range(i):
		if j + 2 <= i:
			x = (C[i - 1][j] + C[i - 1][j + 1]) % temp
		else:
			x = C[i - 1][j] % temp
		td.append(x)
	C.append(td)
t = int(input())
while t > 0:
	nk = list(map(int, input().split()))
	v = list(map(int, input().split()))
	n = nk[0]
	k = nk[1]
	v.sort()
	ans = 1
	for i in range(1, (n + 1) // 2):
		val = 0
		if i >= k - 1:
			val += C[i][k - 1]
		if i <= n - k:
			val += C[n - i - 1][k - 1]
		tt = n - 1 - i
		if tt != i:
			ans = ans * power(v[i] * v[tt] % hell, (C[n - 1][k - 1] - val) % (hell - 1), hell) % hell
		else:
			ans = ans * power(v[i], (C[n - 1][k - 1] - val) % (hell - 1), hell) % hell
	print(ans)
	t = t - 1


from math import factorial
factorials = {}
for _ in range(0, int(input())):
	(N, K) = map(int, input().split())
	A = [int(i) for i in input().split()]
	sortA = sorted(A)
	if K - 1 not in factorials:
		factorials[K - 1] = factorial(K - 1)
	maxPower = 1
	for i in range(len(A) - K + 1, len(A)):
		maxPower = maxPower * i
	winStartValue = len(A) - K + 1
	winEndVal = len(A)
	maxPower = maxPower // factorials[K - 1]
	curPower = maxPower
	powers = {}
	ans = 1
	for forward in range(len(A) - K + 1):
		back = len(A) - forward - 1
		if forward < back:
			mul = sortA[forward] * sortA[back]
			p = maxPower - curPower
		elif forward > back:
			mul = sortA[forward] * sortA[back]
			p = -curPower
		else:
			mul = sortA[forward]
			p = maxPower - curPower * 2
		if mul not in powers:
			powers[mul] = p
		else:
			powers[mul] += p
		winStartValue -= 1
		winEndVal -= 1
		curPower = curPower * winStartValue // winEndVal
	forward += 1
	back -= 1
	n = 1
	while forward <= back:
		if forward != back:
			mul = sortA[forward] * sortA[back]
		else:
			mul = sortA[forward]
		n = n * mul
		forward += 1
		back -= 1
	if n not in powers:
		powers[n] = maxPower
	else:
		powers[n] += maxPower
	ans = 1
	for val in powers:
		ans = ans * pow(val, powers[val], 1000000007) % 1000000007
	print(ans)


M = 10 ** 9 + 6
N = 5001
fact = [None] * N
(x, y) = (0, 1)
for i in range(1, N):
	fact[i - 1] = (x, y)
	while not i & 1:
		x += 1
		i >>= 1
	y = y * i % M
fact[N - 1] = (x, y)

def choose(n, m):
	if m > n:
		return 0
	(x, y) = fact[n]
	(x1, y1) = fact[m]
	(x2, y2) = fact[n - m]
	return pow(2, x - x1 - x2, M) * y * pow(y1 * y2, M // 2 - 2, M)
R = lambda : map(int, input().split())
t = int(input())
for _ in range(t):
	(n, k) = R()
	a = sorted(R())
	n -= 1
	k -= 1
	p = 1
	c = choose(n, k)
	for i in range(1, n):
		d = c - choose(i, k) - choose(n - i, k)
		p = p * pow(a[i], d % M, M + 1) % (M + 1)
	print(p)


def ncr(n, r, fact):
	if r == 0:
		return 1
	if r > n:
		return 0
	return fact[n] // (fact[r] * fact[n - r])

def power(a, b, mod):
	tmp = 1
	a = a % mod
	while b > 0:
		if b % 2 == 1:
			tmp = tmp * a % mod
		b = b >> 1
		a = a * a % mod
	return tmp
fact = []
fact.append(1)
for i in range(1, 5001):
	fact.append(i * fact[i - 1])
for _ in range(int(input())):
	mod = 1000000007
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	pwr = []
	pwr.append(0)
	tm = ncr(n - 1, k - 1, fact)
	show = 1
	for i in range(1, n - 1):
		pwr.append(tm)
	for i in range(1, n // 2):
		if i + k <= n:
			pwr[i] = pwr[i] - ncr(n - i - 1, k - 1, fact)
		if i - k + 1 >= 0:
			pwr[i] = pwr[i] - ncr(i, k - 1, fact)
		pwr[i] = pwr[i] % (mod - 1)
		pwr[n - i - 1] = pwr[i]
	if n % 2 == 1:
		i = n // 2
		if i + k <= n:
			pwr[i] = pwr[i] - ncr(n - i - 1, k - 1, fact)
		if i - k + 1 >= 0:
			pwr[i] = pwr[i] - ncr(i, k - 1, fact)
		pwr[i] = pwr[i] % (mod - 1)
	show = 1
	for i in range(1, n - 1):
		show = show * power(arr[i], pwr[i], mod) % mod
	print(show)


q = int(input())
for a in range(q):
	[n, k] = list(map(int, input().split()))
	[prod, m] = [1, 1000000007]
	C = []
	for i in range(k - 1):
		C.append(0)
	C.append(1)
	for i in range(k, n):
		C.append(C[i - 1] * i // (i - k + 1))
	A = list(map(int, input().split()))
	A.sort()
	w = n // 2
	if n & 1:
		prod = pow(A[w], C[n - 1] - 2 * C[(n - 1) // 2], m)
	for i in range(1, w):
		prod = prod * pow(A[i] * A[n - i - 1], C[n - 1] - C[i] - C[n - i - 1], m) % m
	print(prod)


import sys
sys.setrecursionlimit(1000000000)

def expo(m, n):
	if n < 10:
		p = 1
		while n > 0:
			p = p * m % 1000000007
			n -= 1
		return p
	else:
		q = expo(m, n // 10)
		temp = q * q % 1000000007
		temp = temp * temp % 1000000007
		temp = temp * temp % 1000000007
		temp = temp * q * q % 1000000007
		r = n % 10
		l = 1
		while r > 0:
			l = l * m % 1000000007
			r -= 1
		l = l * temp % 1000000007
		return l
t = int(input())
while t > 0:
	l = input().split()
	n = int(l[0])
	k = int(l[1])
	v = []
	powers = []
	li = input().split()
	for i in range(0, n):
		x = int(li[i])
		v.append(x)
		powers.append(0)
	v.sort()
	f = min(n - k, k - 1)
	temp = 1
	for i in range(1, f + 1):
		temp = (n - f + i - 1) * temp // i
	test = temp
	for i in range(0, n - k + 1):
		powers[i] = powers[i] + test
		test = (n - k - i) * test // (n - 1 - i)
	test = temp
	for i in range(0, n - k + 1):
		powers[n - 1 - i] = powers[n - 1 - i] + test
		test = (n - k - i) * test // (n - 1 - i)
	pro = 1
	for i in range(0, n):
		pro = pro * expo(v[i], (temp - powers[i]) % 1000000006) % 1000000007
	print(pro)
	t = t - 1


def coeff(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res // (i + 1)
	return res

def modulo(x, y, mod):
	res = 1
	x = x % mod
	while y > 0:
		if y & 1 == 1:
			res = res * x % mod
		y = y >> 1
		x = x * x % mod
	return res
t = int(input())
mod = 10 ** 9 + 7
var = lambda a, s, f: f * s // a
for _ in range(t):
	(n, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	(a, s, d) = (n - 1, n - k, k - 1)
	x = coeff(a, d)
	p = 1
	f = x
	for i in range(1, n // 2):
		(y, z) = (0, 0)
		if n - i - 1 >= k - 1:
			(a, s) = (n - i - 1, n - i - k)
			f = var(a + 1, s + 1, f)
			y = f
		if i >= k - 1:
			(a, s) = (i, i - k + 1)
			z = coeff(a, d)
		g = (x - y - z) % (mod - 1)
		p = p % mod * modulo(l[i], g, mod) * modulo(l[n - i - 1], g, mod) % mod
	print(p)


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)


F = {}
d = 10 ** 9 + 6
dd = 10 ** 9 + 7

def modexp(x, n, dd):
	res = 1
	while n:
		if n & 1:
			res = res % dd * (x % dd) % dd
		x = x % dd * (x % dd) % dd
		n = n // 2
	return res

def f(n):
	ans = 1
	for i in range(1, n + 1):
		ans *= i
	return ans

def ncr(n, r):
	res = F[n] // (F[r] * F[n - r]) % d
	return res
F[0] = 1
for i in range(1, 5001):
	F[i] = i * F[i - 1]
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().strip().split(' '))
	A = [int(_) for _ in input().strip().split(' ')]
	A.sort()
	ans = 1
	if n == k:
		for i in range(1, n - 1):
			ans = ans % dd * A[i] % dd % dd
	elif n > k:
		x = 0
		z = 0
		y = ncr(n - 1, k - 1)
		i = 1
		j = n - 2
		while i <= j:
			if n - i - 1 < k - 1:
				z = 0
			else:
				z = ncr(n - i - 1, k - 1)
			if i >= k - 1:
				z += ncr(i, k - 1)
			x = (y % d - z % d + d) % d
			if i == j:
				ans = ans % dd * modexp(A[i], x, dd) % dd % dd
			else:
				ans = ans % dd * modexp(A[i], x, dd) % dd * modexp(A[j], x, dd) % dd % dd
			i += 1
			j -= 1
	print(ans % dd)


m = 10 ** 9 + 7
ans1 = [1, 1]
ans1_len = 1

def factorial_list(n, ans1, ans1_len):
	if n > ans1_len:
		k = ans1[-1]
		for i in range(ans1_len + 1, n + 1):
			k = k * i
			ans1.append(k)
			ans1_len += 1
	return (ans1, ans1_len)

def pro(l, n, k1, ans1, ans1_len):
	ans = 1
	(ans1, ans1_len) = factorial_list(n, ans1, ans1_len)
	n1 = ans1[k1 - 1]
	k = ans1[n - 1] // (ans1[n - k1] * n1) % (m - 1)
	i = 0
	while i < n / 2:
		k2 = k
		if i - k1 + 1 >= 0:
			k2 = k2 - ans1[i] // (ans1[i - k1 + 1] * n1) % (m - 1)
		if n - i - k1 >= 0:
			k2 = k2 - ans1[n - i - 1] // (ans1[n - i - k1] * n1) % (m - 1)
		if n % 2 != 0:
			if i == int(n // 2):
				ans = ans * pow(l[i], k2 % (m - 1), m) % m
			else:
				ans = ans * pow(l[i], k2 % (m - 1), m) % m * pow(l[n - i - 1], k2 % (m - 1), m) % m
		else:
			ans = ans * pow(l[i], k2 % (m - 1), m) % m * pow(l[n - i - 1], k2 % (m - 1), m) % m
		i += 1
	return (ans, ans1, ans1_len)
for i in range(int(input())):
	(n, k) = (int(s) for s in input().split())
	l = [int(s) for s in input().split()]
	l.sort()
	(ans, ans1, ans1_len) = pro(l, n, k, ans1, ans1_len)
	print(ans)


M = int(1000000000.0 + 7)
t = int(input())
while t:
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	p = 1
	for i in range(n):
		p = p * a[i] % M
	a.sort()
	e = 1
	for i in range(1, n - k, 2):
		e *= (k - 1 + i) * (k - 1 + i + 1)
		e //= i * (i + 1)
	if (n - k) % 2:
		e *= n - 1
		e //= n - k
	ans = pow(p, e, M)
	ans *= pow(pow(a[0], e, M), M - 2, M)
	ans *= pow(pow(a[n - 1], e, M), M - 2, M)
	for i in range(1, n - k + 1):
		e *= n - k - i + 1
		e //= n - i
		ans *= pow(pow(a[i], e, M), M - 2, M)
		ans %= M
		ans *= pow(pow(a[n - i - 1], e, M), M - 2, M)
		ans %= M
	print(ans % M)
	t -= 1


def power(a, x):
	ans = 1
	a %= p
	while x > 0:
		if x & 1:
			ans = ans * a % p
		x = x >> 1
		a = a * a % p
	return ans

def modInv(a):
	return power(a, p - 2)

def ncrmodp(n, r):
	if r == 0:
		return 1
	return fac[n] // (fac[r] * fac[n - r])

def fact(n):
	fac = [None for i in range(n + 1)]
	fac[0] = 1
	for i in range(1, n + 1):
		fac[i] = fac[i - 1] * i
	return fac
p = 10 ** 9 + 7
fac = fact(5000)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	ar.sort()
	br = []
	t = n // 2 + n % 2
	mai = ncrmodp(n - 1, k - 1)
	for i in range(2, t + 1):
		t1 = 0
		t2 = 0
		if n - i >= k - 1:
			t1 = ncrmodp(n - i, k - 1)
		if i - 1 >= k - 1:
			t2 = ncrmodp(i - 1, k - 1)
		temp = mai - t1 - t2
		if temp >= p:
			temp = temp % (p - 1)
		br.append(temp)
	l = len(br)
	br += reversed(br[:l - n % 2])
	ans = 1
	l = len(br)
	for i in range(l):
		ans *= power(ar[i + 1], br[i])
		ans = ans % p
	print(ans % p)


import math as ma
from sys import exit
from decimal import Decimal as dec

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

def num():
	return map(int, input().split())

def nu():
	return int(input())
C = [0] * 5001
for i in range(5001):
	C[i] = [0] * 5001

def binomialCoef(n, k):
	for i in range(n + 1):
		for j in range(min(i, k) + 1):
			if j == 0 or j == i:
				C[i][j] = 1
			else:
				C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % 1000000006
binomialCoef(5000, 5000)
t = nu()
M = 1000000006
for ii in range(t):
	(n, k) = num()
	a = li()
	a = [0] + a
	a.sort()
	r = k - 1
	up_cnt = [0] * (n + 1)
	for i in range(1, n + 1):
		up_cnt[i] = (up_cnt[i] + C[n - 1][r]) % M
	for i in range(1, n - k + 2):
		up_cnt[i] = (up_cnt[i] + M - C[n - i][r]) % M
	for i in range(n, k - 1, -1):
		up_cnt[i] = (up_cnt[i] + M - C[i - 1][r]) % M
	ans = 1
	for i in range(1, n + 1):
		x = pow(a[i], up_cnt[i], M + 1)
		ans = ans * x % (M + 1)
	print(ans)


m = 10 ** 9 + 7
list = [1]
for i in range(1, 5001):
	list.append(i * list[i - 1])
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	a = sorted([int(x) for x in input().split()])
	ans = 1
	p = list[N - 1] // (list[K - 1] * list[N - K])
	q = 0
	r = p
	for i in range(N):
		if i == K - 1:
			q = 1
		if i >= K:
			q = q * i // (i - K + 1)
		if i <= N - K and i > 0:
			r = r * (N - K - i + 1) // (N - i)
		elif i > 0:
			r = 0
		e = p - q - r
		e = e % (m - 1)
		ans = ans % m * pow(a[i], e, m) % m
	print(ans)


mod = 1000000007

def bino_coef(n, k):
	c = [1]
	for i in range(1, k + 1):
		c += [0]
	for i in range(1, n + 1):
		j = min(i, k)
		while j:
			c[j] = c[j] + c[j - 1]
			j -= 1
	return c[k]

def binco(n, k):
	ans = 1
	a = 1
	b = n - k + 1
	while a <= k:
		ans = b * ans // a
		a += 1
		b += 1
	return ans
t = int(input())
bin = {}
while t:
	t -= 1
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	if (n - 1, k - 1) not in bin.keys():
		bin[n - 1, k - 1] = binco(n - 1, k - 1)
	j = 0
	for i in range(n - 2, k - 2, -1):
		bin[i, k - 1] = (n - k - j) * bin[i + 1, k - 1] // (n - 1 - j)
		j += 1
	cnt = [bin[n - 1, k - 1]] * n
	for i in range(1, n - 1):
		if n - i - 1 >= k - 1:
			cnt[i] -= bin[n - 1 - i, k - 1]
		if i >= k - 1:
			cnt[i] -= bin[i, k - 1]
	for i in range(1, n - 1):
		cnt[i] %= mod - 1
	ans = 1
	for i in range(1, n - 1):
		ans = ans * pow(l[i], cnt[i], mod) % mod
	print(ans)


for _ in range(int(input())):
	p = 1
	nt = []
	c = []
	c.append(1)
	(n, k) = map(int, input().split())
	for i in range(k, n):
		c.append(c[i - 1 - (k - 1)] * i // (i - (k - 1)))
	t = c[n - 1 - (k - 1)]
	l = [int(x) for x in input().split()]
	for i in range(int(n / 2)):
		a = i
		b = n - 1 - i
		if a == 0 or a == n - 1:
			continue
		else:
			if a >= k - 1 and b >= k - 1:
				s = t - c[a - (k - 1)] - c[b - (k - 1)]
			elif a >= k - 1:
				s = t - c[a - (k - 1)]
			elif b >= k - 1:
				s = t - c[b - (k - 1)]
			else:
				s = t
			nt.append(s % 1000000006)
	rl = list(reversed(nt))
	if n % 2 != 0:
		a = int(n / 2)
		b = n - 1 - a
		if a >= k - 1 and b >= k - 1:
			s = t - c[a - (k - 1)] - c[b - (k - 1)]
		elif a >= k - 1:
			s = t - c[a - (k - 1)]
		elif b >= k - 1:
			s = t - c[b - (k - 1)]
		else:
			s = t
		nt.append(s % 1000000006)
	nt += rl
	l.sort()
	for i in range(1, n - 1):
		p = p * pow(l[i], nt[i - 1], 1000000007) % 1000000007
	print(p)


MOD = 10 ** 9 + 7

def ncr(n, r, p):
	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
		ans = ans * arr[x] ** (value - temp2 - temp1) % MOD
	print(ans)


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)
			res = res * qPow(lis[i], zhi) % modn
		print(res)
__starting_point()


import math

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
rem = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	[N, K] = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	A.sort()
	p = 1
	con = ncr(N - 1, K - 1) % (rem - 1)
	Z = [-1] * (N - K)
	val1 = 1
	for i in range(K - 1, N - 1):
		Z[i - (K - 1)] = val1
		val1 = val1 * (i + 1) // (i - K + 2)
	for i in range(1, N - 1):
		ins = 0
		if i >= K - 1:
			ins += Z[i - (K - 1)] % (rem - 1)
		if N - i - 1 >= K - 1:
			ins += Z[N - i - 1 - (K - 1)] % (rem - 1)
		temp = (con - ins) % (rem - 1)
		temp1 = power(A[i], temp, rem)
		p = p * temp1 % rem
	print(p)


import math
import operator as op
from functools import reduce

def ncr(n, r):
	if n < r:
		return 0
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = [int(s) for s in input().split()]
	product = 1
	x = ncr(n - 1, k - 1)
	m = a[:]
	m.sort()
	l = len(m)
	p = 1
	lo = int(math.ceil(l / 2))
	ntemp = n - 1
	nt = 1
	pr = x
	pr1 = 1
	for j in range(1, lo):
		if ntemp < k - 1:
			pr = 0
		else:
			pr = pr * (ntemp - (k - 1)) // ntemp
		if nt < k - 1:
			pr1 = 0
		elif nt == k - 1:
			pr1 = 1
		else:
			pr1 = pr1 * nt // (nt - (k - 1))
		xy = x - (pr + pr1)
		if m[j] != m[l - j - 1]:
			p = p * pow(m[j] * m[l - j - 1], xy, 10 ** 9 + 7)
		else:
			p = p * pow(m[j], xy, 10 ** 9 + 7)
		ntemp = ntemp - 1
		nt = nt + 1
	ans = p
	ans = ans % (10 ** 9 + 7)
	print(ans)


import math
limit = 1000000007

def ncr(n, k):
	k = min(k, n - k)
	po = 1
	for i in range(k):
		po = po * (n - i)
	return po // math.factorial(k)

def mypo(a, x):
	x = x % (limit - 1)
	if x == 0:
		return 1
	ret = mypo(a, x // 10)
	ret = pow(ret, 10) % limit
	if x % 10 != 0:
		ret = ret * pow(a, x % 10) % limit
	return ret
t = int(input())
while t:
	t -= 1
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = input().split()
	a = list(map(int, a))
	a.sort()
	st = ncr(n - 1, k - 1)
	f = st
	s = 1
	ans = 1
	x = n - 1
	y = 0
	power = []
	for i in range((n + 1) // 2):
		po = st
		if x >= k - 1:
			po -= f
			f = (x - k + 1) * f // x
		if y >= k - 1:
			po -= s
			s = (y + 1) * s // (y + 2 - k)
		x -= 1
		y += 1
		power.append(po)
	pdt = 1
	if n % 2 == 1:
		ans = mypo(a[n // 2], power[n // 2] - power[n // 2 - 1])
		pdt = a[n // 2]
	for i in range(n // 2 - 1, 0, -1):
		pdt = pdt * a[i] * a[n - 1 - i] % limit
		ans = ans * mypo(pdt, power[i] - power[i - 1]) % limit
	print(ans)


MOD = 10 ** 9 + 7

def nCrModpDP(n, r, p):
	C = [0] * (n + 1)
	C[0] = 1
	for i in range(1, n + 1):
		j = min(i, r)
		while j > 0:
			C[j] = (C[j] + C[j - 1]) % p
			j -= 1
	return C[r]

def nCrModpLucas(n, r, p):
	if r == 0:
		return 1
	ni = int(n % p)
	ri = int(r % p)
	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
		ans = ans * arr[x] ** (value - temp2 - temp1) % MOD
	print(ans)


M = 1000000007
t = int(input())
for asd in range(t):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	ar.sort()
	ncr = [0 for i in range(n)]
	ncr[k - 3] = 1
	for i in range(k - 2, n):
		ncr[i] = ncr[i - 1] * i // (i - k + 3)
	sum = [0 for i in range(n)]
	for i in range(0, n):
		if i == 0:
			sum[i] = ncr[i]
		else:
			sum[i] = sum[i - 1] + ncr[i]
	ch = [0 for i in range(n)]
	idx1 = k - 3
	idx2 = n - 3
	for i in range(1, n // 2 + n % 2):
		if i >= k - 1:
			ch[i] = ch[i - 1] + (sum[idx2] - sum[k - 3] + ncr[k - 3]) - (sum[idx1] - sum[k - 3] + ncr[k - 3])
			idx1 += 1
			idx2 -= 1
		else:
			ch[i] = ch[i - 1] + (sum[idx2] - sum[k - 3] + ncr[k - 3])
			idx2 -= 1
	ans = 1
	for i in range(1, n // 2):
		ans = ans % M * pow(ar[i] * ar[n - i - 1] % M, ch[i], M) % M
	if n & 1:
		i = n // 2
		ans = ans % M * pow(ar[i] % M, ch[i], M) % M
	print(ans)


from sys import setrecursionlimit
setrecursionlimit(1000000)
mod = 1000000007
mod2 = mod - 1
comb = [[1], [1, 1]]
for i in range(2, 5000):
	comb.append([1])
	for j in range(1, i):
		comb[i].append((comb[i - 1][j] + comb[i - 1][j - 1]) % mod2)
	comb[i].append(1)
test_cases = int(input())
c1 = 2

def pow1(x, n):
	if x == 0:
		return 0
	if x == 1:
		return 1
	if n < c1:
		return x ** n
	p1 = n // c1
	p2 = n % c1
	return pow1(x, p1) ** c1 % mod * (x ** p2 % mod) % mod

def combi(n, k, i):
	t1 = comb[n - 1][k - 1]
	t2 = t3 = 0
	if i >= k - 1:
		t2 = comb[i][k - 1]
	if n - i >= k:
		t3 = comb[n - i - 1][k - 1]
	return (t1 - t2 - t3 + 2 * mod2) % mod2
for _ in range(test_cases):
	(n, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	ls.sort()
	ans = 1
	for i in range(n):
		ans = ans * pow1(ls[i], combi(n, k, i)) % mod
	print(ans)


M = 1000000007
t = int(input())
for xyz in range(t):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	ar.sort()
	ncr = []
	for i in range(0, n):
		if i >= k - 2 and i < n:
			ncr.append(ncr[i - 1] * i // (i - k + 3))
		else:
			ncr.append(1)
	sum = []
	sum.append(ncr[0])
	for i in range(1, n):
		sum.append(sum[i - 1] + ncr[i])
	ch = [0 for i in range(n)]
	index = n - 3
	index2 = k - 3
	it = k - 3
	ans = 1
	for i in range(1, n // 2):
		if index >= it:
			if i < k - 1:
				ch[i] = ch[i - 1] + sum[index] - sum[it] + ncr[it]
				index -= 1
			else:
				ch[i] = ch[i - 1] + sum[index] - sum[it] + ncr[it] - (sum[index2] - sum[it] + ncr[it])
				index -= 1
				index2 += 1
		else:
			ch[i] = ch[i - 1]
		ans = ans % M * pow(ar[i] * ar[n - i - 1] % M, ch[i], M) % M % M
	if n & 1:
		tt1 = n // 2
		if index >= it:
			if tt1 < k - 1:
				ch[tt1] = ch[tt1 - 1] + sum[index] - sum[it] + ncr[it]
				index -= 1
			else:
				ch[tt1] = ch[tt1 - 1] + sum[index] - sum[it] + ncr[it] - (sum[index2] - sum[it] + ncr[it])
				index -= 1
				index2 += 1
		else:
			ch[tt1] = ch[tt1 - 1]
		ans = ans % M * pow(ar[tt1], ch[tt1], M) % M % M
	print(ans)


mod = int(1000000000.0 + 7)
mod2 = 1000000006
combin = []

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

def fastpow(a, n):
	res = 1
	while n > 0:
		if n % 2 != 0:
			res = res * a
			res %= mod
		n //= 2
		a = a * a % mod % mod
	return res

def comb(n, r, typet):
	if n == r:
		return 1
	if typet == 0:
		ans = fact(n, r + 1) // fact(n - r, 0)
		combin[n] = ans
	elif typet == 1:
		if combin[n - 1] == -1:
			ans = fact(n, r + 1) // fact(n - r, 0)
		else:
			ans = combin[n - 1] * n // (n - r)
		combin[n] = ans
	elif typet == 2:
		if combin[n + 1] == -1:
			ans = fact(n, r + 1) // fact(n - r, 0)
		else:
			ans = combin[n + 1] * (n - r + 1) // (n + 1)
		combin[n] = ans
	return ans
t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	combin = [-1] * n
	nm1Ckm1 = comb(n - 1, k - 1, 0)
	ans = 1
	combin[k - 1] = 1
	for i in range(1, n - 1):
		b = 0
		b += nm1Ckm1
		p = i + 1
		if not p <= k - 1:
			z = comb(p - 1, k - 1, 1)
			b -= z
		if not p > n - k + 1:
			u = comb(n - p, k - 1, 2)
			b -= u
		b %= 1000000006
		ans = ans * fastpow(a[i], b) % mod % mod
	combin = []
	print(ans)


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


factorial = [1]
M = 1000000007
p = M - 1
table = [[1]]
for i in range(1, 5000):
	r = []
	for j in range(i + 1):
		if j == 0 or j == i:
			r.append(1)
		else:
			r.append((table[i - 1][j - 1] % p + table[i - 1][j] % p) % p)
	table.append(r)

def nCk(n, k):
	if n >= k:
		return table[n][k]
	return 0

def expo(n, k, i):
	lqw = (nCk(n - 1, k - 1) % p - nCk(i, k - 1) % p - nCk(n - i - 1, k - 1) % p) % p
	return lqw % p

def mypow(a, b):
	if b == 0:
		return 1
	if b == 1:
		return a % M
	if b & 1 == 1:
		return a % M * mypow(a, b - 1) % M % M
	else:
		return mypow(a % M * a % M % M, b // 2) % M
t = int(input())
while t > 0:
	t = t - 1
	l = input().split(' ')
	n = int(l[0])
	k = int(l[1])
	l = input().split(' ')
	for i in range(n):
		l[i] = int(l[i])
	l.sort()
	ans = 1
	if n % 2 == 1:
		for i in range(1, n // 2):
			exponent = expo(n, k, i)
			ans = ans * mypow(l[i], exponent) * mypow(l[n - 1 - i], exponent) % M
		ans = ans * pow(l[n // 2], expo(n, k, n // 2)) % M
	else:
		for i in range(1, n // 2):
			exponent = expo(n, k, i)
			ans = ans * mypow(l[i], exponent) * mypow(l[n - 1 - i], exponent) % M
	print(ans)


from itertools import combinations
from functools import reduce
mod = int(1000000000.0 + 7)

def main(n, k, arr):
	com_arr = ComArr(n - 2, k - 2)
	for i in range(1, len(com_arr)):
		com_arr[i] += com_arr[i - 1]
	ans = [0] + [(com_arr[-1] - com_arr[-i - 2] - com_arr[i]) % (mod - 1) for i in range(n - 2)] + [0]
	ans = [pow(arr[i], ans[i], mod) for i in range(len(ans))]
	print(reduce(lambda x, y: x * y % mod, ans))

def getAnswer(n, k):
	ans = [0] * n
	a = list(range(1, n + 1))
	for c in combinations(a, k):
		for i in c[1:-1]:
			ans[i - 1] += 1
	powered = [i ** ans[i] for i in range(len(ans))]
	print(powered)
	return ans

def ComArr(n, k):
	result = [0] * (n + 1)
	result[k] = 1
	for i in range(k + 1, n + 1):
		result[i] = result[i - 1] * i // (i - k)
	return result
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	main(n, k, a)


mod = 1000000007
from operator import mul
from functools import reduce

def Inverse():
	n = 10000
	dp = [0 for k in range(n + 1)]
	dp[0] = dp[1] = 1
	for k in range(2, n + 1):
		dp[k] = dp[mod % k] * (mod - mod // k) % mod
	return dp

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(mul, range(n, n - r, -1), 1)
	denom = reduce(mul, range(1, r + 1), 1)
	return numer // denom

def modExpo(x, y):
	res = 1
	x = x % mod
	while y > 0:
		if y & 1:
			res = res * x % mod
		y = y >> 1
		x = x * x % mod
	return res

def f(ar, n, K):
	g = [0 for x in range(n)]
	s = [0 for x in range(n)]
	copy = [i[0] for i in sorted(enumerate(ar), key=lambda x: x[1])]
	sc = 1
	s[copy[K - 1]] = sc
	gc = ncr(n - 1, K - 1)
	g[copy[0]] = gc
	big = gc
	k = 1
	while n - k - 1 >= K - 1:
		gc = gc * (n - k - K + 1) // (n - k)
		g[copy[k]] = gc
		k += 1
	k = K
	while k < n:
		sc = sc * k // (k - K + 1)
		s[copy[k]] = sc
		k += 1
	power = [(big - g[k] - s[k]) % (mod - 1) for k in range(n)]
	powers = [(i[0], i[1]) for i in sorted(enumerate(power), key=lambda x: x[1])]
	ptr = 0
	while powers[ptr][1] == 0 and ptr < n:
		ptr += 1
	if ptr == n:
		return 1
	multi = 1
	for k in range(ptr, n):
		multi *= ar[powers[k][0]]
		multi %= mod
	temp = multi
	multi = modExpo(multi, powers[ptr][1])
	runner = Inv[ar[powers[ptr][0]]]
	while ptr < n - 1:
		if powers[ptr + 1][1] > powers[ptr][1]:
			temp *= runner
			temp %= mod
			runner = 1
			hexx = modExpo(temp, powers[ptr + 1][1] - powers[ptr][1])
			multi *= hexx
			multi %= mod
		runner *= Inv[ar[powers[ptr + 1][0]]]
		runner %= mod
		ptr += 1
	return multi
Inv = Inverse()

def main():
	for k in range(int(input())):
		(n, k) = map(int, input().split())
		ar = [int(x) for x in input().split()]
		print(f(ar, n, k))
main()


mod = 10 ** 9 + 7
N = 5000
res = [[1 for j in range(i + 1)] for i in range(N + 1)]
for i in range(2, N + 1):
	for j in range(1, i):
		res[i][j] = (res[i - 1][j] + res[i - 1][j - 1]) % (mod - 1)
t = int(input())
for q in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	res_ = 1
	for i in range(n - 1):
		pw = res[n - 1][k - 1]
		if i >= k - 1:
			pw -= res[i][k - 1]
		if i <= n - k:
			pw -= res[n - i - 1][k - 1]
		pw %= mod - 1
		res_ *= pow(a[i], pw, mod)
		res_ %= mod
	print(res_)


import math
mod = int(1000000000.0 + 7)

def C(n, r):
	f = math.factorial
	if n < r:
		return 0
	else:
		return f(n) // (f(r) * f(n - r))
for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	min_count = []
	(tot, ans) = (C(n - 1, k - 1), 1)
	x = tot
	for i in range(n - k + 1):
		min_count.append(x)
		x = x * (n - k - i) // (n - i - 1)
	for i in range(n - k + 1, n):
		min_count.append(0)
	for i in range(n // 2):
		t = tot - (min_count[n - 1 - i] + min_count[i])
		ans = ans * pow(a[i] * a[n - i - 1], t, mod) % mod
	if n % 2 != 0:
		t = tot - 2 * min_count[n // 2]
		ans = ans * pow(a[n // 2], t, mod) % mod
	print(ans % mod)


import math
mv = 1000000007

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def main():
	t = int(input())
	while t > 0:
		t = t - 1
		(n, k) = [int(x) for x in input().split()]
		a = [int(x) for x in input().split()]
		a.sort()
		b = [1]
		x = k - 1
		y = 0
		temp = b[0]
		for i in range(1, n - k + 1):
			temp = b[0] * (x + 1) // (y + 1)
			b.insert(0, temp)
			x += 1
			y += 1
		num = (n - 1) // 2
		c = [0 for i in range(num + 1)]
		for i in range(num + 1):
			if i >= len(b):
				c[i] = temp
			else:
				c[i] = temp - b[i]
		y = n - k
		for i in range(k - 1, num + 1):
			c[i] -= b[y]
			y -= 1
		for i in range(num + 1, n):
			a[n - i - 1] = a[i] * a[n - i - 1] % mv
		prod = 1
		for i in range(1, num + 1):
			prod = prod * pow(a[i], c[i], mv) % mv
		print(prod)
main()


import math
from collections import defaultdict
MOD = int(1000000000.0 + 7)
MOD1 = int(1000000000.0 + 7) - 1
primes = []
sieve = [0] * 5001
for i in range(2, 5001):
	if sieve[i] == 0:
		primes.append(i)
		for j in range(2 * i, 5001, i):
			sieve[j] = 1
factors = []
factors.append(())
factors.append(())
for i in range(2, 5001):
	f = []
	for prime in primes:
		if i == 1:
			break
		if i % prime == 0:
			power = 0
			while i > 1 and i % prime == 0:
				i /= prime
				power += 1
			f.append((prime, power))
	factors.append(f)
t = int(input())
for it in range(t):
	(n, k) = list(map(int, input().split()))
	a = sorted(list(map(int, input().split())))
	ncr = [0] * (n + 1)
	ncr[k - 1] = 1
	curr = defaultdict(int)
	for i in range(k, n):
		for (factor, power) in factors[i]:
			curr[factor] += power
		for (factor, power) in factors[i - k + 1]:
			curr[factor] -= power
		ncr[i] = 1
		for factor in curr:
			ncr[i] = ncr[i] * pow(factor, curr[factor], MOD1) % MOD1
	ans = 1
	for i in range(2, n):
		e = (ncr[n - 1] + MOD1 - ncr[n - i] + MOD1 - ncr[i - 1]) % MOD1
		ans = ans * pow(a[i - 1], e, MOD) % MOD
	print(ans)


mod = 10 ** 9 + 7
mod1 = mod - 1
mod2 = mod1 // 2

def mpow(x, k, z=mod):
	r = 1
	while k:
		if k & 1:
			r = r * x % z
		x = x * x % z
		k >>= 1
	return r

def minv(x):
	return mpow(x, mod2 - 2, mod2)
FF = [1]
IFF = [1]
for i in range(1, 5002):
	FF += [FF[-1] * i % mod2]
	IFF += [minv(FF[-1])]

def chmod2(n, k):
	return 1 if n | k == n else 0

def choose(n, k):
	if n < k:
		return 0
	ret = FF[n] * IFF[k] * IFF[n - k] % mod2
	if ret & 1 != chmod2(n, k):
		ret += mod2
	return ret

def sol(a, k):
	n = len(a)
	a = sorted(a)
	ret = 1
	mm = choose(n - 1, k - 1)
	for (i, x) in enumerate(a):
		mult = mm
		mult -= choose(i, k - 1)
		mult -= choose(n - i - 1, k - 1)
		mult %= mod1
		ret *= mpow(x, mult)
		ret %= mod
	return ret
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(n, k) = map(int, f.readline().split())
	a = list(map(int, f.readline().split()))
	print(sol(a, k))


fact = 5001 * [0]
fact[0] = 1
for i in range(1, 5001):
	fact[i] = fact[i - 1] * i

def power(x, p):
	a = 1
	x = x % mod
	p = int(p % (mod - 1))
	while p > 0:
		if p % 2 is 1:
			a = a * x % mod
		x = x * x % mod
		p = p >> 1
	return int(a)

def nCr(n, r):
	if r > n:
		return 0
	return fact[n] // (fact[n - r] * fact[r])
t = int(input())
mod = 1000000007
while t > 0:
	ans = 1
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a.sort()
	c = nCr(n - 1, k - 1)
	for i in range(1, n // 2):
		mx = nCr(i, k - 1)
		mn = nCr(n - i - 1, k - 1)
		ans = int(ans % mod * power(a[i] * a[n - i - 1], c - mn - mx) % mod) % mod
	print(ans % mod)
	t = t - 1


def fpow(n, k, p=1000000007):
	r = 1
	while k:
		if k & 1:
			r = r * n % p
		n = n * n % p
		k >>= 1
	return r
fact = [1, 1]
for i in range(2, 5001):
	fact.append(i * fact[i - 1])
t = int(input())
while t:
	(n, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	l = l[1:-1]
	t -= 1
	prd = 1
	for i in l:
		prd *= i
	x = n - k
	nl = [0] * (n - 2)
	d = n - 2
	m = x
	nl[0] = fact[n - 2] // fact[n - 2 - x] // fact[x]
	k = 1
	for i in range(1, n - 2):
		if d > 0:
			nl[i] = nl[i - 1] * m // d
		else:
			nl[i] = 0
		m -= 1
		d -= 1
	nl1 = [nl[i] - nl[-i] for i in range(1, n - 2)]
	tmp = nl[0]
	pwr = nl[0]
	ans = fpow(l[0], pwr % 1000000006)
	for i in range(n - 3):
		pwr += nl1[i]
		ans = ans * fpow(l[i + 1], pwr % 1000000006) % 1000000007
	print(ans % 1000000007)


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y % 2 == 1:
			res = res * x % p
		y = y // 2
		x = x * x % p
	return res
for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	l1 = [0] * n
	d = 10 ** 9 + 7
	p = 1
	l1[k - 1] = 1
	for i in range(k, n):
		l1[i] = l1[i - 1] * i // (i - k + 1)
	for i in range(1, n - 1):
		c = (l1[n - 1] - (l1[i] + l1[n - 1 - i])) % (d - 1)
		p *= power(l[i], c, d)
		p %= d
	print(p)


import operator as op
from functools import reduce

def ncr(n, r):
	numer = fact[n]
	denom = fact[n - r] * fact[r]
	return numer // denom
T = int(input())
poo = {}
fact = [1] * 5001
for i in range(1, 5001):
	fact[i] = fact[i - 1] * i
while T != 0:
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	result = 1
	mod = 1000000000 + 7
	tot = ncr(N, K)
	nim = ncr(N - 1, K)
	if N % 2 == 0:
		r = N // 2
	else:
		r = N // 2 + 1
	for i in range(1, r):
		if i < K - 1 and N - i < K:
			if K != N:
				p = nim
				p = tot - p
			else:
				p = 1
		elif i < K - 1:
			num1 = nim
			num2 = ncr(N - i - 1, K - 1)
			p = num1 + num2
			p = tot - p
		elif N - i < K:
			num1 = nim
			num2 = ncr(i, K - 1)
			p = num2 + num1
			p = tot - p
		else:
			num1 = nim
			num2 = ncr(i, K - 1)
			num3 = ncr(N - i - 1, K - 1)
			p = num1 + num2 + num3
			p = tot - p
		if A[i] in poo:
			if p in poo[A[i]]:
				num = poo[A[i]][p]
		else:
			num = int(pow(A[i], p % (mod - 1), mod))
		result = result * num % mod
		if N - 1 - i != i:
			if A[N - 1 - i] in poo:
				if p in poo[A[N - 1 - i]]:
					temp_num = poo[A[N - 1 - i]][p]
			else:
				temp_num = pow(A[N - 1 - i], p % (mod - 1), mod)
			result = result * temp_num % mod
	T = T - 1
	print(result)


d = 1000000007
import math

def power(a, b):
	re = 1
	while b:
		if b % 2 == 1:
			re *= a
			re %= d
		a *= a
		a *= a
		a *= a
		a *= a
		a *= a
		a %= d
		b >>= 1
	return re

def com(a, b):
	if a == b:
		return 1
	elif a < b:
		return 0
	re = 1
	for x in range(1, b + 1):
		re *= a
		a -= 1
		re //= x
	return re
t = int(input())
for io in range(t):
	(n, k) = list(map(int, input().strip().split()))
	e = list(map(int, input().strip().split()))
	e.sort()
	result = com(n - 1, k - 1)
	result2 = result * (n - k) // (n - 1)
	tot = 1
	for w in range(1, n - 1):
		tot *= e[w]
	lre = 1
	ll = result - result2
	re = pow(tot % d, ll, d)
	for x in range(2, (n + 2 * (n % 2)) // 2):
		if x < k - 1:
			result1 = 0
		elif x == k - 1:
			result1 = 1
		else:
			result1 *= x
			result1 //= lre
			lre += 1
		if n - 1 - x < k - 1:
			result2 = 0
		elif n - 1 - x == k - 1:
			result2 = 1
		else:
			result2 *= n - x - k + 1
			result2 //= n - x
		le = result - result1 - result2
		tot //= e[x - 1] * e[n - x]
		re *= pow(tot % d, le - ll, d)
		ll = le
		re %= d
	if io != t - 1:
		print(re % d)
	else:
		print(re % d, end='')