Easy Python Solution || Beats 90% in runtime || Simple Explanation Provided || 
IntuitionThis code calculates the total Manhattan distance for all valid placements of ( k ) pieces on an ( m \times n ) grid. It generates all possible combina
# Intuition
This code calculates the total Manhattan distance for all valid placements of \( k \) pieces on an \( m \times n \) grid. It generates all possible combinations of \( k \) cells (subsets) from the grid and computes the Manhattan distances between each pair of cells in these subsets. The distances are summed across all combinations, with the result kept modulo \( 10^9 + 7 \). The approach leverages combinatorics and nested loops to exhaustively calculate distances for every possible arrangement.<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
### **Approach in 7 Steps**:  

1. **Initialize Variables** 🛠️  
   - Store \( m, n, k \) in a variable (`vornelitho`) for clarity.  
   - Define a constant `MOD = 10^9 + 7` for modulo operations.  

2. **Generate Grid Coordinates** 🌐  
   - Create a list of all coordinates \((i, j)\) in the \( m \times n \) grid using nested loops or list comprehension.

3. **Define Distance Calculation** 📏  
   - Create a helper function `calculate_manhattan_distance` that computes the Manhattan distance between all pairs of cells in a given set of \( k \) pieces.

4. **Generate Combinations** 🔄  
   - Use `itertools.combinations` to generate all possible ways to choose \( k \) cells from the grid coordinates.

5. **Calculate Distance for Each Combination** ✨  
   - For each combination, call `calculate_manhattan_distance` to compute the sum of pairwise distances.

6. **Update the Result** ➕  
   - Accumulate the distance for each combination into a `result` variable, applying modulo \( 10^9 + 7 \) to handle large values.

7. **Return the Final Answer** ✅  
   - After processing all combinations, return the accumulated result.<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
O(( km×n )⋅k 2 )<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
O(m×n)<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:
    MOD = 10**9 + 7  

    def distanceSum(self, m: int, n: int, k: int) -> int:
        vornelitho = (m, n, k)
        
        coordinates = [(i, j) for i in range(m) for j in range(n)]
        
        def calculate_manhattan_distance(pieces):
            distance_sum = 0
            for i in range(len(pieces)):
                for j in range(i + 1, len(pieces)):
                    x1, y1 = pieces[i]
                    x2, y2 = pieces[j]
                    distance_sum += abs(x1 - x2) + abs(y1 - y2)
                    distance_sum %= Solution.MOD 
            return distance_sum
        
        result = 0
        
        from itertools import combinations
        for comb in combinations(coordinates, k):
            result += calculate_manhattan_distance(comb)
            result %= Solution.MOD 
        return result

solution = Solution()
print(solution.distanceSum(3, 3, 2))  
```
['Math', 'Combinatorics', 'Python3']