Rikka with Nash Equilibrium

Nash Equilibrium is an important concept in game theory.

Rikka and Yuta are playing a simple matrix game. At the beginning of the game, Rikka shows an $n \times m$ integer matrix $A$. And then Yuta needs to choose an integer in $[1,n]$, Rikka needs to choose an integer in $[1,m]$. Let $i$ be Yuta's number and $j$ be Rikka's number, the final score of the game is $A_{i,j}$.

In the remaining part of this statement, we use $(i,j)$ to denote the strategy of Yuta and Rikka.

For example, when $n=m=3$ and matrix $A$ is
\begin{align*}
\begin{bmatrix}
1 & 2 & 1\\
1 & 4 & 3\\
1 & 1 & 1\\
\end{bmatrix}
\end{align*}
If the strategy is $(1,2)$, the score will be $2$; if the strategy is $(2,2)$, the score will be $4$.

A pure strategy Nash equilibrium of this game is a strategy $(x,y)$ which satisfies neither Rikka nor Yuta can make the score higher by changing his(her) strategy unilaterally. Formally, $(x,y)$ is a Nash equilibrium if and only if:
\begin{align*}
\begin{cases}
A_{x,y} \geq A_{i,y} \ \ \forall i \in [1, n] \\
A_{x,y} \geq A_{x,j} \ \ \forall j \in [1,m]
\end{cases}
\end{align*}

In the previous example, there are two pure strategy Nash equilibriums: $(3,1)$ and $(2,2)$.

To make the game more interesting, Rikka wants to construct a matrix $A$ for this game which satisfies the following conditions:
1. Each integer in $[1, nm]$ occurs exactly once in $A$.
2. The game has at most one pure strategy Nash equilibriums.

Now, Rikka wants you to count the number of matrixes with size $n \times m$ which satisfy the conditions.

The first line contains a single integer $t(1 \leq t \leq 20)$, the number of the testcases.

The first line of each testcase contains three numbers $n,m$ and $K(1 \leq n,m \leq 80, 1 \leq K \leq 10^9)$.

The input guarantees that there are at most $3$ testcases with $\max(n,m) > 50$.

For each testcase, output a single line with a single number: the answer modulo $K$.

2
3 3 100
5 5 2333

64
1170

2018 Multi-University Training Contest 9