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.util.Scanner;
import java.io.*;
import java.util.*;
import java.math.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class D {
    
    public static long N = 1000000007;

    public static void main(String[] args) throws IOException {
        in = new StreamTokenizer( new InputStreamReader( System.in ) );

        int m = nextInt();
        HashMap<Integer,Integer> valz = new HashMap<Integer,Integer>(m);
        long n = 1;
        long nAlmost = 1;
        for(int i = 0;i<m;i++) {
            Integer val = Integer.valueOf(nextInt());
            n = (n * val) % N;
            Integer vInt = valz.get(val);
            if(vInt == null) {
                 valz.put(val,1);
            } else {
                 if(vInt % 2 == 1)
                 nAlmost  = (nAlmost  * val) % N;

                 valz.put(val, vInt+1);
            }
        }
        

        long p = 1;
        long p2 = 1;
        boolean wasEven = false;
        for(Integer key:valz.keySet()) {
            int tmp = valz.get(key) + 1;
            p = (p * tmp) % (N-1);
            if(!wasEven && tmp%2 ==0) {
               wasEven = true;
               tmp>>=1;
               
            }
            p2 = (p2*tmp) %(N-1);
         }

        //System.out.println(nTo(3,3,N));
        if(p%2 == 0) {
            long rez = nTo(n,p2,N);
            System.out.println(rez);
            return;
        } else {
            long rez = nTo(nAlmost,p,N);
            System.out.println(rez);
        }
    }

    static long nTo(long x, long n, long N) {
        long rez = 1;
        while(n >0) {
           
           if((n&1)==1) {
               rez = (rez * x)%N;
           }
           n>>=1;
           x = (x*x)%N;
        }
        return rez;
    }

    static StreamTokenizer in;
    static PrintWriter out;

    static int nextInt() throws IOException {
        in.nextToken();
        return ( int ) in.nval;
    }
    
}