Grid Guardian

앨리스는 $n \times m$ 격자에 $2 \times 2$ 블록을 놓으려 한다. 블록은 축에 평행하게 놓여야 하며, 정확히 격자 칸 4개를 덮어야 한다.

밥은 앨리스가 블록을 놓지 못하게 막으려 한다. 그래서 일부 칸에 장애물을 놓는다. 장애물을 놓은 뒤에는 격자의 모든 $2 \times 2$ 부분 격자에 장애물이 적어도 하나 있어야 한다. 밥은 장애물을 가능한 한 적게 놓으려 한다.

앨리스가 블록을 놓지 못하도록 밥이 최소 개수의 장애물을 놓는 방법의 수를 구하라. 답은 소수 $p$로 나눈 나머지로 출력한다. 답은 장애물의 최소 개수가 아니라 놓는 방법의 수이다. 예를 들어 $n = m = 2$이면 밥은 장애물 1개만 놓으면 되고, 그 방법은 4가지이므로 답은 4이다.

첫 줄에 공백으로 구분된 세 정수 $n$ ($2 \le n \le 25$), $m$ ($2 \le m \le 10^3$), $p$ ($10^8 \le p \le 10^9 + 7$)가 주어진다. 격자의 크기는 $n \times m$이며, $p$는 소수인 나눗셈 법이다.

밥이 $n \times m$ 격자에 최소 개수의 장애물을 놓아 앨리스가 $2 \times 2$ 블록을 놓지 못하게 하는 방법의 수를 $p$로 나눈 나머지를 한 정수로 출력한다.