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>
const long long MOD = 1e9 + 7;
const int MaxN = 200005;
int p[MaxN], m;
std::pair<int, int> pc[MaxN];
long long prefix[MaxN], suffix[MaxN];
long long mpow(long long a, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res = res * a % MOD;
    a = a * a % MOD;
    n >>= 1;
  }
  return res;
}
int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    m = 0;
    for (int i = 0; i < n; i++) scanf("%d", &p[i]);
    std::sort(p, p + n);
    for (int i = 0, j = 0; i < n; i = j) {
      while (j < n && p[i] == p[j]) j++;
      pc[++m] = {p[i], j - i};
    }
    prefix[0] = 1;
    for (int i = 1; i <= m; i++)
      prefix[i] = prefix[i - 1] * (pc[i].second + 1) % (MOD - 1);
    suffix[m + 1] = 1;
    for (int i = m; i >= 1; i--)
      suffix[i] = suffix[i + 1] * (pc[i].second + 1) % (MOD - 1);
    long long res = 1, cur;
    for (int i = 1; i <= m; i++) {
      cur = 1;
      for (int j = 0; j < pc[i].second; j++) {
        cur = cur * pc[i].first % MOD;
        res = res * mpow(cur, prefix[i - 1] * suffix[i + 1] % (MOD - 1)) % MOD;
      }
    }
    printf("%I64d\n", res);
  }
  return 0;
}
