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.
mod=10**9+7

def pow(a,b): #Algoritmo de Exponenciacion binaria modular
    exp=1 # Caso base a^1=a
    x=a % mod 
    b=b%(mod-1) # para a^b % p hacemos a^{b%(p-1)} %p
    while b > 0: 
        if b % 2 == 1:# En caso que b sea impar a^b=a*a^b-1
            exp=(exp*x)%mod # cada operacion de mult la hacemos modulo mod pues lo numeros pueden ser bastante grandes 
        x=(x*x)%mod  # En caso que b sea par a^b=(a^b/2)^2 
        b=b//2   # al hacerlo de forma iterativa y con parte entera de b/2 es este caso este caso es el caso par pues el caso impar habria sido visto en el if primero y ahora
    return exp%mod   

m=input() # el numeros de primos en la factorizacion de n
primes=map(int,input().split())# se captura la entrada del problema con map 
primesDicc=dict() # inicializo un diccionario para guardar la descomposicion en primos de la forma <pi,e1>donde e1 es el exponente con que aparece pi en la descomposicion
n=1;
for p in primes: # Recorro cada primo generado de la entrada 
    n=(n*p)%mod # calculo n a traves de la multiplicacion de sus factores primos
    if p not in primesDicc: # en caso que sea la primera aparicion de ese primo pi agrego la llave pi a mi diccionario con valor 1  
        primesDicc[p]=1
    else:
        primesDicc[p]+=1 # en caso que ya ese primo haya aparecido en el recorrido de la descomposicion es porque al menos aparece mas de una vez por lo que actualizo el exponente +1

countdiv =1 # variable que va a guardar la cantidad de divisores de n
raiz=1 # variable que va a guardar en caso que n sea un cuadrado perfecto
for p in primesDicc: #Hago un recorrido por todos las llaves de mi diccionario para generar el numero de divisores
    countdiv *= primesDicc[p]+1  # el numero de divisores de n es igual a (e1+1)*(e2+1)*...(ek+1) por lo que en cada iteracion primesDicc[p] me da un e_i y actualiza *(e_i+1)
result=0 # variable que va guardar la solucion del problema
if countdiv % 2 == 0: # En caso que la cantidad de divisores sea par 
    result=pow(n,countdiv//2) # la respuesta es n^{cantidad de divisores/2}
else: # En caso que la cantidad de divisores sea impar
    for p in primesDicc:  # Dado que la raiz de n si es entera = al producto de la descomposicion en primos de n  con exponente/2 para cada factor 
        raiz=(raiz*pow(p,primesDicc[p]//2))  # la raiz se calcula como p1^e1/2*p2^e2/2*...*pk^ek/2 
    result=(raiz*pow(n,countdiv//2))%mod  # en caso de ser impar la cantidad de divisores de n la respuesta es sqrt(n)*n^{|_d(x)/2_|}

print(result) # Se imprime en pantalla la solucion