Brute Force to best solution with pen paper proof.
IntuitionKey observation : Each pair can be chosen Comb(m*n-2, k-2) times.I have provided 4 codes :
Best Approach (Accepted)
Better Approach (Accepted)
Intermed
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Key observation : Each pair can be chosen Comb(m*n-2, k-2) times.

I have provided 4 codes :
1. Best Approach (Accepted)
2. Better Approach (Accepted)
3. Intermediate Approach (TLE)
4. Brute force Approach (TLE)

# Approach
<!-- Describe your approach to solving the problem. -->
![3426. Manhattan Distances of All Arrangements of Pieces.jpg](https://assets.leetcode.com/users/images/07d64014-1d35-44a8-b1da-4cb56e65332d_1738396014.0393786.jpeg)

# Best Approach Code
```python3 []
MOD = 10**9 + 7
max_n = 10**5

# Precompute factorial and inverse factorial arrays
fact = [1] * (max_n + 1)
for i in range(1, max_n + 1):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [1] * (max_n + 1)
inv_fact[max_n] = pow(fact[max_n], MOD - 2, MOD)
for i in range(max_n - 1, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

def comb(n, k):
    if n < 0 or k < 0 or k > n:
        return 0
    return ((fact[n] * inv_fact[k] % MOD) * inv_fact[n - k]) % MOD

class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int:
        
        def calc(a,b):
            res = a*a*b*(b*b-1)//6
            res %= MOD
            return res
        
        res = comb(m*n-2,k-2)%MOD * (calc(m,n)+calc(n,m)) % MOD
        return res
```

# Better Approach Code
```python3 []
MOD = 10**9 + 7
max_n = 10**5

# Precompute factorial and inverse factorial arrays
fact = [1] * (max_n + 1)
for i in range(1, max_n + 1):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [1] * (max_n + 1)
inv_fact[max_n] = pow(fact[max_n], MOD - 2, MOD)
for i in range(max_n - 1, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

def comb(n, k):
    if n < 0 or k < 0 or k > n:
        return 0
    return ((fact[n] * inv_fact[k] % MOD) * inv_fact[n - k]) % MOD

class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int:
        res=0
        mn=m*n
        for j in range(n):
            x=n-j-1
            res += x*(x+1)//2
            res %= MOD
        res *= m
        res %= MOD
        
        vec=[n*(n+1)//2]
        s=0
        for j in range(2,n+1):
            s+=j
            i=n-j+1
            vec.append(s+i*(i+1)//2)

        for i in range(m-1):
            for j in range(n):
                # ap
                terms=m-1-i
                s=vec[j]*terms
                s+=terms*n*(terms-1) // 2
                res += s
                res%=MOD
                
        res = res*comb(mn-2,k-2)%MOD
        return res
```

# Intermediate Approach Code
```python3 []
MOD = 10**9 + 7
max_n = 10**5

# Precompute factorial and inverse factorial arrays
fact = [1] * (max_n + 1)
for i in range(1, max_n + 1):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [1] * (max_n + 1)
inv_fact[max_n] = pow(fact[max_n], MOD - 2, MOD)
for i in range(max_n - 1, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

def comb(n, k):
    if n < 0 or k < 0 or k > n:
        return 0
    return ((fact[n] * inv_fact[k] % MOD) * inv_fact[n - k]) % MOD

class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int:
        # Key observation: A pair will be chosen C(m*n-2, k-2) times.
        if m<n:
            return self.distanceSum(n,m,k)
        res=0
        mn=m*n
        for j in range(n):
            x=n-j-1
            res += x*(x+1)//2
            res %= MOD
        res *= m
        res %= MOD
        
        for i in range(m-1):
            for j in range(n):
                vec=[]
                s=0
                for nj in range(n):
                    s+=abs(nj-j)+1
                # ap
                terms=m-1-i
                s*=terms
                s+=terms*n*(terms-1) // 2
                res += s
                res%=MOD
                
        res = res*comb(mn-2,k-2)%MOD
        return res
```
# Brute Force Approach Code
```python3 []
MOD = 10**9 + 7
max_n = 10**5

# Precompute factorial and inverse factorial arrays
fact = [1] * (max_n + 1)
for i in range(1, max_n + 1):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [1] * (max_n + 1)
inv_fact[max_n] = pow(fact[max_n], MOD - 2, MOD)
for i in range(max_n - 1, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

def comb(n, k):
    if n < 0 or k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int:
        res=0
        mn=m*n
        for i in range(m):
            for j in range(n):
                for ni in range(i,m):
                    for nj in range(j+1 if ni == i else 0,n):
                        # if ni == i and nj == j:
                        #     continue
                        res += (abs(ni-i)+abs(nj-j))*comb(mn-2,k-2)
                        res %= MOD

        return res
```
['Math', 'Combinatorics', 'Python3']