Python3: Combinations & Series Sum
IntuitionThis is the same as the other math solutions, i.e. find total distance between all pairs of points and multiply by total number of possible combination
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
This is the same as the other math solutions, i.e. find total distance between all pairs of points and multiply by total number of possible combinations. Just sharing how I derived the calculations for anyone looking for intuition.

# Approach
<!-- Describe your approach to solving the problem. -->
First, recognize that **for any given pair of points, the number of possible board combinations containing that pair of points is the exact same as the total number of possible combinations for any other pair of points.** This number is `(m*n-2) choose (k-2)`: there are m*n - 2 total possible spaces to put pieces (subtract 2 because those are the spaces specified for the chosen pair). There are k-2 remaining pieces that need to be placed. Therefore, `(m*n-2) choose (k-2)` which I will refer to as **(1)**.

If you know, for a given pair of points, how many valid board combinations it appears on, then the total distance contribution from this pair of points to the answer is simply its manhattan distance times the number of valid combinations from above (1). The solution is therefore `(1)*d1 + (1)*d2 + (1)*d3...` where d1, d2...dn represents the manhattan distance of each unique pair of points, or in other words `(1) * (total manhattan distance across all pairs of points)`.

Manhattan distance is the sum of the x-distance and y-distance in a 2-d grid. Since our goal is to simply sum all distances, we can calculate the total x-distance across all pairs and y-distance separately. By way of example, see the grid below.

```
x|1|2|3|4
---------
0|1|2|3|4
```
We start by calculating the total horizontal x-distance. What is the total distance between the first cell 0,0 and all other possible cells? The x-distance between x and each other possible cell on the board is shown above. The sum of the distances is `1+2+3+4 = (m-1)*m / 2` multiplied by n rows `=> n * (m-1) * m / 2`.

```
0|1|2|3|4
---------
x|1|2|3|4
```
For cell (0, 1), the answer is the same, so the total for both cells (0, 0) and (0, 1) is `n * (n * (m-1) * m / 2)` because there are n rows in the first column that you can mark with x.

This pattern repeats for the subsequent columns:
```
0|x|1|2|3   0|0|1|2|3
---------   ---------
0|0|1|2|3   0|x|1|2|3
```
Prior columns are 0 to prevent double counting. Now the sum across this column is `n * n * (m-2) * (m-1) / 2` (note how the series sum formula has decreased by one). This continues for all subsequent columns giving a total sum: `(n * n / 2) * ((m-1) * m + (m-2) * (m-1) + ... + 1 * 2)`

The term on the left is just the factored out shared term. The term on the right is the series sum: $$\sum_{k=1}^{m-1} k * (k + 1)$$ Expanding and using the series identity of first and second order polynomials (just google it) gives you `(m-1) * m * (m+1) / 3`

Putting it together gives a total x-distance across all pairs of `n * n * (m-1) * m * (m+1) / 6`

The y-distance is symmetrical to the x-distance; just swap the m and n terms, i.e. `m * m * (n-1) * n * (n+1) / 6`

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(N) due to factorial calculation in math.comb

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
Linear with respect to factorial term. Can be made O(1) with custom implementation of modular combination calculation.

# Code
```python3 []
class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int:
        md = int(1e9 + 7)
        fac = math.comb(m*n-2, k-2) % md
        a = (n) * (n) * (m-1) * m * (m+1) // (6)
        b = (m) * (m) * (n-1) * n * (n+1) // (6)
        a %= md
        b %= md
        return ((a + b) * fac) % md
```
['Python3']