Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Paths with different exact sums can be grouped when their sums have the same remainder modulo k. Moving into a cell shifts that remainder by the cell value. Since moves come only from above or left, a row-major DP can combine predecessor counts.

Approach

Let dp[row][column][r] count paths ending there with remainder r. Initialize one path at the starting cell's own remainder. For every other cell and target remainder, look up predecessor remainder (r - cellValue) mod k, normalized nonnegative, and sum the available counts from above and left modulo 10^9 + 7. Boundary cells have only one predecessor. Return the destination's remainder-zero count, which includes both endpoint values in each path sum.

class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        MOD = 10**9 + 7
        n = len(grid)
        m = len(grid[0])
        dp = [[[0] * k for _ in range(m)] for _ in range(n)] # dp[i][j][r]
        dp[0][0][grid[0][0] % k] = 1

        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0:
                    continue
                for r in range(k):
                    prev = (r - grid[i][j]) % k
                    if i == 0:
                        dp[i][j][r] += dp[i][j - 1][prev]
                    elif j == 0:
                        dp[i][j][r] += dp[i - 1][j][prev]
                    else:
                        dp[i][j][r] += (dp[i - 1][j][prev] + dp[i][j - 1][prev]) % MOD

        return dp[-1][-1][0]

Complexity analysis

Let r and c be the grid dimensions. Time: O(r * c * k). Auxiliary space: O(r * c * k) for the remainder-count DP table.