Dynamic Programming by Profile

ID 38607. cute patterns

BrokenTiles plans to expand into the backyards of wealthy clients with patterns of black and white tiles, each measuring 1 x 1 meter. It is known that the yards of all wealthy people have the most fashionable for today shape of a rectangle N x M meters. However, when drawing up a financial plan, the director of this organization had two serious problems: firstly, each new client, obviously, wants the pattern laid out in his yard to be different from the patterns of all other clients of this company, and secondly, this pattern should be cute.

A study has shown that a pattern is pretty if it does not contain a 2 x 2 meter square completely covered with tiles of the same color. To draw up a financial plan, director Vasya needs to find out how many customers he can serve before cute patterns of this size run out. Help him!

Input
Enter two positive integers N and M (1 ≤ N · M ≤ 30).

Imprint
Output a single number –  number of different cute patterns that can be laid out in an N x M yard. Patterns that are made from each other by shifting, rotating or reflecting are considered different.
 

Examples

ID 38608. Cute patterns are back

A lot has changed since the previous task was written. Pretty patterns (for what they are – see the "Pretty Patterns" problem) have become very popular all over the world, so people are willing to maintain a very large piece of land, just to have a pattern on it that is not found anywhere else.

BrokenTiles is now the world's leading manufacturer of cute patterns! To make a plan, CEO Vasya still needs to know how many customers can expect a given size pattern.

Since the scales are literally global, N <= 10¹⁰⁰. However, Vasya doesn't like big numbers, so he asks for the answer modulo P.

Input
The first line of input   contains three positive integers separated by a space – N, M and P (1 <= N <= 10¹⁰⁰, 1 <= M <= 5, 1 <= P <= 10,000).

Imprint
Print  the number of different nice patterns N x M modulo P .