// O(N + (max(A_i))^2)解 #include using namespace std; #define all(x) (x).begin(),(x).end() #define rep(i, n) for (int i = 0; i < (n); i++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define endl "\n" typedef long long ll; typedef pair pii; typedef pair pll; template ostream &operator<<(ostream &os, const vector &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;} template ostream &operator<<(ostream &os, const pair &p) {os << "(" << p.first << ", " << p.second << ")"; return os;} const int mod = 1e9 + 7; ll mod_pow(ll x, ll n, ll mod) { ll res = 1; while(n > 0) { if(n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } ll inv(ll x) { return mod_pow(x, mod - 2, mod); } ll f(ll x, ll y) { return (((x + y) % mod) * mod_pow(x, y, mod)) % mod; } // (x + y)x^y < (s + t)s^t // log(x + y) + ylog(x) < log(s + t) + tlog(s) double g(ll x, ll y) { return log(x + y) + y * log(x); } void solve() { int N; cin >> N; assert(N >= 1 && N <= 100000); vector A(N), C(2001); for (int i = 0; i < N; i++) { cin >> A[i]; assert(A[i] >= 1 && A[i] <= 1000); A[i] %= mod; C[A[i]]++; } // 考察1. miをO(N)で求める // iを固定すると,jとしては(i mi_table(N + 1, 1LL << 60); for (int i = N - 1; i >= 0; i--) { mi_table[i] = min(mi_table[i + 1], A[i]); } double mi = g(A[0], mi_table[1]); ll mi_f = f(A[0], mi_table[1]); for (int i = 1; i < N; i++) { if (mi > g(A[i], mi_table[i + 1])) { mi = g(A[i], mi_table[i + 1]); mi_f = f(A[i], mi_table[i + 1]); } } // 考察2. \prod_i \prod_j f(A[i], A[j]) をO(N)で求める // 考察2a. // 塁乗部分は各iについて A[i]^{\sum_{i acc_back(N + 1); for (int i = N - 1; i >= 0; i--) { acc_back[i] = acc_back[i + 1] + A[i]; acc_back[i] %= mod; } ll prod = 1; for (int i = 0; i < N; i++) { prod *= mod_pow(A[i], acc_back[i + 1], mod); prod %= mod; } // 考察2b. // あとはA[i] + A[j] = k (i < j)となるような(i, j)が何個あるかを解けば良い // A[i]が小さいので,kを決め打ちして探索できる. vector pair_cnt(2001); for (int k = 2; k <= 2000; k++) { ll c = 0; for(int a = 0; a <= k; a++) { int b = k - a; c += C[a] * C[b]; c %= mod; } if (k % 2 == 0) c -= C[k / 2]; pair_cnt[k] += c / 2; } for (int k = 0; k < 2001; k++) { prod *= mod_pow(k, pair_cnt[k], mod); prod %= mod; } cout << (prod * inv(mi_f)) % mod << endl; } int main() { #ifdef LOCAL_ENV cin.exceptions(ios::failbit); #endif cin.tie(0); ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(16); solve(); }