안장점

시간 제한1초메모리 제한512 MB

요약

각 원소가 1부터 k까지인 n×m 행렬 가운데, 자기 행과 열에서 모두 순최댓값인 자리를 하나 이상 가지는 행렬의 개수를 10^9+7로 나눈 나머지로 구한다.

문제

bobo는 $n \times m$ 크기의 행렬을 가지고 있다. 행렬의 각 원소는 $[1, k]$ 범위의 정수다.

안장점이 적어도 하나 존재하는 행렬의 개수를 $(10^9+7)$ 로 나눈 나머지를 구하라.

안장점이란 $i$ 번째 행에서 순최대이고 동시에 $j$ 번째 열에서도 순최대인 위치 $(i, j)$ 를 말한다.

$3$ 개의 정수 $n, m, k$ 가 주어진다. ( $1 \leq n, m \leq 500, 1 \leq k \leq 10$ )

행렬의 개수를 나타내는 정수 하나를 출력한다.