Paths in Matrix Whose Sum Is Divisible by K

Count the number of down/right paths from the top-left to bottom-right of a grid whose path-sum is divisible by k, returning the result modulo 1e9+7. This requires dynamic programming that tracks, at each cell, counts of paths for each sum remainder mod k (k ≤ 50), yielding an O(m·n·k) solution.