题目描述

迷宫研究是一个古老而有趣的领域，迷宫是人类智慧的结晶之一，早在古代就被广泛应用于建筑设计、游戏和神秘的仪式中。

在这个背景中，我们面临的问题是，有一个迷宫，由 $N \times M$ 个方格组成，其中包含 $T$ 处障碍物。在迷宫中可以上下左右四个方向移动，每次只能移动一个方格并且不能穿过障碍物。

现在我们需要从给定的起点坐标出发，找到一条路径到达终点坐标。路径必须遵循以下规则：

• 路径只能经过迷宫中的空白方格，不能经过障碍物。
• 每个方格最多只能经过一次，即不能重复经过同一个方格。

我们的目标是确定从起点到终点的所有可能路径的数量。

输入格式

第一行为三个正整数 $N, M, T$，分别表示迷宫的行数、列数和障碍物总数。

第二行为四个正整数 $x_1, y_1, x_2, y_2$，其中 $(x_1, y_1)$ 代表起点坐标，$(x_2, y_2)$ 代表终点坐标。

接下来 $T$ 行，每行两个正整数，表示一个障碍物的坐标。

注意：坐标 $(x, y)$ 中，$x$ 表示行号，$y$ 表示列号（$1 \le x \le N$，$1 \le y \le M$）。

输出格式

输出一个整数，表示从起点坐标到终点坐标的不同路径方案总数。

输入输出样例

输入 #1

2 2 1
1 1 2 2
1 2

输出 #1

1

说明/提示

样例 1 解释

迷宫大小为 $2 \times 2$，障碍物在 $(1, 2)$。

起点 $(1, 1)$，终点 $(2, 2)$。

唯一可行的路径为：$(1,1) \to (2,1) \to (2,2)$，因此输出 $1$。

数据范围

• 对于所有测试点，$0 \le N, M, T \le 10$。
• 坐标在合法范围内。
• 特殊性质：出发点可能在障碍物上，并且可以走出来（即若起点是障碍物，仍视为可从该点出发，且该点不计入“经过的空白方格”限制中的障碍）。