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 javax.swing.text.html.HTMLDocument;

public class Main
{
	static final long P = ( long ) 1e9 + 7;

	static long modpow( long a, long k )
	{
		if ( k == 0 )
			return 1;
		return ( ( k % 2 == 1 ? a : 1 ) * modpow( ( a * a ) % P, k >> 1 ) ) % P;
	}

	public static void main( String[] args )
	{
		Scan scan = new Scan();
		TreeMap<Long, Long> cnt = new TreeMap<>();
		long m = scan.nextLong();
		for ( int i = 0; i < m; i ++ )
		{
			long p = scan.nextLong();
			cnt.put( p, cnt.getOrDefault( p, ( long ) 0 ) + 1 );
		}
		long d = 1, ans = 1;
		Iterator it=cnt.entrySet().iterator();
		while(it.hasNext())
		{
			Map.Entry t=(Map.Entry)it.next();
			long p = (long)t.getKey();
			long k = (long)t.getValue();
			long f = modpow( p, ( k * ( k + 1 ) / 2 ) % ( P - 1 ) );
			ans = ( modpow( ans, k + 1 ) * modpow( f, d ) ) % P;
			d = ( d * ( k + 1 ) ) % ( P - 1 );
		}
		System.out.println( ans );
	}
}

class Scan
{
	BufferedReader br;
	StringTokenizer st;

	Scan()
	{
		br = new BufferedReader( new InputStreamReader( System.in ) );
	}

	boolean hasNext()
	{
		while ( st == null ||  ! st.hasMoreElements() )
		{
			try
			{
				st = new StringTokenizer( br.readLine() );
			}
			catch ( Exception e )
			{
				return false;
			}
		}
		return true;
	}

	String next()
	{
		if ( hasNext() )
			return st.nextToken();
		return null;
	}

	int nextInt()
	{
		if ( hasNext() )
			return Integer.parseInt( st.nextToken() );
		return -1;
	}

	long nextLong()
	{
		if ( hasNext() )
			return Long.parseLong( st.nextToken() );
		return -1;
	}

	String nextLine()
	{
		st = null;
		try
		{
			return br.readLine();
		}
		catch ( Exception e )
		{
			return null;
		}
	}
}
