Please subscribe to the official Codeforces channel in Telegram via the link ×

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!


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


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)

Test #1

3 2

Test #2

4 4

Test #1


Test #2


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