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  q3 {
    public static void main(String[] args) throws Exception
    {
        InputReader in=new InputReader(System.in);
        PrintWriter pw=new PrintWriter(System.out);
        int n=in.nextInt();
        HashMap<Long,Long> hm=new HashMap<Long,Long>();
        for(int i=0;i<n;i++)
        {
            long temp=in.nextLong();
            if(hm.containsKey(temp))
            {
                hm.put(temp, hm.get(temp)+1);
            }
            else
            {
                hm.put(temp, 1L);
            }
        }
        long ans=1;
        long prefix=1;
        for(Map.Entry<Long, Long> mp:hm.entrySet())
        {
            long tt=mp.getValue();
            ans=pow(ans,tt+1);
            long ff=pow(mp.getKey(),tt*1l*(tt+1)/2);
            ans*=pow(ff,prefix);
            ans%=MOD;
            prefix*=1l*(tt+1);
            prefix%=MOD-1;
        }
        pw.println(ans%MOD);
        pw.close();
    }
    static int MOD=(int)(1e9+7);
    public static long pow(long a,long b){
        if(b <= 0)  return 1;
        if(b == 1)  return a % MOD;
        long t = pow(a,b >> 1);
        t = (t * t) % MOD;
        if((b & 1) == 1)
            t = (t * a) % MOD;
        return t;

    }
    
    
    
    
    
    
    
     static class InputReader {

        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar;
        private int snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int snext() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }

            int res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));

            return res * sgn;
        }
        
        public long nextLong() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }

            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));

            return res * sgn;
        }
        
        public String readString() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

}
