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;
long long prime[200000];
long long pow(long long a, long long n) {
  if (n == 1)
    return a;
  else {
    if (n % 2 == 1)
      return (pow(a, n - 1) * a) % 1000000007;
    else {
      long long temp = pow(a, n / 2);
      return (temp * temp) % 1000000007;
    }
  }
}
int main(void) {
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) cin >> prime[i];
  sort(prime, prime + m);
  vector<pair<long long, int> > v;
  for (int i = 0; i < m; i++) {
    pair<long long, int> temp = make_pair(prime[i], 1);
    while (i + 1 < m && prime[i] == prime[i + 1]) {
      temp.second++;
      i++;
    }
    v.push_back(temp);
  }
  bool iseven = false;
  long long product = 1;
  for (int i = 0; i < v.size(); i++) {
    if ((v[i].second + 1) % 2 == 0) {
      if (iseven == false) {
        iseven = true;
        product *= (v[i].second + 1) / 2;
      } else
        product *= (v[i].second + 1);
    } else
      product *= (v[i].second + 1);
    product %= 1000000006;
  }
  long long result = 1;
  for (int i = 0; i < v.size(); i++) {
    long long power;
    if (iseven == false)
      power = product * (v[i].second / 2);
    else
      power = product * v[i].second;
    power %= 1000000006;
    result *= pow(v[i].first, power);
    result %= 1000000007;
  }
  cout << result << endl;
  return 0;
}
