19262번 - Fresh Matrix 다국어

A matrix of 0s and 1s is good if there are no two 1s in two matrix cells which share a side.

A matrix of 0s and 1s is connected if between all pairs of 0s there is a path which doesn't contain any 1s, and every two consecutive cells of the path share a side.

How many good connected matrices of 0s and 1s with $n$ rows and $m$ columns are there? As the answer can be rather big, print only its remainder modulo prime $p$.

On the first line, you are given three integers $n$, $m$, and $p$: the number of rows and columns in the matrix and an integer you should use for taking the modulo ($2 \le n \le 11$; $1 \le m \le 10^9$; $2 \le p \le 10^9$; $p$ is prime).

Print one integer: the number of good connected matrices modulo $p$.