Placing Kings

Submit solution
Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
Zeyu
Problem type

Bob is playing with a chess board!

Bob currently has a \(1 \times N\) board as well as \(M\) king pieces. Being very board bored, he wants to see how many ways he can put \(M\) kings on the board without any of them in position to attack.

Can you help Bob be a little bit less bored and solve the problem for him?

Input Specification

The first and only line contains two integers \(N\) and \(M\) \((1 \le M \le N \le 20)\), the width of the chess board and the number of king pieces.

Output Specification

Output consists of one integer, the number of distinct ways Bob can place the kings without any of them being in range of each other.

Sample Input

5 2

Sample Output

6

Explanation of Output

There are six ways Bob can place the pieces:

1- [K . K . .]
2- [K . . K .]
3- [K . . . K]
4- [. K . K .]
5- [. K . . K]
6- [. . K . K]

Comments