| Автор: | И. Туфанов | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt |
Прямоугольник состоит из M × N квадратиков размером 1 × 1. Три вершины каждого квадратика раскрашены в белый цвет, а одна — в черный. Правильной считается раскраска, при которой стыкующиеся вершины квадратиков имеют одинаковые цвета.
Необходимо найти количество различных способов правильной раскраски прямоугольника. Ответ выведите по модулю m.
Выведите в выходной файл единственно число — количество способов правильной раскраски по заданному модулю.
В приведенном примере существует 10 раскрасок, а 10 по модулю 7 (т. е. остаток от деления 10 на 7) дает 3.
1 ≤ N, M ≤ 105
2 ≤ m ≤ 109
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|