Out of Boundary - Implementation

Here's the memoized solution:

function findPaths
    MOD := 10^9 + 7
    dp := 3D (three-dimensional) array [m][n][maxMove + 1], all -1
    return solve
function solve(r, c, k, m, n, MOD)
    if r < 0 or r >= m or c < 0 or c >= n then
        return 1
    if k = 0 then
        return 0
    if dp[r][c][k] ≠ -1 then
        return dp[r][c][k]
    result := 0
    result := (result + solve(r - 1, c, k - 1, m, n, MOD)) % MOD
    result := (result + solve(r + 1, c, k - 1, m, n, MOD)) % MOD
    result := (result + solve(r, c - 1, k - 1, m, n, MOD)) % MOD
    result := (result + solve(r, c + 1, k - 1, m, n, MOD)) % MOD
    dp[r][c][k] := result
    return result

Leaving the grid returns $1$. Staying with no moves returns $0$. Sum over $4$ directions, modulo $10^9 + 7$.

Time: $O(m \cdot n \cdot k)$. Space: $O(m \cdot n \cdot k)$ for the $3$D memoization table.