题面

你有 $n$ 个数 $a_1,a_2,\dots,a_n$ 要进行 $k$ 次操作，每次随机选择一个数 $x \in [1,n]$ ，把 $a_x$ 减一，并将答案增加除 $a_x$ 外所有数的乘积。

求最终答案的期望，答案对 $10^9 + 7$ 取模。

题解

设最终 $a_i$ 的减少量为 $b_i$ ，可以把答案转化为 $\prod_{i=1}^na_i-\prod_{i=1}^n(a_i-b_i)$ 。于是即求 $\prod_{i=1}^n(a_i-b_i)$ 的期望值。

这里 $\sum b_i=k$ ，于是明显有

$$\begin{aligned}\mathbb{E}&=\frac{1}{n^k}\binom{k}{b_1,b_2,\cdots,b_n}\prod_{i=1}^n(a_i-b_i)\\ &=\frac{k!}{n^k}\prod_{i=1}^n\frac{a_i-b_i}{b_i!}\end{aligned}$$

对后面那个积用 EGF 处理

$$\begin{aligned}\hat f_i(x)&=\sum_{j=0}\frac{a_i-j}{j!}x^j\\ &=\sum_{j=0}\left(\frac{a_i}{j!}x^j-\frac{x\cdot x^{j-1}}{(j-1)!}\right)\\ &=(a_i-x)e^x\end{aligned}$$

$$\begin{aligned}\hat F(x)&=\prod_{i=1}^n\hat f_i(x)\\ &=e^{nx}\prod_{i=1}^n(a_i-x)\end{aligned}$$

答案求 $\frac{k!}{n^k}[x^k]\hat F(x)$ 。先考虑把 $\hat F(x)$ 拆为两部分，exp 那部分为 $\sum \frac{n^i}{i!}$ ，另一部分可以令

$$G(x)=\prod_{i=1}^n(a_i-x)=\sum_{i=0}^nc_ix^i $$

则

$$[x^k]\hat F(x)=\sum_{i=0}^nc_i\frac{n^{k-i}}{(k-i)!} $$

$n$ 小 $\mathcal{O}(n^2)$ 即可。

const int N = 5e3 + 5, mod = 1e9 + 7;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	ll a[N], f[N];
	ll qpow (ll a, int b) {
		ll ans = 1ll;
		for (; b; b >>= 1, a = 1ll * a * a % mod)
			if (b & 1) ans = 1ll * ans * a % mod;
		return ans;
	}
	int main () {
		n = Read(), m = Read();
		f[0] = 1;
		for (int i = 1; i <= n; i++) {
			a[i] = Read();
			for (int j = i; j; j--) f[j] = (1ll * f[j] * a[i] - f[j - 1] + mod) % mod;
			f[0] = 1ll * f[0] * a[i] % mod;
		}
		ll ans = 0, fac = 1, inv = qpow (n, mod - 2);
		for (int i = 0; i <= n; ++i) {
			ans = (ans + f[i] * fac) % mod;
			fac = fac * (m - i) % mod * inv % mod;
		}
		printf ("%lld\n", (f[0] - ans + mod) % mod);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}