Domino Covering

Elizur has an empty $n \times m$ grid. He wants to cover the whole grid with some $1 \times 2$ and $2 \times 1$ dominoes. Each domino covers exactly two adjacent squares, and each square is covered by exactly one domino. Two squares are adjacent if they share a side.

The grid can be covered if and only if at least one of $n$ and $m$ is even. Otherwise, some square must always be left empty. He wants to know how many ways there are to cover the entire grid. Two coverings are different if there exist a domino from one covering and a domino from the other such that they cover the same square in one place but cover different squares elsewhere.

The answer can be very large, so output it modulo a prime $p$.

The first line contains one integer $T$ ($1 \le T \le 20000$), the number of queries.

Each of the next $T$ lines contains three integers $n$ ($1 \le n \le 35$), $m$ ($1 \le m \le 10^{18}$), and $p$ ($2 \le p \le 2^{30}$, $p$ is prime).

At most 1000 queries satisfy $n > 5$ or $m > 10^9$.

For each query, output one line containing the number of covering ways modulo $p$.

The figure shows all 11 possible coverings of a $3 \times 4$ grid.