<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

225. Little Knights
time limit per test: 1 sec.
memory limit per test: 65536 KB
input: standard
output: standard




Oh no, here it comes again
Can't remember when we came so close to love before
Hold on, good things never last
Nothing's in the past, it always seems to come again
Again and again and again

...

Bloodied angels fast descending
Moving on a never-bending light
Phantom figures free forever
Out of shadows, shining ever-bright

Neon Knights!

Black Sabbath, "Neon Knights"


The knight is the piece in the game of chess. The knight moves the following way: first he moves 2 squares in horizontal or vertical direction and then 1 square in the perpendicular direction. Figures on the way of knight do not interfere with its movement. Two knights are in the attacking position if they can move to each other's cells.

Input

The input file contains two integers n (1 ≤ n ≤ 10) and k (0 ≤ k ≤ n2).

Output

Print a line containing the total number of ways one can put k knights on a chessboard of size n × n so that no two of them are in the attacking positions.

Sample test(s)

Input
Test #1

3 2

Test #2

4 4

Output
Test #1

28

Test #2

412
Author:	Andrew Stankevich
Resource:	Little Chess Pieces Series, SPb IFMO 2003-2004 Authumn Training Sessions
Date:	2003-10-11

<|response|>
1. Abridged problem statement  
Given an n×n chessboard (1≤n≤10) and an integer k (0≤k≤n²), count the number of ways to place exactly k knights so that no two knights attack each other. A knight’s attack moves are the usual chess knight moves.

2. Key observations  
- A knight placed at (r,c) can only attack cells in the previous two rows (r−1 or r−2).  
- When we scan the board in row-major order (cell by cell from top-left to bottom-right), at each step we only need to remember which of the last two rows—and the part of the current row to the left—are occupied by knights.  
- We can encode that “window” of cells as a bitmask of width W=2n+1.  Each new cell corresponds to the least significant bit (LSB); at each step we shift the mask left by 1 and drop bits that fall out of the 2n+1 window.  
- Let dp[pos_parity][mask][used] = number of ways after processing pos cells (pos_parity = pos&1), with the current sliding mask = mask, and having placed exactly used knights so far.  
- Transition for the next cell:  
  • shift = (mask<<1)&((1<<W)−1)  
  • Option A: do not place a knight → dp[nxt][shift][used] += dp[now][mask][used]  
  • Option B: if used<k and none of the bits in mask corresponding to attacking offsets is set → place a knight → dp[nxt][shift|1][used+1] += dp[now][mask][used]  
- The bit positions for the four “attacking” moves are precomputed by a helper get_bit_position(r,c,dr,dc).  
- This DP runs in O(n²·2^W·k).  For n up to 7, W≤15 so 2^W≤32768 and it is fast enough.  For n=8,9,10 we precompute the answers offline and hard-code them.

3. Full solution approach  
a. Read n,k.  
b. If n≥8, output from a precomputed array pre[n][k] in O(1).  
c. Otherwise:  
   1. Let W=2n+1, M=1<<W.  
   2. Initialize a 2×M×(k+1) DP array dp, set dp[0][0][0]=1.  
   3. For pos from 0 to n*n−1:  
      - now=pos&1, nxt=now^1, r=pos/n, c=pos%n.  
      - zero out dp[nxt] layer.  
      - For each mask in [0..M−1], each used in [0..k] with ways=dp[now][mask][used]>0:  
         * shifted=(mask<<1)&(M−1)  
         * dp[nxt][shifted][used] += ways  
         * If used<k and for all four knight moves (dr,dc) bit at get_bit_position(r,c,dr,dc) is 0 in mask:  
             dp[nxt][shifted|1][used+1] += ways  
   4. At the end pos=n*n, sum dp[(n*n)&1][mask][k] over all mask to get the answer.  

4. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, k;

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

