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.*;
import java.io.*;
import java.math.*;
public class Main {
static long binPow(long temp,long pow,long mod){
	if(pow == 0)return 1;
	if(pow == 1)return temp;
	long t = binPow(temp,pow/2,mod);
	t = t*t % mod;
	if((pow & 1) == 1)
		t = temp*t % mod;
	return t;
}
static int modInv(long val,long mod){
	return BigInteger.valueOf(val).modInverse(BigInteger.valueOf(mod)).intValue();
}
public static void main(String [] args)throws Exception{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int m = Integer.parseInt(br.readLine());
	long mod = 1000_000_000 + 7;
	int array[] = new int[200000 + 5];
	int lmul[] = new int[200000 + 5];
	int rmul[] = new int[200000 + 5];
	lmul[0] = 1;rmul[rmul.length - 1] = 1;
	StringTokenizer st = new StringTokenizer(br.readLine());
	for(int i = 0;i < m;i++){
	    int a = Integer.parseInt(st.nextToken());
		array[a]++;
	}
    for(int i = 1;i < lmul.length;i++)lmul[i] = (int)((lmul[i - 1])*1L*(array[i] + 1) % (mod - 1));
    for(int i = rmul.length - 2 ;i >= 0;i--)rmul[i] = (int)(rmul[i + 1]*1L*(array[i] + 1) % (mod - 1));
	long ans = 1;
	for(int i = 2;i < array.length;i++){
		if(array[i] == 0)continue;
		long pow = lmul[i - 1]*1L*rmul[i + 1];
		pow %= (mod - 1);
		long temp = i;
		long var = 1;
		for(int j = 1;j <= array[i];j++){
			var *= binPow(temp,pow,mod);
			var %= mod;
			temp = temp*i % mod;
		}
		ans = ans*var % mod;
	}
	System.out.print(ans);
}
}