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


public class CF_615D {
	public static final long MOD = 1_000_000_007L;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		long number = 1;
		int[] factorCounts = new int[200_001];
		for(int i=0;i<n;i++) {
			int factor = scan.nextInt();
			factorCounts[factor]++;
			number *= factor;
			number %= MOD;
		}
		boolean isSquare = true;
		long sqrt = 1;
		for(int i=1;i<factorCounts.length;i++) {
			if(factorCounts[i] % 2 != 0)
				isSquare = false;
			if(isSquare) {
				sqrt *= fastmodpow(i,factorCounts[i]/2);
				sqrt %= MOD;
			}
		}
		long powed = isSquare ? sqrt : number;
		boolean hasHalved = isSquare;
		for(int i=1;i<factorCounts.length;i++) {
			if(factorCounts[i] != 0) {
				int pow = factorCounts[i] + 1;
				if(!hasHalved && pow % 2 == 0) {
					pow /= 2;
					hasHalved = true;
				}
				powed = fastmodpow(powed,pow);
				isSquare = false;
			}
		}
		System.out.println(powed);
		scan.close();
	}
	public static long fastmodpow(long base, int exp) {
		if(exp == 0) return 1;
		base %= MOD;
		
		long bonus = 1;
		while(exp > 1) {
			if(exp % 2 != 0) {
				bonus *= base;
				bonus %= MOD;
			}
			base *= base;
			base %= MOD;
			exp /= 2;
		}
		return (base * bonus) % MOD;
	}
}