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

public class CodeForces
{
	public static void main(String args[])
	{
		Scanner input = new Scanner(System.in);

		long mod = 1000000007L;

		Hashtable<Long, Long> hm = new Hashtable<>();
		int m = input.nextInt();
		long prod = 1;
		for (int i = 0; i < m; i++)
		{
			long z = input.nextLong();
			prod = (prod * z) % mod;
			if (hm.get(z) != null)
			{
				long t = hm.get(z);
				hm.put(z, t + 1);
			} else
			{
				hm.put(z, 1L);
			}
		}
		boolean square = true;
		long index = 0;
		long num = 1;
		for (long i = 2; i <= 200000; i++)
		{
			if (hm.get(i) != null)
			{
				if (hm.get(i) % 2 == 1)
				{
					index = i;
					num = (hm.get(i) + 1) / 2;
					square = false;
					break;
				}
			}
		}
		if (square)
		{
			long prod1 = 1;
			long count = 1;

			for (long i = 2; i <= 200000; i++)
			{
				if (hm.get(i) != null)
				{
					count = (count * (hm.get(i) + 1)) % (mod - 1);
					prod1 = (prod1 * power(i, hm.get(i) / 2, mod)) % mod;
				}
			}
			System.out.println((power(prod1, count, mod) + mod) % mod);
		} else
		{
			for (long i = 2; i <= 200000; i++)
			{
				if (i != index)
				{
					if (hm.get(i) != null)
					{
						num = (num * (hm.get(i) + 1)) % (mod - 1);
					}
				}
			}
			System.out.println((power(prod, num, mod) + mod) % mod);
		}
	}

	public static long power(long a, long b, long mod)
	{
		long result = 1;
		while (b > 0)
		{
			if (b % 2 != 0)
			{
				result = (result * a) % mod;
				b--;
			}
			a = (a * a) % mod;
			b /= 2;
		}
		return result;
	}

	public static long modular_inverse(long n, long mod)
	{
		return power(n, mod - 2, mod);
	}

}