직사각형의 개수

$N \times M$ 크기의 격자판이 있다. 각 칸에는 1 이상 $K$ 이하의 숫자가 하나씩 적혀 있다. $i$행 $j$열 ($1 \le i \le N$, $1 \le j \le M$)의 칸을 $(i, j)$로 나타낸다.

직사각형은 $1 \le x_1 \le x_2 \le N$, $1 \le y_1 \le y_2 \le M$을 만족하는 네 정수 $x_1$, $y_1$, $x_2$, $y_2$로 정해지고, $x_1 \le x \le x_2$와 $y_1 \le y \le y_2$를 만족하는 모든 칸 $(x, y)$를 모은 것이다. 이 직사각형의 크기는 $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$이다. 네 값 $[x_1, y_1, x_2, y_2]$가 다르면 서로 다른 직사각형이다.

격자판 안에서 정확히 $k$종류의 숫자가 적혀 있고 크기가 $n \times m$인 직사각형의 개수를 $C_{k,n,m}$이라 하자. 모든 $C_{k,n,m}$을 구하는 프로그램을 작성하라.

예를 들어 $N = M = K = 3$이고 숫자가 다음 그림과 같이 적혀 있다고 하자.

$x_1 = 2$, $y_1 = 1$, $x_2 = 3$, $y_2 = 2$이면 네 칸 $(2, 1)$, $(2, 2)$, $(3, 1)$, $(3, 2)$가 한 직사각형에 속한다. 이 직사각형만 떼어 적으면 다음과 같다.

이 직사각형에는 1과 2만 있으므로 두 종류의 숫자가 쓰인 직사각형이다.

입력은 하나의 테스트 케이스로 이루어진다.

첫째 줄에 세 정수 $N$, $M$, $K$ ($1 \le N, M \le 512$, $1 \le K \le 9$)가 공백으로 구분되어 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 격자판의 각 줄에 적힌 숫자 $M$개가 공백 없이 주어진다. 각 숫자는 1 이상 $K$ 이하이다.

모든 $C_{k,n,m}$을 출력하기에는 시간이 너무 오래 걸린다. 첫째 줄에 다음 값을 1000000007로 나눈 나머지를 출력한다.

$\prod_{k=1}^{K}\prod_{n=1}^{N}\prod_{m=1}^{M}\left(C_{k,n,m} + k \times n \times m\right)$