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 int mod = 1e9 + 7, MAX = 2e5 + 5;
int fast_power(long long x, long long n, int mod) {
  long long ans = 1, base = x % mod;
  while (n) {
    if (n & 1) {
      ans = (ans * base) % mod;
      n--;
    } else {
      base = (base * base) % mod;
      n /= 2;
    }
  }
  if (ans < 0) ans += mod;
  return ans;
}
int mod_inv(int a, int mod) { return fast_power(a, mod - 2, mod); }
int main() {
  int m, x;
  scanf("%d", &m);
  int a[MAX] = {0};
  for (int i = 0; i < m; i++) {
    scanf("%d", &x);
    a[x]++;
  }
  long long ans = 1;
  long long prodl[MAX] = {0}, prodr[MAX] = {0};
  prodl[0] = prodr[MAX - 1] = 1;
  for (int i = 1; i < MAX; i++) {
    prodl[i] = a[i] + 1;
    prodl[i] *= prodl[i - 1];
    prodl[i] %= mod - 1;
  }
  for (int i = MAX - 2; i >= 0; i--) {
    prodr[i] = a[i] + 1;
    prodr[i] *= prodr[i + 1];
    prodr[i] %= mod - 1;
  }
  for (int i = 2; i < MAX; i++) {
    if (a[i]) {
      long long b = (prodl[i - 1] * prodr[i + 1]) % (mod - 1);
      for (int j = 1; j <= a[i]; j++) {
        ans *= fast_power(i, (j * b) % (mod - 1), mod);
        ans %= mod;
      }
    }
  }
  printf("%lld\n", ans);
}
