Manhattan Distances of All Arrangements of Pieces

Description

You are given three integers m, n, and k.

Consider all valid arrangements of k identical pieces on an m x n grid (at most one piece per cell). Return the sum of Manhattan distances between every pair of pieces, summed over all valid arrangements.

Since the answer may be very large, return it modulo 109 + 7.

The Manhattan distance between (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.

Code

class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int: