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;
const long long maxN = 1e18;
const long long minN = -1e18;
const int INF = 2e9;
const long long MOD = 1e9 + 7;
const long long MOD1 = 998244353;
const int baseHash = 331;
const int bigNumLength = 5000;
const long double PI = acos(-1);
const int limit = 2e5 + 5;
const int limit1 = 4e6 + 5;
const int limit2 = 1e3 + 5;
pair<int, int> dir[] = {{0, 1}, {1, 0},  {0, -1}, {-1, 0},
                        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
pair<int, int> NON = {-1, -1};
int n;
int a[limit];
int minPrime[limit];
int cnt[limit];
set<int> pr;
int IT[4 * limit];
void update(int id, int l, int r, int pos, int val) {
  if (l > pos || r < pos) return;
  if (l == r) {
    IT[id] = val;
    return;
  }
  int mid = (l + r) >> 1;
  update(id << 1, l, mid, pos, val);
  update(id << 1 | 1, mid + 1, r, pos, val);
  IT[id] = (1LL * IT[id << 1] * IT[id << 1 | 1]) % (MOD - 1);
}
int get(int id, int l, int r, int u, int v) {
  if (u > v) return 1;
  if (l > v || r < u) return 1;
  if (u <= l && r <= v) return IT[id];
  int mid = (l + r) >> 1;
  return 1LL * get(id << 1, l, mid, u, v) * get(id << 1 | 1, mid + 1, r, u, v) %
         (MOD - 1);
}
int power(int n, int k, int m) {
  if (k == 0) return 1;
  int t = power(n, k >> 1, m);
  return (k & 1) ? 1LL * t * t % m * n % m : 1LL * t * t % m;
}
void init() {
  int n = 2e5;
  for (int i = 2; i * i <= n; ++i) {
    if (minPrime[i]) continue;
    for (int j = i * i; j <= n; j += i) {
      if (!minPrime[j]) minPrime[j] = i;
    }
  }
  for (int i = (1); i <= (n); ++i)
    if (!minPrime[i]) minPrime[i] = i;
}
void factorize(int n) {
  while (n != 1) {
    pr.insert(minPrime[n]);
    ++cnt[minPrime[n]];
    n /= minPrime[n];
  }
}
void solveProblem() {
  init();
  for (int i = (1); i <= (n); ++i) factorize(a[i]);
  vector<int> primes((pr).begin(), (pr).end());
  int sumProd = 1;
  int m = primes.size() - 1;
  for (int i = (0); i < ((int)primes.size()); ++i) {
    update(1, 0, m, i, cnt[primes[i]] + 1);
  }
  int ans = 1;
  for (int i = (0); i < ((int)primes.size()); ++i) {
    int sumProd =
        1LL * get(1, 0, m, 0, i - 1) * get(1, 0, m, i + 1, m) % (MOD - 1);
    long long cur = 1;
    for (int j = (1); j <= (cnt[primes[i]]); ++j) {
      (cur *= primes[i]) %= MOD;
      ans = (1LL * ans * power(cur, sumProd, MOD)) % MOD;
    }
  }
  cout << ans << '\n';
}
void fastInput() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
void readInput() {
  cin >> n;
  for (int i = (1); i <= (n); ++i) cin >> a[i];
}
int main() {
  fastInput();
  readInput();
  solveProblem();
}
