Республиканская олимпиада по информатике 2008 год

Задача C. Трубы

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Сколькими способами на площадке из $NxM$ ячеек можно расставить трубы 11-ти различных типов, приведенных на рисунке

, так чтобы каждая труба занимала ровно одну ячейку, и чтобы трубы образовали одну или несколько замкнутых систем? Система труб замкнута, если каждый конец любой трубы соединен с каким-либо концом другой трубы. Пример замкнутой системы приведен на рисунке

. На площадке могут остаться пустые ячейки. Ответ необходимо вывести по модулю числа P ($0$ <= ответ < $P$).

Формат входного файла

Первая строка входного файла содержит три целых числа $N$, $М$ и $P$ (1 <= $N$ <= $8$, 1 <= $M$ <= $8$, 2 <= $P$ <= $10^9$). Числа разделены пробелом.

Формат выходного файла

Выходной файл должен содержать одно целое число — ответ на задачу.

Пример:

Вход

2 2 10

Ответ

1

Замечание

Пример из ответа: