Problem Description

On an $N \times N$ chessboard, place $K$ kings so that they do not attack each other. How many placement schemes are there? A king can attack one square in each of the eight directions: up, down, left, right, and the four diagonals (upper-left, lower-left, upper-right, lower-right), for a total of $8$ squares.

Input Format

There is only one line containing two integers $N,K$.

Output Format

The number of such arrangements.

3 2

16

Hint

Constraints and Conventions

For all testdata, $1 \le N \le 9$, $0 \le K \le N\times N$.

$\text{upd 2018.4.25}$: The testdata has been strengthened.

Translated by ChatGPT 5