<|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.

223. Little Kings
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard
output: standard



After solving nice problems about bishops and rooks, Petya decided that he would like to learn to play chess. He started to learn the rules and found out that the most important piece in the game is the king.

The king can move to any adjacent cell (there are up to eight such cells). Thus, two kings are in the attacking position, if they are located on the adjacent cells.

Of course, the first thing Petya wants to know is the number of ways one can position k kings on a chessboard of size n × n so that no two of them are in the attacking position. Help him!

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 the given number of kings on a chessboard of the given size so that no two of them are in attacking positions.

Sample test(s)

Input
Test #1

3 2

Test #2

4 4

Output
Test #1

16

Test #2

79
Author:	Andrew Stankevich
Resource:	Little Chess Pieces Series, SPb IFMO 2003-2004 Authumn Training Sessions

<|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 indistinguishable kings so that no two attack each other. Two kings attack if they occupy adjacent cells in any of the eight directions. The answer fits in a 64-bit integer.

2. Key observations  
- In any single row, two kings cannot sit in adjacent columns.  
  Represent a row’s placement by an n-bit mask; “no two kings adjacent” means the mask has no consecutive 1-bits.  
- Between two consecutive rows, no king may be directly above, above-left, or above-right of another.  
  If the mask of row i is m and of row i–1 is p, we require  
    (m & p) == 0,         // no vertical adjacency  
    (m << 1 & p) == 0,    // no diagonal from m’s left to p  
    (m >> 1 & p) == 0     // no diagonal from m’s right to p  
- The total kings used is the sum of bits in all row-masks. We must end up using exactly k bits.

3. Full solution approach  
Step 1: Enumerate all “valid row masks” of length n (0 ≤ mask < 2^n) that have no two consecutive 1-bits. Store them in a list valid_masks. Also store their bit-counts.  
Step 2: Precompute compatibility: for each valid_masks[i] (call it m) and valid_masks[j] (call it p), record that j can follow i if  
    (m & p) == 0 and ((m<<1) & p) == 0 and ((m>>1) & p) == 0.  
Step 3: Let M be the number of valid_masks. Create a DP array  
    dp[row][used][i] = number of ways to fill rows 1..row, having used exactly used kings so far, and row-mask index = i.  
Dimension sizes: row = 0..n, used = 0..k, i = 0..M–1.  
Step 4: Initialization: dp[0][0][ idx_of_mask_0 ] = 1. (Mask 0 means no kings in the “previous” row.)  
Step 5: Transition for row from 1 to n:  
  For each used = 0..k, for each prev-mask index pi, let ways = dp[row–1][used][pi]. If ways=0 skip.  
  For each new-mask index ni that is compatible with pi:  
    c = bitcount(valid_masks[ni])  
    if used + c ≤ k then  
      dp[row][used + c][ni] += ways  
Step 6: The answer is sum of dp[n][k][i] over all mask-indices i.

Time complexity:  
- Number of valid masks M ≈ Fibonacci(n+2), for n=10 this is 144.  
- Transitions: O(n · k · M · average_degree). average_degree ≤ M, so roughly O(n·k·M²) ≲ 10·100·144² ≈ 20 million. Fast enough in C++/Python.

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;

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

