3426. Manhattan Distances of All Arrangements of Pieces

You are given three integers m, n, and k. There is a rectangular grid of size m × n containing k identical pieces. Return the sum of Manhattan distances between every pair of pieces over all valid arrangements of pieces. A valid arrangement is a placement of all k pieces on the grid with at most one piece per cell. Since the answer may be very large, return it modulo 109 + 7. The Manhattan Dis