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.util.Map;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeMap;
import java.util.ArrayList;
import java.io.IOError;
import java.util.Iterator;
import java.util.Set;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author skt
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    final long mod = 1000000007;
    int m;
    TreeMap<Integer, Long> treeMap;
    int[] p;
    long[] base, pre, rail;

    public long power(long a, long n, long m) {
        long ans = 1l;
        while (n != 0) {
            if ((n & 1) != 0) {
                ans = ans * a % m;
            }
            a = a * a % m;
            n >>= 1;
        }
        return ans;
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        treeMap = new TreeMap<Integer, Long>();
        m = in.nextInt();
        p = new int[m];
        for (int i = 0; i < m; i ++) {
            p[i] = in.nextInt();
            if (treeMap.containsKey(p[i])) {
                treeMap.put(p[i], treeMap.get(p[i]) + 1l);
            } else {
                treeMap.put(p[i], 1l);
            }
        }
        Iterator it = treeMap.entrySet().iterator();
        ArrayList<Map.Entry> arrayList = new ArrayList<Map.Entry>();
        while (it.hasNext()) {
            Map.Entry entry = (Map.Entry) it.next();
            arrayList.add(entry);
        }
        int listsize = arrayList.size();
        base = new long[listsize];
        pre = new long[listsize];
        rail = new long[listsize];
        for (int i = 0; i < listsize; i ++) {
            if (i == 0) {
                pre[i] = 1l;
            } else {
                pre[i] = pre[i - 1] * ((Long)arrayList.get(i - 1).getValue() + 1) % (mod - 1);
            }
        }
        for (int i = listsize - 1; i >= 0; i --) {
            if (i == listsize - 1) {
                rail[i] = 1l;
            } else {
                rail[i] = rail[i + 1] * ((Long)arrayList.get(i + 1).getValue() + 1) % (mod - 1);
            }
        }
        long ans = 1l;
        for (int i = 0; i < listsize; i ++) {
            long x = (Integer)arrayList.get(i).getKey();
            long y = (long)arrayList.get(i).getValue();
            y = (y + 1) * y / 2;
            base[i] = power(x, y, mod);
            ans = ans * power(base[i], (pre[i] * rail[i]) % (mod - 1), mod);
            ans %= mod;
        }
        out.println(ans);
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

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

}

