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.
//package com.codeforces.competitions.year2016.jantomarch.round338div2;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.InputMismatchException;

/**
 * Codeforces Round 338 Div. 2 : Multipliers
 * <br />
 * Question Link : <b>http://codeforces.com/contest/615/problem/D</b>
 */
public final class Q4
{
	static int m, primeFactors[], count[];
	static long mod = (long) (1e9 + 7);
	static InputReader in;
	static OutputWriter out;
	
	public static void main(String[] args)
	{
		in = new InputReader(System.in);
		out = new OutputWriter(System.out);
		
		solve3();
		
		out.flush();
		
		in.close();
		out.close();
	}

	static void solve()
	{
/*		m = in.nextInt();
		
		factors = new int[m];
		
		for (int i = 0; i < m; i++)
			factors[i] = in.nextInt();*/

		long product = 1;

		for (int i = 1; i <= 600; i++)
		{
			if (600 % i == 0)
			{
				product = CMath.mod(product * i, mod);

//				System.out.println(i);
			}
		}

		System.out.println("product : " + product);

		long myProduct = CMath.mod(CMath.mod(CMath.modPower(2, 36, mod) * CMath.modPower(3, 12, mod), mod)
				* CMath.modPower(5, 24,	mod), mod);

		System.out.println("myProduct : " + myProduct);

		System.out.println("(2 ^ 15) % 7 = " + CMath.mod(32768, 7));
		System.out.println("(2 ^ (15 % 6)) % 7 = " + CMath.mod(CMath.power(2, CMath.mod(15, 6)), 7));
	}

	static void solve2()
	{
		m = in.nextInt();

		count = new int[(int) (2 * 1e5 + 1)];

		for (int i = 0; i < m; i++)
		{
			int prime = in.nextInt();

			count[prime]++;
		}

		long commonValue, modMinusOne;

		commonValue = 1;
		modMinusOne = mod - 1;

		for (int i = 2; i <= 2 * 1e5; i++)
			if (count[i] > 0)
				commonValue = CMath.mod(commonValue * (count[i] + 1), modMinusOne);

		System.out.println("commonValue before mul : " + commonValue);
		System.out.println("2 ^ (1e9 - 1 - 2) : " + CMath.moduloInverse(2, modMinusOne));

		commonValue = CMath.mod(commonValue * CMath.moduloInverse(2, modMinusOne), modMinusOne);
		
		System.out.println("commonValue after mul : " + commonValue);

		long product = 1;

		for (int i = 2; i <= 2 * 1e5; i++)
		{
			if (count[i] > 0)
			{
				long power = CMath.mod(CMath.mod(count[i] * commonValue, modMinusOne), modMinusOne);

				product = CMath.modPower(CMath.mod(product * i, mod), power, mod);
			}
		}

		out.println(product);
	}

	static void solve3()
	{
		m = in.nextInt();

		primeFactors = new int[m];
		count = new int[(int) (2 * 1e5 + 1)];

		for (int i = 0; i < m; i++)
		{
			primeFactors[i] = in.nextInt();

			count[primeFactors[i]]++;
		}

		long[] primes, occurrences;
		int primesCount = 0;

		primes = new long[(int) (2 * 1e5 + 1)];
		occurrences = new long[(int) (2 * 1e5 + 1)];

		for (int i = 2; i < 2 * 1e5; i++)
		{
			if (count[i] > 0)
			{
				primes[primesCount] = i;
				occurrences[primesCount++] = count[i];
			}
		}

		long[] left, right;
		long reducedMod = (mod - 1) / 2;

		left = new long[primesCount];
		right = new long[primesCount];

		left[0] = occurrences[0] + 1;
		right[primesCount - 1] = occurrences[primesCount - 1] + 1;

		for (int i = 1; i < primesCount; i++)
			left[i] = CMath.mod(left[i - 1] * (occurrences[i] + 1), mod - 1);

		for (int i = primesCount - 2; i >= 0; i--)
			right[i] = CMath.mod(right[i + 1] * (occurrences[i] + 1), mod - 1);

		long answer = 1;

		for (int i = 0; i < primesCount; i++)
		{
			long power = CMath.mod(occurrences[i] * (occurrences[i] + 1) / 2, mod - 1);

//			System.out.println("raw power : " + power);

			if (i > 0)
				power = CMath.mod(power * left[i - 1], mod - 1);

//			System.out.println("semi prepared power : " + power);

			if (i < primesCount - 1)
				power = CMath.mod(power * right[i + 1], mod - 1);

//			System.out.println("export quality power : " + power);

			answer = CMath.mod(answer * CMath.modPower(primes[i], power, mod), mod);

//			System.out.println("**i : " + i + ", answer : " + answer);
		}

		out.println(answer);
	}
	
