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.
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T abs(T t) {
  return t < 0 ? -t : t;
}
const long long modn = 1000000007;
inline long long mod(long long x) { return x % modn; }
const long long modn2 = 1000000006;
inline long long mod2(long long x) { return x % modn2; }
const int MAXN = 200010;
int n, m, mrk[MAXN];
long long res, e, num, q[MAXN], p[MAXN];
long long expo(long long base, long long ex) {
  if (ex == 1) return base;
  if (ex == 0) return 1;
  long long ans = 1;
  if (ex % 2) ans = mod(ans * base);
  long long aux = expo(base, ex / 2);
  ans = mod(ans * mod(aux * aux));
  return ans;
}
int main() {
  scanf("%d", &n);
  num = 1;
  for (int a = 0; a < n; a++) {
    cin >> p[a];
    num *= p[a];
    q[p[a]]++;
  }
  long long nper = 0;
  for (int a = 0; a < n; a++) {
    nper = max(nper, (q[p[a]] % 2));
  }
  e = 1;
  int f = 1;
  for (int a = 0; a < n; a++) {
    if (mrk[p[a]] == 0) {
      mrk[p[a]] = 1;
      long long aux = (q[p[a]] + 1);
      if (f && !(aux % 2)) {
        aux /= 2;
        f--;
      }
      e = mod2(e * aux);
    }
  }
  if (f) {
    e /= 2;
  }
  res = 1;
  for (int a = 0; a < n; a++) {
    res = mod(res * expo(p[a], e));
  }
  if (!nper) {
    long long sqr = 1;
    for (int a = 0; a < n; a++) {
      if (mrk[p[a]] == 1) {
        mrk[p[a]] = 0;
        sqr = mod(sqr * expo(p[a], q[p[a]] / 2));
      }
    }
    res = mod(res * sqr);
  }
  cout << res;
}
