21102번 - Local Maxima 다국어

문제

Given an $n \times m$ integer matrix $A,ドル a local maximum of $A$ is a location $(i, j)$ (1ドル \le i \le n$ and 1ドル \le j \le m$) such that $A_{i, j}$ is no smaller than any other integer on the $i$-th row or on the $j$-th column.

For example, in the 3ドル \times 3$ matrix $$ \begin{bmatrix} 2 & 5 & 4 \\ 2 & 1 & 6 \\ 2 & 2 & 2 \end{bmatrix}\text{,} $$ there are three local maxima: locations $(1, 2),ドル $(2, 3),ドル and $(3, 1)$ with values 5ドル,ドル 6ドル,ドル and 2ドル,ドル repectively.

An $n \times m$ integer matrix $A$ is good if and only if it satisfies the following two conditions:

• There is exactly one local maximum in $A$.
• Each integer from 1ドル$ to $n \times m$ occurs exactly once in $A$.

Given $n,ドル $m,ドル and a prime number $P,ドル your task is to count the number of good matrices of size $n \times m$ modulo $P$.

입력

The first line contains three integers, $n,ドル $m,ドル and $P,ドル where 1ドル \le n, m \le 3000$ and 10ドル^8 \le P \le 10^9 + 7$. It is guaranteed that $P$ is prime.

출력

Output a single line with a single integer: the number of good matrices modulo $P$.

제한

힌트