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.
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

//package codeforces338;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
/**
 *
 * @author Sourav Kumar Paul
 */
public class SolveD {
    private static int mod =1000000000+7;
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(reader.readLine());
    //System.out.println(100.5%56);
        int a[] = new int[m];
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int hash[] = new int[200000+5];
        for(int i=0; i<m; i++)
        {
            a[i] = Integer.parseInt(st.nextToken());
            hash[a[i]]++;
        }
        long div = 1;
        boolean parity = false;
        for(int i=0; i<=200000; i++)
        {
            if((hash[i]+1) % 2 ==0)
            {
                parity = true;
                break;
            }
           // div *= (hash[i]+1);
        }
       
        if(parity)
        {
          // System.out.println("Hell");
            long ans =1;
            for(int i=0; i<m; i++)
            {
                ans = (ans * a[i])%mod;
            }
            //System.out.println(ans);
            boolean tt = false;
            for(int i=0; i<=200000; i++)
            {
                if(hash[i] !=0 && !tt && hash[i]%2==1)
                {
                    ans = modPow(ans , (hash[i] + 1)/2, mod);
                    tt =true;
                }
                  //  System.out.println(ans);
                    else
                ans = modPow(ans , (hash[i] + 1), mod);
                    
            }
            System.out.println(ans);
        }
        else
        {
           // div = div/2;
            // System.out.println(div);
            long ans =1;
             div = 1;
           
           // System.out.println(ans);
            boolean tt = false;
            double xx ;
            double dd=1.0;
            long temp=1;
            for(int i=0; i<=200000; i++)
            {
                if(hash[i]==0)
                    continue;
                if(hash[i] !=0 && !tt )
                {
                    xx = ((double)(hash[i] + 1))/2;
                //    System.out.println(xx);
                    dd = (dd * xx)%(mod-1);
                     tt =true;
                    continue;
                }
                  //  System.out.println(ans);
                   // System.out.println(modPow(36 , (hash[i] + 1), mod));
                dd = (dd * (hash[i]+1))%(mod-1);
                   
            }
            for(int i=0; i<m; i++)
        {
            ans = (ans * modPow(a[i], (long)dd, mod))%mod;
        }
        for(int i=0; i<=200000; i++)
        {
            if(hash[i]!=0)
            {
                ans = (ans * modPow(i,hash[i]/2,mod))%mod;
            }
        }
        System.out.println(ans);
        }
       
        
    }
     private static long modPow(long base, long exp, long mod) {

        /* if(exp ==1 )
             return base;
         if(exp % 2== 0)
         {
             return (modPow(base, exp/2, mod) * modPow(base, exp/2, mod)) % mod;
         }
         else
             return (base * modPow(base, (exp -1)/2, mod) * modPow(base, (exp-1)/2, mod)) % mod;
        */ // Recursion won't work here
        // better go for iteration
        base = base % mod;
        long result =1;
        while(exp > 0)
        {
            if(exp % 2== 1)
            {
                result = (result * base) % mod;
                exp --;
            }
            else
            {
                base = (base * base) % mod;
                exp = exp >> 1;
            }
            
        }
        return result;
        
    }

    
}
