eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сокровища ацтеков

Сокровища ацтеков

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Недавно во время раскопок в Теотиуакане археологи обнаружили странную шкатулку, содержимое которой, вероятно, использовалось во время легендарных жертвоприношений Монтесумы, и множество одинаковых вырезанных из кости прямоугольных фигурок размером 1 × 2.

Археологи выяснили, что для того чтобы открыть шкатулку, необходимо замостить фигурками прямоугольную крышку этой шкатулки строго определённым образом. Фигурки не могут накладываться друг на друга и выходить за границы крышки. Археологи боятся взламывать шкатулку, поэтому они хотят просто перебрать все возможные способы замощения. Вы должны посчитать количество таких способов.

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

В одной строке заданы длина l и ширина w крышки шкатулки (1l, w100).

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

Выведите искомое количество способов по модулю 10^9 + 7.

Пример

Входные данные #1
3 4
Выходные данные #1
11
Автор Игорь Чевдарь
Источник 2009 Petrozavodsk Winter Session, Ural SU Contest, Февраль 4, Задача B