Ayrat has number n, represented as it's prime factorization p_{i} of size m, i.e. n = p_1·p_2·...·p_{m}. Ayrat got secret information that that the product of all divisors of n taken modulo 10^9 + 7 is the password to the secret data base. Now he wants to calculate this value.


-----Input-----

The first line of the input contains a single integer m (1 ≤ m ≤ 200 000) — the number of primes in factorization of n. 

The second line contains m primes numbers p_{i} (2 ≤ p_{i} ≤ 200 000).


-----Output-----

Print one integer — the product of all divisors of n modulo 10^9 + 7.


-----Examples-----
Input
2
2 3

Output
36

Input
3
2 3 2

Output
1728



-----Note-----

In the first sample n = 2·3 = 6. The divisors of 6 are 1, 2, 3 and 6, their product is equal to 1·2·3·6 = 36.

In the second sample 2·3·2 = 12. The divisors of 12 are 1, 2, 3, 4, 6 and 12. 1·2·3·4·6·12 = 1728.

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
from functools import reduce
import sys
m = int(input())
p = 10 ** 9 + 7
dividors = [int(x) for x in input().split()]
D = {}
for d in dividors:
	if d in D:
		D[d] += 1
	else:
		D[d] = 1
prod = reduce(lambda x, y: x * y % p, dividors)
deg = reduce(lambda x, y: x * y, (d + 1 for d in list(D.values())))
if deg % 2:
	prod = reduce(lambda x, y: x * y % p, (pow(d, i // 2, p) for (d, i) in list(D.items())))
	ans = pow(prod, deg % (p - 1), p)
else:
	ans = pow(prod, deg // 2 % (p - 1), p)
print(ans)


import math
lca = lambda a, b: a * b // math.gcd(a, b)
mod = 1000000007
m = int(input())
ps = map(int, input().split())
cnt = {}
for p in ps:
	if p not in cnt:
		cnt[p] = 0
	cnt[p] += 1
lca_i = 1
k = 1
for i in cnt.values():
	k *= i + 1
	lca_i = lca(lca_i, i + 1)
ans = 1
for (p, i) in cnt.items():
	ans = ans * pow(p, i * (i + 1) // 2 * lca_i // (i + 1), mod) % mod
ans = pow(ans, k // lca_i, mod)
print(ans)


mod_number = 10 ** 9 + 7

def power_mod(n, p):
	if p < 2:
		return n ** p % mod_number
	sub_result = power_mod(n, p // 2)
	if p % 2 == 0:
		return sub_result ** 2 % mod_number
	else:
		return sub_result ** 2 * n % mod_number

def get_frequency_map(items):
	frequency_map = {}
	for item in items:
		if item in frequency_map:
			frequency_map[item] += 1
		else:
			frequency_map[item] = 1
	return frequency_map

def get_product_of_others(items):
	length = len(items)
	prefix_product_of_others = [1] * length
	suffix_product_of_others = [1] * length
	for i in range(1, length):
		prefix_product_of_others[i] = prefix_product_of_others[i - 1] * items[i - 1] % (mod_number - 1)
	for i in reversed(list(range(length - 1))):
		suffix_product_of_others[i] = suffix_product_of_others[i + 1] * items[i + 1] % (mod_number - 1)
	return [prefix_product_of_others[i] * suffix_product_of_others[i] for i in range(length)]

def main():
	m = int(input())
	prime_factors = [int(t) for t in input().split()]
	prime_factors_count_map = get_frequency_map(prime_factors)
	ordered_prime_factors = list(prime_factors_count_map.keys())
	each_prime_factor_choices = [prime_factors_count_map[prime_factor] + 1 for prime_factor in ordered_prime_factors]
	other_prime_factors_choices = get_product_of_others(each_prime_factor_choices)
	total_factors = 1
	for (i, prime_factor) in enumerate(ordered_prime_factors):
		prime_factor_count = prime_factors_count_map[prime_factor]
		total_power_of_factor = prime_factor_count * (prime_factor_count + 1) // 2
		product_of_factor_by_prime_factor = power_mod(prime_factor, total_power_of_factor % (mod_number - 1))
		total_factors *= power_mod(product_of_factor_by_prime_factor, other_prime_factors_choices[i] % (mod_number - 1))
	print(total_factors % mod_number)

def __starting_point():
	main()
__starting_point()


import collections

def logpow(a, b, mod):
	if b == 0:
		return 1
	v = logpow(a, b // 2, mod)
	ret = v * v % mod
	if b % 2 == 1:
		ret = ret * a % mod
	return ret
mod = 1000000007
n = int(input())
d = collections.defaultdict(int)
for x in input().split():
	d[int(x)] += 1
b = [(x, y) for (x, y) in list(d.items())]
pl = [1 for i in range(len(b) + 2)]
pr = [1 for i in range(len(b) + 2)]
for i in range(1, len(b) + 1):
	pl[i] = pl[i - 1] * (1 + b[i - 1][1]) % (mod - 1)
	j = len(b) - i + 1
	pr[j] = pr[j + 1] * (1 + b[j - 1][1]) % (mod - 1)
ret = 1
for i in range(1, len(b) + 1):
	pp = pl[i - 1] * pr[i + 1] % (mod - 1)
	pp = pp * (b[i - 1][1] * (b[i - 1][1] + 1) // 2) % (mod - 1)
	ret = ret * logpow(b[i - 1][0], pp, mod) % mod
print(ret)


n = int(input())
MOD = 10 ** 9 + 7
p = [int(i) for i in input().split()]
p.sort()
a = []
index = 0
now = p[0]
cnt_now = 0
while index < n:
	while index < n and p[index] == now:
		index += 1
		cnt_now += 1
	a.append([now, cnt_now])
	if index < n:
		now = p[index]
		cnt_now = 0
tau = 1
ans = 1
for i in range(len(a)):
	tau = tau * (a[i][1] + 1)
for i in range(len(a)):
	deg = tau * a[i][1] // 2
	ans = ans * pow(a[i][0], deg % (MOD - 1), MOD) % MOD
print(ans)


import math
m = 10 ** 9 + 7
n = int(input())
lis = list(map(int, input().split()))
ans = [0] * 200005
t = ta = 1
for i in lis:
	ans[i] += 1
for i in range(1, 200005):
	if ans[i] == 0:
		continue
	else:
		p = pow(i, ans[i] * (ans[i] + 1) // 2 % (m - 1), m)
		t = pow(t, ans[i] + 1, m) * pow(p, ta, m) % m
		ta = ta * (ans[i] + 1) % (m - 1)
print(t)


from collections import Counter
md = 10 ** 9 + 7
m = int(input())
cnt = Counter(list(map(int, input().split())))
ans = x = 1
for k in cnt.values():
	x *= k + 1
for (a, b) in cnt.items():
	p = x * b // 2 % (md - 1)
	ans = ans * pow(a, p, md) % md
print(ans)


from collections import Counter as C
from operator import __mul__
mod = 10 ** 9 + 7
n = int(input())
m = C(map(int, input().split()))
ans = mul = 1
for elem in m.values():
	mul *= elem + 1
for (a, b) in m.items():
	curr = mul * b // 2
	curr %= mod - 1
	ans *= pow(a, curr, mod)
	ans %= mod
print(ans)


import operator
from collections import Counter
from functools import reduce

def solve(primes):
	products = 1
	for x in primes.values():
		products *= x + 1
		products %= 2 * (10 ** 9 + 6)
	n = 1
	for (x, y) in primes.items():
		n *= pow(x, y * (y + 1) // 2 * products // (y + 1), 10 ** 9 + 7)
		n %= 10 ** 9 + 7
	return n

def main():
	m = int(input())
	primes = Counter(map(int, input().split()))
	print(solve(primes))

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10001)

def main():
	m = int(input())
	temp = input().split()
	primes = [int(x) for x in temp]
	print(solver2(primes))

def solver2(primes):
	modulus = 10 ** 9 + 7
	primesDict = dict()
	for p in primes:
		if p not in primesDict:
			primesDict[p] = 1
		else:
			primesDict[p] += 1
	factors = 1
	for p in primesDict:
		factors *= primesDict[p] + 1
	if factors % 2 == 0:
		n = 1
		for p in primesDict:
			n = n * pow(p, primesDict[p], modulus) % modulus
		return pow(n, factors // 2, modulus)
	else:
		sqrtN = 1
		for p in primesDict:
			sqrtN = sqrtN * pow(p, primesDict[p] // 2, modulus) % modulus
		return pow(sqrtN, factors, modulus)

def expMod(n, e, modulus, recLimit=0):
	if e == 1:
		return n % modulus
	elif e % 2 == 0:
		return expMod(n, e // 2, modulus) ** 2 % modulus
	else:
		return n * expMod(n, e // 2, modulus) ** 2 % modulus

def digitCount(n):
	n = abs(n)
	count = 0
	while n > 0:
		count += 1
		n //= 10
	return count
main()


from collections import Counter
from functools import reduce

def main():
	input()
	MOD = int(1000000000.0 + 7)
	u = list(map(int, input().split()))
	v = Counter(u)
	e = reduce(lambda a, b: a * b, [it + 1 for it in v.values()])
	ans = 1
	e %= 2 * (MOD - 1)
	for (a, b) in v.items():
		ans = ans * pow(a, b * e // 2, MOD) % MOD
	print(ans)
main()


def rint():
	return int(input())

def rints():
	return list(map(int, input().split()))
from itertools import groupby
from functools import reduce
MOD = 10 ** 9 + 7
n = rint()
p = rints()
p.sort()
p2 = [(k, sum((1 for _ in g))) for (k, g) in groupby(p)]
prefdivs = [0] * len(p2)
prefdivs[0] = p2[0][1] + 1
for i in range(1, len(p2)):
	prefdivs[i] = prefdivs[i - 1] * (p2[i][1] + 1) % (MOD - 1)
suffdivs = [0] * len(p2)
suffdivs[-1] = p2[-1][1] + 1
for i in reversed(range(len(p2) - 1)):
	suffdivs[i] = suffdivs[i + 1] * (p2[i][1] + 1) % (MOD - 1)
res = 1
for (i, (pi, e)) in enumerate(p2):
	remdivs = (1 if i == 0 else prefdivs[i - 1]) * (1 if i + 1 == len(p2) else suffdivs[i + 1]) % (MOD - 1)
	for i in range(e + 1):
		res = res * pow(pi, i * remdivs % (MOD - 1), MOD) % MOD
print(res)


MD = 1000000007
m = int(input())
p = list(map(int, input().split()))
q = {}
for el in p:
	if el in q:
		q[el] += 1
	else:
		q[el] = 2
sum1 = 1
sum2 = 1
for el in q:
	sum1 = sum1 * q[el]
	sum2 = sum2 * pow(el, q[el] - 1, MD)
sum = pow(sum2, sum1 // 2, MD)
if sum1 % 2 == 1:
	for el in q:
		sum = sum * pow(el, q[el] // 2, MD) % MD
print(sum)


from collections import Counter
M = 10 ** 9 + 7

def multipliers(pfs):
	y = 1
	for c in pfs.values():
		y *= c + 1
	if y % 2:
		sx = 1
		for (p, c) in pfs.items():
			sx = sx * pow(p, c // 2, M) % M
		return pow(sx, y, M)
	else:
		x = 1
		for (p, c) in pfs.items():
			x = x * pow(p, c, M) % M
		return pow(x, y // 2, M)
m = int(input())
pfs = Counter(map(int, input().split()))
print(multipliers(pfs))


n = int(input())
exps = {}
for x in [int(x) for x in input().split()]:
	exps[x] = exps.get(x, 0) + 1
(r, m) = (1, 1)
M = 1000000007
P = M - 1
for (p, e) in exps.items():
	E = e * (e + 1) // 2 % P
	E = E * m % P
	r = pow(r, e + 1, M) * pow(p, E, M) % M
	m = m * (e + 1) % P
print(r)


MOD = 1000000007
top = 0
t = [0] * 200005
x = int(input())
y = list(map(int, input().split(' ')))
if 10 ** 9 + 7 in y:
	print(0)
	quit()
base = 1
sq = True
for i in y:
	t[i] += 1
	base *= i
	base %= MOD
for i in range(200005):
	if t[i] % 2 == 1:
		sq = False
ans = 1
powf = 1
if sq:
	for i in range(200005):
		ans *= pow(i, t[i] // 2, MOD)
		ans %= MOD
		powf *= t[i] + 1
		powf %= MOD - 1
	print(pow(ans, powf, MOD))
	quit()
two = False
for i in range(200005):
	if not two and t[i] % 2 == 1:
		two = True
		powf *= (t[i] + 1) // 2
	else:
		powf *= t[i] + 1
	powf %= MOD - 1
print(pow(base, powf, 10 ** 9 + 7))


from collections import *
input()
d = 1000000007
c = Counter(map(int, input().split()))
s = n = 1
for k in c.values():
	n *= k + 1
for (p, k) in c.items():
	s = s * pow(p, n * k // 2 % (d - 1), d) % d
print(s)


n = int(input())
s = input().split()
m = [-1]
ch = 1
md = 1000000007
for i in range(n):
	m.append(int(s[i]))
	ch = ch * int(s[i]) % md
m.sort()
kol = 1
z = 1
kolraz = 0
fl = 1
sq = 1
for i in range(2, n + 1):
	if m[i] == m[i - 1]:
		kol += 1
	else:
		for j in range(kol // 2):
			sq = sq * m[i - 1] % md
		if kol % 2 == 1:
			fl = 0
		z *= kol + 1
		kol = 1
		kolraz += 1
z *= kol + 1
for j in range(kol // 2):
	sq = sq * m[n] % md
if kol % 2 == 1:
	fl = 0
res = 1
kol = z
kol //= 2
if fl:
	res = sq
while kol:
	if kol & 1:
		res = res * ch % 1000000007
	ch = ch * ch % md
	kol >>= 1
print(res)


from sys import stdin
m = int(stdin.readline())
p = [int(x) for x in stdin.readline().split()]
pD = {}
for x in p:
	if x in pD:
		pD[x] += 1
	else:
		pD[x] = 1
perms = 1
for x in pD:
	perms *= pD[x] + 1
	perms %= 1000000006 * 2
prod = 1
for x in pD:
	prod *= pow(x, perms * pD[x] // 2, 1000000007)
	prod %= 1000000007
print(prod % 1000000007)


M = 10 ** 9 + 7
m = int(input())
A = list(map(int, input().split()))
D = {}
for i in A:
	if i not in D:
		D[i] = 0
	D[i] += 1
alph = 1
for j in D:
	alph *= D[j] + 1
ans = 1
for j in D:
	ans *= pow(j, alph * D[j] // 2 % (M - 1), M)
	ans %= M
print(ans)


def binaryPow(a, q, mod):
	a %= mod
	if q == 0:
		return 1
	elif q % 2 == 1:
		return a * binaryPow(a * a, q // 2, mod) % mod
	else:
		return binaryPow(a * a, q // 2, mod) % mod
mod = 1000000007
n = int(input())
gg = [int(a) for a in input().split()]
fact = {}
for i in range(n):
	if gg[i] not in fact.keys():
		fact[gg[i]] = 1
	else:
		fact[gg[i]] += 1
d = 1
ans = 1
for (k, v) in fact.items():
	tmp = binaryPow(k, (v + 1) * v // 2, mod)
	ans = binaryPow(ans, v + 1, mod) * binaryPow(tmp, d, mod) % mod
	d = d * (v + 1) % (mod - 1)
print(ans)


import functools, operator
m = int(input())
p = [int(x) for x in input().split()]
P = {}
n = 1
for i in p:
	P[i] = P.get(i, 0) + 1
	n = n * i % 1000000007
dv = functools.reduce(operator.mul, (l + 1 for l in list(P.values())))
prod = 0
if dv & 1:
	prod = pow(int(functools.reduce(operator.mul, (pow(p, i // 2, 1000000007) for (p, i) in list(P.items())))), dv, 1000000007)
else:
	prod = pow(n, dv // 2, 1000000007)
print(prod % 1000000007)


mod = 10 ** 9 + 7

def pow(a, b):
	exp = 1
	x = a % mod
	b = b % (mod - 1)
	while b > 0:
		if b % 2 == 1:
			exp = exp * x % mod
		x = x * x % mod
		b = b // 2
	return exp % mod
x = input()
primes = map(int, input().split())
primesDicc = dict()
n = 1
for p in primes:
	n = n * p % mod
	if p not in primesDicc:
		primesDicc[p] = 1
	else:
		primesDicc[p] += 1
countdiv = 1
raiz = 1
for p in primesDicc:
	countdiv *= primesDicc[p] + 1
result = 0
if countdiv % 2 == 0:
	result = pow(n, countdiv // 2)
else:
	for p in primesDicc:
		raiz = raiz * pow(p, primesDicc[p] // 2)
	result = raiz * pow(n, countdiv // 2) % mod
print(result)


from collections import Counter
MOD = 1000000007

def pow_m(base, pw):
	if pw == 0:
		return 1
	elif pw % 2 == 1:
		return pow_m(base, pw // 2) ** 2 % MOD * base % MOD
	else:
		return pow_m(base, pw // 2) ** 2 % MOD
m = int(input())
p = [int(x) for x in input().split()]
c = Counter(p)
is_square = all((c[x] % 2 == 0 for x in c))
(base, root, pw) = (1, 1, 1)
for elem in c:
	if is_square:
		ppw = pow_m(elem, c[elem] // 2)
		base = base * (ppw ** 2 % MOD) % MOD
		root = root * ppw % MOD
	else:
		base = base * pow_m(elem, c[elem]) % MOD
	pw *= c[elem] + 1
pw = pw // 2 % (MOD - 1)
prod = pow_m(base, pw)
if is_square:
	prod = prod * root % MOD
print(prod)


import sys
input = sys.stdin.readline
from collections import Counter
m = int(input())
p = list(map(int, input().split()))
mod = 10 ** 9 + 7
cnt = Counter(p)
ans = x = 1
for k in cnt.values():
	x *= k + 1
for (a, b) in cnt.items():
	q = x * b // 2 % (mod - 1)
	ans = ans * pow(a, q, mod) % mod
print(ans)


import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
from collections import deque
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	n = int(input())
	a = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	d = collections.Counter(a)
	t = 1
	for x in a:
		t = t * x
		t = t % mod
	res = 1
	for k in d.keys():
		res = res * (d[k] + 1)

	def quickpower(v, count, p):
		tmp = 1
		while count:
			if count & 1:
				tmp = tmp * v % p
			v = v * v % p
			count = count >> 1
		return tmp
	cnt = res // 2
	ans = quickpower(t, cnt, mod)
	if res % 2 == 1:
		for k in d.keys():
			for j in range(d[k] // 2):
				ans = ans * k
				ans = ans % mod
	print(ans)
main()


readInts = lambda : list(map(int, input().split()))
n = int(input())
a = readInts()
p = {}
for b in a:
	p[b] = p.get(b, 0) + 1
MOD = 10 ** 9 + 7
ret = 1
cnt = 1
for x in list(p.items()):
	t = x[1]
	now = pow(x[0], (1 + t) * t // 2, MOD)
	ret *= pow(ret, t, MOD)
	ret %= MOD
	ret *= pow(now, cnt, MOD)
	ret %= MOD
	cnt = cnt * (t + 1)
	cnt %= MOD - 1
print(ret)


def read_list():
	return [int(i) for i in input().split()]

def new_list(n):
	return [0 for i in range(n)]

def new_matrix(n, m=0):
	return [[0 for i in range(m)] for i in range(n)]
mod = 1000000007

def binPow(a, q, mod):
	a %= mod
	if q == 0:
		return 1
	return (q % 2 == 1 and a or 1) * binPow(a * a, q // 2, mod) % mod
n = int(input())
a = {}
b = read_list()
for c in b:
	if c in a:
		a[c] += 1
	else:
		a[c] = 1
(d, answ) = (1, 1)
for p in a:
	c = a[p]
	fp = binPow(p, (c + 1) * c // 2, mod)
	answ = binPow(answ, c + 1, mod) * binPow(fp, d, mod) % mod
	d = d * (c + 1) % (mod - 1)
print(answ)


MOD = 10 ** 9 + 7
ans = 1
tau = 1
N = 200005
cnt = [0] * N
n = int(input())
for x in input().split():
	cnt[int(x)] += 1
for i in range(1, N):
	if cnt[i] == 0:
		continue
	ans = pow(ans, cnt[i] + 1, MOD) * pow(i, cnt[i] * (cnt[i] + 1) // 2 % (MOD - 1) * tau % (MOD - 1), MOD) % MOD
	tau = tau * (cnt[i] + 1) % (MOD - 1)
print(ans)


n = int(input())
l = list(map(int, input().split()))
M = int(1000000000.0 + 7)
counter = {}
num = 1
for elem in l:
	num = num * elem % M
	try:
		counter[elem] += 1
	except:
		counter[elem] = 2
d = 1
for elem in counter:
	d *= counter[elem]
res = pow(num, d // 2, M)
checkodd = 1
for elem in counter:
	if counter[elem] % 2 == 0:
		checkodd = 0
		break
if checkodd:
	for elem in counter:
		for i in range(counter[elem] // 2):
			res = res * elem % M
print(res)


M = 1000000007

def mpow(n, p):
	if p == 0:
		return 1
	ans = mpow(n, int(p / 2))
	ans = ans * ans % M
	if p % 2 == 1:
		ans = ans * n
	return ans % M
n = int(input())
arr = input().split(' ')
m = [0] * 200001
for i in arr:
	m[int(i)] = m[int(i)] + 1
d = 1
ans1 = 1
ans2 = 1
e = -1
for i in m:
	e += 1
	if i == 0:
		continue
	if i % 2 == 0:
		ans1 = ans1 * mpow(e, i / 2) % M
	else:
		ans2 = ans2 * mpow(e, i) % M
b = False
for i in m:
	ans1 = mpow(ans1, i + 1) % M
	if i % 2 == 1:
		if not b:
			ans2 = mpow(ans2, (i + 1) / 2) % M
		else:
			ans2 = mpow(ans2, i + 1) % M
		b = True
	else:
		ans2 = mpow(ans2, i + 1) % M
print(ans1 * ans2 % M)


from collections import Counter
m = input()
values = Counter(map(int, input().split()))
M = 1000000007
d = 1
n = 1
for x in values.values():
	d *= x + 1
if d % 2:
	for (x, y) in values.items():
		n = n * pow(x, y // 2, M) % M
	print(pow(n, d, M))
else:
	for (x, y) in values.items():
		n = n * pow(x, y, M) % M
	print(pow(n, d // 2, M))


def I():
	return list(map(int, input().split()))
from collections import Counter
input()
x = Counter([i % 1000000007 for i in I()])
num_divisors = 1
n = 1
sqrt = 1
for prime in x:
	num_divisors *= x[prime] + 1
	n *= pow(prime, x[prime]) % 1000000007
	sqrt *= pow(prime, x[prime] // 2) % 1000000007
if num_divisors % 2 == 0:
	print(pow(n, num_divisors // 2, 1000000007))
else:
	print(pow(sqrt, num_divisors, 1000000007))


import sys
M = int(input())
P0 = list(map(int, input().split()))
P0 = sorted(P0)
P = []
Q = []
temp = 0
for i in range(M):
	if temp != P0[i]:
		temp = P0[i]
		P.append(temp)
		Q.append(1)
	else:
		Q[len(Q) - 1] += 1
mod = 10 ** 9 + 7
M = len(Q)
T = [1] * M
T1 = [1] * (M + 1)
T2 = [1] * (M + 1)
for i in range(M):
	T[i] = Q[i] * (Q[i] + 1) // 2 % (mod - 1)
	T1[i + 1] = T1[i] * (Q[i] + 1) % (mod - 1)
	T2[M - i - 1] = T2[M - i] * (Q[M - i - 1] + 1) % (mod - 1)
ans = 1
for i in range(M):
	temp = pow(P[i], T[i], mod)
	t = T1[i] * T2[i + 1] % (mod - 1)
	a = pow(temp, t, mod)
	ans = ans * a % mod
print(ans)


m = int(input())
a = []
a = input().split()
ans = 1
mod = int(1000000000.0 + 7)

def bin_pow(x, y):
	res = x
	ret = 1
	while y > 0:
		if y % 2:
			ret = ret * res % mod
		res = res * res % mod
		y //= 2
	return ret % mod
b = []
for i in range(200001):
	b.append(0)
for i in range(m):
	a[i] = int(a[i])
	b[a[i]] += 1
cnt = 1
for i in range(200001):
	if b[i] != 0:
		cnt = cnt * (b[i] + 1) % (2 * (mod - 1))
c = []
for i in range(200001):
	c.append(0)
for i in range(m):
	if c[a[i]] == 0:
		ans = ans * bin_pow(a[i], cnt * b[a[i]] / 2 % (2 * (mod - 1))) % mod
		c[a[i]] = 1
print(int(ans % mod))


def rint():
	return int(input())

def rints():
	return list(map(int, input().split()))
from itertools import groupby
from functools import reduce
MOD = 10 ** 9 + 7
(n, p) = (rint(), sorted(rints()))
p2 = ((k, sum((1 for _ in g))) for (k, g) in groupby(p))
(res, numdivs) = reduce(lambda t1, t2: (pow(t1[0], t2[1] + 1, MOD) * pow(t2[0], t2[1] * (t2[1] + 1) // 2 * t1[1] % (MOD - 1), MOD) % MOD, t1[1] * (t2[1] + 1) % (MOD - 1)), p2, (1, 1))
print(res)


input()
a = list(map(int, input().split()))
p = {}
for el in a:
	p[el] = p.get(el, 0) + 1
mod = 1000000007
(res, cnt) = (1, 1)
for x in p.items():
	t = x[1]
	now = pow(x[0], (t + 1) * t // 2, mod)
	res = res * pow(res, t, mod) % mod
	res = res * pow(now, cnt, mod) % mod
	cnt = cnt * (t + 1) % (mod - 1)
print(res)


mbase = 10 ** 9 + 7
nof = int(input())
facts = [int(x) for x in input().split()]
pmap = {}
for p in facts:
	pmap[p] = pmap.get(p, 0) + 1
onepprod = 1
for (p, q) in pmap.items():
	onepprod *= q + 1
	onepprod %= 2 * (mbase - 1)
res = 1
for (p, q) in pmap.items():
	res *= pow(p, q * onepprod // 2, mbase)
	res %= mbase
print(res)


m = int(input())
mod = 10 ** 9 + 7
exp = [0] * 200005
for x in input().split():
	exp[int(x)] += 1
p = 1
ans = 1
for i in range(1, 200005):
	if exp[i] == 0:
		continue
	temp = pow(i, exp[i] * (exp[i] + 1) // 2 % (mod - 1), mod)
	ans = pow(ans, exp[i] + 1, mod) * pow(temp, p, mod) % mod
	p = p * (exp[i] + 1) % (mod - 1)
print(ans)


import sys

def input():
	return sys.stdin.readline().rstrip()
DXY = [(0, -1), (1, 0), (0, 1), (-1, 0)]
mod = int(1000000000.0 + 7)
from collections import defaultdict

def main():
	n = int(input())
	d = defaultdict(int)
	a = list(map(int, input().split()))
	for v in a:
		d[v] += 1
	group_product = 1
	group_size = 1
	for (p, ord) in d.items():
		group_product = pow(group_product, ord + 1, mod)
		group_product *= pow(p, ord * (ord + 1) // 2 * group_size, mod)
		group_product %= mod
		group_size *= ord + 1
		group_size %= mod - 1
	print(group_product % mod)
	return 0
main()


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
sys.setrecursionlimit(300000)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
n = int(input())
l = list(map(int, input().split()))
d = defaultdict(int)
er = 1
for i in range(n):
	d[l[i]] += 1
	er *= l[i]
	er %= mod
cop = er
f = 0
ans = 1
t = 0
er1 = 1
tot = 1
k = 0
for i in d:
	t += 1
	tot *= d[i] + 1
	if d[i] % 2 == 1 and f == 0:
		f = 1
		ans = pow(er, (d[i] + 1) // 2, mod)
	elif f == 0 and t == len(d):
		k = 1
		tot //= d[i] + 1
		ans = pow(er, (d[i] + 1) // 2, mod)
	else:
		ans = pow(er, d[i] + 1, mod)
	er = ans
	er1 *= pow(i, d[i] // 2, mod)
	er1 %= mod
if f == 1:
	er1 = 1
if k == 1:
	ans *= pow(cop, tot // 2, mod)
er1 *= ans
er1 %= mod
print(er1)


m = int(input())
primes = list(map(int, input().split()))
dict = {}
result = 1
for p in primes:
	dict[p] = dict.get(p, 0) + 1
mult = 1
for x in dict.values():
	mult *= x + 1
	mult %= 2 * (10 ** 9 + 6)
for (x, y) in dict.items():
	result *= pow(x, y * mult // 2, 10 ** 9 + 7)
	result %= 10 ** 9 + 7
print(result)