	static class InputReader
	{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream)
		{
			this.stream = stream;
		}

		public int read()
		{
			if (numChars == -1)
				throw new InputMismatchException();

			if (curChar >= numChars)
			{
				curChar = 0;
				try
				{
					numChars = stream.read(buf);
				}
				catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}

			return buf[curChar++];
		}

		public int nextInt()
		{
			int c = read();

			while (isSpaceChar(c))
				c = read();

			int sgn = 1;

			if (c == '-')
			{
				sgn = -1;
				c = read();
			}

			int res = 0;

			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();

				res *= 10;
				res += c & 15;

				c = read();
			} while (!isSpaceChar(c));

			return res * sgn;
		}
		
		public int[] nextIntArray(int arraySize)
		{
			int array[] = new int[arraySize];
			
			for (int i = 0; i < arraySize; i++)
				array[i] = nextInt();
			
			return array;
		}

		public long nextLong()
		{
			int c = read();

			while (isSpaceChar(c))
				c = read();

			int sign = 1;

			if (c == '-')
			{
				sign = -1;

				c = read();
			}

			long result = 0;

			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();

				result *= 10;
				result += c & 15;

				c = read();
			} while (!isSpaceChar(c));

			return result * sign;
		}
		
		public long[] nextLongArray(int arraySize)
		{
			long array[] = new long[arraySize];
			
			for (int i = 0; i < arraySize; i++)
				array[i] = nextLong();
			
			return array;
		}

		public float nextFloat() // problematic
		{
			float result, div;
			byte c;

			result = 0;
			div = 1;
			c = (byte) read();

			while (c <= ' ')
				c = (byte) read();

			boolean isNegative = (c == '-');

			if (isNegative)
				c = (byte) read();

			do
			{
				result = result * 10 + c - '0';
			} while ((c = (byte) read()) >= '0' && c <= '9');

			if (c == '.')
				while ((c = (byte) read()) >= '0' && c <= '9')
					result += (c - '0') / (div *= 10);

			if (isNegative)
				return -result;

			return result;
		}

		public double nextDouble() // not completely accurate
		{
			double ret = 0, div = 1;
			byte c = (byte) read();

			while (c <= ' ')
				c = (byte) read();

			boolean neg = (c == '-');

			if (neg)
				c = (byte) read();

			do
			{
				ret = ret * 10 + c - '0';
			} while ((c = (byte) read()) >= '0' && c <= '9');

			if (c == '.')
				while ((c = (byte) read()) >= '0' && c <= '9')
					ret += (c - '0') / (div *= 10);

			if (neg)
				return -ret;

			return ret;
		}

		public String next()
		{
			int c = read();

			while (isSpaceChar(c))
				c = read();

			StringBuilder res = new StringBuilder();

			do
			{
				res.appendCodePoint(c);

				c = read();
			} while (!isSpaceChar(c));

			return res.toString();
		}

		public boolean isSpaceChar(int c)
		{
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
		
		public String nextLine()
		{
			int c = read();
			
			StringBuilder result = new StringBuilder();
			
			do
			{
				result.appendCodePoint(c);
				
				c = read();
			} while (!isNewLine(c));
			
			return result.toString();
		}
		
		public boolean isNewLine(int c)
		{
			return c == '\n';
		}

		public void close()
		{
			try
			{
				stream.close();
			}
			catch (IOException e)
			{
				e.printStackTrace();
			}
		}

	}

	static class OutputWriter
	{
		private PrintWriter writer;

		public OutputWriter(OutputStream stream)
		{
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
					stream)));
		}

		public OutputWriter(Writer writer)
		{
			this.writer = new PrintWriter(writer);
		}

		public void println(int x)
		{
			writer.println(x);
		}

		public void print(int x)
		{
			writer.print(x);
		}

		public void println(int array[], int size)
		{
			for (int i = 0; i < size; i++)
				println(array[i]);
		}

		public void print(int array[], int size)
		{
			for (int i = 0; i < size; i++)
				print(array[i] + " ");
		}

		public void println(long x)
		{
			writer.println(x);
		}

		public void print(long x)
		{
			writer.print(x);
		}

		public void println(long array[], int size)
		{
			for (int i = 0; i < size; i++)
				println(array[i]);
		}

		public void print(long array[], int size)
		{
			for (int i = 0; i < size; i++)
				print(array[i]);
		}

		public void println(float num)
		{
			writer.println(num);
		}

		public void print(float num)
		{
			writer.print(num);
		}

		public void println(double num)
		{
			writer.println(num);
		}

		public void print(double num)
		{
			writer.print(num);
		}

		public void println(String s)
		{
			writer.println(s);
		}

		public void print(String s)
		{
			writer.print(s);
		}

		public void println()
		{
			writer.println();
		}

		public void printSpace()
		{
			writer.print(" ");
		}

		public void flush()
		{
			writer.flush();
		}

		public void close()
		{
			writer.close();
		}

	}

	static class CMath
	{
		static long power(long number, long power)
		{
			if (number == 1 || number == 0 || power == 0)
				return 1;

			if (power == 1)
				return number;

			if (power % 2 == 0)
				return power(number * number, power / 2);
			else
				return power(number * number, power / 2) * number;
		}

		static long modPower(long number, long power, long mod)
		{
			if (number == 1 || number == 0 || power == 0)
				return 1;

			number = mod(number, mod);

			if (power == 1)
				return number;

			long square = mod(number * number, mod);

			if (power % 2 == 0)
				return modPower(square, power / 2, mod);
			else
				return mod(modPower(square, power / 2, mod) * number, mod);
		}

		static long moduloInverse(long number, long mod)
		{
			return modPower(number, mod - 2, mod);
		}

		static long mod(long number, long mod)
		{
			return number - (number / mod) * mod;
		}

	}

}

