OUT_OF_BOUNDARY_PATHS

class Solution {
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        // you can do with 3D dp (or) by seeing contraints you can calculate for each move
        vector<vector<int>> dp1(m, vector<int>(n,0));
        int mod = 1000 * 1000 * 1000 + 7;
        int ans= 0;
        dp1[startRow][startColumn] = 1;
        for(int moves = 1; moves <= maxMove; moves++) {

            //for every new move we will be swaping and computing the answer
            //we need till k -1
            //1 move for going to the boundary

            vector<vector<int>> dp2(m, vector<int>(n,0));

            for(int i = 0; i < m ; ++i) {
                for(int j = 0; j < n; ++j) {
                    // check all directions
                    // form i, j

                    //right
                    dp2[i][j] = (dp2[i][j] + ((j + 1 < n) ? dp1[i][j + 1] : 0)) % mod;
                    //left
                    dp2[i][j] = (dp2[i][j] + ((j - 1 >= 0) ? dp1[i][j - 1] : 0)) % mod;

                    //top
                    dp2[i][j] = (dp2[i][j] + ((i - 1 >= 0) ? dp1[i - 1][j] : 0)) % mod;
                    //bottom
                    dp2[i][j] = (dp2[i][j] + ((i + 1 < m) ? dp1[i + 1][j] : 0)) % mod;

                }
            }

            for(int i = 0; i < m; ++i) {
                ans = (ans + dp1[i][0]) % mod;;
                ans = (ans + dp1[i][n - 1]) % mod;
            }

            for(int i = 0; i < n; ++i) {
                ans = (ans + dp1[0][i]) % mod;;
                ans = (ans + dp1[m - 1][i]) % mod;
            }
            swap(dp1, dp2);

        }

        return ans;

    }
};