Day 50

#paths-in-matrix-whose-sum-is-divisible-by-k:-
class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        MOD = 10**9 + 7
        m, n = len(grid), len(grid[0])
        dp = [[0] * k for _ in range(n)]
        dp[0][grid[0][0] % k] = 1
        
        for j in range(1, n):
            v = grid[0][j] % k
            for r in range(k):
                dp[j][(r + v) % k] = (dp[j][(r + v) % k] + dp[j-1][r]) % MOD
        
        for i in range(1, m):
            new_dp = [[0] * k for _ in range(n)]
            v = grid[i][0] % k
            for r in range(k):
                new_dp[0][(r + v) % k] = (new_dp[0][(r + v) % k] + dp[0][r]) % MOD
            
            for j in range(1, n):
                v = grid[i][j] % k
                for r in range(k):
                    if dp[j][r]:
                        new_dp[j][(r + v) % k] = (new_dp[j][(r + v) % k] + dp[j][r]) % MOD
                    if new_dp[j-1][r]:
                        new_dp[j][(r + v) % k] = (new_dp[j][(r + v) % k] + new_dp[j-1][r]) % MOD
            dp = new_dp
        
        return dp[n-1][0] % MOD