543. Paths With a Divisible Sum

Walk from the top-left cell to the bottom-right cell, moving only RIGHT or DOWN. A path's score is the total of every cell it visits, including both ends. Count the paths whose score is divisible by k.

Print the count modulo 1000000007.

5 2 4 3 0 5 k = 3 -> 2 0 7 2

## Why the position is not enough

Problem 532 counts paths and needs only the cell. Here two paths reaching the same cell are NOT interchangeable: one may be extendable to a divisible total and the other not, depending on what each has collected so far.

So the state has to carry something about the score. Carrying the score itself is hopeless, since it ranges over the sum of the whole grid.

## Carry the residue

The question only ever asks whether the final total is divisible by k, and that depends on the running total only through its REMAINDER:

dp[r][c][t] = how many paths reach (r, c) with running total congruent to t mod k

The state records exactly what the objective can distinguish, and no more. Two running totals with the same remainder behave identically for the rest of the walk, so they merge.

Same principle as problem 492's residue state for subsets, applied to a grid.

## The transition

dp[r][c][ (t + g[r][c]) mod k ] += dp[r-1][c][t] + dp[r][c-1][t]

or equivalently, reading rather than pushing:

dp[r][c][t] = dp[r-1][c][(t - g[r][c]) mod k] + dp[r][c-1][(t - g[r][c]) mod k]

The subtraction has to be taken modulo k and made non-negative first, which in most languages means ((t - v) % k + k) % k. Python's % already returns a non-negative value, so a solution prototyped there and ported can fail on exactly this line.

## The answer

dp[m-1][n-1][0]. Residue 0 means divisible, and the destination cell's own value must already be included, which is why the base case is dp[0][0][g[0][0] mod k] = 1 rather than dp[0][0][0] = 1.

Forgetting that the START cell counts is the other common error. 1 as a one-cell grid with k = 1 answers 1 and with k = 2 answers 0, and that pair catches it.

## Boundaries

0 0 / 0 0 with k = 5 answers 2: every path sums to 0, which is divisible by anything, so both paths qualify.

2 2 2 / 2 2 2 / 2 2 2 with k = 2 answers 6: every path visits 5 cells summing to 10, so all six paths qualify.

## Cost

Time O(m n k). Space O(n k) with two rows.

Constraints - `1 ≤ m ≤ 100` - `1 ≤ n ≤ 100` - `1 ≤ k ≤ 100` - `0 ≤ value ≤ 100`