Migrated from Lutece 3145 激流勇进

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一场大雨让清水河校区的道路都变成了河。Tri17 把他上学期喝完的几百个可乐瓶组装成了一艘小船，从而应对雨天赶路慢上早八会迟到的情况。

学校的地图可以简化为一个矩形，含有 $n*m$ 个位置。每个位置存在着不同的积水高度。Tri17 的可乐瓶小船每次可以向相邻的四个方向行驶，并且只能在当前位置积水高度比相邻位置高出$h$的时候才能向该相邻位置转移。如果高度差小于 $h$ ，将无法提供足够的重力势能保持小船行驶，大于 $h$ 则会由于船速过快导致可乐瓶散架。

如果一条路线不被其他路线包含（即起点和终点无法再延伸），不经过无积水位置且长度至少为 $k$ ，则认为这条路线可以满足划船需求。

现在他想知道，校区内总共有多少条路线能满足他划船的需求。

Input

第一行输入四个正整数 $n,m,h,k$ ，分别表示学校地图的规模，允许转移的高度差和满足需求路线最短长度。

接下来 $n$ 行 $m$ 列依次输入每个位置的积水高度，无积水位置的高度用 $-1$ 表示。

Output

输出满足需求的路线数对 $10^9+7$ 取模的结果。

Samples

4 2 2 4
1 7
3 5
1 7
-1 -1

4

5 5 1 2
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

24

Constraints

$1 \le n,m \le 1000,2 \le k \le 10,1\le h,a_{i,j} \le 10^9$

Note

对于样例1，存在四条路线： $(1,2)\rightarrow(2,2)\rightarrow(2,1)\rightarrow(1,1)$ $(1,2)\rightarrow(2,2)\rightarrow(2,1)\rightarrow(3,1)$ $(3,2)\rightarrow(2,2)\rightarrow(2,1)\rightarrow(1,1)$ $(3,2)\rightarrow(2,2)\rightarrow(2,1)\rightarrow(3,1)$

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming