# Out of Boundary Paths

There is an **m** by **n** grid with a ball. Given the start coordinate **(i,j)** of the ball, you can move the ball to **adjacent** cell or cross the grid boundary in four directions (up, down, left, right). However, you can **at most** move **N** times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.

**Example 1:**

```
Input: m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
Explanation:
```

![](https://1817027152-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M97UlEWvq7aSC1s7hjT%2F-MDIlbMt_XPHAqHkToMN%2F-MDItGF6a9M9t2bBec_b%2Fimage.png?alt=media\&token=04519375-501c-4c7b-a94c-8848924619a7)

**Example 2:**

```
Input: m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12
Explanation:
```

![](https://1817027152-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M97UlEWvq7aSC1s7hjT%2F-MDIlbMt_XPHAqHkToMN%2F-MDItDfLxmsAQ4ax7ZiD%2Fimage.png?alt=media\&token=db9632a5-e768-40c6-904d-2c79765d27dd)

**Note:**

1. Once you move the ball out of boundary, you cannot move it back.
2. The length and height of the grid is in range \[1,50].
3. N is in range \[0,50].

```java
class Solution {
    long mod = 1_000_000_007;
    int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
    long dp[][][];

    public int findPaths(int m, int n, int N, int x, int y) {
        dp = new long[m][n][N + 1];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                for (int k = 1; k <= N; k++)
                    dp[i][j][k] = -1L;
        // dp[i][j][k] -> Answer from pos(i,j) with k steps allowed
        return (int) helper(m, n, x, y, N);
    }

    public long helper(int m, int n, int x, int y, int N) {
        if (x < 0 || x >= m || y < 0 || y >= n) {
            if (N >= 0)
                return 1L;
            return 0L;
        }
        if (N <= 0)
            return 0L;
        if (dp[x][y][N] != -1)
            return dp[x][y][N];
        long ans = 0;
        for (int i = 0; i < 4; i++)
            ans = (ans + helper(m, n, x + dir[i][0], y + dir[i][1], N - 1)) % mod;
        dp[x][y][N] = ans;
        return ans;
    }
}
```
