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>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const int nmax = 500010;
long long res, cnt = 1e+9 + 7;
long double eps = 1e-6;
long long n, l, r, x, y, c, d;
map<long long, long long> del, st;
vector<int> mn;
long long bin_pow(long long a, long long b) {
  long long rs = 1;
  while (b) {
    if (b % 2) {
      rs = ((rs % cnt) * (a % cnt)) % cnt;
      --b;
    } else {
      a = ((a % cnt) * (a % cnt)) % cnt;
      b /= 2;
    }
  }
  return rs;
}
int main() {
  scanf("%lld", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%lld ", &l);
    ++del[l];
  }
  res = 1;
  for (auto it = del.begin(); it != del.end(); ++it) {
    if (it->second % 2 && !x) {
      ++x;
      break;
    }
  }
  if (!x) {
    x = 2;
  } else {
    x = 1;
  }
  for (auto it = del.begin(); it != del.end(); ++it) {
    res = ((res % cnt) * (bin_pow(it->first, it->second / x) % cnt)) % cnt;
  }
  for (auto it = del.begin(); it != del.end(); ++it) {
    if (x == 1 && it->second % 2) {
      res = ((bin_pow(res, (it->second + 1) / 2) % cnt)) % cnt;
      ++x;
    } else
      res = ((bin_pow(res, (it->second + 1)) % cnt)) % cnt;
  }
  printf("%lld", res % cnt);
  return 0;
}
