INSPECTOR CHAUHAN and his team is trapped in a rectangular battlefield which is full of land mines.He and his team wants to escape the battlefield with minimum risk.INSPECTOR CHAUHAN is carrying a secret map with him,the map consists of N x M matrix, each cell A(i,j) of it denotes the number of land mines in that particular region.They are currently standing at position (1,1) and they want to reach (N,M).At every step INSPECTOR CHAUHAN can order his team to move forward to adjacent cell ( i.e. from A(i,j) to A(i+1,j) or A(i,j+1) ).However the map is scaled so its a very difficult task to find the minimum risk on his way.

INSPECTOR CHAUHAN being very GEEKY figured out an algorithm to calculate it,which is as follows :-

1- Find the minimum risk paths from source to destination (there can be multiple paths) on the map.

2- Risk associated with each path is defined as the summation of land mines encountered during the walk from source to destination using that path.

3- Max_Risk=(Minimum Risk)x(Number of minimum risk paths)x(Team Size).

Now repeat step 4 to 5 for every minimum risk path Q.

4- Form a Path array P from Q by repeating each element of Q,S (scaling factor) number of times.For example if Q[]={1,2,3,4} and S=3 then P[]={1,1,1,2,2,2,3,3,3,4,4,4}.

5- Find the value of Average_Risk (here n is the size of path array).

Actual Minimum Risk is the summation of the Average_Risk of all the minimum risk path. You are assingned a task to implement the above algorithm and give the desired result.As answer could be large, calculate value modulo 1000000007.

INPUT:-

The first line contains four integers n,m,s,t denoting Rows,Columns,Scaling factor and Team size(including INSPECTOR CHAUHAN) respectively.

Each of the next n lines contains m integers,jth integer in ith line denotes the value of** A(i,j).**

OUTPUT:-

Output a single line containing Actual Minimum Risk modulo 1000000007.

Constraints:-

1 < n,m < 10

1 <= A(i,j) <= 10^7

1 <= s <= 90

1 <= t <= 10^18

1 <= Max_Risk <= 10^18