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