Counting rectangles by distinct numbers

There is an $N \times M$ grid. Each cell holds one number between 1 and $K$. The cell in row $i$ and column $j$ ($1 \le i \le N$, $1 \le j \le M$) is written as $(i, j)$.

A rectangle is fixed by four integers $x_1$, $y_1$, $x_2$, $y_2$ with $1 \le x_1 \le x_2 \le N$ and $1 \le y_1 \le y_2 \le M$, and it consists of every cell $(x, y)$ with $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$. Its size is $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$. Two rectangles are different when the values $[x_1, y_1, x_2, y_2]$ differ.

Let $C_{k,n,m}$ be the number of rectangles of size $n \times m$ in the grid that hold exactly $k$ kinds of numbers. Write a program that computes every $C_{k,n,m}$.

For example, let $N = M = K = 3$ and let the numbers be written as in the picture below.

With $x_1 = 2$, $y_1 = 1$, $x_2 = 3$, $y_2 = 2$, the four cells $(2, 1)$, $(2, 2)$, $(3, 1)$, $(3, 2)$ belong to one rectangle. Taken on its own, that rectangle looks like this.

Only 1 and 2 appear in it, so it is a rectangle with two kinds of numbers.

The input consists of a single test case.

The first line contains three integers $N$, $M$, $K$ ($1 \le N, M \le 512$, $1 \le K \le 9$) separated by spaces.

Each of the next $N$ lines contains the $M$ numbers written in one row of the grid, with no spaces between them. Each number is between 1 and $K$.

Printing every $C_{k,n,m}$ takes too long, so print on the first line the following value modulo 1000000007.

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