For many years programmer Starostin had been writing a checkers-playing program
for the n × n board. The triumph moment was very near—he was going to
issue the final version soon and enjoy the glory of the creator of the best checkers program in
the world. The program was almost invincible already, and with
the new big endgame database there would be no equals to it. It only remained
to generate that database...
When he finished writing the generator of moves in assembler, Starostin found out
that there was no empty space left on his hard disk. The endgame database would
require a huge amount of memory. In order to estimate the number of hard disks
he would have to buy, Starostin decided to compute in advance the number of
positions in his database.
The database must contain only those positions in which there are exactly k
pieces on the board. Each piece is characterized by its color (white or black)
and type (a man or a king). There must be at least one piece of each color on
the board, all pieces must occupy black squares, and men mustn't stand on their
crowning squares (this means that white men can't be in the last rank and black
men can't be in the first rank).
The only input line contains space-separated integers n and k
(4 ≤ n ≤ 1000; 2 ≤ k ≤ n2/4; n is even).
Output the number of positions in the endgame database computed
modulo 109 + 7.
Problem Author: Igor Chevdar
Problem Source: XIV Open USU Championship