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.*;
/*
2
2 3

3
2 3 2

2
7 7

7
2 3 2 3 5 5 5

67
98929 19079 160079 181891 17599 91807 19079 98929 182233 92647 77477 98929 98639 182233 181891 182233 160079 98929 19079 98639 114941 98929 161341 91807 160079 22777 132361 92647 98929 77477 182233 103913 160079 77477 55711 77477 77477 182233 114941 91807 98929 19079 104393 182233 182233 131009 132361 16883 161341 103913 16883 98929 182233 114941 92647 92647 104393 132361 181891 114941 19079 91807 114941 132361 98639 161341 182233

 */
public class D {
	
	static long mod;
	
	public static void main(String[] args) {
		
		Scanner qwe = new Scanner(System.in);
		
		mod = (int)(1e9+7);
		
		//System.out.println(new BigInteger("2").modInverse(new BigInteger((mod-1)+"")));
		
		long n = qwe.nextInt();
		
		
		long[] ps = new long[(int)n];
		boolean alleven = true;
		for (int i = 0; i < ps.length; i++) {
			ps[i] = qwe.nextLong();
		}
		
//		TreeMap<Long,Integer> tm = new TreeMap<Long, Integer>();
//		for (int i = 0; i < ps.length; i++) {
//			if(!tm.containsKey(ps[i])){
//				tm.put(ps[i], 0);
//			}
//			int amount = tm.get(ps[i]);
//			tm.put(ps[i], amount+1);
//		}
//		
//		long p2 = 1;
//		
//		for (Long key : tm.keySet()) {
//			p2 = (p2*(tm.get(key)+1))%mod;
//		}
		
		Arrays.sort(ps);
		//System.out.println(Arrays.toString(ps));
		long run = 1;
		long product = 1;
		for (int i = 1; i < ps.length; i++) {
			if(ps[i] == ps[i-1]){
				run++;
			}
			else{
				//System.out.println("run: " + run);
				if(run % 2 != 0 && alleven){
					alleven = false;
					product *= (run+1)/2;
					product %= (mod-1);
				}
				else{
					product *= (run+1);
					product %= (mod-1);
				}
				
				
				run = 1;
			}
		}
		//System.out.println("run: " + run + " product " + product);
		if(run % 2 != 0 && alleven){
			alleven = false;
			product *= (run+1)/2;
			//System.out.println("product: " + product);
			product %= (mod-1);
		}
		else{
			product *= (run+1);
			product %= (mod-1);
		}
		
		product %= (mod-1);
				
		
	
		long base = 1;
		long root = 1;
		for (int i = 0; i < n; i++) {
			base = (base*(ps[i]))%mod;
			if(i % 2 == 0) root = (root*(ps[i]))%mod;
		}
		
		//System.out.println(base + " " + product + " " + root + " " + alleven);
		//System.out.println("p2: " + p2);
		long ans = fastExpo(base,product);
		if(alleven) ans = fastExpo(root,product);
		
		ans %= mod;
		
		System.out.println(ans);
		
		
		qwe.close();
	}
	
	public static long fastExpo (long num, long pow) {
		if (pow == 0)
			return 1;
		
		if (pow%2 == 1)
			return (num * fastExpo(num, pow-1))%mod;
		
		long temp = fastExpo(num, pow/2);
		return (temp*temp)%mod;
	}
	
	
	
	

}
