1
vector<vector<vector<int>>> dp;
2

3
int dx[4] = {0,0,1,-1};
4
int dy[4] = {1,-1,0,0};
5

6
int mod = 1e9+7;
7

8
int fun(int i,int j,int n,int m,int k){
9

10
    if(i < 0 || j < 0 || i == n || j == m)return 1;
11
    else if(k == 0)return 0;
12

13
    if(dp[i][j][k] != -1)return dp[i][j][k];
14

15
    int ans = 0;
16
    for(int c = 0; c < 4; c++){
17
        int ni = i+dx[c] , nj = j+dy[c];
18
        ans = (ans + fun(ni,nj,n,m,k-1)) % mod;
19
    }
20

21
    return dp[i][j][k] = ans;
22
}
23

24
int findPaths(int m, int n, int maxMove, int startRow, int startCol) {
25

26
    dp = vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(maxMove+1, -1)));
27

28
    return fun(startRow, startCol,m,n,maxMove);
29
}