human
Write me a Python code to print one integer — the product of all divisors of n modulo 109 + 7 given the following:
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.
Solve the task in PYTHON.
assistant
#Here is Python code to print one integer — the product of all divisors of n modulo 109 + 7.

#!/usr/bin/python

import os
import sys
import itertools

MOD = 10 ** 9 + 7

def solve(f):
    m = f.read_int()
    p = {}

    for i in f.read_int_list():
        p[i] = p.get(i,0L) + 1

    base = 1
    for k,v in p.items():
        base *= v+1

    ans = 1
    if base % 2 == 1:
        for k,v in p.items():
            ans = (ans * long(pow(k, v/2, MOD))) % MOD
        ans = pow(ans, base, MOD)
    else:
        for k,v in p.items():
            ans = (ans * long(pow(k, v, MOD))) % MOD
        ans = pow(ans, base/2, MOD)

    return ans

class Reader(object):
    def __init__(self, filename=None):
        if filename: self.f = open(filename)
        else: self.f = sys.stdin

    def read_int(self):
        return int(self.f.readline().strip())
    def read_float(self):
        return float(self.f.readline().strip())
    def read_long(self):
        return long(self.f.readline().strip())
    def read_str(self):
        return self.f.readline().strip()

    def read_int_list(self):
        return [int(item) for item in self.f.readline().split()]
    def read_float_list(self):
        return [float(item) for item in self.f.readline().split()]
    def read_long_list(self):
        return [long(item) for item in self.f.readline().split()]
    def read_str_list(self):
        return self.f.readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv)>1 else None
    f = Reader(filename)
    print solve(f)