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.*;

public class Codeforces {
	private static final int MOD = 1000000007, PHI = MOD-1, MAD = 2*PHI, DIM = 100;
	private static final long[] TWO = new long[] {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648L, 4294967296L, 8589934592L, 17179869184L, 34359738368L, 68719476736L, 137438953472L, 274877906944L, 549755813888L, 1099511627776L, 2199023255552L, 4398046511104L, 8796093022208L, 17592186044416L, 35184372088832L, 70368744177664L, 140737488355328L, 281474976710656L, 562949953421312L, 1125899906842624L, 2251799813685248L, 4503599627370496L, 9007199254740992L, 18014398509481984L, 36028797018963968L, 72057594037927936L, 144115188075855872L, 288230376151711744L, 576460752303423488L, 1152921504606846976L, 2305843009213693952L, 4611686018427387904L};
	
	static Scanner in = new Scanner(System.in);
    static int[] getInts(int n) {
    	int[] ans = new int[n];
    	for (int i = 0; i < n; i++) ans[i] = in.nextInt();
    	return ans;
    }
	static void println(Object s) {System.out.println(s);}
	static void print(Object s) {System.out.print(s);}
    public static void main(String[] args) {
    	int m = in.nextInt();
    	int[] pr = getInts(m);
    	Arrays.sort(pr);
    	long nf = 1;
    	int cc = 0;
    	int cn = 1;
    	for (int i = 0; i < m; i++) {
    		if (pr[i] == cc) {
    			cn++;
    		}
    		else {
    			nf = nf * cn % MAD;
    			cc = pr[i];
    			cn = 2;
    		}
    	}
    	nf = nf * cn % MAD;
    	long num = 1;
    	if (nf % 2 == 1) { // square
    		for (int i = 0; i < m; i += 2) {
    			num = num * pr[i] % MOD;
    		}
    	}
    	else {
    		for (int i = 0; i < m; i++) {
    			num = num * pr[i] % MOD;
    		}
    		nf /= 2;
    	}
    	long[] pow = new long[DIM];
    	pow[0] = num;
    	for (int i = 1; i < DIM; i++) {
    		pow[i] = pow[i-1] * pow[i-1] % MOD;
    	}
    	long ans = 1;
    	while (nf > 0) {
    		int t = prev2(nf);
    		ans = ans * pow[t] % MOD;
    		nf -= TWO[t];
    	}
    	System.out.println(ans);
    }
    private static int prev2(long n) {
    	int i;
    	for (i = 0; TWO[i] <= n; i++);
    	return i-1;
    }
}