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
  if (i < 0 || j < 0 || i == n || j == m)
10
    return 1;
11
  else if (k == 0)
12
    return 0;
13

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

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

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

25
int findPaths(int m, int n, int maxMove, int startRow, int startCol) {
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
}