Maximum Submatrix Sum

You are given an integer matrix with n rows and m columns. Your task is to compute the sum of the maximum elements in each submatrix of size k × k. Since the answer can be large, output the result modulo \(10^9+7\).

Detailed Explanation:

• For each possible submatrix of size k × k within the given matrix, determine the maximum element.
• Compute the sum of all these maximum elements and then take the modulo with \(10^9+7\).

The first line of input provides three integers: n, m, and k. This is followed by n lines each containing m space-separated integers representing the matrix.

It is guaranteed that 1 ≤ k ≤ min(n, m).

inputFormat

The input is given via standard input (stdin) and has the following format:

n m k
row1_element1 row1_element2 ... row1_elementm
row2_element1 row2_element2 ... row2_elementm
...
rown_element1 rown_element2 ... rown_elementm

Where n is the number of rows, m is the number of columns, and k is the size of the submatrix.

outputFormat

Output a single integer representing the sum of the maximum elements from each submatrix of size k × k, taken modulo \(10^9+7\), via standard output (stdout).

## sample

3 3 2
1 2 3
4 5 6
7 8 9

28