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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @author Don Li
 */
public class Multipliers {

    static final int MAXN = 200_005;
    static final int MOD = (int) (1e9 + 7);
    static final int MMOD = MOD - 1;

    int[] E;

    long[] sum;
    long[] L;
    long[] R;

    void solve() {
        int m = in.nextInt();

        E = new int[MAXN];
        for (int i = 0; i < m; i++) {
            int p = in.nextInt();
            E[p]++;
        }

        sum = new long[MAXN];
        sum[0] = 0;
        for (int i = 1; i < MAXN; i++) sum[i] = (sum[i - 1] + i) % MMOD;

        L = new long[MAXN];
        L[0] = 1;
        for (int i = 1; i < MAXN; i++) L[i] = L[i - 1] * (E[i] + 1) % MMOD;

        R = new long[MAXN];
        R[MAXN - 1] = 1;
        for (int i = MAXN - 2; i >= 0; i--) R[i] = R[i + 1] * (E[i] + 1) % MMOD;

        long res = 1;
        for (int i = 2; i < MAXN; i++) {
            if (E[i] > 0) {
                long exp = L[i - 1] * R[i + 1] % MMOD;
                exp = (long) E[i] * (E[i] + 1) / 2 % MMOD * exp % MMOD;
                res = res * pow(i, exp) % MOD;
            }
        }

        out.println(res);
    }

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

        E = new int[MAXN];
        for (int i = 0; i < m; i++) {
            int p = in.nextInt();
            E[p]++;
        }

        L = new long[MAXN];
        R = new long[MAXN];
        L[0] = 1;
        for (int i = 1; i < MAXN; i++) {
            L[i] = L[i - 1] * (E[i] + 1) % MMOD;
        }
        R[MAXN - 1] = 1;
        for (int i = MAXN - 2; i >= 0; i--) {
            R[i] = R[i + 1] * (E[i] + 1) % MMOD;
        }

        long ret = 1;
        for (int i = 1; i < MAXN; i++) {
            if (E[i] > 0) {
                long num = L[i - 1] * R[i + 1] % MMOD;
                ret = ret * pow(i, (long) E[i] * (E[i] + 1) / 2 % MMOD * num) % MOD;
            }
        }
        out.println(ret);
    }

    private long calc(int p) {
        long exp = ((long) (E[p] + 1) * E[p] / 2 % MMOD * (L[p - 1] * R[p + 1]) % MMOD) % MMOD;
        return pow(p, exp);
    }

    private long pow(long a, long n) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) > 0) res = res * a % MOD;
            a = a * a % MOD;
            n >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new Multipliers().solve();
        out.close();
    }

    static FastScanner in;
    static PrintWriter out;

    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;

        public FastScanner(BufferedReader in) {
            this.in = in;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

        public long nextLong() {
            return Long.parseLong(nextToken());
        }

        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}
