printРабочее место участника

printЗадачи

1451. Три плюс один

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
Источник: Отборочные соревнования ВКОШП Дальневосточного региона, 2008
loading