Entanglement

Time limit3sMemory limit256 MB

Summary

Count pairs of arrays A (length N) and B (length M) with values from 1 to K such that every cell C[i][j] equals A[i] or B[j].

Level: Hard9 of 10
Topics: Combinatorics, Graph, Math
Solved: No attempts yet

Problem

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

You are given a matrix $C$ of size $N \times M$ and an integer $K$ . Count the pairs of arrays $(A, B)$ such that:

$A$ has length $N$ .
$B$ has length $M$ .
Every element of $A$ and $B$ is in $\{1, 2, \ldots, K\}$ .
$C$ is an entanglement of $A$ and $B$ .

Print the count modulo $10^9 + 7$ .

Input

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

Each of the next $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]$ .

Output

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

Examples1

Example 1
Input
```
2 2 2
1 1
1 2
```
Expected output
```
5
```