400909: GYM100283 C Tomb Raiders

Egypt is full of hidden treasures (tombs, golden statues ...), and many thieves (called tomb raiders) are searching to steal them. To find the location of these treasures you need a good knowledge of the area. The police needed some honest young people to help them with guidance in exploring these areas.

Mashrat - the most dangerous thief in the city - wants to retire robbery and spend the rest of his life relaxing on a luxury island as he got old and tired from being wanted. He wants to make a big treasures robbery as his last mission that will secure money for his plans.

As we remember when the city needed to pave its roads; Bakkar & Hassona helped the governor to estimate the roads' pavement costs, leaving a very positive impression on the governor. Once the governor knew that the police needed some help from young people from the city, he didn't hesitate to introduce Bakkar & Hassona to the chief police officer. The chief police officer gave them a little introduction about the thieves they are chasing and the area they are planning to rob.

The area that Mashrat is planning to rob can be represented as a grid, with N rows and M columns. In the beginning, Mashrat starts at position (p_i, p_j) which means he starts at the cell in the p_ith row and p_jth column (all positions are 1-based).

Mashrat and his gang heard that the police is coming after S time units and they want to finish before they arrive. But thieves are lazy, they don't want to do any work unless it's too late. A thief will hire other thieves to search for him if there is more than 1 time unit left, and he will pay for them later a percentage of the treasures they bring back to him (don't worry, thieves never betray each other!). A thief at position (i, j) with t time units left (t > 1), will hire a thief for every grid cell (x, y) that satisfies |i - x| + |j - y| < t, (i.e. Manhattan distance). Note that (x, y) can be equal to (i, j). Hiring thieves takes 1 time unit (1 time unit for all the thieves hired not for each), and original thief does nothing from now on, and waits for the hired thieves to return with the treasures in the end. There can be multiple thieves at the same cell working in parallel.

All the thieves including Mashrat follow the above behavior until they have 1 time unit left. At this time, they do not hire anymore, and quickly dig the ground looking for treasures. A thief standing on cell (i, j) will dig up G[i][j] worth of treasure (even if multiple thieves are on the same cell, each will get G[i][j]).

The Egyptian Police guided by Bakkar & Hassona arrived very fast and caught them before they left the site (Mashrat future plans are now all ruined up; they had to share the treasure on the spot, didn't they??). The police are suspecting that the thieves have hidden some of the treasures before they arrived and again asked for Bakkar & Hassona's help. As computer geeks, Bakkar & Hassona are required to calculate the total value of stolen treasure by all thieves. Since the value can be very large, the police only want it modulo 1,000,000,007.

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  100). Followed by T test cases.

Each test case start with five integers separated by a single space N, M, S, p_i, p_j, the number of rows, the number of columns, the time till the police arrives, and the position of Mashrat. (1  ≤  N,M,S  ≤  100, 1  ≤  p_i  ≤  N, 1  ≤  p_j  ≤  M).

N lines follow, each with M non-negative integers, representing the values in G. The values in each cell will not be more than 10,000.

For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by a single space, then a single integer representing the total value of treasures stolen modulus 1,000,000,007.

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

Case 1: 29

Test Case Explanation:

At the beginning there is only one thief at cell (3,2) but since he still have 2 time units left, he hires 4 thieves at positions (3,1), (2,2), (3,2), (3,3) (where distance is < 2). He doesn't hire at position (4,2) because its outside the grid. Now there is only 1 time unit left so each thief digs up the treasures giving a total of G[3][1] + G[2][2]+ G[3][2] + G[3][3] = 7 + 5 + 8 + 9 = 29