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.HashMap;
import java.util.Locale;
import java.util.Map;
import java.util.StringTokenizer;

public class D implements Runnable {

    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    private BufferedReader in;
    private PrintWriter out;
    private StringTokenizer tok = new StringTokenizer("");

    private void init() throws FileNotFoundException {
        Locale.setDefault(Locale.US);
        String fileName = "";
        if (ONLINE_JUDGE && fileName.isEmpty()) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }
        }
    }

    String readString() {
        while (!tok.hasMoreTokens()) {
            try {
                tok = new StringTokenizer(in.readLine());
            } catch (Exception e) {
                return null;
            }
        }
        return tok.nextToken();
    }

    int readInt() {
        return Integer.parseInt(readString());
    }

    long readLong() {
        return Long.parseLong(readString());
    }

    double readDouble() {
        return Double.parseDouble(readString());
    }

    int[] readIntArray(int size) {
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = readInt();
        }
        return a;
    }

    public static void main(String[] args) {
        //new Thread(null, new _Solution(), "", 128 * (1L << 20)).start();
        new D().run();
    }

    long timeBegin, timeEnd;

    void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    @Override
    public void run() {
        try {
            timeBegin = System.currentTimeMillis();
            init();
            solve();
            out.close();
            time();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

    final int MOD = 1000 * 1000 * 1000 + 7;

    private void solve() {
        int n = readInt();
        Map<Integer, Integer> primes = new HashMap<>();

        long answer = 1;
        int[] p = new int[n];

        for (int i = 0; i < n; i++) {
            p[i] = readInt();
            if (primes.containsKey(p[i])) {
                primes.put(p[i], primes.get(p[i]) + 1);
            } else {
                primes.put(p[i], 1);
            }
        }

        boolean allOdd = true;
        for (Map.Entry<Integer, Integer> entry : primes.entrySet()) {
            int count = entry.getValue();
            allOdd &= count % 2 == 0;
        }

        for (Map.Entry<Integer, Integer> entry : primes.entrySet()) {
            int count = entry.getValue();
            if (allOdd) {
                count /= 2;
            }
            for (int i = 0; i < count; i++) {
                answer = (answer * entry.getKey()) % MOD;
            }
        }

        boolean wasDivided = false;
        for (Map.Entry<Integer, Integer> entry : primes.entrySet()) {
            int power = (entry.getValue() + 1);
            if (!wasDivided && !allOdd && power % 2 == 0) {
                wasDivided = true;
                power /= 2;
            }
            answer = binpow(answer, power);
        }

        out.println(answer);
    }

    int getReverse(int x) {
        return binpow(x, MOD - 2);
    }

    int binpow(long a, int n) {
        if (n == 0) {
            return 1 % MOD;
        }
        if (n % 2 == 0) {
            int value = binpow(a, n / 2);
            return (int) (((long) value * value) % MOD);
        } else {
            return (int) ((a * binpow(a, n - 1)) % MOD);
        }
    }
}
