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>
#pragma warning(disable : 4996)
using namespace std;
long long m, p[200002], tmp, ans = 1, cnt = 1, x[40], q;
bool sq = true;
int main() {
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    cin >> tmp;
    p[tmp]++;
  }
  for (int i = 2; i < 200001; i++) {
    if (p[i] % 2 == 1) sq = false;
  }
  x[0] = 1;
  for (int i = 2; i < 200001; i++) {
    for (int j = 0; j < p[i]; j++) {
      x[0] *= i;
      x[0] %= 1000000007;
    }
  }
  if (sq)
    for (int i = 2; i < 200001; i++) {
      for (int j = 0; j < p[i] / 2; j++) {
        ans *= i;
        ans %= 1000000007;
      }
    }
  for (int i = 0; i < 200001; i++) {
    cnt *= (p[i] + 1);
    q *= (p[i] + 1);
    q += cnt / 1000000006;
    q %= 2;
    cnt %= 1000000006;
  }
  if (sq) cnt--;
  cnt /= 2;
  if (q % 2 == 1) cnt += 500000003;
  for (int i = 1; i < 40; i++) {
    x[i] = x[i - 1] * x[i - 1];
    x[i] %= 1000000007;
  }
  int i = 0;
  while (cnt > 0) {
    if (cnt % 2 == 1) {
      ans *= x[i];
      ans %= 1000000007;
    }
    cnt /= 2;
    i++;
  }
  cout << ans;
}
