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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;
import java.util.TreeSet;

public class D {	
	final long MOD = (long)(1e9+7);
	HashMap<Integer, Integer> pp;
	int pows[];
	int m;
	ArrayList<Integer> p;
	void readInput() throws NumberFormatException, IOException{
		//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		p = new ArrayList<Integer>(m);
		for(int i=0; i<m; i++){
			p.add( sc.nextInt() );
		}
	}
	
	public long powmod(long a, long x, long n){
		long res = 1;
		a = a % n;
		while(x>0){
			if ( x % 2 == 1)
				res = (res*a) %n;
			a = (a*a) %n;
			x = x >> 1;
		}
		return res;
	}	
	
	void solve(){
		//F(p^a n) = p^(a*(a+1)/2 * sigma(n)) * F(n)^(a+1)
		pp = new HashMap<Integer,Integer>();		
		for(int i=0; i<m; i++){
			int prime = p.get(i);
			if (pp.containsKey(prime))
				pp.put(prime, pp.get(prime)+1);
			else
				pp.put(prime,1);			
		}

		long m = pp.size();
		long ssol = 1;
		ArrayList<Long> divs = new ArrayList<Long>();
		divs.add(1L);
		int u = 1;
		for(Integer p:pp.keySet()){
			long alpha = pp.get(p);
			long alpha2 = alpha*(alpha+1)/2;
			
			long xp = p;			
			for(Long v : divs)
				xp = powmod(xp, v, MOD);
			xp = powmod(xp, alpha2, MOD);
			ssol = powmod(ssol,alpha+1,MOD);
			ssol = ssol*xp%MOD;			
			
			if (alpha+1<Long.MAX_VALUE/divs.get(u-1)){
				divs.set(u-1, divs.get(u-1)*(alpha+1));
			}
			else
			{
				u++;
				divs.add((alpha+1));
			}
		}
		System.out.println(ssol);
	}
	
	void solve2(){
		//F(n) = prod p^sigma(n)*a/2
		pp = new HashMap<Integer,Integer>();		
		for(int i=0; i<m; i++){
			int prime = p.get(i);
			if (pp.containsKey(prime))
				pp.put(prime, pp.get(prime)+1);
			else
				pp.put(prime,1);			
		}
		
		boolean hasoddpower = false;
		for(int prime : pp.keySet()){
			int alpha = pp.get(prime);
			if (alpha % 2 == 1){
				hasoddpower = true;
				break;
			}						
		}
		
		long n = 1;
		for(int prime : pp.keySet()){
			int alpha = pp.get(prime);
			if (hasoddpower){
				n = n * powmod(prime,alpha,MOD) % MOD;
			}
			else
			{
				n = n * powmod(prime,alpha/2,MOD) % MOD;
			}
		}
		
		for(int prime : pp.keySet()){
			int alpha = pp.get(prime);
			if (hasoddpower && alpha% 2 == 1){
				n = powmod(n,(alpha+1)/2,MOD) % MOD;
				hasoddpower = false;
			}
			else
			{
				n = powmod(n,alpha+1,MOD) % MOD;
			}
		}
		System.out.println(n);		
	}
	

	public static void main(String[] args) throws NumberFormatException, IOException {
		D a = new D();
		a.readInput();
		a.solve2();
		//a.solve();
	}

}
