Super Ants

This game is called the ants game. You are given a grid with $N$ rows and $M$ columns. The rows are numbered from $1$ to $N$ from top to bottom, and the columns are numbered from $1$ to $M$ from left to right. Every cell in the grid has an unlimited store of one type of sugar, and collecting one unit of sugar from a cell gives the score written in that cell. The game is just one step. Place one super ant on any cell of the grid, and the ant does the rest of the work and fixes your score.

Once a super ant is placed on a cell, it behaves in a fixed way. If there is no remaining time, the ant gets one unit of sugar from the store of its cell and stops working. If there is some remaining time, it starts the cloning operation. It clones itself into every cell it can still reach with the current remaining time, and all of the cloning starts at the same time. Cloning into a cell at distance $D$ takes $D$ seconds, so the new ant has $D$ seconds less time left. The distance between position $(R_1, C_1)$ and position $(R_2, C_2)$ is $\max(|R_1 - R_2|, |C_1 - C_2|)$. A newly cloned ant is a super ant as well, and it acts the same way with its remaining time.

An ant that clones itself also collects one unit of sugar from its own cell. Whenever an ant appeared, it ends by collecting one unit of sugar from the cell it sits on, and your score is the sum of the values of all collected sugar units.

An ant cannot clone itself into a cell farther away than its current remaining time, it cannot clone itself into the same cell more than once, and it cannot clone itself into its own cell. Any cell can hold any number of ants at any time.

So which cells can an ant clone itself into? First, an ant cannot clone itself outside of the grid. Second, it can only clone into cells on one of the 8 direction vectors that start at its position. A direction vector means all consecutive cells in the same direction. For example, from position $(A, B)$ the east vector gives $(A, B+1)$, $(A, B+2)$, $(A, B+3)$ and so on. A super ant with 2 seconds remaining can clone itself into 16 cells, 8 of them at distance 1 and 8 at distance 2.

You are given the score of one sugar unit in every cell, the total time you are allowed, and the cell the first super ant starts from. Compute the score you get for that cell. The time starts running once the first ant is placed.

The first line contains a single integer $T$, the number of test cases. ($1 \le T \le 100$)

Each test case starts with a line containing three integers separated by a single space, $N$, $M$ and $S$: the number of rows in the grid, the number of columns, and the remaining time. ($1 \le N, M \le 50$, $0 \le S \le 500$)

The next line contains two integers separated by a single space, $I$ and $J$: the row number and the column number of the cell the first ant starts from. ($1 \le I \le N$, $1 \le J \le M$)

Then follow $N$ lines, each containing $M$ integers separated by a single space, the value of one sugar unit in each cell of that row. Every integer in the grid is not less than $0$ and not greater than $9$.

For each test case, print a single line with a single integer, the score you get at the end of the game. The result may be very large, so print it modulo $10^9 + 7$, that is 1,000,000,007.

In the first test case of the example input, the first ant collects one unit of sugar worth 5 from its own cell, and it clones 8 ants in the 8 directions. Those clones have no time left, so each one collects only a single unit of sugar from its cell. The score is $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45$.

In the second test case, the first ant clones itself into 8 cells at distance 2 with 0 remaining time, and into 8 cells at distance 1 with 1 second of remaining time, so each of the latter clones goes on to clone itself again.