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;
int n, p[200009], t, q, w, ww, a[200009], qq, mod = 1000000007;
bool v[200009];
int z(int a, int b) {
  int q = 1, w = a;
  while (b) {
    if (b % 2) q = (long long)q * w % mod;
    w = (long long)w * w % mod;
    b >>= 1;
  }
  return q;
}
int main() {
  for (int i = 2; i <= 200000; i++) {
    if (!v[i]) {
      p[t++] = i;
      for (int j = i + i; j <= 200000; j += i) {
        v[j] = 1;
      }
    }
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &q);
    a[lower_bound(p, p + t, q) - p]++;
  }
  q = w = 1;
  for (int i = 0; i < t; i++) {
    if (a[i]) {
      qq = q;
      ww = 1;
      for (int j = 0; j < a[i]; j++) {
        ww = (long long)ww * p[i] % mod;
        qq = (long long)qq * q % mod;
        qq = (long long)qq * z(ww, w) % mod;
      }
      w = (long long)w * (a[i] + 1) % (mod - 1);
      q = qq;
    }
  }
  printf("%d\n", q);
  return 0;
}
