시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

bobo has a matrix of size $n \times m$, whose elements are integers from $[1, k]$.

Find out the number of matrices with at least one saddle point, modulo $(10^9+7)$.

Note that a saddle point is a position $(i, j)$ which is both strict maximum of the $i$-th row and $j$-th column.

입력

$3$ integers $n, m, k$ ($1 \leq n, m \leq 500, 1 \leq k \leq 10$).

출력

A single integer denotes the number of matrices.

예제 입력 1

2 2 2

예제 출력 1

6

예제 입력 2

500 500 2

예제 출력 2

48326276