Easy C++ Solution with explanation || O(n+m) || Mathematic Combinatorics
ApproachRow distance contribution:
Suppose we have two rows, and we want to calculate the distance between pieces in these rows.
If the distance between the row
# Approach
#### Row distance contribution:

- Suppose we have two rows, and we want to calculate the distance between pieces in these rows.
- If the distance between the rows is d, the possible pairs of rows where pieces can be placed are (0, d), (1, d+1), ..., (m-d-1, m-1). There are m - d such pairs.
- For the remaining pieces, after selecting the two, we calculate how many ways we can place them in the grid using combinations (comb(m*n - 2, k-2)).
- So, for each horizontal distance d, we calculate the contribution and sum it up.
#### Column distance contribution:
A similar process happens for the columns: 
- if the distance between columns is d, we calculate the combinations of column pairs, then multiply by the possible vertical and horizontal placements, and finally, compute the contribution to the total Manhattan distance.

# Complexity
- Time complexity:
$$O(n+m)$$

- Space complexity:
$$O(1e6)$$

# Code
```cpp []
class Solution{
public:
    int mod = 1e9 + 7;
    typedef long long ll;
    vector<ll> vect;
    Solution(){
        vect.resize(100000);
        fact();
    }

    ll binpow(ll a, ll b){
        ll res = 1;
        while(b){
            if(b % 2){
                res = (res * a) % mod;
            }
            a =(a*a)%mod;
            b /= 2;
        }
        return res;
    }

    void fact(){
        vect[0]= 1;
        for(int i = 1; i < 100000; i++){
            vect[i] = (vect[i - 1]* i) % mod;
        }
    }

    ll comb(ll n, ll r){
        if (n < r || n >= 100000 || r >= 100000) return 0;
        ll ans = vect[n]% mod;
        ll tmp = (binpow(vect[r], mod - 2) * binpow(vect[n - r], mod - 2))%mod;
        return (ans*tmp) % mod;
    }

    int distanceSum(int m, int n, int k){
        ll cnt = 0;
        for(int d = 1; d<m; d++){
            ll tmp = comb(m*n - 2, k-2);
            tmp = (tmp * d) % mod;
            tmp = (tmp * (m - d)) % mod;
            tmp = (tmp * n) % mod;
            tmp = (tmp * n) % mod;
            cnt = (cnt + tmp) % mod;
        }

        for(int d=1; d<n; d++){
            ll tmp = comb(m*n - 2, k-2);
            tmp = (tmp * d) % mod;
            tmp = (tmp * (n - d)) % mod;
            tmp = (tmp * m) % mod;
            tmp = (tmp * m) % mod;
            cnt = (cnt + tmp) % mod;
        }
        return cnt;
    }
};

```
['Combinatorics', 'C++']