Minimise the SUM.

You are given a matrix of size N*M having non-negative integers and a non-negative integer K. You are allowed to do the following operation at most K times:

• You can reduce the value of any element of the matrix by 1.
• you cannot reduce an element to a negative value.

Find the minimum possible sum of the sum of all the elements in each submatrix after performing at most K decrements. Print the answer modulo (10^9)+7 (ten to the power nine + seven).

Input Format

• The first line contains T denoting the number of test cases.
• The first line of each test case contains 2 integers N,M representing dimensions of the matrix.
• Then N lines follow, with each line having M elements representing the elements of the matrix.
• Next line contains the value K as described in the problem.

Output format
For each test case - print the required answer in a separate line.

Constraints
1<=T<=10
1<=N,M<=500
0<=K<=10^12
0<=element of the matrix <= 10^6

Sample input :
1
3 3
1 2 3
4 0 5
2 7 4
5
Sample output
246

Explanation:
One possible way to get minimum sum using atmost 5 operation is: 3 operations to reduce the element having value 7 and remaining 2 operations to reduce element having value 5.