vector<int64_t> precomputed_for_8 = {
    1ll,           64ll,          1848ll,       32084ll,       376560ll,
    3184708ll,     20202298ll,    98796304ll,   379978716ll,   1167053680ll,
    2897726604ll,  5876860140ll,  9825415557ll, 13660238780ll, 15932672964ll,
    15737653004ll, 13304668385ll, 9742722088ll, 6260518246ll,  3574590840ll,
    1830733371ll,  844203844ll,   349524138ll,  128874944ll,   41833846ll,
    11792736ll,    2840224ll,     572432ll,     93840ll,       12004ll,
    1122ll,        68ll,          2ll,          0ll,           0ll,
    0ll,           0ll,           0ll,          0ll,           0ll,
    0ll,           0ll,           0ll,          0ll,           0ll,
    0ll,           0ll,           0ll,          0ll,           0ll,
    0ll,           0ll,           0ll,          0ll,           0ll,
    0ll,           0ll,           0ll,          0ll,           0ll,
    0ll,           0ll,           0ll,          0ll,           0ll
};

vector<int64_t> precomputed_for_9 = {
    1ll,
    81ll,
    3016ll,
    68796ll,
    1080942ll,
    12472084ll,
    110018552ll,
    762775440ll,
    4241252429ll,
    19206532478ll,
    71707869632ll,
    222946143752ll,
    582155146204ll,
    1286247689414ll,
    2421159140764ll,
    3908273840366ll,
    5446391581062ll,
    6599640204257ll,
    7010436668992ll,
    6589213734278ll,
    5537849837497ll,
    4207779106033ll,
    2920161348852ll,
    1865346129716ll,
    1101125592067ll,
    600730512987ll,
    302041066250ll,
    139345014744ll,
    58692638521ll,
    22451454400ll,
    7755194754ll,
    2403337080ll,
    663103709ll,
    161373907ll,
    34237130ll,
    6238414ll,
    957145ll,
    120334ll,
    11914ll,
    872ll,
    42ll,
    1ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll
};

vector<int64_t> precomputed_for_10 = {
    1ll,
    100ll,
    4662ll,
    135040ll,
    2732909ll,
    41199404ll,
    481719518ll,
    4491423916ll,
    34075586550ll,
    213628255072ll,
    1120204619108ll,
    4961681221524ll,
    18715619717199ll,
    60541371615660ll,
    168976761361446ll,
    409191804533576ll,
    864172675710439ll,
    1599730843649564ll,
    2609262108838924ll,
    3770687313420780ll,
    4857550050070531ll,
    5616928666465104ll,
    5874943705896600ll,
    5604501518609804ll,
    4917655076255841ll,
    3999855946779732ll,
    3034690618677388ll,
    2156485957257040ll,
    1437827591264317ll,
    899278231344296ll,
    526753407546620ll,
    288274613750624ll,
    146990556682887ll,
    69626509814580ll,
    30542906352994ll,
    12366448408056ll,
    4604442057431ll,
    1569983914256ll,
    487876545370ll,
    137395261280ll,
    34831261750ll,
    7884855000ll,
    1578162590ll,
    275861904ll,
    41455966ll,
    5246412ll,
    543534ll,
    44244ll,
    2652ll,
    104ll,
    2ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll,
    0ll
};

void read() { cin >> n >> k; }

int get_bit_position(int r, int c, int dr, int dc) {
    int target_r = r + dr;
    int target_c = c + dc;

    if(target_r < 0 || target_c < 0 || target_c >= n) {
        return -1;
    }

    return n * (-dr) + c - target_c - 1;
}

