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 java.io.*;
import java.util.*;

public class P615D
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        TreeMap<Long, Integer> primesCount = new TreeMap<Long, Integer>();
        for(int i = 0; i < n; ++i)
        {
            long prime = in.nextLong();
            primesCount.put(prime, primesCount.getOrDefault(prime, 0) + 1);
        }

        long mod = 1000000007;
        long ans = 1;
        long[] primes = new long[primesCount.size()];
        long[] count = new long[primesCount.size()];
        {
            int i = 0;
            for(Map.Entry<Long, Integer> entry : primesCount.entrySet())
            {
                primes[i] = entry.getKey();
                count[i] = entry.getValue();
                ++i;
            }
        }

        long[] baseBefore = new long[primesCount.size()];
        long[] baseAfter = new long[primesCount.size()];
        for(int i = 0; i < primes.length; ++i)
        {
            if(i == 0)
            {
                baseBefore[i] = 1;
            }
            else
            {
                baseBefore[i] = baseBefore[i - 1] * (count[i - 1] + 1);
                baseBefore[i] = baseBefore[i] % (mod - 1);
            }
        }
        for(int i = primes.length - 1; i >= 0; --i)
        {
            if(i == primes.length - 1)
            {
                baseAfter[i] = 1;
            }
            else
            {
                baseAfter[i] = baseAfter[i + 1] * (count[i + 1] + 1);
                baseAfter[i] = baseAfter[i] % (mod - 1);
            }
        }

        for(int i = 0; i < primes.length; ++i)
        {
            long base = baseBefore[i] * baseAfter[i];
            base = base % (mod - 1);
            base = base * ((count[i] * (count[i] + 1) / 2) % (mod - 1));
            base = base % (mod - 1);
            ans = ans * powMod(primes[i], base, mod);

            // out.println(primes[i] + " " + base + " " + mod + " " + powMod(primes[i], base, mod));

            ans = ans % mod;
        }

        out.println(ans);

        out.close();
    }

    // a ^ b % c
    private static long powMod(long a, long b, long c)
    {
        if(b == 0)
        {
            return 1;
        }
        long t = powMod(a, b / 2, c);
        if(b % 2 == 1)
        {
            return (((t * t) % c) * a) % c;
        }
        else
        {
            return (t * t) % c;
        }
    }
}
