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

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).

Input

The only input line contains space-separated integers n and k (4 ≤ n ≤ 1000; 2 ≤ kn2/4; n is even).

Output

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

Sample

inputoutput
4 2
172
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