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

public class Main {
    public static void main(String[] args) {
//     Test.testing();
        ConsoleIO io = new ConsoleIO();
        new Main(io).solve();
        io.flush();
    }
    ConsoleIO io;
    Main(ConsoleIO io) {
        this.io = io;
    }

    ArrayList<ArrayList<Integer>> gr1;
    boolean[] visit;
    //

    class Edge{
        public Edge(int u,int v) {
            this.u = u;
            this.v = v;
        }
        public int u;
        public int v;
    }

    int n,m,k,fn;
    public void solve() {
        m = io.readInt();
        int[] l = io.readIntArray();
        int[] c = new int[200001];
        for (int i = 0; i < l.length; i++)
            c[l[i]]++;
        long res = 1;
        long sum = 1;
        for (int i = 2; i < c.length; i++) if(c[i]>0) {
            long v = 1;
            long prev = res;
            res = 1;
            for(int t = 0;t<=c[i];t++) {
                long x = (prev * pow(v, sum)) % mod;
                res = (res * x) % mod;
                v = (v * i) % mod;
            }
            sum = (sum*(c[i]+1))%(mod-1);
        }
        io.writeLine("" + res);
    }
    long mod = 1_000_000_007;
    long pow(long a, long d){
        long res= 1;
        long v = a;
        while(d>0) {
            if ((d & 1) == 1) res = (res * v) % mod;
            v = (v * v) % mod;
            d/=2;
        }
        return res;
    }

}

class ConsoleIO {
    BufferedReader br;
    PrintWriter out;
    public ConsoleIO(){br = new BufferedReader(new InputStreamReader(System.in));out = new PrintWriter(System.out);}
    public void flush(){this.out.close();}
    public void writeLine(String s) {this.out.println(s);}
    public void writeInt(int a) {this.out.print(a);this.out.print(' ');}
    public void writeWord(String s){
        this.out.print(s);
    }
    public String readLine() {try {return br.readLine();}catch (Exception ex){ return "";}}
    public long readLong() {
        return Long.parseLong(this.readLine());
    }
    public int readInt() {
        return Integer.parseInt(this.readLine().trim());
    }
    public long[] readLongArray() {
        String[]n=this.readLine().trim().split(" ");long[]r=new long[n.length];
        for(int i=0;i<n.length;i++)r[i]=Long.parseLong(n[i]);
        return r;
    }
    public int[] readIntArray() {
        String[]n=this.readLine().trim().split("\\s+");int[]r=new int[n.length];
        for(int i=0;i<n.length;i++)r[i]=Integer.parseInt(n[i]);
        return r;
    }
}

