Easy C++ code of Manhattan Distance
IntuitionThe solution leverages combinatorics and modular arithmetic to efficiently compute the sum of distances. By precomputing factorials and their inverses,
# Intuition 
<!-- Describe your first thoughts on how to solve this problem. -->
The solution leverages combinatorics and modular arithmetic to efficiently compute the sum of distances. By precomputing factorials and their inverses, we can quickly calculate combinations. Modular exponentiation ensures handling large numbers without overflow. The problem is broken down into row and column-wise distance calculations, optimizing the overall process. This approach avoids brute force methods, which would be inefficient for larger grids, ensuring a scalable and fast solution.
# Complexity
- Time complexity: If X=(m*n), then TC: O(X+X+X)=O(X)=O(m*n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: SC: O(mn) for storing factorials and inverses.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    using ll = long long;

    ll modularExponentiation(ll base, ll exp, ll mod) {
        ll result = 1;
        base %= mod;
        while(exp > 0) {
            if (exp & 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }
    int distanceSum(int m, int n, int k) {
        const int MOD = 1e9 + 7;
        int totalCells = m * n;
        std::vector<ll> factorial(totalCells + 1, 1);
        std::vector<ll> inverseFactorial(totalCells + 1, 1);
        for(int i = 1; i <= totalCells; i++) {
            factorial[i] = (factorial[i - 1] * i) % MOD;
        }
        inverseFactorial[totalCells] = modularExponentiation(factorial[totalCells], MOD - 2, MOD);
        for(int i = totalCells - 1; i >= 0; i--) {
            inverseFactorial[i] = (inverseFactorial[i + 1] * (i + 1)) % MOD;
        }
        ll sumX = (ll)n * n % MOD;
        sumX = (sumX * m % MOD) * (m - 1) % MOD;
        sumX = (sumX * (m + 1) % MOD) * 166666668 % MOD;

        ll sumY = (ll)m * m % MOD;
        sumY = (sumY * n % MOD) * (n - 1) % MOD;
        sumY = (sumY * (n + 1) % MOD) * 166666668 % MOD;

        ll totalSum = (sumX + sumY) % MOD;

        if(k < 2 || k > totalCells) {
            return 0;
        }
        ll combinations = (factorial[totalCells - 2] * inverseFactorial[k - 2] % MOD) * inverseFactorial[totalCells - k] % MOD;
        ll result = (totalSum * combinations) % MOD;
        return (int)result;
    }
};
```
['C++']