|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|6 초||256 MB||6||4||4||66.667%|
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$.
2 2 998244353
4 1 998244353
4 5 998244353