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.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;


public class D {
	private static final int MOD = 1000000007;
	private static int mul(long a, long b) {
		return (int) ((a * b) % MOD);
	}
	private static int pow(long n, int k) {
		if (k == 0) {
			return 1;
		}
		if (k == 1) {
			return (int) (n % MOD);
		}
		long res = pow(n, k/2);
		res = mul(res, res);
		if (k%2 == 1) {
			res = mul(res, n);
		}
		return (int) res;
	}
	public static void main(String[] args) {
		try (Scanner s = new Scanner(System.in)) {
			final int m = s.nextInt();
			final int[] p = new int[m];
			for (int i = 0; i < m; ++i) {
				p[i] = s.nextInt();
			}
			final Map<Integer, Integer> map = new HashMap<>();
			for (int i = 0; i < m; ++i) {
				if (map.containsKey(p[i])) {
					map.put(p[i], map.get(p[i]) + 1);
				} else {
					map.put(p[i], 1);
				}
			}
			List<int[]> factors = new ArrayList<>();
			for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
				final int key = entry.getKey();
				final int value = entry.getValue();
				factors.add(new int[] {key, value});
			}
			long[] prefix = new long[factors.size() + 1];
			prefix[0] = 1;
			for (int i = 1; i < prefix.length; ++i) {
				prefix[i] = (prefix[i - 1] * (factors.get(i - 1)[1] + 1)) % (MOD - 1);
			}
			long[] suffix = new long[factors.size() + 1];
			suffix[suffix.length - 1] = 1;
			for (int i = suffix.length - 2; i >= 0; --i) {
				suffix[i] = (suffix[i + 1] * (factors.get(i)[1] + 1)) % (MOD - 1);
			}
			long res = 1;
			for (int i = 0; i < factors.size(); ++i) {
				final int[] factor = factors.get(i);
				final long k = factor[0];
				final long v = factor[1];
				long exc = (prefix[i] * suffix[i + 1]) % (MOD - 1);
				long pow = ((v*(v + 1))/2) % (MOD - 1);
				long total = (exc * pow) % (MOD - 1);
				res = mul(res, pow(k, (int) total));
			}
			System.out.println(res);
		}
	}
}
