题目描述

给定一个 $N*M$ 方格的迷宫，迷宫里有 $T$ 处障碍，障碍处不可通过。给定起点坐标和终点坐标，问：每个方格最多经过 $1$ 次，请输出从起点到终点的所有可行方案数量。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

输入格式

第一行 $N$、$M$ 和 $T$，其中 $N$ 为行，$M$ 为列（最多 $10$ 行 $10$ 列），$T$ 为障碍总数。

第二行起点坐标 $SX$，$SY$，终点坐标 $EX$，$EY$。

接下来T行，每行为障碍点的坐标。

输出格式

从起点到终点的路径方案数量。

样例

3 3 1
1 1 3 3
2 2

2

3 3 2
1 1 3 3
2 3
3 2

0