도미노 덮기

Elizur에게 빈 $n \times m$ 격자가 있다. 그는 $1 \times 2$ 과 $2 \times 1$ 도미노 몇 개로 격자 전체를 덮으려 한다. 각 도미노는 인접한 두 칸을 정확히 덮고, 각 칸은 정확히 하나의 도미노에 덮인다. 두 칸이 변을 공유하면 인접하다고 한다.

$n$과 $m$ 중 적어도 하나가 짝수일 때에만 덮을 수 있다. 그렇지 않으면 반드시 빈 칸이 남는다. 그는 격자 전체를 덮는 방법이 몇 가지인지 알고 싶어 한다. 두 덮개는 한쪽 도미노와 다른 쪽 도미노 중 어떤 두 도미노가 같은 칸 하나를 덮으면서도 다른 칸은 다르게 덮는 경우가 있으면 서로 다른 방법으로 본다.

답은 매우 클 수 있으므로, 소수 $p$로 나눈 나머지를 구한다.

첫 줄에 질문의 개수 $T$ ($1 \le T \le 20000$)가 주어진다.

이어지는 $T$개의 줄에는 각각 세 정수 $n$ ($1 \le n \le 35$), $m$ ($1 \le m \le 10^{18}$), $p$ ($2 \le p \le 2^{30}$, $p$는 소수)가 주어진다.

$n > 5$ 이거나 $m > 10^9$ 인 질문은 최대 1000개이다.

각 질문마다 덮는 방법의 수를 $p$로 나눈 나머지를 한 줄에 출력한다.

그림은 $3 \times 4$ 격자를 덮는 가능한 11가지 방법을 모두 보여준다.