Problem

Submissions

0

Avg. time to solve

45 min

Success Rate

60%

Problem Statement

```
You can’t decrease a number below 0.
```

```
You are given ‘K’ = 5, and matrix
‘mat’ = [[1, 2, 3],
[4, 0, 5],
[2 , 7, 4]]
You can do 3 operations on element 7 and 2 operations on element 5. Then the sum of all submatrices will be 246.
```

```
The first line of input contains a single integer ‘T’, denoting the number of test cases.
The first line of each test case contains three space-separated integers ‘N’, ‘M’, and ‘K’, representing the rows, columns of the matrix, and the given integer.
The following ‘N’ lines of input contain ‘M’ space-separated integers representing the matrix elements.
```

```
For each test case, print a single integer representing the minimum possible sum of all elements in each submatrix. Print the answer in the modulo 10^9 + 7.
Print a single line for each test case.
```

```
1 <= T <= 10
1 <= N, M <= 500
0 <= K <= 10^12
1<= mat[i][j] <= 10^6
Time Limit: 1 sec
```

```
2
3 3 5
1 2 3
4 0 5
2 7 4
1 2 1
3 4
```

```
246
12
```

```
For the first test case, given K = 5, and matrix
‘mat’ = [[1, 2, 3],
[4, 0, 5],
[2 , 7, 4]]
You can do three operations on element 7 and 2 operations on element 5. Then the sum of all submatrices will be 246.
For the second test case, given K = 1 and the matrix
mat = [[3, 4]]
You can do one operation on element 4. Then the sum of all submatrices will be 12.
```

```
2
2 2 4
1 2
3 4
3 3 3
1 2 3
3 4 5
5 6 7
```

```
24
368
```

Console