# 2435. Paths in Matrix Whose Sum Is Divisible by K
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k/description/
## 思路

## Code

class Solution {
public int numberOfPaths(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
long[][][] dp = new long[m][n][k];
int mod = 1000000007;
dp[0][0][grid[0][0]%k]=1;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i==0 && j==0) continue;
for(int a=0; a<k; a++){
if(i!=0 && dp[i-1][j][a]!=0) dp[i][j][(a+grid[i][j]%k)%k] = (dp[i][j][(a+grid[i][j]%k)%k]+dp[i-1][j][a])%mod;
if(j!=0 && dp[i][j-1][a]!=0) dp[i][j][(a+grid[i][j]%k)%k] = (dp[i][j][(a+grid[i][j]%k)%k]+dp[i][j-1][a])%mod;
}
}
}
return (int)dp[m-1][n-1][0];
}
}