当前没有测试数据。

必经节点的路径计数

题目描述

考古队在沙漠古城布置了多处补给站，整个区域被划成 $n\times m$ 的方格。队伍从入口 $(1,1)$ 出发，只能向右或向下行进到出口 $(n,m)$。地图上有两处必须经过的遗迹点 $(x_1,y_1)$ 与 $(x_2,y_2)$，行进顺序固定为先到达第一处，再去第二处，最后离开古城。部分格子被流沙吞没无法踏入。请计算满足要求的不同走法数量，结果对 $10^9+7$ 取模。

输入格式

第一行包含两个整数 $n,m$，表示区域的行数与列数。

第二行包含四个整数 $x_1,y_1,x_2,y_2$，表示两处必须经过的遗迹坐标（均为 $1$ 开始编号）。

接下来 $n$ 行，每行包含 $m$ 个整数，$0$ 表示可通行，$-1$ 表示流沙禁区。

起点、终点及两处遗迹保证不在流沙上。

输出格式

输出一个整数，表示合法走法数量对 $10^9+7$ 取模的结果；若不存在合法路线，输出 $0$。

输入输出样例 #1

输入 #1

4 4
2 2 3 3
0 0 0 0
0 0 -1 0
0 0 0 0
0 -1 0 0

输出 #1

4

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 200$。EOF