/*

47
9041 60013 53609 82939 160861 123377 74383 74383 184039 19867 123377 101879 74383 193603 123377 115331 101879 53609 74383 115331 51869 51869 184039 193603 91297 160861 160861 115331 184039 51869 123377 74383 160861 74383 115331 115331 51869 74383 19867 193603 193603 115331 184039 9041 53609 53609 193603
: corr

67
98929 19079 160079 181891 17599 91807 19079 98929 182233 92647 77477 98929 98639 182233 181891 182233 160079 98929 19079 98639 114941 98929 161341 91807 160079 22777 132361 92647 98929 77477 182233 103913 160079 77477 55711 77477 77477 182233 114941 91807 98929 19079 104393 182233 182233 131009 132361 16883 161341 103913 16883 98929 182233 114941 92647 92647 104393 132361 181891 114941 19079 91807 114941 132361 98639 161341 182233
: corr

44
73 59 17 41 37 7 71 47 29 83 67 17 53 61 43 43 3 23 29 11 7 83 61 79 31 37 37 83 41 71 11 19 83 2 83 73 7 67 83 13 2 53 31 47
: corr

42
1657 1871 2423 3037 5023 5099 5449 5701 6361 6619 7393 7489 8179 9743 9791 9907 12289 12457 13063 13933 14947 16141 16829 16943 17191 17863 20161 20947 21661 22727 23197 23201 23813 24023 24181 24223 24391 26479 28619 30529 32441 32611
:
 */
