/*
QUESTION 8: Knight Rider Paths to Corners

Problem Statement:
You are given integer N.
The board size is 2N x 2N.

A rider starts at the top-left cell.

In one move, the rider moves like a chess knight.

You are also given K.
Count the number of distinct paths that reach any corner of the board using at most K moves.

Hard Constraints:
1 <= N <= 10
1 <= K <= 10

Example:
N = 3
K = 2

Expected Output:
1

Explanation:
The starting cell is already a corner, so the 0-move path is counted.
No other corner is reached within 2 moves in this example.

Brute Force:
Recursively try all knight moves up to K moves.
Count paths that end at a corner.

Time Complexity:
O(8^K)

Optimized Approach:
Use DP by number of moves.

dp[x][y] =
number of ways to stand at cell (x, y) after current moves.

For every step, move from each cell to all valid knight positions.
Whenever a corner is reached, add those paths to the answer.

Time Complexity:
O(K * N^2)

Space Complexity:
O(N^2)
*/

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long countPaths(int N, int K) {
        int L = 2 * N;

        vector<pair<int, int>> moves = {
            {2, 1}, {2, -1}, {-2, 1}, {-2, -1},
            {1, 2}, {1, -2}, {-1, 2}, {-1, -2}
        };

        vector<vector<long long>> dp(L, vector<long long>(L, 0));
        dp[0][0] = 1;

        long long ans = 1;

        auto isTargetCorner = [&](int x, int y) {
            if (x == 0 && y == 0) return false;

            return (x == 0 && y == L - 1) ||
                   (x == L - 1 && y == 0) ||
                   (x == L - 1 && y == L - 1);
        };

        for (int step = 1; step <= K; step++) {
            vector<vector<long long>> next(L, vector<long long>(L, 0));

            for (int x = 0; x < L; x++) {
                for (int y = 0; y < L; y++) {
                    if (dp[x][y] == 0) continue;

                    for (auto [dx, dy] : moves) {
                        int nx = x + dx;
                        int ny = y + dy;

                        if (nx >= 0 && nx < L && ny >= 0 && ny < L) {
                            next[nx][ny] += dp[x][y];
                        }
                    }
                }
            }

            for (int x = 0; x < L; x++) {
                for (int y = 0; y < L; y++) {
                    if (isTargetCorner(x, y)) {
                        ans += next[x][y];
                    }
                }
            }

            dp = next;
        }

        return ans;
    }
};

int main() {
    Solution sol;

    int N = 3;
    int K = 2;

    cout << sol.countPaths(N, K) << endl;

    return 0;
}