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;
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vll = vector<ll>;
using pdd = pair<double, double>;
using vpdd = vector<pdd>;
template <typename T>
using uset = unordered_set<T>;
template <typename T>
using umultiset = unordered_multiset<T>;
template <typename K, typename V>
using umap = unordered_map<K, V>;
template <typename K, typename V>
using umultimap = unordered_multimap<K, V>;
const int dr[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dc[] = {0, 1, 0, -1, 1, -1, -1, 1};
const double eps = 1e-9;
const int INF = 0x7FFFFFFF;
const ll INFLL = 0x7FFFFFFFFFFFFFFFLL;
const double pi = acos(-1);
template <typename T>
T take(queue<T>& O) {
  T tmp = O.front();
  O.pop();
  return tmp;
}
template <typename T>
T take(stack<T>& O) {
  T tmp = O.top();
  O.pop();
  return tmp;
}
template <typename T>
T take(priority_queue<T>& O) {
  T tmp = O.top();
  O.pop();
  return tmp;
}
template <typename T>
inline bool inRange(const T& z, const T& a, const T& b) {
  return a <= z && z <= b;
}
void OPEN(const string& in = "input.txt", const string& out = "output.txt") {
  freopen(in.c_str(), "r", stdin);
  freopen(out.c_str(), "w", stdout);
  return;
}
constexpr int MOD = 1000000007;
constexpr int MOD5 = 1000000006;
map<int, int> counter;
vii prime_factors;
int prefix[200005], suffix[200005];
int p, a;
int pkt(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = (1LL * res * a) % MOD;
    b >>= 1;
    a = (1LL * a * a) % MOD;
  }
  return res;
}
int main(int argc, char** argv) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> p;
  for (int(i) = (0), _t = (p); i < (_t); ++(i)) {
    cin >> a;
    if (counter.find(a) == counter.end()) {
      counter[a] = 0;
    }
    ++counter[a];
  }
  for (const auto& prime_factor : counter) {
    prime_factors.push_back(prime_factor);
  }
  for (int(i) = (0), _t = ((int)prime_factors.size()); i < (_t); ++(i)) {
    prefix[i] = prime_factors[i].second + 1;
    suffix[i] = prime_factors[i].second + 1;
  }
  for (int(i) = (1), _t = ((int)prime_factors.size()); i < (_t); ++(i)) {
    prefix[i] = (1LL * prefix[i - 1] * prefix[i]) % MOD5;
  }
  for (int(i) = ((int)prime_factors.size() - 2), _t = (0); i >= (_t); --(i)) {
    suffix[i] = (1LL * suffix[i + 1] * suffix[i]) % MOD5;
  }
  int ans = 1LL;
  for (int(i) = (0), _t = ((int)prime_factors.size()); i < (_t); ++(i)) {
    ll mul = 1LL;
    if (i) mul = (mul * prefix[i - 1]) % MOD5;
    if (i + 1 < (int)prime_factors.size()) mul = (mul * suffix[i + 1]) % MOD5;
    int lol = 1;
    for (int(j) = (0), _t = (prime_factors[i].second); j <= (_t); ++(j)) {
      ans = (1LL * ans * pkt(lol, mul)) % MOD;
      lol = (1LL * lol * prime_factors[i].first) % MOD;
    }
  }
  cout << ans << "\n";
}
