[c++]  Focus on Single Pair (All pairs are Symmetric)
Intuition1 Focus on simple case : if there is just ONE pair. what is the total Manhattan Distance between just two points?We can focus on vertical and horizonta
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

1 Focus on simple case : if there is just ONE pair. what is the total Manhattan Distance between just two points? 

We can focus on vertical and horizontal seperately and then combine the sum together.

total combo of pairs is C(n*m, 2);
assume total Manhattan Distance is SUM (see check cal(int n, int m) function below)

2 If there are multiple points  
total combo is C(n*m, k);
and total pair is C(n*m, k) * C(k, 2);

3 Final Answer = 
C(n*m, k) * C(k, 2)  / C(n*m, 2) * SUM

We assume all pairs are symmetric


# 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 []
typedef long long ll;
class Solution {
public:
    const static ll mod = (ll) (1e9 +7);
    ll c2(ll x)
    {
        return (x * (x - 1) / 2) % mod; 
    }

    pair<ll, ll> cal(int n, int m)
    {
        ll ans = 0;
        ll p = 0;
        for (int d = 1; d < n; d++)
        {
            ll ps = n - d;
            ll t = (ps * m * m) % mod;
            ll cur = (t * d) % mod;
            p += t;
            //cout << d << "," << cur << endl;
            ans = (ans + cur) % mod;
        }
        //cout << p << endl;
        return {ans, p};
    }
    ll fact(ll x, ll k)
    {
        ll ans = 1;
        for (int i = 0; i < k; i++)
        {
            ans = (ans * (x - i)) % mod;
        }
        //cout << "factor: " <<  x << "," << k << "," << ans << endl;
        return ans;
    }
    ll pow(ll x, ll c)
    {
        ll base = x;
        ll bit = 1;
        ll ans = 1;
        while (bit <= c)
        {
            if ((bit & c) == bit)
            {
                ans = (ans * base) % mod;
            }
            base = (base * base) % mod;
            bit = bit << 1;
        }
        return ans;
    }

    ll inv(ll x)
    {
        ll ans = pow(x, mod - 2);
        //cout << "inv" << x << ":" << ans << endl;
        return ans;
    }
    int distanceSum(int m, int n, int k) {
        ll pairs = c2(k);
        auto a = cal(n, m);
        auto b = cal(m, n);
        ll t = n * m;
        ll x = a.first + b.first;
        ll y = c2(t);
        //cout << "xy " <<  x << "," << y << endl;

        
        ll ans = fact(t, k) % mod * inv(fact(k, k)) % mod *inv(y) % mod * x % mod * pairs % mod;
        return ans;
    }
};
```
['C++']