P5255 [JSOI2013] Beautiful Home

Nowadays, wealthy families often have their own villas, and the courtyard of a villa is usually paved with black and white tiles. How to pave the tiles is quite a sophisticated matter, because it involves aesthetics. What kind of paving is considered beautiful? Look at the following two examples:  The one in Figure 1 is considered relatively beautiful, while the paving in Figure 2 is not beautiful. This is because people believe that if there exists a $2*2$ area where there is only one color, then it is not beautiful; otherwise, it is beautiful. Now, Xiao G's company has received a task: a courtyard of size $N*M$ must be paved with tiles. Everyone loves beauty, so the owner naturally hopes the tiling of this courtyard is beautiful. Therefore, he first wants Xiao G's company to provide the total number of design plans. Moreover, the owner seems to be especially superstitious about the number $P$, so he wants the result to be the total number of plans modulo $P$.

There is only one line containing three positive integers $N,~M,~P$ separated by spaces, corresponding to the values described in the statement.

Output the total number of plans modulo $P$.

$1~\leq~N~\leq~10^{100}$ $1~\leq~M~\leq~5$ $1~\leq~P~\leq~10000$ Translated by ChatGPT 5