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

numberOfPaths.js

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var numberOfPaths = function(grid, k) {
    const MOD = 1e9 + 7; // modulus for large answers
    const m = grid.length;      // number of rows
    const n = grid[0].length;   // number of columns
    
    // Initialize a 3D DP array:
    // dp[i][j][r] = number of ways to reach (i,j) with remainder r
    // Dimensions: m x n x k
    let dp = Array.from({ length: m }, () =>
        Array.from({ length: n }, () =>
            Array(k).fill(0)
        )
    );
    
    // Base case: starting point (0,0)
    // The remainder is grid[0][0] % k
    dp[0][0][grid[0][0] % k] = 1;
    
    // Fill the DP table
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            for (let r = 0; r < k; r++) {
                let count = dp[i][j][r];
                if (count === 0) continue; // skip if no paths
                
                // Move down (i+1, j)
                if (i + 1 < m) {
                    let newR = (r + grid[i+1][j]) % k;
                    dp[i+1][j][newR] = (dp[i+1][j][newR] + count) % MOD;
                }
                
                // Move right (i, j+1)
                if (j + 1 < n) {
                    let newR = (r + grid[i][j+1]) % k;
                    dp[i][j+1][newR] = (dp[i][j+1][newR] + count) % MOD;
                }
            }
        }
    }
    
    // The answer is the number of ways to reach (m-1, n-1) with remainder 0
    return dp[m-1][n-1][0];
};