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


if __name__ == '__main__':
    main()
