ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Open Ural SU Championship 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Endgame Database

Time limit: 1.0 second
Memory limit: 64 MB
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 ≤ kn2/4; n is even).


Output the number of positions in the endgame database computed modulo 109 + 7.


4 2
Problem Author: Igor Chevdar
Problem Source: XIV Open USU Championship
To submit the solution for this problem go to the Problem set: 1734. Endgame Database