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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    Scanner in = new Scanner(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    TaskD solver = new TaskD();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskD {
    private static final int MAX_PRIME = 200001;
    private static final int MOD = 1000000007;

    public void solve(int testNumber, Scanner in, PrintWriter out) {
      int n = in.nextInt();
      int a[] = new int[MAX_PRIME];
      for (int i = 0; i < n; i++) {
        a[in.nextInt()]++;
      }
      long phi = MOD - 1;
      long[] sum = new long[MAX_PRIME];
      sum[0] = 0;
      for (int i = 1; i < sum.length; i++) {
        sum[i] = (sum[i - 1] + i) % phi;
      }
      long[] before = new long[MAX_PRIME];
      long[] after = new long[MAX_PRIME];
      for (int i = 0; i < before.length; i++) {
        before[i] = 1;
        if (i > 0) {
          before[i] = Modular.multiply(Modular.multiply(before[i], before[i - 1], phi), a[i - 1] + 1, phi);
        }
      }
      for (int i = after.length - 1; i >= 0; --i) {
        after[i] = 1;
        if (i < after.length - 1) {
          after[i] = Modular.multiply(after[i + 1], a[i + 1] + 1, phi);
        }
      }
      long res = 1;
      for (int i = 0; i < a.length; i++) {
        if (a[i] > 0) {
          long exponent = Modular.multiplyAll(phi, sum[a[i]], before[i], after[i]);
          res = Modular.multiply(res, Modular.exp(i, exponent, MOD), MOD);
        }
      }
      out.println(res);
    }

  }

  static class Modular {
    public static long exp(long a, long n, long mod) {
      long res = 1;
      while (n > 0) {
        if (n % 2 == 1) { res = (res * a) % mod; }
        n /= 2;
        a = (a * a) % mod;
      }
      return res;
    }

    public static long multiply(long x, long y, long mod) {
      return (x * y) % mod;
    }

    public static long multiplyAll(long mod, long... a) {
      long res = 1;
      for (long l : a) {
        res = (res * l) % mod;
      }
      return res;
    }

  }
}

