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.*;
import java.util.*;

public class multipliers
{
	public long pow_calc(long a, long q, long MOD)
	{
		a = a % MOD ;
		if (q == 0)        			return 1;
		if ((q % 2) == 1)
			 						return ((a*(pow_calc(a*a, q/2,MOD))%MOD));
		else 						return (pow_calc(a*a,q/2,MOD)%MOD);
	}
	
	
	public static void main(String args[])throws IOException
	{
		Scanner sc = new Scanner (System.in);
		int m;
		//System.out.println("enter m");
		m = sc.nextInt();
		 long MOD = 1_000_000_007;
		multipliers mm = new multipliers();
		
		long [] count  = new long [200_001];
		
		for (int i =0; i< m; i++)
		{
			//System.out.println("Enter the value of primes");
			int temp = sc.nextInt();
			count [temp] = count [temp] + 1;	
		}
		
		long ans  = 1;
		long d = 1;
		
		//for (int i =0; i< m+1; i++)
			//System.out.println(count[i] +" " + i);
		
		for (int i = 1; i< count.length; i++)
		{
			
			
			{
				//if (count[i]!=0)
				{
					long fp = mm.pow_calc(i, (((count[i] + 1)*(count[i]))/2), MOD);
					
					//System.out.println(fp + " this is p" + i);
					ans  = mm.pow_calc(ans, count[i]+1, MOD) * mm.pow_calc( fp , d , MOD)%MOD;
					d = d * (count[i]+1) % (MOD - 1);
				}
				
			}		
		}	
		System.out.println(ans);
	}
}
