ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1734. База эндшпилей

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Программист Старостин уже много лет писал программу для игры в шашки на доске размера n × n. И момент триумфа был близок — скоро он собирался выпустить финальную версию и наслаждаться славой создателя лучшей в мире шашечной программы. Программа и так была уже практически непобедима, а с новой большой базой эндшпилей ей просто не должно было быть равных. Оставалось лишь сгенерировать эту базу...
Когда Старостин дописал генератор ходов на ассемблере, он обнаружил, что место на жёстком диске его компьютера закончилось. Для базы эндшпилей же требовалось огромное количество памяти. Чтобы оценить, сколько винчестеров придётся докупить, Старостин решил посчитать количество позиций в его базе эндшпилей заранее.
В базе будут храниться лишь те позиции, в которых на доске расположено ровно k фигур. Каждая фигура характеризуется её цветом (белый или чёрный) и типом (обычная шашка или дамка). Кроме того, на доске должна присутствовать хотя бы одна фигура каждого цвета, все фигуры должны стоять на чёрных клетках, а обычные шашки не должны стоять на своих полях превращения (белые шашки не могут стоять на последней горизонтали, а чёрные — на первой).

Исходные данные

В единственной строке через пробел записаны числа n и k (4 ≤ n ≤ 1000; 2 ≤ kn2/4; n чётно).

Результат

Выведите количество позиций в базе эндшпилей, вычисленное по модулю 109 + 7.

Пример

исходные данныерезультат
4 2
172
Автор задачи: Игорь Чевдарь
Источник задачи: XIV Открытый командный чемпионат УрГУ по программированию