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$.

제한

힌트