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.*;

public class Main {
	public static void main(String args[]) {new Main().run();}

	FastReader in = new FastReader();
	PrintWriter out = new PrintWriter(System.out);
	void run(){
		work();
		out.flush();
	}
	long mod=1000000007;
	void work() {
		int n=in.nextInt();
		int[] A=new int[200001];
		for(int i=0;i<n;i++) {
			A[in.nextInt()]++;
		}
		long m=1;
		for(int i=0;i<200001;i++) {
			m*=A[i]+1;
			m%=(mod-1)*2;
		}
		long ret=1;
		for(int i=2;i<200001;i++) {
			int v=A[i];//(m/v)%mod
			//i*i^2*i^3...=i^((1+c)*c/2)=>^(m/v)%mod
			ret*=pow(i,v*m/2)%mod;
			ret%=mod;
		}
		out.println(ret);
	}
	private long pow(long v, long l) {
		long r=1;
		while(l>0) {
			if(l%2==1) {
				r*=v;
			}
			l/=2;
			v=v*v;
			v%=mod;
			r%=mod;
		}
		return r;
	}
}	



class FastReader
{
	BufferedReader br;
	StringTokenizer st;

	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}

	public String next() 
	{
		if(st==null || !st.hasMoreElements())
		{
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	public int nextInt() 
	{
		return Integer.parseInt(next());
	}

	public long nextLong()
	{
		return Long.parseLong(next());
	}
}