# 576. Out of Boundary Paths

#### Medium

***

There is an `m x n` grid with a ball. The ball is initially at the position `[startRow, startColumn]`. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply **at most** `maxMove` moves to the ball.

Given the five integers `m`, `n`, `maxMove`, `startRow`, `startColumn`, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it **modulo** `109 + 7`.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/04/28/out_of_boundary_paths_1.png)

```
Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output: 6
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/04/28/out_of_boundary_paths_2.png)

```
Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output: 12
```

 

**Constraints:**

* `1 <= m, n <= 50`
* `0 <= maxMove <= 50`
* `0 <= startRow < m`
* `0 <= startColumn < n`

```python
class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        return self.dfs(m,n, startRow, startColumn, maxMove) % (10**9 + 7)
    
    @lru_cache(None)
    def dfs(self, m, n , row, col, movesLeft):
        if ((row < 0 or row >= m) or (col < 0 or col >= n)) and movesLeft >= 0:
            return 1
        if movesLeft < 0:
            return 0
        return self.dfs(m,n,row-1,col, movesLeft-1) +  self.dfs(m,n,row,col+1, movesLeft-1) + self.dfs(m,n,row+1,col, movesLeft-1) + self.dfs(m,n,row,col-1, movesLeft-1)
```