python3 combinatorics O(mn)
For a pair of a certain configuration, we are left with mn-2 positions from which to choose k-2 positions, that is, C(mn-2,k-2) times it will be counted.For eac
For a pair of a certain configuration, we are left with m*n-2 positions from which to choose k-2 positions, that is, C(m*n-2,k-2) times it will be counted.

For each grid point we traverse the whole grid to calculate the sum of mahattan distance of all possible second point -- by considering the ros of columns seperately it is easy to do so.

Don't forget the 2 factor since all pairs are considered twice.

# Code
```python3 []
@cache
def myfac(i):
    if i <=1:return 1
    return i*myfac(i-1) % (10**9+7)
@cache
def myinvfac(i):
    if i <= 1:return 1
    return pow(i,-1,10**9+7)*myinvfac(i-1) % (10**9+7)

@cache
def mycomb(a,b):
    if b == 0:return 1
    if b == 1:return a % (10**9+7)
    #return mycomb(a-1,b)*mycomb(a-1,b-1) % (10**9+7)
    return myfac(a)*myinvfac(b)*myinvfac(a-b) % (10**9+7)

class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int:
        res = 0
        for i in range(m):
            for j in range(n):
                res += m*(j*(j+1)//2 + (n-j-1)*(n-j)//2) % (10**9+7)
                res += n*(i*(i+1)//2 + (m-i-1)*(m-i)//2) % (10**9+7)
        res = res // 2 % (10**9+7)
        return res*mycomb(m*n-2,k-2) % (10**9+7)
        
```
['Combinatorics', 'Python3']