Мозаика медресе
Пол медресе в Узгене выкладывают плитками-домино: каждая плитка — прямоугольник 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.
Подсказка
Динамика по профилю: состояние — какие клетки следующего столбца уже заняты плитками, торчащими из текущего. Переходы между профилями образуют матрицу, а её степень считается быстро.
Комментарии