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.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main 
{
	static int mod=(int)(1e9)+7;
	static long quick(long a, long b)
	{
		long ans=1L;
		while(b!=0)
		{
			if(b%2==1)
				ans=ans*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ans%mod;
	}
	public static void main(String[] args) 
	{
		InputReader in = new InputReader();
		PrintWriter out = new PrintWriter(System.out);
//		int[] num=new int[200005];
//		Arrays.fill(num, 0);
//		for(int i=2;i<=200000;i++)
//			for(int j=i;j<=200000;j+=i)
//				num[j]++;
		while(in.hasNext())
		{
			int n=in.nextInt();
			long ans=1L;
			int[] num=new int[200005];
			for(int i=0;i<n;i++)
			{
				int x=in.nextInt();
				ans=ans*x%mod;
				num[x]++;
			}
			long cur=1L;
			boolean ok=false;
			for(int i=1;i<=200000;i++)
				if(!ok && num[i]%2==1)
				{
					ok=true;
					cur=(cur*((num[i]+1)/2))%(mod-1);
				}
				else 
					cur=(cur*(num[i]+1))%(mod-1);
			if(ok)
				out.println(quick(ans, cur));
			else 
			{
				ans=1L;
				for(int i=1;i<=200000;i++)
					ans=ans*quick(i, num[i]/2)%mod;
				out.println(quick(ans, cur));
			}
//			int sq=(int)Math.sqrt(n*1.0);
//			long ans=n;
//			if(sq*sq==n)
//				ans=quick(n, (num[n]-1)/2)*sq%mod;
//			else
//				ans=quick(n, num[n]/2);
//			out.println(ans);
		}
		out.close();
	}
}

class InputReader 
{
	BufferedReader buf;
	StringTokenizer tok;
	InputReader() 
	{
		buf = new BufferedReader(new InputStreamReader(System.in));
	}

	boolean hasNext() 
	{
		while (tok == null || !tok.hasMoreElements()) 
		{
			try 
			{
				tok = new StringTokenizer(buf.readLine());
			} 
			catch (Exception e) 
			{
				return false;
			}
		}
		return true;
	}

	String next() 
	{
		if (hasNext())
			return tok.nextToken();
		return null;
	}

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

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

	double nextDouble() 
	{
		return Double.parseDouble(next());
	}

	BigInteger nextBigInteger() 
	{
		return new BigInteger(next());
	}

	BigDecimal nextBigDecimal() 
	{
		return new BigDecimal(next());
	}
}