НачалоПодразделы
Другие разделы
| 1446. Марсианская лингвистическая реформа |
| 1447. Домик для друзей |
| 1448. Транспортное кольцо |
| 1449. Планета странной формы |
| 1450. Поездка на Хэллоуин |
| 1452. Торанианхендж |
| 1453. Geometry with a ruler |
Дата и время
19/04/2024 09:53:12
1451. Три плюс один
Три плюс один
Комбинаторика, теория ПойаОлимпиадные задачи на русском языке
| 24/06/2010 | Лето 2010 дорешивание ( 8F) |
| 09/07/2010 | Лето 2010 - 8 (F) |
| 14/07/2017 | Лето 2017 (командное) - 10 (H) |
| 25/11/2023 | Марафон 80 задач, 6 этап (C) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Прямоугольник состоит из `M\ times\ N` квадратиков размером `1\ times\ 1`.
Три вершины каждого квадратика раскрашены в белый цвет, а одна – в черный. Правильной считается
раскраска, при которой стыкующиеся вершины квадратиков имеют одинаковые цвета.
Необходимо найти количество различных способов правильной раскраски прямоугольника. Ответ выведите по модулю `m`.
Формат входного файла
Во входном файле находятся числа `N\ M\ m`.
Формат выходного файла
Выведите в выходной файл единственно число – количество способов правильной раскраски по заданному модулю.
В приведенном примере существует 10 раскрасок, а 10 по модулю 7 (т. е. остаток от деления 10 на 7) дает 3.
Ограничения
`1\ ≤\ N,\ M\ ≤\ 10^5`, `2\ ≤\ m\ ≤\ 10^9`
Пример ввода
2 3 7
Пример вывода
3
