#ifndef CLASS_POLYNOMIAL #define CLASS_POLYNOMIAL #include #include #include #include class polynomial { private: using type = double; const type epsilon = 1.0e-9; std::size_t sz; std::vector a; inline bool equivalent(type ra, type rb) const { return (epsilon <= ra - rb && ra - rb <= epsilon); } void discrete_fourier_transform(std::vector >& v, bool rev) { std::size_t n = v.size(); const type pi = acos(type(-1)); for (std::size_t i = 0, j = 1; j < n - 1; ++j) { for (std::size_t k = n >> 1; k > (i ^= k); k >>= 1); if (i > j) std::swap(v[i], v[j]); } for (std::size_t b = 1; b < n; b <<= 1) { std::complex wr = std::polar(type(1), (rev ? type(-1) : type(1)) * pi / b); for (std::size_t i = 0; i < n; i += 2 * b) { std::complex w = type(1); for (std::size_t j = 0; j < b; ++j) { std::complex v0 = v[i + j]; std::complex v1 = w * v[i + j + b]; v[i + j] = v0 + v1; v[i + j + b] = v0 - v1; w *= wr; } } } if (!rev) return; for (std::size_t i = 0; i < n; i++) v[i] /= n; } public: explicit polynomial() : sz(1), a(std::vector({ type() })) {}; explicit polynomial(std::size_t sz_) : sz(sz_), a(std::vector(sz_, type())) {}; explicit polynomial(std::vector a_) : sz(a_.size()), a(a_) {}; polynomial& operator=(const polynomial& p) { sz = p.sz; a = p.a; return (*this); } std::size_t size() const { return sz; } std::size_t degree() const { return sz - 1; } type operator[](std::size_t idx) const { return a[idx]; } type& operator[](std::size_t idx) { return a[idx]; } bool operator==(const polynomial& p) const { for (std::size_t i = 0; i < sz || i < p.sz; ++i) { if (!equivalent(i < sz ? a[i] : type(0), i < p.sz ? p.a[i] : type(0))) { return false; } } return true; } bool operator!=(const polynomial& p) const { return !(operator==(p)); } polynomial resize_transform(std::size_t d) const { // Resize polynomial to d: in other words, f(x) := f(x) mod x^d polynomial ans(*this); ans.sz = d; ans.a.resize(d, type(0)); return ans; } polynomial star_transform() const { // f*(x) = x^degree * f(1/x) polynomial ans(*this); reverse(ans.a.begin(), ans.a.end()); return ans; } polynomial inverse(std::size_t d) const { // Find g(x) where g(x) * f(x) = 1 (mod x^d) polynomial ans(std::vector({ type(1) / a[0] })); while (ans.size() < d) { polynomial nxt; nxt = -ans * resize_transform(ans.size() * 2); nxt.a[0] += type(2); nxt *= ans; ans = nxt.resize_transform(ans.size() * 2); } ans = ans.resize_transform(d); return ans; } polynomial& operator+=(const polynomial& p) { sz = std::max(sz, p.sz); a.resize(sz); for (std::size_t i = 0; i < sz; ++i) a[i] += p.a[i]; return (*this); } polynomial& operator-=(const polynomial& p) { sz = std::max(sz, p.sz); a.resize(sz); for (std::size_t i = 0; i < sz; ++i) a[i] -= p.a[i]; return (*this); } polynomial& operator*=(const polynomial& p) { std::size_t n = 2; while (n < sz * 2 || n < p.sz * 2) n <<= 1; std::vector > v(n), pv(n); for (std::size_t i = 0; i < sz; ++i) v[i] = a[i]; for (std::size_t i = 0; i < p.sz; ++i) pv[i] = p.a[i]; discrete_fourier_transform(v, false); discrete_fourier_transform(pv, false); for (std::size_t i = 0; i < n; ++i) v[i] *= pv[i]; discrete_fourier_transform(v, true); sz += p.sz - 1; a.resize(sz, type(0)); for (std::size_t i = 0; i < sz; ++i) a[i] = v[i].real(); return (*this); } polynomial operator+() const { return polynomial(*this); } polynomial operator-() const { return polynomial() - polynomial(*this); } polynomial operator+(const polynomial& p) const { return polynomial(*this) += p; } polynomial operator-(const polynomial& p) const { return polynomial(*this) -= p; } polynomial operator*(const polynomial& p) const { return polynomial(*this) *= p; } }; #endif #ifndef CLASS_MODINT #define CLASS_MODINT #include template class modint { private: std::uint32_t n; public: modint() : n(0) {}; modint(std::int64_t n_) : n((n_ >= 0 ? n_ : mod - (-n_) % mod) % mod) {}; static constexpr std::uint32_t get_mod() { return mod; } std::uint32_t get() const { return n; } bool operator==(const modint& m) const { return n == m.n; } bool operator!=(const modint& m) const { return n != m.n; } modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; } modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; } modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; } modint operator+(const modint& m) const { return modint(*this) += m; } modint operator-(const modint& m) const { return modint(*this) -= m; } modint operator*(const modint& m) const { return modint(*this) *= m; } modint inv() const { return (*this).pow(mod - 2); } modint pow(std::uint64_t b) const { modint ans = 1, m = modint(*this); while (b) { if (b & 1) ans *= m; m *= m; b >>= 1; } return ans; } }; #endif // CLASS_MODINT #include #include using namespace std; using modulo = modint<1000000007>; int main() { cin.tie(0); ios_base::sync_with_stdio(false); int N; cin >> N; vector A(N); for (int i = 0; i < N; ++i) cin >> A[i]; int mx = *max_element(A.begin(), A.end()); polynomial hist(mx + 1); for (int i = 0; i < N; ++i) hist[A[i]] += 1.0; hist *= hist; for (int i = 0; i < N; ++i) hist[A[i] * 2] -= 1.0; for (int i = 0; i <= 2 * mx; ++i) hist[i] *= 0.5; modulo ans = 1; for (int i = 0; i <= 2 * mx; ++i) { if (hist[i] > 0) { ans *= modulo(i).pow(hist[i]); } } long long sum = 0; for (int i = N - 1; i >= 0; --i) { ans *= modulo(A[i]).pow(sum); sum += A[i]; } int curmin = 1 << 30, p1 = -1, p2 = -1; double curlog = 1.0e+99; for (int i = N - 1; i >= 0; --i) { double newlog = log(A[i]) * curmin; if (curlog > newlog) { curlog = newlog; p1 = A[i]; p2 = curmin; } curmin = min(curmin, A[i]); } ans *= modulo(p1).pow(p2).inv(); cout << ans.get() << endl; return 0; }