Atcoder ABC 127E（数学，计数，概率）

选 $k$ 个格子的方案数为 $C(n+m, k)$，在 $k$ 个格子中，任选 $2$ 个出来，有 $C(k,2)$ 种，考虑它们的贡献：

因为是全部方案，所以可以考虑用 期望值 来做！

问题转化为，从 $N \times M$ 的矩阵中，选择 $2$ 个不同的点 $(x_i, y_i), (x_j,y_j)$ ，求 $|x_i - x_j| + |y_i-y_j|$ 的期望？

期望为： $\frac{n+m}{3}$

如果推式子很难，这里是一些小技巧（仅用于 分母中无 $n,m$ ，并且分子中不存在 $nm$ 之类的项）：

打表找规律：假设期望值 $E(n,m)$ 是一个关于 $n,m$ 的多项式，那么固定一下 $n$ 的值，然后让 $m = 1,2,3…$ 来打表找出 $E(n,m)$ 和 $m$ 的关系。同理可以找出 $E(n,m)$ 和 $n$ 的关系，相加一下就可以了。

拉格朗日插值法：设 $ans = F(n,m) = E(n,m) * C(nm, 2)$，我们可以固定 $n$，然后用插值法找出 $F(n,m)$ 和 $m$ 的关系。（这个函数有两个变量，按理说应该是固定每一个 $n$ 然后对每一个 $n$ 都进行一次插值法的，以后遇到了可以尝试一下。）

严谨证明：

考虑一个点 $(x,y)$，那么

纵向贡献 为： $v_{x,y} = [(1+2+…+x-1) + (1+2+…+n-x)] * m$

横向贡献 为： $h_{x,y} = [(1+2+…y-1) + (1+2+…+m-y)] * n$

期望就是 $E(n,m) = \frac{\sum\limits_{x=1}^n \sum\limits_{y=1}^m (v_{x,y} + h_{x,y})}{C(nm,2)} = \frac{n+m}{3}$

以上，最终的答案就是

$ans = C(nm,k) * C(k,2) * \frac{n+m}{3}$

我们选择 $2$ 个格子，有 $C(nm-2, k-2)$ 种。

对于横坐标的差值为 $d_x$ 的情况，有 $(n-d_x) m^2$ 种。贡献就是 $(n-d_x)m^2*d_x$

对于纵坐标的差值为 $d_y$ 的情况，有 $(m-d_y) n^2$ 种。贡献就是 $(m-d_y) n^2*d_y$

所以答案就是

$ans = C(nm-2, k-2) (\sum\limits_{d_x=1}^{n-1} (n-d_x)m^2*d_x + \sum\limits_{d_y=1}^{m-1} (m-d_y)n^2*d_y)$

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

#define ll long long
const int mod = 1e9+7;
const int maxn = 2e5+5;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1)
            (res *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll a) {
    return qpow(a, mod-2);
}

ll n,m,k;
ll fac[maxn];

void init() {
    fac[0] = 1;
    fac[1] = 1;
    for (int i = 2; i <= n*m; i++) {
        fac[i] = (fac[i-1] * (ll)(i)) % mod;
    }
}

int main() {
    cin >> n >> m >> k;
    init();

    ll nu = fac[n*m] * k % mod * (k-1) % mod * (n+m) % mod;
    ll de = inv(fac[k]) * inv(fac[n*m-k]) % mod * inv(6) % mod;
    cout << (nu * de) % mod << endl;
}