I LOVE MATH ❤️❤️❤️
IntuitionTrying to iterate over all (kmn​) subsets and then finding the manhattan distance between all (2k​) pairs takes way too much time, and there isn't any
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Trying to iterate over all $mn \choose k$ subsets and then finding the manhattan distance between all $k \choose 2$ pairs takes way too much time, and there isn't any obvious optimization


So try to find a formula instead




# Approach
<!-- Describe your approach to solving the problem. -->
A valid arrangement of k pieces is the same as choosing a subset of size k out of the M = m*n cells


So let such a subset be represented as $S \subseteq \{1, 2, ..., M\}$ with $|S|=k$


And let $d(i, j)$ be the manhattan distance between cells $i$ and $j$


Then for a particular subset $S$, we want $\sum\limits_{\substack{i, j \in S \\ i < j}} d(i, j)$


We want to sum this quantity over all $M \choose k$ subsets
So in the end we want $\sum\limits_{\substack{S \in \{1, 2, ..., M\} \\ |S| = k}}\sum\limits_{\substack{i, j \in S \\ i < j}} d(i, j)$


The trick here is that we can switch the order of the summations and analyze each pair of $(i, j), i < j$


Each pair appears in $M-2 \choose k-2$ subsets because once we decide to include $i$ and $j$ we have to choose $k-2$ other cells from the remaining $M-2$ cells


Thus, our sum becomes $\sum\limits_{1\leq i\leq j\leq M} d(i, j){M-2 \choose k-2}$


${M-2 \choose k-2}$ is constant so we can factor it out and have ${M-2 \choose k-2}\sum\limits_{1\leq i\leq j\leq M} d(i, j)$


This is much nicer, but we still need to figure out how to calculate $\sum\limits_{1\leq i\leq j\leq M} d(i, j)$


Let's analyze $d(i, j)$


If we have two points $(x_1, y_1)$ and $(x_2, y_2)$, the $d((x_1, y_1), (x_2, y_2)) = |x_1-x_2| + |y_1-y_2|$


So $\sum\limits_{(x_1, y_1), (x_2, y_2)} d((x_1, y_1), (x_2, y_2)) = \sum\limits_{(x_1, y_1), (x_2, y_2)} (|x_1-x_2| + |y_1-y_2|)$


Notice that the $x$ and $y$ coordinates are independent
So we can split the summation into $\sum\limits_{(x_1, y_1), (x_2, y_2)} |x_1-x_2| + \sum\limits_{(x_1, y_1), (x_2, y_2)} |y_1-y_2|$


Now let's look at the sum over $x$'s


For each particular $x \in {0, 1, ..., m-1}$, there are $n$ cells with that $x$ coordinate since $y$ can range from $0$ to $n-1$


Thus $\sum\limits_{(x_1, y_1), (x_2, y_2)} |x_1-x_2| = n^2 \sum\limits_{x_1=0}^{m-1}\sum\limits_{x_2=0}^{m-1}|x_1-x_2|$


Similarly for the sum over $y$'s, $\sum\limits_{(x_1, y_1), (x_2, y_2)} |y_1-y_2| = m^2\sum\limits_{y_1=0}^{n-1}\sum\limits_{y_2=0}^{n-1}|y_1-y_2|$


We can also show that $\sum\limits_{x_1=0}^{m-1}\sum\limits_{x_2=0}^{m-1}|x_1-x_2| = \frac{(m-1)(m)(m+1)}{3}$ and $\sum\limits_{y_1=0}^{n-1}\sum\limits_{y_2=0}^{n-1}|y_1-y_2| = \frac{(n-1)(n)(n+1)}{3}$


I'll leave this proof to the reader as an exercise


Therefore, $\sum\limits_{(x_1, y_1), (x_2, y_2)} d((x_1, y_1), (x_2, y_2)) = n^2 \cdot \frac{(m-1)(m)(m+1)}{3} + m^2 \cdot \frac{(n-1)(n)(n+1)}{3}$


But remember in the original problem that we actually want the sum over all unordered pairs $(i, j)$ with $i < j$


$d(i, i) = 0$ and $d(i, j) = d(j, i)$ which are each counted once, so we can simply take half of the expression:


$\sum\limits_{i<j}d(i, j) = \frac{1}{2}[n^2 \cdot \frac{(m-1)(m)(m+1)}{3} + m^2 \cdot \frac{(n-1)(n)(n+1)}{3}] = \frac{n^2m(m^2-1)+m^2n(n^2-1)}{6}$


**THEREFORE, IN THE END, WE HAVE OUR FINAL ANSWER AS:**


${M-2 \choose k-2} \times \frac{n^2m(m^2-1)+m^2n(n^2-1)}{6}$


under MOD $10^9+7$, which we can find with standard combinatorial techniques




# Code
```
class Solution {
    static int MOD = 1000000007;
    static int MAX = 100000;
    
    static long[] fact = new long[MAX + 1];
    static long[] invFact = new long[MAX + 1];
    
    static {
        fact[0] = 1L;
        for (int i = 1; i <= MAX; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        invFact[MAX] = modInverse(fact[MAX], MOD);
        for (int i = MAX - 1; i >= 0; i--) {
            invFact[i] = invFact[i + 1] * (i + 1) % MOD;
        }
    }
    
    public static long modInverse(long a, int m) {
        return fastPow(a, m - 2, m);
    }
    
    public static long fastPow(long base, long exp, long mod) {
        long result = 1L;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }
    
    public static long binom(int n, int r) {
        if (r < 0 || r > n) return 0;
        return fact[n] * ((invFact[r] * invFact[n - r]) % MOD) % MOD;
    }
    
    public int distanceSum(int m, int n, int k) {
        int M = m * n;
        
        long ways = binom(M - 2, k - 2);
        
        long mm = (long) m % MOD;
        long nn = (long) n % MOD;
        
        long n2 = (nn * nn) % MOD;
        long m2 = (mm * mm) % MOD;
        
        long term1 = (n2 * mm) % MOD;
        long m2Minus1 = (m2 - 1 + MOD) % MOD;
        term1 = (term1 * m2Minus1) % MOD;
        
        long term2 = (m2 * nn) % MOD;
        long n2Minus1 = (n2 - 1 + MOD) % MOD;
        term2 = (term2 * n2Minus1) % MOD;
        
        long sumD = (term1 + term2) % MOD;
        
        long inv6 = modInverse(6, MOD);
        sumD = (sumD * inv6) % MOD;
        
        long ans = (sumD * ways) % MOD;
        
        return (int) ans;
    }
}
```

['Java']