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.util.*;
import java.io.*;
public class C 
{
    public static void main(String[] args)
    {
        new C().solve();
    }

    FasterScanner in=new FasterScanner();
    PrintWriter out=new PrintWriter(System.out);

    int mod=(int)(1e9)+7;
    public void solve()
    {
        int m1=in.nextInt();
        long[] f=new long[(int)1e5*2+1];
        int max=0;
        for(int i=0;i<m1;i++)
        {
            int x=in.nextInt();
            f[x]++;
            max=Math.max(max, x);
        }
        long[] l=new long[f.length];
        long[] m=new long[f.length];
        l[1]=1;
        m[1]=1;
        for(int i=2;i<=max;i++)
        {
            l[i]=(l[i-1]*(f[i]+1))%(mod-1);
            m[i]=pow(m[i-1],f[i]+1)*pow(i,((((f[i]*(f[i]+1))/2)%(mod-1))*(l[i-1]))%(mod-1));
            m[i]%=mod;
        }
        
        out.println(m[max]);
        out.close();
    }

    long pow(long a,long n) 
    { 
        
        if(n==1) 
            return a; 
        if(n==0) 
            return 1; 
        if(a==1)
            return 1;
        long ans=pow(a,n/2); 
        ans*=ans; 
        ans%=mod; 
        if(n%2!=0) 
            ans*=a; 
        ans%=mod; 
        return ans; 
    } 

    class s implements Comparable<s>
    {
        int time;
        int floor;
        public s(int t,int f)
        {
            this.time=t;
            this.floor=f;
        }

        @Override
        public int compareTo(s o) {
            // TODO Auto-generated method stub
            if(this.floor!=o.floor)
                return Integer.compare(this.floor, o.floor);
            else
                return Integer.compare(this.time, o.time);
        }
    }

    public static class FasterScanner {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = System.in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }
        private boolean isEndOfLine(int c) {
            return c=='\n' || c=='\r' || c==-1;
        }
        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        private boolean isSpaceChar(int c) {
            return c=='\n' || c=='\r' || c==-1 || c==' ' || c=='\t';
        }
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
        public double nextDouble()
        {
            return Double.parseDouble(nextString());
        }
        public int[] nextIntArray(int n)
        {
            int[] arr=new int[n];
            for(int i=0;i<n;i++)
            {
                arr[i]=nextInt();
            }
            return arr;
        }
        public long[] nextLongArray(int n)
        {
            long[] arr=new long[n];
            for(int i=0;i<n;i++)
            {
                arr[i]=nextLong();
            }
            return arr;
        }
        public int[] nextIntArray10(int n)
        {
            int[] arr=new int[n+1];
            for(int i=1;i<=n;i++)
            {
                arr[i]=nextInt();
            }
            return arr;
        }
        public long[] nextLongArray10(int n)
        {
            long[] arr=new long[n+1];
            for(int i=1;i<=n;i++)
            {
                arr[i]=nextLong();
            }
            return arr;
        }
        public int[] nextIntArray11(int n)
        {
            int[] arr=new int[n+2];
            for(int i=1;i<=n;i++)
            {
                arr[i]=nextInt();
            }
            return arr;
        }
        public long[] nextLongArray11(int n)
        {
            long[] arr=new long[n+2];
            for(int i=1;i<=n;i++)
            {
                arr[i]=nextLong();
            }
            return arr;
        }
    }

}