Ivo화

Ivo는 행렬을 다루며 노는 것을 좋아한다. 최근에는 정사각 행렬 하나에 적용하는 연산을 만들고 Ivo화라고 이름 붙였다.

Ivo화는 정사각 행렬 하나에서 수 하나를 계산하는 연산이다. 그 수는 행렬에 들어 있는 모든 수 쌍의 차의 절댓값을 더한 값이다. 행렬의 원소를 $a_1, a_2, \dots, a_{K^2}$이라고 하면 Ivo화 값은 $\sum_{i=1}^{K^2} \sum_{j=1}^{K^2} |a_i - a_j|$이다. 두 첨자가 같은 쌍도 더하지만 그 값은 0이다. 예를 들어 수 (1, 5, 2, 4)를 담은 정사각 행렬의 Ivo화 값은 다음과 같이 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는 $N$행 $M$열 행렬 안에 완전히 들어가면서 행이 정확히 $K$개, 열이 정확히 $K$개인 모든 정사각 부분행렬의 Ivo화 값을 모두 더하고 싶다. 그 합을 구하라.

첫째 줄에 자연수 $N$, $M$, $K$가 주어진다 ($1 \le N, M, K \le 500$).

다음 $N$개 줄에는 각각 $M$개의 수 $A_{ij}$가 주어진다 ($1 \le A_{ij} \le 10^9$).

모든 $A_{ij}$는 서로 다르다.

첫째 줄에 변의 길이가 $K$인 모든 정사각 부분행렬의 Ivo화 값의 합을 $10007$로 나눈 나머지 $S$를 출력한다.

$K$가 $N$보다 크거나 $M$보다 크면 그런 부분행렬이 하나도 없으므로 $S$는 $0$이다.