private int countWaysV2(int[][] M, int[] s, int[] e, int k) {
        int row = M.length;
        int col = M[0].length;

        int[][][] dp = new int[k + 1][row][col];
        dp[0][s[0]][s[1]] = 1;

        for(int i = 1; i <= k; i++) {

            int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};
            int[] dy = {2, -2, 2, -2, 1, -1, 1, -1};

            for(int j = 0; j < row; j++) {
                for(int l = 0; l < col; l++) {
                    for(int d = 0; d < 8; d++) {
                        int xx = j - dx[d];
                        int yy = l - dy[d];

                        if (isValid(M, xx, yy)) {
                            dp[i][j][l] += dp[i-1][xx][yy];
                        }
                    }
                }
            }
        }

        return dp[k][row - 1][col - 1];
    }