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>
T gcd(T first, T second) {
  while (second > 0) {
    first %= second;
    swap(first, second);
  }
  return first;
}
template <class T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <class _T>
inline _T sqr(const _T &first) {
  return first * first;
}
template <class _T>
inline string tostr(const _T &a) {
  ostringstream os("");
  os << a;
  return os.str();
}
const long double PI = 3.1415926535897932384626433832795L;
template <typename T>
inline void input(T &a) {
  static int ed;
  a = 0;
  while (!isdigit(ed = getchar()) && ed != '-') {
  }
  char neg = 0;
  if (ed == '-') {
    neg = 1;
    ed = getchar();
  }
  while (isdigit(ed)) {
    a = 10 * a + ed - '0';
    ed = getchar();
  }
  if (neg) a = -a;
}
template <typename T = int>
inline T nxt() {
  T res;
  input(res);
  return res;
}
mt19937 generator;
bool check(int v) {
  if (v < 2) return false;
  for (int i = 2; i * i <= v; ++i) {
    if (v % i == 0) {
      return false;
    }
  }
  return true;
}
long long pw(long long a, long long n, long long m) {
  long long res = 1;
  while (n) {
    if (n & 1ll) {
      res = res * a % m;
    }
    a = a * a % m;
    n >>= 1;
  }
  return res;
}
long long bin[5][5];
void pre() {
  for (int i = 0; i < 5; ++i) {
    bin[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      bin[i][j] = bin[i - 1][j] + bin[i - 1][j - 1];
    }
  }
}
void read() {}
void test() {}
long long mod = 1000000007;
void solve() {
  int n = nxt();
  int a[n];
  map<int, int> cnt;
  for (int i = 0; i < n; ++i) {
    a[i] = nxt();
    cnt[a[i]]++;
  }
  vector<pair<int, int> > first;
  for (auto v : cnt) {
    first.push_back(v);
  }
  long long pr[first.size() + 1];
  pr[0] = 1;
  for (int i = 0; i < first.size(); ++i) {
    pr[i + 1] = pr[i] * (first[i].second + 1) % (mod - 1);
  }
  long long su[first.size() + 1];
  su[first.size()] = 1;
  for (int i = (int)first.size() - 1; i >= 0; --i) {
    su[i] = su[i + 1] * (first[i].second + 1) % (mod - 1);
  }
  long long ans = 1;
  for (int i = 0; i < first.size(); ++i) {
    long long q = pr[i] * su[i + 1] % (mod - 1);
    for (int k = 1; k <= first[i].second; ++k) {
      ans = ans * pw(first[i].first, q * k % (mod - 1), mod) % mod;
    }
  }
  cout << ans << endl;
}
void solve2() {}
int main() {
  int t = 1;
  pre();
  while (t--) {
    read();
    solve();
  }
  return 0;
}
