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

public class Main {
	
	public static void main(String[] args) {
		FastReader in = new FastReader(System.in);
		PrintWriter out = new PrintWriter(System.out);

		final int mod = (int) 1e9 + 7;
        final int pmod = mod - 1;
        final int max = 2 * 100000 + 100;

        int m = in.nextInt();

        int a[] = new int[max];
        for (int i = 0; i < m; i++)
            a[in.nextInt()]++;

        long pre[] = new long[max];
        long suf[] = new long[max];

        pre[0] = 1;
        for (int i = 1; i < max; i++)
            pre[i] = ((a[i] + 1) * pre[i - 1]) % pmod;

        suf[max - 1] = 1;
        for (int i = max - 2; i >= 0; i--)
            suf[i] = ((a[i] + 1) * suf[i + 1]) % pmod;

        long ans = 1;

        for (int i = 2; i + 1 < max; i++) {
            long curr = i;
            long oth = (pre[i - 1] * suf[i + 1]) % pmod;
            for (int j = 1; j <= a[i]; j++) {
                ans = (ans * powerMod(curr, oth, mod)) % mod;
                curr = (curr * i) % mod;
            }
        }

        out.println(ans);

		out.close();
	}

	public static long powerMod(long a, long n, long mod) {
		a %= mod;
		int x = Long.numberOfLeadingZeros(n);
		long ans = 1L;
		for(;x >= 0; --x) {
			ans = ans * ans % mod;
			if(n << 63 - x < 0)
				ans = ans * a % mod;
		}
		return ans;
	}
	static class FastReader {
	    private InputStream stream;
	    private final byte[] buf = new byte[8192];
	    private int curChar;
	    private int pnumChars;

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

	    private int pread() {
	        if (pnumChars == -1) {
	            throw new InputMismatchException();
	        }
	        if (curChar >= pnumChars) {
	            curChar = 0;
	            try {
	                pnumChars = stream.read(buf);
	            } catch (IOException e) {
	                throw new InputMismatchException();
	            }
	            if (pnumChars <= 0) {
	                return -1;
	            }
	        }
	        return buf[curChar++];
	    }

	    private int peek() {
	        if (pnumChars == -1) {
	            return -1;
	        }
	        if (curChar >= pnumChars) {
	            curChar = 0;
	            try {
	                pnumChars = stream.read(buf);
	            } catch (IOException e) {
	                return -1;
	            }
	            if (pnumChars <= 0) {
	                return -1;
	            }
	        }
	        return buf[curChar];
	    }

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

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

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

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

	    public String nextString() {
	        int c = pread();
	        while (isSpaceChar(c))
	            c = pread();
	        StringBuilder res = new StringBuilder();
	        do {
	            res.appendCodePoint(c);
	            c = pread();
	        } while (!isSpaceChar(c));
	        return res.toString();
	    }

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

	    private boolean isEndOfLine(int c) {
	        return c == '\n' || c == '\r' || c == -1;
	    }

	    public String nextLine() {
	        int c = pread();
	        while (isSpaceChar(c))
	            c = pread();
	        StringBuilder res = new StringBuilder();
	        do {
	            res.appendCodePoint(c);
	            c = pread();
	        } while (!isEndOfLine(c));
	        return res.toString();
	    }

	    public BigInteger nextBigInteger() {
	        try {
	            return new BigInteger(nextString());
	        } catch (NumberFormatException e) {
	            throw new InputMismatchException();
	        }
	    }

	    public char nextCharacter() {
	        int c = pread();
	        while (isSpaceChar(c))
	            c = pread();
	        return (char) c;
	    }

	    public char[] nextCharacterArray(int n) {
	        char[] chars = new char[n];
	        for (int i = 0; i < n; i++) {
	            chars[i] = nextCharacter();
	        }
	        return chars;
	    }

	    public char[][] nextCharacterMap(int n, int m) {
	        char[][] map = new char[n][];
	        for (int i = 0; i < n; i++) {
	            map[i] = nextCharacterArray(m);
	        }
	        return map;
	    }

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

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