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 Main {

    public static int N = 200100, M = 1000000007;
    public static int[] cnt = new int[N];
    public static long[] pref = new long[N];
    public static long[] suff = new long[N];

    public static void solve(FastIO io) {
        int m = io.nextInt();
        for(int i = 0; i < m; ++i)
            ++cnt[io.nextInt()];

        pref[0] = 1;
        for(int i = 1; i < N; ++i)
            pref[i] = (cnt[i]+1) * pref[i-1] %(M-1);

        suff[N-1] = 1;
        for(int i = N-2; i >= 0; --i)
            suff[i] = (cnt[i]+1) * suff[i+1] %(M-1);

        long res = 1;
        for(int i = 1; i < N-1; ++i){
            long pw = ((((long)cnt[i] * (cnt[i]+1)/2)%(M-1)) * ((pref[i-1] * suff[i+1])%(M-1)))%(M-1);
            res = res * binPow(i, pw, M)%M;
        }

        io.println(res);
    }

    public static long binPow(long a, long b, long m){
        a %= m;
        long res = 1;
        while (b > 0) {
            if ((b & 1) != 0)
                res = res * a % m;
            a = a * a % m;
            b >>= 1;
        }
        return res;
    }

    public static class FastIO {
        private InputStream reader;
        private PrintWriter writer;

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

        public FastIO(InputStream r, OutputStream w) {
            reader = r;
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(w)));
        }

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

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

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

        public int[] nextIntArray(int n) {
            return nextIntArray(n, 0);
        }

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

        public long[] nextLongArray(int n) {
            return nextLongArray(n, 0);
        }

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

        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 void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects) {
            print(objects);
            writer.println();
        }

        public void printArray(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(arr[i]);
            }
        }

        public void printArray(long[] arr) {
            for (int i = 0; i < arr.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(arr[i]);
            }
        }

        public void printlnArray(int[] arr) {
            printArray(arr);
            writer.println();
        }

        public void printlnArray(long[] arr) {
            printArray(arr);
            writer.println();
        }

        public void printf(String format, Object... args) {
            print(String.format(format, args));
        }

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

    public static void main(String[] args) {
        FastIO io = new FastIO(System.in, System.out);
        solve(io);
        io.flush();
    }
}
