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

Starter code:

Solutions:
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;
#n = functools.reduce(operator.mul, (pow(p,i,1000000007) for p,i in P.items()))
if dv & 1:
    #prod = pow(int(n**0.5), dv, 1000000007)
    prod = pow(int(functools.reduce(operator.mul, (pow(p,i//2,1000000007) for p,i in list(P.items())))), dv, 1000000007)
    #prod = pow(int(n**0.5), dv, 1000000007);
else:
    #prod = pow(n, dv//2, 1000000007)
    #prod = pow(functools.reduce(operator.mul, p), dv//2, 1000000007)
    prod = pow(n, dv//2, 1000000007)
print(prod % 1000000007)



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 functools import reduce
import sys

#f = open('test', 'r')
#sys.stdin = f
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 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)


#!/usr/bin/env python3
import math
lca = lambda a, b: a * b // math.gcd(a,b)
mod = 1000000007
m = int(input())
ps = list(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 list(cnt.values()):
    k *= i + 1
    lca_i = lca(lca_i, i+1)
ans = 1
for p, i in list(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)


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)


n = int(input())
l = list(map(int, input().split()))
M = int(1e9+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)

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)

from collections import Counter
md = 10**9+7
m = int(input())
cnt = Counter(list(map(int,input().split())))

ans = x = 1
for k in list(cnt.values()) : x*=k+1
for (a,b) in list(cnt.items()) :
    p = (x*b//2)%(md-1)
    ans = (ans*pow(a,p,md))%md
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())

    # if prime factor 2 occurs three times
    # it can be choose four way to form other factors
    # taking three times, taking two times, taking one times and not taking 2 to form a factor
    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]
        # if prime factor 2 occurs four time then possible factors by 2, 4, 8
        # means product of the factors will be 2^(1+2+3)
        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()

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)

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:
        for i in range(q[el]//2):
            sum = (sum * el) % MD
print(sum)

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

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 list(pmap.items()):
	onepprod*= q+1
	onepprod%= 2*(mbase-1)

res = 1
for (p, q) in list(pmap.items()):
	res*= pow(p, (q*onepprod)//2, mbase)
	res%= mbase

print(res)


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)

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
	# create mapping of primes to their count
	primesDict = dict()
	for p in primes:
		if p not in primesDict:
			primesDict[p] = 1
		else:
			primesDict[p] += 1
	# total number of factors
	factors = 1
	for p in primesDict:
		factors *= (primesDict[p] + 1)
		factors %= 2 * (modulus - 1)
	if factors % 2 == 0:
		# calculate n
		n = 1
		for p in primesDict:
			n = (n * expMod(p, primesDict[p], modulus)) % modulus
		#if primes[0] == 31481:
			#print(digitCount(factors))
		#	return 86721852
		return expMod(n, factors // 2, modulus)
	else:
		# all powers are even, so 
		#n must be a perfect square
		#try:
		#	sqrtN = int(round(n**0.5))
		#except:
		sqrtN = 1
		for p in primesDict:
			sqrtN = (sqrtN * expMod(p, primesDict[p] // 2, modulus)) % modulus
		return expMod(sqrtN, factors, modulus)

def expMod(n, e, modulus, recLimit = 0):
	if e == 1:
		return n % modulus
	#elif recLimit == 10000:
	#	return (n**e) % modulus
	elif e % 2 == 0:
		return (expMod(n, e // 2, modulus)**2) % modulus
	# e % 2 != 0
	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()
#print(digitCount(2**200000))
#975988510
#factors = 10**5234
#print(expMod(975988510, factors, 10**9 + 7))

#print(expMod(3, 9, 2))
#print(solver2([135391] * 200000))
#print(solver2([2, 3, 2]))
#print(solver2([63997, 63997]))

#print(63997 **3 % (10**9 + 7))
#print(63997**2)
#print(expMod(135391, 100000, 10**9 + 7))
#a = 135391**100000 % (10**9 + 7)
#print(a)

# a = "31481 140797 186479 4861 79613 178439 137909 106291 31069 22271 22643 50549 31981 24631 129443 83449 11969 102299 199499 40627 56701 188017 138727 63473 22643 6763 24631 118463 93239 22643 166399 129401 106291 142469 4153 199499 53129 127 41863 24551 106291 50671 81773 132421 86467 49171 41491 133769 13147 53453 83449 51659 157279 33679 138727 118463 18593 24631 16693 26437 139871 135701 58741 133723 111149 41491 137909 93239 78511 199499 41863 166399 103087 24029 3001 182297 17981 53453 53327"
# a = a.split()
# a = [int(x) for x in a]
# print(solver2(a))
# print(200000 // 79)



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)

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
	# create mapping of primes to their count
	primesDict = dict()
	for p in primes:
		if p not in primesDict:
			primesDict[p] = 1
		else:
			primesDict[p] += 1
	# total number of factors
	factors = 1
	for p in primesDict:
		factors *= (primesDict[p] + 1)
		#factors %= 2 * (modulus - 1)
	if factors % 2 == 0:
		# calculate n
		n = 1
		for p in primesDict:
			n = (n * pow(p, primesDict[p], modulus)) % modulus
		#if primes[0] == 31481:
			#print(digitCount(factors))
		#	return 86721852
		return pow(n, factors // 2, modulus)
	else:
		# all powers are even, so 
		#n must be a perfect square
		#try:
		#	sqrtN = int(round(n**0.5))
		#except:
		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 recLimit == 10000:
	#	return (n**e) % modulus
	elif e % 2 == 0:
		return (expMod(n, e // 2, modulus)**2) % modulus
	# e % 2 != 0
	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()
#print(digitCount(2**200000))
#975988510
#factors = 10**5234
#print(expMod(975988510, factors, 10**9 + 7))

#print(expMod(3, 9, 2))
#print(solver2([135391] * 200000))
#print(solver2([2, 3, 2]))
#print(solver2([63997, 63997]))

#print(63997 **3 % (10**9 + 7))
#print(63997**2)
#print(expMod(135391, 100000, 10**9 + 7))
#a = 135391**100000 % (10**9 + 7)
#print(a)

# a = "31481 140797 186479 4861 79613 178439 137909 106291 31069 22271 22643 50549 31981 24631 129443 83449 11969 102299 199499 40627 56701 188017 138727 63473 22643 6763 24631 118463 93239 22643 166399 129401 106291 142469 4153 199499 53129 127 41863 24551 106291 50671 81773 132421 86467 49171 41491 133769 13147 53453 83449 51659 157279 33679 138727 118463 18593 24631 16693 26437 139871 135701 58741 133723 111149 41491 137909 93239 78511 199499 41863 166399 103087 24029 3001 182297 17981 53453 53327"
# a = a.split()
# a = [int(x) for x in a]
# print(solver2(a))
# print(200000 // 79)



#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2016 missingdays <missingdays@missingdays>
#
# Distributed under terms of the MIT license.

"""

"""

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


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)




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)

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)


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)

from collections import Counter
from functools import reduce

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

def __starting_point():
    main()

__starting_point()