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.math.BigInteger;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;


public class CFProbD {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		int numberOfPrimes = input.nextInt();
		SegmentTree holdPrimes = new SegmentTree(0, 200001);//200001);
		int[] primes = new int[200001];
		for(int a = 0; a < numberOfPrimes; a++){
			int temp = input.nextInt();
			primes[temp]++;
		}
		
		for(int a = 0; a < primes.length; a++){
			holdPrimes.insert(a, primes[a]+1);
		}
	//	BigInteger permutationNumber = multiplyAll(primes, 0, primes.length-1);
		long bigProduct = 1;
		for(int a = 0; a < 200001; a++){
			if(primes[a] != 0){
				long primeNth = takePrimeNth(a, primes[a]);
				long numPossibilities = (holdPrimes.rangeQuery(0, a-1)*(holdPrimes.rangeQuery(a+1, 200001)));// permutationNumber.divide(new BigInteger((primes[a]+1)+""));
				long result = (nthPow(primeNth, new BigInteger(numPossibilities + "")))%1000000007;//FIX THIS
				bigProduct = (bigProduct * result) % 1000000007;
			}
		}
		System.out.println(bigProduct);		
	}	
	private static BigInteger multiplyAll(int[] primes, int start, int end) {
		if(start == end){
			return new BigInteger((primes[start]+1)+ "");
		}
		return multiplyAll(primes, start, start + (end-start)/2).multiply(multiplyAll(primes, start + (end-start)/2 + 1, end));
	}
	private static long takePrimeNth(int prime, int power) {
		long tempPower = power;
		tempPower = (tempPower * (tempPower+1)) / 2;
		return nthPow(prime, new BigInteger(tempPower + ""));
	}
	private static long nthPow(long prime, BigInteger numPossibilities) {
		if(numPossibilities.equals(BigInteger.ZERO)){
			return 1;
		}
		if(numPossibilities.equals(BigInteger.ONE)){
			return prime;
		}
		long temp = nthPow(prime, numPossibilities.divide(new BigInteger("2")));
		long temp2 = (temp * temp) %1000000007;
		
		return (temp2 * nthPow(prime, numPossibilities.mod(new BigInteger(2+""))))%1000000007;
	}
	public static class SegmentTree{
		int left;
		int right;
		SegmentTree leftTree;
		SegmentTree rightTree;
		long product;
		public SegmentTree(int left, int right){
			product = 1;
			this.left = left;
			this.right = right;
			if(left != right){
				leftTree = new SegmentTree(left, left + (right-left)/2);
				rightTree = new SegmentTree(left + (right-left)/2+1, right);
			}
		}
		public void insert(int location, int prime){
			if(left <= location && right >= location){
				product *= prime;
				product = product%1000000006;
				if(left != right){
					leftTree.insert(location, prime);
					rightTree.insert(location, prime);
				}
			}
		}
		public long rangeQuery(int leftQuery, int rightQuery){
			if(leftQuery <= left && rightQuery >= right){
				return product;
			}
			if(leftQuery > right || rightQuery < left){
				return 1;
			}
			if(left != right){
				return (leftTree.rangeQuery(leftQuery, rightQuery) * rightTree.rangeQuery(leftQuery, rightQuery)) % 1000000006;
			}
			return 1;
		}
		public String toString(){
			if(left == right){
				return "Left: " + left + " Right: " + right + " Product: " + product +"\n";
			}
			else{
				return "Left: " + left + " Right: " + right + " Product: " + product +"\n" + leftTree.toString() + rightTree.toString();
			}
		}
	}
}
