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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.io.Writer;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;

//################################################################################################################
public class R338D2D {
	public static void main(String[] args) {
		R338D2D d = new R338D2D();
		InputReader1 reader = d.new InputReader1(System.in);
		OutputWriter writer = d.new OutputWriter(System.out);
		// think about the brute-force approach
		// read input
		// code boundary conditions
		int m = reader.readInt();
		Map<Integer, Integer> pr = new HashMap<Integer, Integer>();
		for (int i = 0; i < m; i++) {
			int p = reader.readInt();
			if (pr.containsKey(p)) {
				pr.put(p, pr.get(p) + 1);
			} else {
				pr.put(p, 1);
			}
		}
		int[] pra = new int[pr.size()];
		int[] prca = new int[pr.size()];
		int MOD = 1000000007;
		int ii = 0;
		for (int prime : pr.keySet()) {
			pra[ii] = prime;
			prca[ii] = pr.get(prime);
			ii++;
		}
		long[] lmul = new long[pra.length];
		long[] rmul = new long[pra.length];
		lmul[0] = prca[0] + 1;
		for (int i = 1; i < pra.length; i++) {
			lmul[i] = (lmul[i - 1] * (prca[i] + 1)) % (MOD - 1);
		}
		rmul[pra.length - 1] = prca[prca.length - 1] + 1;
		for (int i = pra.length - 2; i >= 0; i--) {
			rmul[i] = (rmul[i + 1] * (prca[i] + 1)) % (MOD - 1);
		}
		long ans = 1;
		for (int i = 0; i < pra.length; i++) {
			long cexp = 1;
			if (i > 0) {
				cexp = (cexp * lmul[i - 1]) % (MOD - 1);
			}
			if (i < (pra.length - 1)) {
				cexp = (cexp * rmul[i + 1]) % (MOD - 1);
			}
			cexp = (cexp * ((((long) prca[i] * (prca[i] + 1)) / 2) % (MOD - 1)))
					% (MOD - 1);
			ans = (ans * fastPow(pra[i], cexp, MOD)) % MOD;
		}
		writer.println(ans);
		reader.close();
		writer.close();
	}

	public static long fastPow(long x, long exp, long MOD) {
		if (exp == 0) {
			return 1;
		}
		if (exp == 1) {
			return x % MOD;
		}
		long xhexp = fastPow(x, exp / 2, MOD);
		if (exp % 2 == 0) {
			long tmp = (xhexp * xhexp) % MOD;
			return tmp;
		} else {
			long tmp = (xhexp * xhexp) % MOD;
			tmp = (tmp * (x % MOD)) % MOD;
			return tmp;
		}
	}

	class InputReader1 {
		// private final boolean finished = false;

		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader1(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 peek() {
			if (numChars == -1)
				return -1;
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					return -1;
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar];
		}

		public int readInt() {
			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 - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long readLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String readString() {
			int length = readInt();
			if (length < 0)
				return null;
			byte[] bytes = new byte[length];
			for (int i = 0; i < length; i++)
				bytes[i] = (byte) read();
			try {
				return new String(bytes, "UTF-8");
			} catch (UnsupportedEncodingException e) {
				return new String(bytes);
			}
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private String readLine0() {
			StringBuffer buf = new StringBuffer();
			int c = read();
			while (c != '\n' && c != -1) {
				if (c != '\r')
					buf.appendCodePoint(c);
				c = read();
			}
			return buf.toString();
		}

		public String readLine() {
			String s = readLine0();
			while (s.trim().length() == 0)
				s = readLine0();
			return s;
		}

		public String readLine(boolean ignoreEmptyLines) {
			if (ignoreEmptyLines)
				return readLine();
			else
				return readLine0();
		}

		public BigInteger readBigInteger() {
			try {
				return new BigInteger(readString());
			} catch (NumberFormatException e) {
				throw new InputMismatchException();
			}
		}

		public char readCharacter() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			return (char) c;
		}

		public double readDouble() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.') {
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, readInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.') {
				c = read();
				double m = 1;
				while (!isSpaceChar(c)) {
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, readInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}

		public boolean isExhausted() {
			int value;
			while (isSpaceChar(value = peek()) && value != -1)
				read();
			return value == -1;
		}

		public String next() {
			return readString();
		}

		public boolean readBoolean() {
			return readInt() == 1;
		}

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

	class OutputWriter {
		private final 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(String s) {
			writer.println(s);
		}

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

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

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

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

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