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>
constexpr long long MOD = 1e9 + 7;
long long binpow(long long a, long long n, long long m) {
  if (!n) {
    return 1;
  }
  if (n == 1) {
    return a % m;
  }
  long long x = binpow(a, n / 2, m);
  x = (x * x) % m;
  if (n & 1) {
    x = (x * a) % m;
  }
  return x;
}
int main() {
  long long m, q;
  std::cin >> m;
  std::map<long long, long long> cnt;
  for (int i = 0; i < m; ++i) {
    std::cin >> q;
    ++cnt[q];
  }
  std::vector<std::pair<long long, long long>> cs;
  for (auto& p : cnt) {
    cs.push_back(p);
  }
  std::sort(cs.begin(), cs.end());
  int sz = cs.size();
  std::vector<long long> pref(sz + 1), suff(sz + 2);
  pref[0] = 1;
  for (int i = 1; i <= sz; ++i) {
    pref[i] = (pref[i - 1] * (cs[i - 1].second + 1)) % (MOD - 1);
  }
  suff[sz + 1] = 1;
  for (int i = sz; i > 0; --i) {
    suff[i] = (suff[i + 1] * (cs[i - 1].second + 1)) % (MOD - 1);
  }
  long long ans = 1;
  for (int i = 1; i <= sz; ++i) {
    long long q = cs[i - 1].first, c = cs[i - 1].second;
    long long deg = (pref[i - 1] * suff[i + 1]) % (MOD - 1);
    ans = (ans * binpow(binpow(q, (c * (c + 1)) / 2, MOD), deg, MOD)) % MOD;
  }
  std::cout << ans << '\n';
  return 0;
}
