CF891E.cpp

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 5010, P = 1e9+7;
int n, k, a[N];

int qpow(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % P;
        a = a * a % P;
        k >>= 1;
    }
    return res;
}

vector<int> solve(int l, int r) {
    if (l > r) return {1};

    if (l == r) return {a[l], P-1};

    vector<int> F = solve(l, (l+r) / 2);
    vector<int> G = solve((l+r)/2+1, r);

    vector<int> H(F.size() + G.size());
    for (int i = 0; i < F.size(); i++) {
        for (int j = 0; j < G.size(); j++) {
            H[i+j] = (H[i+j] + F[i] * G[j]) % P;
        }
    }
    return H;
}

int fact(int i) {
    int res = 1;
    for (int j = 0; j < i; j++) res = res * (k - j) % P;
    return res;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    vector<int> F = solve(1, n);

    int res = 0;
    for (int i = 1; i < F.size() && k-i >= 0; i++) {
        
        res = (res + (P - F[i]) * fact(i) % P * qpow(n, k-i)) % P;
    }
    res = res * qpow(n, P-1-k) % P;
    cout << res << '\n';
    return 0;
}