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.*;
import java.io.*;
import java.math.BigInteger;
public class Multipliers{
	public static long mod = 1000000007, mod1=mod-1;
	public static BigInteger dos = new BigInteger("2");
	public static void main(String args[]) throws IOException{
	BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
	int tmp = Integer.parseInt(lector.readLine());
	String t[] = lector.readLine().split(" ");
	Vector<Long> prim = new Vector<Long>();
	Vector<Long> exp = new Vector<Long>();
	Vector<Long> comb = new Vector<Long>();
	Vector<Long> pil = new Vector<Long>();
	int r[]=new int[tmp];
	long res = 1L;//BigInteger res = BigInteger.ONE;
	for(int n = 0;n<tmp;n++)r[n]=Integer.parseInt(t[n]);
	Arrays.sort(r);
	long trun = 1L;
	for(int n = 0;n<tmp;){
		int a = r[n];
		int u = n;
		int c =1;
		while(++u<tmp && a==r[u])c++;
		n=u;
		prim.add((long)a);//res=(pow((long)a),)%mod;
		//BigInteger p = new BigInteger(""+c);
		exp.add((long)c);
		trun = (trun*((long)c+1L))%mod1;//trun.multiply(p.add(BigInteger.ONE));
		pil.add(trun);
		comb.add(((((long)c)*((long)c+1))/2L)%mod1);
	}
		long col[] = new long[pil.size()];
		for(int n = exp.size()-1;n>-1;n--)
			col[n]=((n==exp.size()-1?1L:col[n+1])*(exp.get(n)+1L))%mod1;
	//System.out.println(prim+" "+exp+" "+trun+" "+pil);
	//for(int n = 0;n<col.length;n++)
		//System.out.print(col[n]+"--");
	for(int n = 0;n<exp.size();n++){
		long taa = comb.get(n)%mod1;
		taa = (taa*((n==0)?1L:pil.get(n-1)))%mod1;
		taa = (taa*(n==exp.size()-1?1L:col[n+1]))%mod1;
		while(taa<0)taa+=mod1;
		res = (res*pow(prim.get(n),taa))%mod;//res.multiply(new BigInteger().powMod(,mod)));
		//res = (res*pow(prim.get(n),(trun.divide(exp.get(n).add(BigInteger.ONE))).multiply(comb.get(n))))%mod;
	//System.out.println("ooo>"+prim.get(n)+" "+(comb.get(n)+(((n==0)?1L:pil.get(n-1))*(n==exp.size()-1?1L:col[n+1]))));
	}
	System.out.println(res);
	}
	public static long inv(long a,long b){
		BigInteger bb = new BigInteger(""+a).modInverse(new BigInteger(""+b));
		long r = Long.parseLong(bb.toString());
		while(r<0)r+=b;
		return r;
	}
	public static long pow(long a,long b){
		if(b==0)return 1L;
		if(b==1)return a;
		if(b%2==1)return (a*pow(a,b-1))%mod;
		long t = pow(a,b/2L);
		return (t*t)%mod;
		
	}
	
}