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.*;
import java.math.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Double.parseDouble;
import static java.lang.String.*;

public class Main {
    
    static int MOD = (int)1e9+7;
    static boolean work;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        StringTokenizer tk;
        
        int m = parseInt(in.readLine());
        tk = new StringTokenizer(in.readLine());
        long [] f = new long[200001];
        
        int n = 1,x,d=-1;
        long div = 1,ans = 1;
        
        for(int i=0; i<m; i++) {
            f[(x = parseInt(tk.nextToken()))]++;
        }
        
        for(int i=2; i<=200000; i++) {
            if(f[i]==0) continue;
            long B = pow(i,(f[i]+1)*f[i]/2);
            ans = (pow(ans,f[i]+1) * pow(B, div))%MOD;
            div = div * (f[i]+1)%(MOD-1);
        }
        
        System.out.println(ans);
   }
   
   static long pow(long n,long p) {
       if(p==0)
           return 1;
       
       if(p%2==1)
           return mul(pow(n,p-1),n);
       
       long r = pow(n,p/2);
       
       return mul(r,r);
   }
   
   static long pow2(long n,long p) {
       if(p==0)
           return 1;
       
       if(p%2==1)
           return mul(pow(n,p-1),n);
       
       long r = pow(n,p/2);
       
       return mul(r,r);
   }
    static long mul(long a,long b) {
        return ((a%MOD)*(b%MOD))%MOD;
    }
    
    static long mul2(long a,long b) {
        return ((a%(MOD-1))*(b%(MOD-1)))%(MOD-1);
    }
}