#include using namespace std; typedef complex cpx; const double PI = acos(-1); vector FFT(vector P, bool inv = 0) { assert(__builtin_popcount(P.size()) == 1); int lg = 31 - __builtin_clz(P.size()), n = 1 << lg; // == P.size(); for (int j = 1, i = 0; j < n - 1; ++j) { for (int k = n >> 1; k > (i ^= k); k >>= 1) ; if (j < i) swap(P[i], P[j]); } // bit reverse auto w1 = exp((2 - 4 * inv) * PI / n * cpx(0, 1)); // order is 1<>= 1; } return r; } int inv(int v, int m = M) { return ipow(v, m - 2, m); } int main() { ios::sync_with_stdio(false); int N; cin >> N; vector A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; } pair dnr(A[0], A[1]); for (int i = N - 2, minp = A[N - 1]; ~i; --i) { auto log_eval = [](int x, int y) { return log(x + y) + y * log(x); }; if (log_eval(A[i], minp) < log_eval(dnr.first, dnr.second)) { dnr = make_pair(A[i], minp); } minp = min(minp, A[i]); } vector pa(N + 1); for (int i = 0; i < N; ++i) { pa[i + 1] = pa[i] + A[i]; } int maxa = *max_element(A.begin(), A.end()); int maxa2 = maxa * 2 + 1; while (__builtin_popcount(maxa2) != 1) ++maxa2; vector c(maxa2); for (int a : A) c[a] += 1.0; vector fc = FFT(c); for (int i = 0; i < fc.size(); ++i) { fc[i] *= fc[i]; } vector c2 = FFT(fc, true); int ans = 1; for (int s = 2; s < maxa * 2 + 1; ++s) { int64_t cs = int(real(c2[s]) + 0.5) / 2; if (~s & 1) cs -= int(real(c[s / 2]) + 0.5) / 2; ans = 1LL * ans * ipow(s, cs) % M; } for (int i = 0; i + 1 < N; ++i) { ans = 1LL * ans * ipow(A[i], pa[N] - pa[i + 1]) % M; } int idnr = inv(1LL * (dnr.first + dnr.second) % M * ipow(dnr.first, dnr.second) % M); ans = 1LL * ans * idnr % M; cout << ans << endl; return 0; }