class Solution {
public:
    const int dx[4] = {0, 1, 0, -1};
    const int dy[4] = {-1, 0, 1, 0};
    void dfs(vector<vector<vector<int>>>& grid, int i, int j, int N, int past) {
        if (N == 0) {
            return;
        }
        cout << i << ' ' << j << endl;

        grid[i][j][N] += past;
        for (int l = 0; l < 4; l++) {
            int new_i = i + dx[l];
            int new_j = j + dy[l];

            if (new_i >= 0 && new_i < grid.size() && new_j >= 0 && new_j < grid[0].size()) {
                dfs(grid, new_i, new_j, N - 1, grid[i][j][N]);
            }
        }

    }

    int findPaths(int m, int n, int N, int i, int j) {
        vector<vector<vector<int>>> grid;
        grid.resize(m, vector<vector<int>>(n, vector<int>(N + 1)));

        grid[i][j][N] = 1;

        dfs(grid, i, j, N, 0);
        int ans = 0;
        const int dev = 1e9 + 7;
        for (int k = 0; k < m; k++) {
            for (int l = 0; l < n; l++) {
                int sum = 0;
                for (int y = 1; y <= N; y++) {
                    sum += grid[k][l][y];
                }
                cout << sum << ' ';
                for (int h = 0; h < 4; h++) {
                    int new_k = k + dx[h];
                    int new_l = l + dy[h];

                    if (new_k < 0 || new_k >= m || new_l < 0 || new_l >= n){
                        ans += sum;
                        ans %= dev;
                    }
                }
            }
            cout << endl;
        }
        return ans;
    }
};