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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;



public final class CF_338_Multipliers {

	void log(int[] X){
		int L=X.length;
		for (int i=0;i<L;i++){
			logWln(X[i]+" ");
		}
		log("");
	}


	void log(long[] X){
		int L=X.length;
		for (int i=0;i<L;i++){
			logWln(X[i]+" ");
		}
		log("");
	}
	void log(Object[] X){
		int L=X.length;
		for (int i=0;i<L;i++){
			logWln(X[i]+" ");
		}
		log("");
	}


	void log(Object o){
		logWln(o+"\n");
	}

	void logWln(Object o){
		System.out.print(o);
		//outputWln(o);

	}
	void info(Object o){
		System.out.println(o);
		//output(o);
	}

	void output(Object o){

		outputWln(""+o+"\n");

	}

	void outputWln(Object o){
		// System.out.print(o);

		try {
			out.write(""+ o);
		} catch (Exception e) {

		}
	}
	
	long powerMod(long b,long e,long m){
    	long x=1;
    	while (e>0) {
    		if (e%2==1)
    			x=(b*x)%m;
    		b=(b*b)%m;
    		e=e/2;
    	}
    	return x; 
    }

	long solveStupid(){
		long x=1;
		for (int u:p)
			x*=u;
		long res=1;
		for (int y=1;y<=x;y++){
			if (x%y==0){
				res*=y;
				if (res>=MOD)
					res%=MOD;
			}
		}
		return res;
	}
	
	int[] primes={2,3,5,7,11,13,17,19,23,29};
	
	void test(){
		log("Testing");
		//int L=primes.length;
		//int L=primes.length;
		int L=4;
		int NTESTS=10000;
		Random r=new Random();
		for (int t=0;t<NTESTS;t++){
		M=r.nextInt(8)+1;
		p=new int[M];
		for (int i=0;i<M;i++)
			p[i]=primes[r.nextInt(L)];
			
		long s1=solveStupid();
		long s2=solve();
		if (s1!=s2){
			log("Error");
			log(M);
			log(p);
			log("Good:"+s1+" Bad:"+s2);
			return;
			}
		}
		log("Done");
	}
	
	long solve(){
		Arrays.sort(p);
		ArrayList<Long[]> list=new ArrayList<Long[]>();
		for (int i=0;i<M;i++){
			long x=p[i];
			long num=1;
			while ((i+1)<M && x==p[i+1]){
				num++;
				i++;
			}
			list.add(new Long[]{x,num});
		}
		
		int L=list.size();
		
		long m=1;
		long count=1;
		for (int i=0;i<L;i++){
			//log("count:"+count);
			Long[] tmp=list.get(i);
			//log(tmp);
			long x=tmp[0];
			long n=tmp[1];

			m*=powerMod(m,n,MOD);
			if (m>=MOD)
				m%=MOD;
			long y;
			y=powerMod(x,(n*(n+1))/2,MOD);
			//log("y:"+y);
			y=powerMod(y,count,MOD);
			m*=y;
			if (m>=MOD)
				m%=MOD;
			
			count*=(n+1);
			if (count>=MOD-1)
				count%=MOD-1;
		}
		return m;
	}
	
	int M;
	int[] p;

	BufferedWriter out;
	String s,t;
	static long MOD=1000000007;
	
	void process() throws Exception {

		//test();
		
		out = new BufferedWriter(new OutputStreamWriter(System.out));
		InputReader reader=new InputReader(System.in);
		M=reader.readInt();
		p=new int[M];
		for (int i=0;i<M;i++)
			p[i]=reader.readInt();
		
		output(solve());
	//	output(solveStupid());
	
		try {
			out.close();
		}
		catch (Exception e){}


	}



	public static void main(String[] args) throws Exception {
		CF_338_Multipliers J=new CF_338_Multipliers();

		J.process();


	}


	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}


		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res=new StringBuilder();
			do {
				res.append((char)c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			//log("d:"+d);
			if (d=='-') {
				neg=true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			//log("d:"+d);
			if (d=='-') {
				neg=true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}




		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

} 