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.*;
import java.util.*;

public class D {

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static InputReader r = new InputReader(System.in);
    static PrintWriter pw = new PrintWriter(System.out);

    static long MOD = (long)(1e9+7);
    public static void main(String[] args) {
        
        long n = 1;
        ArrayList<Integer> exp = new ArrayList<Integer>();
        int m = r.nextInt();
        Multiset set = new Multiset();
        for(int i = 0; i < m; i++){
            int x = r.nextInt();
            set.add(x);
            n *= x;
            n %= MOD;
        }
        boolean square = true;
        for(Map.Entry<Integer, Integer> entry : set.set.entrySet()){
            if(entry.getValue() % 2 == 1){
                square = false;
            }
        }

        
        for(Map.Entry<Integer, Integer> entry : set.set.entrySet()){
            exp.add(entry.getValue() + 1);
        }
        if(square){
            for(Map.Entry<Integer, Integer> entry : set.set.entrySet()){
                entry.setValue(entry.getValue() / 2);
            }
        }
        if(square){
            n = 1;
            for(Map.Entry<Integer, Integer> entry : set.set.entrySet()){
                for(int i = 0; i < entry.getValue(); i++){
                    n *= entry.getKey();
                    n %= MOD;
                }
            }
        }
        if(!square){
            for(int i = 0; i < exp.size(); i++){
                if(exp.get(i) % 2 == 0){
                    exp.set(i, exp.get(i)/2);
                    break;
                }
            }
        }

        long ans = n;
        for(int e : exp){
            long t = ans;
            for(int i = 1; i < e; i++){
                ans *= t;
                ans %= MOD;
            }
        }
        /*
        System.out.println(square);
        System.out.println(set.set);
        System.out.println(n);
        System.out.println(exp);
        */
        pw.println(ans);
        pw.close();
    }

    static class Multiset{
        TreeMap<Integer, Integer> set;
        public Multiset(){
            this.set = new TreeMap<Integer, Integer>();
        }
        public void add(int n){
            if(set.containsKey(n)){
                set.put(n, set.get(n)+1);
            } else {
                set.put(n, 1);
            }
        }
        public void remove(int n){
            set.put(n, set.get(n)-1);
            if(set.get(n).equals(0)){
                set.remove(n);
            }
        }
        public String toString(){
            return set.toString();
        }
    }
}

/**
*                _        _                 _                                                
*               | |      | |               | |                                               
*   ___ ___   __| | ___  | |__  _   _    __| | __ _ _ __ _ __ ___ _ __     _   _  __ _  ___  
*  / __/ _ \ / _` |/ _ \ | '_ \| | | |  / _` |/ _` | '__| '__/ _ \ '_ \   | | | |/ _` |/ _ \ 
* | (_| (_) | (_| |  __/ | |_) | |_| | | (_| | (_| | |  | | |  __/ | | |  | |_| | (_| | (_) |
*  \___\___/ \__,_|\___| |_.__/ \__, |  \__,_|\__,_|_|  |_|  \___|_| |_|   \__, |\__,_|\___/ 
*                                __/ |                               ______ __/ |            
*                               |___/                               |______|___/             
 */