Ayrat has number n, represented as it's prime factorization pi of size m, i.e. n = p1·p2·...·pm. Ayrat got secret information that that the product of all divisors of n taken modulo 109 + 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 pi (2 ≤ pi ≤ 200 000).

Output

Print one integer — the product of all divisors of n modulo 109 + 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.
import math

def modpow (base, pwr, t):
    ret = 1
    while (pwr > 0):
        if ((pwr % 2) != 0):
            ret *= base
            ret %= t
        base **= 2
        base %= t
        pwr = int (pwr / 2)
    return ret

m = int(raw_input())
pi = [int (i) for i in raw_input().split()]
#pi.sort()
t = 1000000007
n = 1L
for i in xrange (m):
    n *= pi[i]
    n %= t
#apreekjina cik kura daliitaaja
pr = {}
#cnt = 0
for p in pi:
    if p in pr:
        pr[p] += 1
    else:
        pr[p] = 1
#    if (pi[i] == pi[i - 1]):
#        pc[cnt] += 1
#    else:
#        pc.append(1)
#        pr.append(pi[i])
#        cnt += 1
#div fun
df = 1
res = 1
for p in pr:
    df *= (pr[p] + 1)
dh = df / 2
if ((df % 2) == 1):
    for p in pr:
        res *= modpow(p, (pr[p] / 2), t)
        res %=t

res *= modpow(n, dh, t)
res %= t
print res
