404180: GYM101445 D Уголки

D. Уголкиограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Петя с двумя друзьями писал контест. Но тут его сокомандники отказались писать задачу, потому что она сложная. Расстроенный Петя раскатал первого из друзей в полоску, состоящую из 2 на n одинаковых квадратных клеточек, а второго разрезал на k уголков по три клеточки каждый. Теперь он интересуется вопросом: а сколько способов разместить эти уголки на полоске так, чтобы они не пересекались (то есть, чтобы ни одна клетка полосы не была покрыта более чем одним уголком). Петя не может отличить один уголок от другого, так что расстановки, отличающиеся только порядком уголков следует считать одинаковыми. Так как число способов может быть большим, а Петя добрый мальчик, ответ нужно вывести по модулю 10⁹ + 7.

Входные данные

Два натуральных числа n и k через пробел, 1 ≤ n ≤ 5000, 1 ≤ k ≤ 10⁹.

Выходные данные

Выведите единственное число – ответ на задачу.

ПримерыВходные данные

2 1

Выходные данные

4

Входные данные

2 2

Выходные данные

0

Входные данные

3 2

Выходные данные

2

Входные данные

10 4

Выходные данные

5820