The Monk wants to teach all its disciples a lesson about patience, since they are always in a hurry to do something crazy. To teach them this, he gives them a list of N numbers, which may or may not be distinct. The students are supposed to solve a simple Mathematical equation based on the array of these N numbers.
g(x) - GCD (a[ 0 ], a[ 1 ], a[ 2 ]... a[n-1] )
f(x) - (a[ 0 ] * a[ 1 ] * a[ 2 ]... * a[n-1] )

The value of the MonkQuotient is: 10^9 + 7.

The equation to be solved is: ( f(x)^g(x) ) % MonkQuotient

Input constraints:
The first line of input will contain an integer — N. The next line will contain N integers denoting the elements of the list. 

Output constraints:
Print the required answer of the equation.

Constraints:
1 ≤ N ≤ 50 
1 ≤ Ai ≤ 10^3

SAMPLE INPUT
2
2 6

SAMPLE OUTPUT
144

Explanation

Here we can see that the product of the elements of array is 12 and the GCD of the array comes out to be 2 .
Thus the answer would be 12^2 which is 144.
def gcd(a,b):
	e=max(a,b)
	f=min(a,b)
	while e%f != 0:
		r=e%f
		e=f
		f=r
	return f
 
def gx(a):
	if len(a) == 1: return a[0]
	result=gcd(a[0],a[1])
	for i in range(2,len(a)):
		result=gcd(result,a[i])
	return result
def fx(a):
	product=1
	for i  in range(len(a)):
		product=product*a[i]
	return product
 
def main():
	quotient=(10**9)+7
	n=input('')
	a=raw_input().split(' ')
	for i in range(len(a)):
		a[i]=int(a[i])
	
	if fx(a)**gx(a) < quotient:
		print fx(a)**gx(a)
	else:
		print (fx(a)**gx(a))%quotient
main()