시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 19 | 15 | 12 | 85.714% |
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:
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$.
2 2 1000000007
16
4 3 1000000007
95800320
100 100 998244353
848530760