<p>You are given a <strong>0-indexed</strong> <code>m x n</code> integer matrix <code>grid</code> and an integer <code>k</code>. You are currently at position <code>(0, 0)</code> and you want to reach position <code>(m - 1, n - 1)</code> moving only <strong>down</strong> or <strong>right</strong>.</p>

<p>Return<em> the number of paths where the sum of the elements on the path is divisible by </em><code>k</code>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img src="https://assets.leetcode.com/uploads/2022/08/13/image-20220813183124-1.png" style="width: 437px; height: 200px;" />
<pre>
<strong>Input:</strong> grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are two paths where the sum of the elements on the path is divisible by k.
The first path highlighted in red has a sum of 5 + 2 + 4 + 5 + 2 = 18 which is divisible by 3.
The second path highlighted in blue has a sum of 5 + 3 + 0 + 5 + 2 = 15 which is divisible by 3.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img src="https://assets.leetcode.com/uploads/2022/08/17/image-20220817112930-3.png" style="height: 85px; width: 132px;" />
<pre>
<strong>Input:</strong> grid = [[0,0]], k = 5
<strong>Output:</strong> 1
<strong>Explanation:</strong> The path highlighted in red has a sum of 0 + 0 = 0 which is divisible by 5.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img src="https://assets.leetcode.com/uploads/2022/08/12/image-20220812224605-3.png" style="width: 257px; height: 200px;" />
<pre>
<strong>Input:</strong> grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
<strong>Output:</strong> 10
<strong>Explanation:</strong> Every integer is divisible by 1 so the sum of the elements on every possible path is divisible by k.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= m * n &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 100</code></li>
	<li><code>1 &lt;= k &lt;= 50</code></li>
</ul>

class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        rows, cols = len(grid), len(grid[0])
        dp = [[[-1] * k for _ in range(cols)] for _ in range(rows)]

        def f(m, n, r):
            if m == rows -1 and n == cols - 1:
                return 1 if grid[m][n] % k == r else 0

            if dp[m][n][r] != -1:
                return dp[m][n][r]

            need = (k + r - grid[m][n] % k) % k
            ans = 0
            if n + 1 < cols:
                ans = f(m, n + 1, need)
            if m + 1 < rows:
                ans = (ans + f(m + 1, n, need)) % (10**9 + 7)
            dp[m][n][r] = ans
            return ans

        return f(0, 0, 0)

#Time O(rows x cols x k) Space O(rows x cols x k) 
#In the worst case, each state (m, n, r) will be computed once because of memoization.
# The number of unique states in the memoization table dp is determined by the dimensions of the grid and the modulo value k.For each state (m, n, r), the function makes up to 2 recursive calls (one for moving right and one for moving down). Each recursive call computes a new state and returns an answer in constant time 

#The dp table is a 3D array of size rows * cols * k to store the results for each state (m, n, r).

    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        rows, cols = len(grid), len(grid[0])
        dp = [[[0] * k for _ in range(cols) ] for  _ in range(rows)]
        dp[rows - 1][cols - 1][ grid[rows - 1][cols - 1] % k] = 1

        for m in range(rows - 2, -1, -1 ):
            for r in range(k):
                dp[m][cols - 1][r] = dp[m + 1][cols - 1][ (k + r - grid[m][cols - 1] % k ) % k ]
        for n in range(cols - 2, -1, -1):
            for r in range(k):
                dp[rows - 1][n][r] = dp[rows - 1][n + 1][ (k + r - grid[rows - 1][n] % k ) % k ]

        for m in range(rows - 2, -1, -1):
            for n in range(cols - 2, -1, -1):
                for r in range(k):
                    dp[m][n][r] = dp[m + 1][n][ (k + r - grid[m][n] % k) % k]
                    dp[m][n][r] = (dp[m][n][r] + dp[m][n + 1][ (k + r - grid[m][n] % k) % k]) % (10**9+7)

        return dp[0][0][0]


        
#Time O(rows x cols x k) Space O(rows x cols x k)             

2343