슈퍼 개미

$N$행 $M$열 격자에서 하는 개미 게임이다. 행 번호는 위에서 아래로 $1$부터 $N$까지, 열 번호는 왼쪽에서 오른쪽으로 $1$부터 $M$까지 붙는다. 각 칸에는 한 종류의 설탕이 무한히 쌓여 있고, 그 칸에서 설탕 한 단위를 모으면 칸마다 정해진 점수를 얻는다. 게임에서 하는 일은 하나뿐이다. 슈퍼 개미 한 마리를 원하는 칸에 놓으면 나머지는 개미가 알아서 하고, 그것으로 점수가 정해진다.

칸에 놓인 슈퍼 개미는 정해진 방식으로 움직인다. 남은 시간이 없으면 자기 칸의 창고에서 설탕 한 단위를 얻고 일을 끝낸다. 남은 시간이 있으면 복제를 시작한다. 남은 시간으로 갈 수 있는 모든 칸에 자신을 복제하며, 복제는 전부 동시에 시작한다. 거리가 $D$인 칸으로 복제하는 데 $D$초가 걸리므로 그렇게 생긴 개미의 남은 시간은 $D$초만큼 줄어든다. 위치 $(R_1, C_1)$과 위치 $(R_2, C_2)$ 사이의 거리는 $\max(|R_1 - R_2|, |C_1 - C_2|)$이다. 새로 생긴 개미도 슈퍼 개미여서 남은 시간으로 똑같이 행동한다.

복제를 한 개미도 자기 칸에서 설탕 한 단위를 모은다. 언제 생긴 개미든 마지막에는 자기가 있는 칸의 설탕 한 단위를 모으고, 점수는 모든 개미가 모은 설탕 값의 합이다.

개미는 남은 시간보다 먼 칸으로 복제하지 못하고, 같은 칸에 두 번 복제하지 않으며, 자기가 있는 칸으로도 복제하지 않는다. 한 칸에 개미가 몇 마리 있어도 상관없다.

그러면 개미는 어떤 칸으로 복제할 수 있는가? 먼저 격자 밖으로는 복제하지 못한다. 그리고 자기 위치에서 뻗어 나가는 8개 방향 벡터 위의 칸으로만 복제할 수 있다. 방향 벡터는 한 방향으로 계속 이어지는 칸 전체를 말한다. 예를 들어 $(A, B)$에서 동쪽 벡터는 $(A, B+1)$, $(A, B+2)$, $(A, B+3)$처럼 이어진다. 남은 시간이 2초인 슈퍼 개미라면 거리가 1인 8칸과 거리가 2인 8칸, 모두 16칸으로 복제할 수 있다.

각 칸에 있는 설탕 한 단위의 점수, 쓸 수 있는 전체 시간, 첫 슈퍼 개미가 출발할 칸이 주어진다. 그 칸을 골랐을 때 얻는 점수를 구하라. 시간은 첫 개미를 놓는 순간부터 흐른다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100$)

각 테스트 케이스의 첫 줄에는 격자의 행 개수 $N$, 열 개수 $M$, 남은 시간 $S$가 공백 하나로 구분되어 주어진다. ($1 \le N, M \le 50$, $0 \le S \le 500$)

다음 줄에는 첫 개미가 출발할 칸의 행 번호 $I$와 열 번호 $J$가 공백 하나로 구분되어 주어진다. ($1 \le I \le N$, $1 \le J \le M$)

이어지는 $N$개의 줄에는 줄마다 $M$개의 정수가 공백 하나로 구분되어 주어진다. 이 값은 그 행에 있는 각 칸의 설탕 한 단위의 점수이며, $0$보다 작지 않고 $9$보다 크지 않다.

각 테스트 케이스마다 게임이 끝났을 때 얻는 점수를 한 줄에 정수 하나로 출력한다. 결과가 매우 커질 수 있으므로 $10^9 + 7$, 즉 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력의 첫 번째 테스트 케이스에서는 첫 개미가 자기 칸에서 점수 5인 설탕 한 단위를 모으고, 8개 방향으로 개미 8마리를 복제한다. 복제된 개미는 남은 시간이 없어서 각자 자기 칸의 설탕 한 단위만 모은다. 그래서 점수는 $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45$이다.

두 번째 테스트 케이스에서는 첫 개미가 거리 2인 8칸으로는 남은 시간이 0인 개미를, 거리 1인 8칸으로는 남은 시간이 1인 개미를 복제한다. 뒤쪽 8마리는 각자 다시 복제한다.