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;
/*
23
190979 191627 93263 72367 52561 188317 198397 24979 70313 105239 86263 78697 6163 7673 84137 199967 14657 84391 101009 16231 175103 24239 123289

 */
public class d 
{
	public static void main(String[] arg) throws IOException
	{
		new d();
	}
	long MOD = 1_000_000_007;
	
	public d() throws IOException
	{
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int m = in.nextInt();
		long d = 1;
		long ans = 1;
		long[] bin = new long[200_001];
		for(int i = 0; i < m; i++)
		{
			bin[in.nextInt()]++;
		}
		for(int i = 1; i < bin.length; i++)
		{
			long b = pow(i, (bin[i]+1)*bin[i]/2);
			ans = pow(ans, bin[i]+1)*pow(b, d)%MOD;
			d = d*(bin[i]+1)%(MOD-1);
		}
		out.println(ans);
		in.close(); out.close();
	}
	long pow(long base, long exp)
	{
		if(exp == 0) return 1;
		if((exp&1) == 1) return pow(base, exp-1)*base%MOD;
		long ret = pow(base, exp/2)%MOD;
		return ret*ret%MOD;
	}
	class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;
		public FastScanner(InputStream in)
		{
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer("");
		}
		public String next() throws IOException
		{
			while(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}
		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}
		public void close() throws IOException
		{
			br.close();
		}
	}
}
