Динамическое программирование по профилю


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 38607. Симпатичные узоры
Темы: Динамическое программирование по профилю    Динамическое программирование на таблицах   

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узоров из черных и белых плиток, каждая из которых имеет размер 1 х 1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника N х M метров. Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во-первых, каждый новый клиент, очевидно, захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во-вторых, этот узор должен быть симпатичным.

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2 х 2 метра, полностью покрытого плитками одного цвета. Для составления финансового плана директору Васе необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!

Входные данные
Вводятся два положительных целых числа N и M (1 ≤ N · M ≤ 30).

Выходные данные
Выведите единственное число –  количество различных симпатичных узоров, которые можно выложить во дворе размера N х M. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.
 

Примеры
Входные данные Выходные данные
1 1 2 4
2 2 3 50

ID 38608. Симпатичные узоры возвращаются
Темы: Динамическое программирование по профилю   

Со времен написания условия предыдущей задачи многое изменилось. Симпатичные узоры (о том, что это такое – см. задачу "Симпатичные узоры") стали очень популярны по всему миру, поэтому люди готовы содержать очень большой участок земли, лишь бы иметь на ней узор, не встречающийся больше нигде.

Теперь компания BrokenTiles является ведущим производителем симпатичных узоров в мире! Для составления плана исполнительному директору Васе по-прежнему необходимо знать, сколько клиентов могут рассчитывать на узор данных размеров.

Так как масштабы буквально мировые, N <= 10100. Однако Вася не любит большие числа, поэтому просит выдать ответ по модулю P.

Входные данные
В первой строке входных данных  содержатся три положительных целых числа, разделенные пробелом – N, M и P (1 <= N <= 10100, 1 <= M <= 5, 1 <= P <= 10 000).

Выходные данные
Выведите  количество различных симпатичных узоров N x M по модулю P .