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

/**
 * Created by Администратор on 14.12.2015.
 */
public class Main {
    public static final long OSN = (long)1e9+7;
    public static final long twoInv = 500000004;
    public static final BigInteger TWO = new BigInteger("2");
    static long powmod(long a, BigInteger b1, long b2)
    {

        BigInteger b = b1.multiply(BigInteger.valueOf(b2)).divide(TWO).mod(BigInteger.valueOf(OSN - 1));
        long c = 1;
        while (b.compareTo(BigInteger.ZERO)>0)
        {
                if (b.mod(TWO).equals(BigInteger.ONE))
                {
                b = b.subtract(BigInteger.ONE);
                c = (c * a)%OSN;
            }
            else
            {
                a = (a*a)%OSN;
                b = b.divide(TWO);
            }
      //      System.out.println("b = " + b);
        }
  //      if (b2>0)
//            System.out.println("c = " + c);
        return c;
    }
    static boolean w = false;
    static long powmod_(long a, long b1, long b2)
    {
        if (!w)
            b2/=2;

        long b = (b1 * b2)%(OSN-1);
        long c = 1;
        while (b>0)
        {
            if (b%2==1)
            {
                c = (c*a)%OSN;
                b--;
            }
            else{
                a = (a*a)%OSN;
                b/=2;
            }
        }
        return c;


    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        final int MAXN = 3*(int)1e5 + 2;
        int[] divs = new int[MAXN];
     //   BigInteger N = BigInteger.ONE;
        int[] tester = new int[MAXN];
        for (int i=0;i<n;i++)
        {
            int x = sc.nextInt();
            tester[i] = x;
            divs[x]++;
        }
        /*BigInteger divCount = BigInteger.ONE;
        for (int i=0;i<MAXN;i++)
            if (divs[i]>0)
                divCount = divCount.multiply(BigInteger.valueOf(divs[i]+1));*/
        long divCount = 1;
        for (int i=0;i<MAXN;i++)
            if (divs[i]>0)
                divCount = (divCount * (divs[i]+1))%(OSN-1);
        long divCount_2  = 1;
        for (int i=0;i<MAXN;i++)
            if (divs[i]>0)
            {
                if ((divs[i]+1)%2==0 && !w)
                {
                    divCount_2 = (divCount_2 * (divs[i]+1)/2)%(OSN-1);
                    w = true;

                }
                else divCount_2 = (divCount_2 * (divs[i]+1))%(OSN-1);
            }

     //   System.out.println("divCount_2 = " + divCount_2);

        long result = 1;
        for (int i=0;i<MAXN;i++)
            if (divs[i]>0)
        {
            //a^b mod m
            result = (result*powmod_(i, divCount_2, divs[i]))%OSN;
        }
        //System.out.println("divCount = " + divCount);
        //System.out.println("result = " + result);
        System.out.println(result);
    }
}
