题目描述

一个机器人在 $n \times m$ 的迷宫中，从左上角 $(1,1)$ 走到右下角 $(n,m)$。每一步只能向右或向下走。

迷宫中每个格子有两个属性：时间消耗 $t_{i,j}$ 和能量消耗 $e_{i,j}$。

机器人有总时间限制 $T$ 和总能量限制 $E$。求在限制内能到达终点的路径数量。

输入格式

第一行四个整数 $n, m, T, E$。

接下来 $n$ 行，每行 $m$ 个整数，表示时间消耗矩阵。

接下来 $n$ 行，每行 $m$ 个整数，表示能量消耗矩阵。

输出格式

输出一个整数，表示路径数量（对 $10^9+7$ 取模）。

输入输出样例 #1

输入 #1

样例

输入

2 2 10 10
1 2
3 4

输出

2 1
3 2

输出 #1

2

说明/提示

样例解释：两条路径：(1,1)→(1,2)→(2,2) 时间=1+2+4=7, 能量=2+1+2=5；(1,1)→(2,1)→(2,2) 时间=1+3+4=8, 能量=2+3+2=7。两条都满足限制。

数据范围

• $1 \le n, m \le 50$
• $1 \le T, E \le 500$
• $1 \le t_{i,j}, e_{i,j} \le 20$