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.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;


public class Main_Round338Div2_D1 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Printer pr = new Printer(System.out);

		final long MOD = 1_000_000_007;

		int m = sc.nextInt();
		Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
		for (int i = 0; i < m; i++) {
			int p = sc.nextInt();
			if (hm.containsKey(p)) {
				hm.put(p, hm.get(p) + 1);
			} else {
				hm.put(p, 1);
			}
		}

		int n = hm.size();
		Integer[] p = new Integer[0];
		p = hm.keySet().toArray(p);
		Integer[] v = new Integer[0];
		v = hm.values().toArray(v);
		long[] fm = new long[n + 1];
		long[] bm = new long[n + 1];
		fm[0] = 1;
		bm[n] = 1;
		for (int i = 0; i < n; i++) {
			fm[i + 1] = fm[i] * (v[i] + 1) % (MOD - 1);
			bm[n - 1 - i] = bm[n - i] * (v[n - 1 - i] + 1) % (MOD - 1);
		}

		long ret = 1;
		for (int i = 0; i < n; i++) {
			long tmp = (long)v[i] * (v[i] + 1) / 2 % (MOD - 1);
			tmp = tmp * fm[i] % (MOD - 1);
			tmp = tmp * bm[i + 1] % (MOD - 1);
			long loop = tmp;
			long x = p[i];
			while (loop > 0) {
				if (loop % 2 == 1) {
					ret = ret * x % MOD;
				}
				x = x * x % MOD;
				loop /= 2;
			}
		}

		pr.println(ret);

		pr.close();
		sc.close();
	}

	@SuppressWarnings("unused")
	private static class Scanner {
		BufferedReader br;
		Iterator<String> it;

		Scanner (InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

		String next() throws RuntimeException  {
			try {
				if (it == null || !it.hasNext()) {
					it = Arrays.asList(br.readLine().split(" ")).iterator();
				}
				return it.next();
			} catch (IOException e) {
				throw new IllegalStateException();
			}
		}

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

		long nextLong() throws RuntimeException {
			return Long.parseLong(next());
		}

		float nextFloat() throws RuntimeException {
			return Float.parseFloat(next());
		}

		double nextDouble() throws RuntimeException {
			return Double.parseDouble(next());
		}

		void close() {
			try {
				br.close();
			} catch (IOException e) {
//				throw new IllegalStateException();
			}
		}
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}
