Региональная олимпиада по программированию, личный тур, 27 апреля 2014

Соревнование завершилось 27.04.14 в 16:00

A. Игра в Недобоулинг

Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Источник: личный тур межвузовской олимпиады 2014 года

Игра в Недобоулинг состоит из N раундов. В начале каждого раунда напротив игрока выставляются 10 кегель. В каждом раунде игрок бросает 2 шара. Первый из шаров сбивает Ai кегель (0 ≤ Ai ≤ 10), а второй шар сбивает Bi из оставшихся кегель (0 ≤ Bi ≤ 10 - Ai), где i – номер раунда (1 ≤ iN). В конце игры подсчитывается количество набранных очков равное сумме всех сбитых кегель по итогам всех раундов и заработанных бонусов. В i-ом раунде игрок получит бонус:

  1. 10 + Ai+2, если Ai = 10 и Ai+1 = 10
  2. Ai+1 + Bi+1, если Ai = 10 и Bi+1 > 0
  3. Ai+1, если Bi > 0 и Ai + Bi = 10
  4. 0, если Bi > 0 и Ai + Bi < 10

Считать, что AN+1 = 0, BN+1 = 0 и AN+2 = 0

Рассмотрим пример получения бонусов.

раунд 1раунд 2раунд 3раунд 4раунд 5раунд 6.
[10 0][10 0][7 3][3 2][2 3][0 10](кегли)
17103000(бонусы)

В первом раунде начислен бонус по первому критерию, во втором раунде — бонус по второму критерию, в третьем раунде — бонус по третьему критерию. В четвертом и пятом раундах бонусов не начислено. В шестом раунде начислен бонус по второму критерию, но из-за граничных условий он равен 0. Общее количество сбитых кегель 50. Общее количество бонусов 30. Количество набранных за игру очков 80.

Требуется определить количество способов набрать ровно M очков за игру.

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

В единственной строке даны два целых числа через пробел N (3 ≤ N ≤ 100) и M (0 ≤ M ≤ (N-1) ∙ 30).

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

Вывести единственное число — ответ на задачу. Ответ вывести по модулю 109 + 7.

Пример

Стандартный вводСтандартный вывод
6 8017427669
3 221