c++
Intuition

ApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
![image.png](https://assets.leetcode.com/users/images/8f713c81-fb5c-4dd6-9a01-65cc633ac087_1737459609.6519988.png)
![image.png](https://assets.leetcode.com/users/images/3b3a75e8-c4b5-423d-8535-4a476f5f49b7_1737459614.6739767.png)
![image.png](https://assets.leetcode.com/users/images/9c332222-63ba-45c6-8ecd-e01e098b31ce_1737459631.5831652.png)



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

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

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

# 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;
    }
};
```
['C++']