# Leetcode: Paths in Matrix Whose Sum Is Divisible by K

## A Dynamic Programming (DP) problem

You are given a **0-indexed** `m x n`

integer matrix `grid`

and an integer `k`

. You are currently at position `(0, 0)`

and you want to reach position `(m - 1, n - 1)`

moving only **down** or **right**.

Return* the number of paths where the sum of the elements on the path is divisible by *`k`

. Since the answer may be very large, return it **modulo** `10^9 + 7`

.

**Example 1:**