void solve() {
    // Broken-profile DP that fills the board cell by cell in row-major order,
    // placing kings one at a time. The profile is a window of the last n+1
    // decided cells: dp[mask][pi][j][l] is the number of partial fillings where
    // mask holds the occupancy of the n cells immediately preceding the current
    // one (bit 0 is the cell to the left, bit n-1 the cell directly above, and
    // bits n-2 / n give the two diagonal neighbours above), pi is the parity of
    // the current row used to ping-pong two layers, j is the column index within
    // the row, and l is the number of kings still to place. A cell may take a
    // king only when its left, up and two upper-diagonal neighbours are all
    // empty (with edge bits forced to 0 at the borders). Shifting mask left as
    // we advance keeps the window aligned; at the end of a row (j == n) we roll
    // over into the next parity layer. The answer sums all states with no kings
    // left after the last cell.

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

    dp[0][0][0][k] = 1;

    for(int i = 0, pi = 0; i < n; ++i, pi ^= 1) {
        for(int mask = 0; mask < (2 << n); ++mask) {
            for(int j = 0; j <= n; ++j) {
                for(int l = 0; l <= k; ++l) {
                    dp[mask][pi ^ 1][j][l] = 0;
                }
            }
        }

        for(int j = 0; j <= n; ++j) {
            for(int mask = 0; mask < (2 << n); ++mask) {
                for(int l = 0; l <= k; ++l) {
                    if(dp[mask][pi][j][l] == 0) {
                        continue;
                    }

                    if(j == n) {
                        dp[mask][pi ^ 1][0][l] += dp[mask][pi][j][l];
                        continue;
                    }

                    dp[(mask << 1) & ((2 << n) - 1)][pi][j + 1][l] +=
                        dp[mask][pi][j][l];

                    int bit_left = (mask & 1), bit_up = (mask >> (n - 1)) & 1,
                        bit_diag_left = (mask >> n) & 1,
                        bit_diag_right = (mask >> (n - 2)) & 1;

                    if(i == 0) {
                        bit_up = 0;
                        bit_diag_left = 0;
                        bit_diag_right = 0;
                    }

                    if(j == 0) {
                        bit_left = 0;
                        bit_diag_left = 0;
                    }

                    if(j == n - 1) {
                        bit_diag_right = 0;
                    }

                    if(bit_left == 0 && bit_up == 0 && bit_diag_left == 0 &&
                       bit_diag_right == 0 && l > 0) {
                        dp[((mask << 1) | 1) & ((2 << n) - 1)][pi][j + 1]
                          [l - 1] += dp[mask][pi][j][l];
                    }
                }
            }
        }
    }

    int64_t ans = 0;
    for(int mask = 0; mask < (2 << n); ++mask) {
        ans += dp[mask][n & 1][0][0];
    }
    cout << ans << '\n';
}

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

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

    return 0;
}
```

5. Python implementation with detailed comments  
```python
import sys
def main():
    data = sys.stdin.read().split()
    n, k = map(int, data)

    # Step 1: valid row‐masks
    valid = []
    popc = []
    for m in range(1<<n):
        if m & (m<<1) == 0:       # no two adjacent 1s
            valid.append(m)
            popc.append(bin(m).count("1"))
    M = len(valid)

    # Step 2: compatibility graph
    compat = [[] for _ in range(M)]
    for i, m in enumerate(valid):
        for j, p in enumerate(valid):
            if (m & p) == 0 and ((m<<1)&p)==0 and ((m>>1)&p)==0:
                compat[i].append(j)

    # Step 3: dp[r][used][i]
    # Use a 3D list, sizes (n+1)×(k+1)×M
    dp = [[[0]*M for _ in range(k+1)] for __ in range(n+1)]

    # Step 4: base case: before any row, used=0, prev‐mask = 0
    idx0 = valid.index(0)
    dp[0][0][idx0] = 1

    # Step 5: fill DP
    for r in range(1, n+1):
        for used in range(k+1):
            for pi in range(M):
                ways = dp[r-1][used][pi]
                if ways == 0:
                    continue
                for ni in compat[pi]:
                    c = popc[ni]
                    if used + c <= k:
                        dp[r][used + c][ni] += ways

    # Step 6: sum ways for row=n, used=k
    result = sum(dp[n][k])
    print(result)

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

Explanation of the main ideas:  
- We reduce the 2D placement problem to a 1D “row by row” DP by encoding each row as a bitmask.  
- Ensuring no two kings attack horizontally is done by banning consecutive bits in the same mask.  
- Ensuring no two kings attack vertically or diagonally is done by checking bitwise non-overlap between masks of adjacent rows under shifts.  
- We count the total number of kings placed by summing the bit-counts of the row-masks.  
- The final DP state counts exactly k kings across all n rows.