Math + combinatorics solution [EXPLAINED]
IntuitionCalculate a sum based on the distances between points, using a mathematical approach to avoid brute force calculations. The key challenge is handling l
# Intuition
Calculate a sum based on the distances between points, using a mathematical approach to avoid brute force calculations. The key challenge is handling large values efficiently and working with combinatorics, which represents selecting r items from n. We use modular arithmetic to prevent overflow and ensure the result stays within the bounds of the problem constraints.

# Approach
We calculate the factorial and inverse factorial for the range up to n * m + 1 using modular arithmetic, then precompute the nCr function for quick access. Next, for each point, we calculate the distance sum by evaluating the sum of distances to all other points and applying the combinatoric value we precomputed. We finally return the result after dividing by 2 (to account for over-counting).

# Complexity
- Time complexity:
O(M), where M is n * m + 1, as we perform factorial and inverse factorial calculations, and each distance sum computation for every point takes constant time. Thus, the overall complexity is dominated by the precomputation step.

- Space complexity:
O(M), where M is the size of the fac and invfac vectors, as they store factorials and inverse factorials up to M.

# Code
```rust []
impl Solution {
    const MOD: i64 = 1_000_000_007;

    fn add(x: i64, y: i64) -> i64 {
        ((x % Self::MOD + y % Self::MOD) % Self::MOD + Self::MOD) % Self::MOD
    }

    fn mul(x: i64, y: i64) -> i64 {
        (x % Self::MOD * y % Self::MOD) % Self::MOD
    }

    fn binpow(mut x: i64, mut y: i64) -> i64 {
        let mut z = 1;
        while y > 0 {
            if y % 2 == 1 {
                z = Self::mul(z, x);
            }
            x = Self::mul(x, x);
            y /= 2;
        }
        z
    }

    fn inv(x: i64) -> i64 {
        Self::binpow(x, Self::MOD - 2)
    }

    fn divide(x: i64, y: i64) -> i64 {
        Self::mul(x, Self::inv(y))
    }

    pub fn distance_sum(m: i32, n: i32, k: i32) -> i64 {
        let m = m as i64;
        let n = n as i64;
        let k = k as i64;

        let M = n * m + 1;

        let mut fac = vec![1; (M + 1) as usize];
        let mut invfac = vec![0; (M + 1) as usize];

        for i in 1..=M {
            fac[i as usize] = Self::mul(fac[(i - 1) as usize], i);
        }

        invfac[M as usize] = Self::inv(fac[M as usize]);
        for i in (0..M).rev() {
            invfac[i as usize] = Self::mul(invfac[(i + 1) as usize], i + 1);
        }

        let ncr = |n: i64, r: i64| -> i64 {
            Self::mul(fac[n as usize], Self::mul(invfac[(n - r) as usize], invfac[r as usize]))
        };

        let mut ans = 0;
        let val = ncr(n * m - 2, k - 2);

        let cal = |x: i64| -> i64 {
            std::cmp::max(0, (x * (x + 1)) / 2)
        };

        for i in 1..=n {
            for j in 1..=m {
                let dist = Self::add(
                    Self::mul(n, Self::add(cal(j - 1), cal(m - j))),
                    Self::mul(m, Self::add(cal(i - 1), cal(n - i)))
                );
                ans = Self::add(ans, Self::mul(val, dist));
            }
        }

        Self::divide(ans, 2)
    }
}

```
['Math', 'Combinatorics', 'Rust']