C++ Combinatorics + Contribution Technique + Inverse Modulo
IntuitionApproachComplexity

Time complexity:
O (m*n)


Space complexity:

Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
O (m*n)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:

#define ll long long

const ll mod = 1e9 + 7 ;

    ll inv (ll a) {

        return a <= 1LL ? a : mod - (mod / a) * inv (mod % a) % mod ;

    }

    ll C (ll n, ll r, vector <ll> &fac, vector <ll> &invfac) {

        if (r > n) return 0LL ;

        return fac [n] * invfac [n - r] % mod * invfac [r] % mod ;
    }

    int distanceSum(int m, int n, int k) {

        if (k == 1) return 0 ;
        
        vector <ll> fac (100010), invfac (100010) ;

        ll cap = 100005 ;

        fac [0] = 1 ;

        for (ll i = 1 ; i <= cap ; i ++) fac [i] = fac [i - 1] * i % mod ;

        invfac [cap] = inv (fac [cap]) ;

        for (int i = cap - 1 ; i >= 0 ; i --) invfac [i] = invfac [i + 1] * (i + 1) % mod ;
        

        ll val = 0 ;

        for (ll i = 1 ; i <= n ; i ++) for (ll j = 1 ; j <= m ; j ++) {

            ll lh = j - 1, rh = m - j ;

            ll uv = i - 1, bv = n - i ;

            ll hv = lh * (lh + 1) / 2 + rh * (rh + 1) / 2 ;
            
            ll vv = uv * (uv + 1) / 2 + bv * (bv + 1) / 2 ;

            val += hv * n % mod + vv * m % mod ;

            val %= mod ;
           
        }

        ll ans = val * inv (2) % mod * C (m * n - 2, k - 2, fac, invfac) % mod ;
        
        return ans ;
    }
};
```
['Combinatorics', 'C++']