시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 256 MB 2 2 2 100.000%

문제

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

예제 입력 1

2 2 998244353

예제 출력 1

5

예제 입력 2

4 1 998244353

예제 출력 2

4

예제 입력 3

4 5 998244353

예제 출력 3

2749