void solve() {
    // The solution here is the classical bit mask profile, by keeping the last
    // two rows. We always need to keep 2n+1 cells before, so this yields
    // 2^(2n+1) masks naively. However we need to multiply this by n^4, as we
    // have n^2 cells, and k <= n^2. This is slow for n >= 8, so we precompute
    // all answers for n = 8,9,10.

    if(n == 8) {
        cout << precomputed_for_8[k] << endl;
        return;
    }

    if(n == 9) {
        cout << precomputed_for_9[k] << endl;
        return;
    }

    if(n == 10) {
        cout << precomputed_for_10[k] << endl;
        return;
    }

    vector<vector<vector<int64_t>>> dp(
        2, vector<vector<int64_t>>(1 << (2 * n + 1), vector<int64_t>(k + 1, 0))
    );
    dp[0][0][0] = 1;

    for(int pos = 0; pos < n * n; pos++) {
        int cp = pos & 1;
        int r = pos / n;
        int c = pos % n;

        for(int mask = 0; mask < (1 << (2 * n + 1)); mask++) {
            for(int knights = 0; knights <= k; knights++) {
                dp[cp ^ 1][mask][knights] = 0;
            }
        }

        for(int mask = 0; mask < (1 << (2 * n + 1)); mask++) {
            for(int knights = 0; knights <= k; knights++) {
                if(dp[cp][mask][knights] == 0) {
                    continue;
                }

                int new_mask = (mask << 1) & ((1 << (2 * n + 1)) - 1);
                dp[cp ^ 1][new_mask][knights] += dp[cp][mask][knights];

                if(knights < k) {
                    bool can_place = true;

                    for(auto move: knight_moves) {
                        int bit_pos =
                            get_bit_position(r, c, move.first, move.second);
                        if(bit_pos != -1 && (mask & (1 << bit_pos))) {
                            can_place = false;
                            break;
                        }
                    }

                    if(can_place) {
                        dp[cp ^ 1][new_mask | 1][knights + 1] +=
                            dp[cp][mask][knights];
                    }
                }
            }
        }
    }

    int64_t result = 0;
    for(int mask = 0; mask < (1 << (2 * n + 1)); mask++) {
        result += dp[(n * n) & 1][mask][k];
    }

    cout << result << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // precompute();
    // return 0;

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

// void precompute() {
//     precomputed.resize(11);
//     for(int board_n = 8; board_n <= 10; board_n++) {
//         cout << "Computing n=" << board_n << "..." << endl;
//         precomputed[board_n].resize(board_n * board_n + 1, 0);

//         vector<vector<vector<int64_t>>> dp(
//             board_n * board_n + 1, vector<vector<int64_t>>(
//                                        1 << (2 * board_n + 1),
//                                        vector<int64_t>(board_n * board_n + 1,
//                                        0)
//                                    )
//         );
//         dp[0][0][0] = 1;

//         for(int pos = 0; pos < board_n * board_n; pos++) {
//             int r = pos / board_n;
//             int c = pos % board_n;

//             for(int mask = 0; mask < (1 << (2 * board_n + 1)); mask++) {
//                 for(int knights = 0; knights <= board_n * board_n; knights++)
//                 {
//                     if(dp[pos][mask][knights] == 0) {
//                         continue;
//                     }

//                     int new_mask = (mask << 1) & ((1 << (2 * board_n + 1)) -
//                     1); dp[pos + 1][new_mask][knights] +=
//                     dp[pos][mask][knights];

//                     if(knights < board_n * board_n) {
//                         bool can_place = true;

//                         for(auto move: knight_moves) {
//                             int target_r = r + move.first;
//                             int target_c = c + move.second;

//                             if(target_r >= 0 && target_c >= 0 &&
//                                target_c < board_n) {
//                                 int bit_pos =
//                                     board_n * (-move.first) + c - target_c -
//                                     1;
//                                 if(bit_pos >= 0 &&
//                                    bit_pos < (2 * board_n + 1) &&
//                                    (mask & (1 << bit_pos))) {
//                                     can_place = false;
//                                     break;
//                                 }
//                             }
//                         }

//                         if(can_place) {
//                             dp[pos + 1][new_mask | 1][knights + 1] +=
//                                 dp[pos][mask][knights];
//                         }
//                     }
//                 }
//             }
//         }

//         for(int knights = 0; knights <= board_n * board_n; knights++) {
//             for(int mask = 0; mask < (1 << (2 * board_n + 1)); mask++) {
//                 precomputed[board_n][knights] +=
//                     dp[board_n * board_n][mask][knights];
//             }
//         }
//     }

//     for(int board_n = 8; board_n <= 10; board_n++) {
//         cout << "vector<int64_t> precomputed_for_" << board_n << " =  {";
//         for(int knights = 0; knights <= board_n * board_n; knights++) {
//             if(knights > 0) {
//                 cout << ", ";
//             }
//             cout << precomputed[board_n][knights] << "ll";
//         }
//         cout << "};" << endl;
//     }
//     cout << "};" << endl;
// }
```

5. Python implementation with detailed comments  
```python
import sys
sys.setrecursionlimit(10**7)

# Four knight-move offsets that reach previous rows in a row-major scan
knight_moves = [(-2,-1),(-2,1),(-1,-2),(-1,2)]

# Precomputed answers for n=8,9,10
pre8 = [1,64,1848,32084,376560,3184708,20202298,98796304,
    379978716,1167053680,2897726604,5876860140,9825415557,
    13660238780,15932672964,15737653004,13304668385,9742722088,
    6260518246,3574590840,1830733371,844203844,349524138,
    128874944,41833846,11792736,2840224,572432,93840,12004,
    1122,68,2]
pre9 = [1,81,3016,68796,1080942,12472084,110018552,
    762775440,4241252429,19206532478,71707869632,
    222946143752,582155146204,1286247689414,2421159140764,
    3908273840366,5446391581062,6599640204257,7010436668992,
    6589213734278,5537849837497,4207779106033,2920161348852,
    1865346129716,1101125592067,600730512987,302041066250,
    139345014744,58692638521,22451454400,7755194754,
    2403337080,663103709,161373907,34237130,6238414,957145,
    120334,11914,872,42,1]
pre10 = [1,100,4662,135040,2732909,41199404,481719518,
    4491423916,34075586550,213628255072,1120204619108,
    4961681221524,18715619717199,60541371615660,168976761361446,
    409191804533576,864172675710439,1599730843649564,
    2609262108838924,3770687313420780,4857550050070531,
    5616928666465104,5874943705896600,5604501518609804,
    4917655076255841,3999855946779732,3034690618677388,
    2156485957257040,1437827591264317,899278231344296,
    526753407546620,288274613750624,146990556682887,
    69626509814580,30542906352994,12366448408056,4604442057431,
    1569983914256,487876545370,137395261280,34831261750,
    7884855000,1578162590,275861904,41455966,5246412,
    543534,44244,2652,104,2]

def get_bit_position(n, r, c, dr, dc):
    """Map a knight at (r+dr,c+dc) into a bit index in the sliding mask,
       or return -1 if outside the window of 2n+1 bits."""
    rr, cc = r+dr, c+dc
    if rr<0 or cc<0 or cc>=n:
        return -1
    return n*(-dr) + (c - cc) - 1

def main():
    data = sys.stdin.read().split()
    n, k = map(int, data)
    # for n>=8 use precomputed
    if n==8:
        print(pre8[k]); return
    if n==9:
        print(pre9[k]); return
    if n==10:
        print(pre10[k]); return

    W = 2*n+1
    M = 1<<W
    # dp[2][M][k+1]
    dp = [
        [ [0]*(k+1) for _ in range(M) ],
        [ [0]*(k+1) for _ in range(M) ]
    ]
    dp[0][0][0] = 1

    # scan each cell
    for pos in range(n*n):
        now = pos & 1
        nxt = now ^ 1
        r, c = divmod(pos, n)
        # clear next layer
        for m in range(M):
            for t in range(k+1):
                dp[nxt][m][t] = 0
        # transitions
        for mask in range(M):
            for used in range(k+1):
                ways = dp[now][mask][used]
                if ways==0:
                    continue
                # skip
                shifted = (mask<<1) & (M-1)
                dp[nxt][shifted][used] += ways
                # place knight?
                if used<k:
                    ok = True
                    for dr,dc in knight_moves:
                        bp = get_bit_position(n, r, c, dr, dc)
                        if bp>=0 and (mask & (1<<bp)):
                            ok = False
                            break
                    if ok:
                        dp[nxt][shifted|1][used+1] += ways

    # sum up
    final = (n*n)&1
    ans = sum(dp[final][m][k] for m in range(M))
    print(ans)

if __name__=='__main__':
    main()
```