Мозаика медресе


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Пол медресе в Узгене выкладывают плитками-домино: каждая плитка — прямоугольник 1 × 2, её можно положить вдоль или поперёк. Пол — полоса из n × m клеток; её нужно покрыть плитками целиком, без наложений и выступов.

Рисунок

Сколькими способами можно выложить пол? Ответ выведите по модулю 10⁹ + 7.

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

В единственной строке — два целых числа n и m (1 ≤ n ≤ 7, 1 ≤ m ≤ 10¹⁸).

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

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

Пример 1

Вход:

2 3

Выход:

3

Пояснение

Полосу 2 × 3 можно выложить тремя способами (на рисунке), полосу 3 × 4 — одиннадцатью.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n · m ≤ 30.

Подсказка

Динамика по профилю: состояние — какие клетки следующего столбца уже заняты плитками, торчащими из текущего. Переходы между профилями образуют матрицу, а её степень считается быстро.


Комментарии

Еще нет ни одного комментария.