[Java/C++/Python] Combinations, O(m + n)
ExplanationConsider the contribution of distance from two different rows:If the distance of rows is d = 1,
there are m - 1 combination: (0,1),(1,2) ...
If the d

# **Explanation**
Consider the contribution of distance from two different rows:

If the distance of rows is `d = 1`,
there are `m - 1` combination: (0,1),(1,2) ...
If the distance of rows is `d = 2`,
there are `m - 2` combination: (0,2),(1,3) ...
For distance `d`, there are `m - d` combinations.

For each combination of `(xi, xj)` above,
the `yi` has `n` options,
`yj` has `n` options,
the rest of points has `comb(m - n - 2, k - 2)` combinations.

Same process for contribution from two different cols.

# **Complexity**
Time `O(m + n + k)`
Space `O(1)`
<br>

```py [Python3]
    def distanceSum(self, m: int, n: int, k: int) -> int:
        mod = 10 ** 9 + 7
        base = comb(m * n - 2, k - 2) % mod
        res = 0
        for d in range(1, n):
            res += d * (n - d) * m * m
        for d in range(1, m):
            res += d * (m - d) * n * n
        return res * base % mod
```
```Java [Java]
    private long comb(long a, long b, long mod) {
        if (b > a) return 0;
        long numer = 1, denom = 1;
        for (long i = 0; i < b; ++i) {
            numer = numer * (a - i) % mod;
            denom = denom * (i + 1) % mod;
        }
        // Fermat's Little Theorem
        long denom_inv = 1;
        long exp = mod - 2;
        while (exp > 0) {
            if (exp % 2 > 0) {
                denom_inv = denom_inv * denom % mod;
            }
            denom = denom * denom % mod;
            exp /= 2;
        }
        return numer * denom_inv % mod;
    }

    public int distanceSum(int m, int n, int k) {
        long res = 0, mod = 1000000007;
        long base = comb(m * n - 2, k - 2, mod);
        for (int d = 1; d < n; ++d) {
            res = (res + 1L * d * (n - d) % mod * m % mod * m % mod) % mod;
        }
        for (int d = 1; d < m; ++d) {
            res = (res + 1L * d * (m - d) % mod * n % mod * n % mod) % mod;
        }
        return (int)(res * base % mod);
    }
```

```C++ [C++]
    long long comb(long long a, long long b, long long mod) {
        if (b > a) return 0;
        long long numer = 1, denom = 1;
        for (long long i = 0; i < b; ++i) {
            numer = numer * (a - i) % mod;
            denom = denom * (i + 1) % mod;
        }

        // Fermat's Little Theorem
        long long denom_inv = 1;
        long long exp = mod - 2;
        while (exp) {
            if (exp % 2) denom_inv = denom_inv * denom % mod;
            denom = denom * denom % mod;
            exp /= 2;
        }
        return numer * denom_inv % mod;
    }

    int distanceSum(int m, int n, int k) {
        int mod = 1e9 + 7;
        long long base = comb(m * n - 2, k - 2, mod);
        long long res = 0;
        for (int d = 1; d < n; ++d) {
            res = (res + 1LL * d * (n - d) % mod * m % mod * m % mod) % mod;
        }
        for (int d = 1; d < m; ++d) {
            res = (res + 1LL * d * (m - d) % mod * n % mod * n % mod) % mod;
        }
        return res * base % mod;
    }
```


['Python', 'C++', 'Java']