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 j4 {
    BufferedReader br;
    StringTokenizer in;
    PrintWriter out;

    public String nextToken() throws IOException {
        while (in == null || !in.hasMoreTokens()) {
            in = new StringTokenizer(br.readLine());
        }
        return in.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    public static void main(String[] args) throws IOException {
        new j4().run();
    }

    public long fastpow(long a, long b, long mod)
    {
        long answer = 1;
        if (b == 0)
            return answer;
        if (b % 2 == 1)
            answer = (answer * a) % mod;        
        answer *= fastpow((a * a) % mod, b / 2, mod);
        return answer % mod;
    }
    
    public void solve() throws IOException 
    {
        long n = nextLong();
        long a[] = new long [200000];
        long b[] = new long [200000];
        long c[] = new long [200000];
        long pref[] = new long [200000];
        long suff[] = new long [200000];
        Map <Integer, Integer> cnt = new HashMap <Integer, Integer>();
        //out.print(n);
        long mod = 1000000007;
        for (int i = 0; i < n; i++)
        {
            a[i] = nextInt();
            if (cnt.containsKey((int)a[i]))
            {
                int now = cnt.get((int)a[i]);
                cnt.remove((int)a[i]);
                cnt.put((int) a[i], now + 1);
            }
            else
                cnt.put((int) a[i],  1);    
        }
        Set set = cnt.entrySet();
        Iterator it = set.iterator();
        int i = 0;
        long answer = 1;
        while (it.hasNext())
        {
            Map.Entry<Integer, Integer> v = (Map.Entry<Integer, Integer>)it.next();
            b[i] = v.getKey();
            c[i] = v.getValue();
            pref[i] = c[i] + 1;
            suff[i] = c[i] + 1;
            i++;
        }
        n = i;
        if (n == 1)
        {
            long cur = b[0];
            for (i = 1; i <= c[0]; i++)
            {
                answer = (answer * cur) % mod;
                cur = (cur * b[0]) % mod;
            }
            out.print(answer);
            return;
        }

        for (i = 1; i < n; i++)
            pref[i] = (pref[i - 1] * pref[i]) % (mod - 1);
        for (i = (int) (n - 2); i >= 0; i--)
            suff[i] = (suff[i + 1] * suff[i]) % (mod - 1);
        for (i = 0; i < n; i++)
        {
            if (i == 0)
            {
                long cur = b[i];
                for (int j = 1; j <= c[i]; j++)
                {
                    long deg = suff[1];
                    answer = (answer * fastpow(cur, deg, mod)) % mod;
                    cur = (cur * b[i]) % mod;
                }
            }
            else
                if (i == (int)(n - 1))
                {
                    long cur = b[i];
                    for (int j = 1; j <= c[i]; j++)
                    {
                        long deg = pref[i - 1];
                        answer = (answer * fastpow(cur, deg, mod)) % mod;
                        cur = (cur * b[i]) % mod;
                    }
                    
                }
                else
                {
                    long cur = b[i];
                    for (int j = 1; j <= c[i]; j++)
                    {
                        long deg = (suff[i + 1] * pref[i - 1]) % (mod - 1);
                        answer = (answer * fastpow(cur, deg, mod)) % mod;
                        cur = (cur * b[i]) % mod;
                    }                   
                }           
        }
        out.print(answer);
    }

    public void run() {
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);

            solve();

            out.close();
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(1);
        }
    }
}