1
class Solution {
2
  int[][][] dp;
3
  int mod = 1000000007;
4

5
  public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
6
    dp = new int[m][n][maxMove + 1];
7
    for (int i = 0; i < m; i++)
8
      for (int j = 0; j < n; j++) for (int k = 0; k <= maxMove; k++) dp[i][j][k] = -1;
9
    return count(m, n, maxMove, startRow, startColumn) % mod;
10
  }
11

12
  public int count(int m, int n, int move, int r, int c) {
13
    if (r < 0 || c < 0 || r >= m || c >= n) return 1;
14
    if (move <= 0) return 0;
15
    if (dp[r][c][move] != -1) return dp[r][c][move] % mod;
16
    dp[r][c][move] =
17
        ((count(m, n, move - 1, r + 1, c) % mod + count(m, n, move - 1, r - 1, c) % mod) % mod
18
                + (count(m, n, move - 1, r, c + 1) % mod + count(m, n, move - 1, r, c - 1) % mod)
19
                    % mod)
20
            % mod;
21
    return dp[r][c][move] % mod;
22
  }
23
}