1
class Solution:
2
    def helper(self, m, n, maxMove, startRow, startColumn, mat, dp) -> int:
3
        if startRow < 0 or startRow >= m or startColumn < 0 or startColumn >= n:
4
            return 1
5

6
        if dp[maxMove][startRow][startColumn] != -1:
7
            return dp[maxMove][startRow][startColumn]
8

9
        if mat[startRow][startColumn] == 1:
10
            return 0
11

12
        if maxMove <= 0:
13
            return 0
14

15
        # mat[startRow][startColumn] = 1
16
        a = self.helper(m, n, maxMove - 1, startRow + 1, startColumn, mat, dp)
17
        b = self.helper(m, n, maxMove - 1, startRow - 1, startColumn, mat, dp)
18
        c = self.helper(m, n, maxMove - 1, startRow, startColumn + 1, mat, dp)
19
        d = self.helper(m, n, maxMove - 1, startRow, startColumn - 1, mat, dp)
20
        dp[maxMove][startRow][startColumn] = a + b + c + d
21
        return dp[maxMove][startRow][startColumn]
22

23
    def findPaths(
24
        self, m: int, n: int, maxMove: int, startRow: int, startColumn: int
25
    ) -> int:
26
        mat = [[0 for i in range(n)] for j in range(m)]
27
        dp = [
28
            [[-1 for i in range(n + 1)] for j in range(m + 1)]
29
            for k in range(maxMove + 1)
30
        ]
31
        return self.helper(m, n, maxMove, startRow, startColumn, mat, dp) % (10**9 + 7)