시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 1 1 1 100.000%

문제

Consider an array $A$ of length $N$ and an array $B$ of length $M$. An entanglement of these two arrays is a matrix $C$ of size $N \times M$ such that for all $0 \le i \le N - 1$ and $0 \le j \le M - 1$, at least one of the following conditions holds: $C[i][j] = A[i]$ or $C[i][j] = B[j]$.

You are given a matrix $C$ of size $N \times M$ and a number $K$. Your task is to count the number of pairs of arrays $(A, B)$ such that:

  • $A$ has length $N$.
  • $B$ has length $M$.
  • $A$ and $B$ consist of values from the set $\{1, 2, \ldots, K\}$.
  • $C$ is an entanglement of $A$ and $B$.

Print the number of such pairs modulo $10^9 + 7$.

입력

The first line of input contains three integers $N$, $M$ and $K$ ($1 \le N, M \le 300$, $1 \le K \le N \times M$).

Each of the following $N$ lines contains $M$ integers separated by spaces, the $j$-th number on the $i$-th of these lines is $C[i - 1][j - 1]$.

출력

Print a single line containing a single integer: the number of pairs of arrays $(A, B)$ modulo $10^9 + 7$.

예제 입력 1

2 2 2
1 1
1 2

예제 출력 1

5