C++ Code

Time Complexity: O(N*m*n)

Space Complexity: O(m*n)

Beat 100% of C++ Submissions!

```
int findPaths(int m, int n, int N, int i, int j) {
vector<vector<int>> T1 = vector<vector<int>>(m, vector<int>(n, 0)), T2 = T1;
for (unsigned int k = 0; k < N; k++) {
for (unsigned int row = 0; row < m; row++) {
for (unsigned int col = 0; col < n; col++) {
T2[row][col] += row == 0 ? 1 : T1[row - 1][col] % (unsigned int)(pow(10.0, 9) + 7);
T2[row][col] += col == 0 ? 1 : T1[row][col - 1] % (unsigned int)(pow(10.0, 9) + 7);
T2[row][col] += row == m - 1 ? 1 : T1[row + 1][col] % (unsigned int)(pow(10.0, 9) + 7);
T2[row][col] += col == n - 1 ? 1 : T1[row][col + 1] % (unsigned int)(pow(10.0, 9) + 7);
}
}
T1 = T2;
T2 = vector<vector<int>>(m, vector<int>(n, 0));
}
return T1[i][j] % (unsigned int)(pow(10.0, 9) + 7);
}
```