Ivoization

Ivo likes playing with matrices. His latest invention is an operation on a single square matrix, and he calls it Ivoization.

Ivoization turns one square matrix into one number. That number is the sum of the absolute differences over all pairs of numbers in the matrix. If the entries of the matrix are $a_1, a_2, \dots, a_{K^2}$, the Ivoization value is $\sum_{i=1}^{K^2} \sum_{j=1}^{K^2} |a_i - a_j|$. Pairs with two equal indices are included, and they contribute 0. For example, the Ivoization value of a square matrix holding the numbers (1, 5, 2, 4) is 28.

$|1-1| + |1-5| + |1-2| + |1-4| + |5-5| + |5-1| + |5-2| + |5-4| + |2-2| + |2-1| + |2-5| + |2-4| + |4-4| + |4-1| + |4-5| + |4-2| = 28$

Ivo wants to add up the Ivoization values of all square submatrices with exactly $K$ rows and exactly $K$ columns that lie entirely inside a matrix with $N$ rows and $M$ columns. Compute that sum.

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

Each of the next $N$ lines contains $M$ numbers $A_{ij}$ ($1 \le A_{ij} \le 10^9$).

All $A_{ij}$ are distinct.

Print $S$, the sum of the Ivoization values of all square submatrices with side length $K$, modulo $10007$.

If $K$ is greater than $N$ or greater than $M$, no such submatrix exists, so $S$ is $0$.