AT_joi2007yo_f.通学経路

太郎君居住的 JOI 市由 $a$ 条南北方向的道路和 $b$ 条东西方向的道路组成，形成了一个棋盘格状的街区。

南北方向的 $a$ 条道路从西向东依次编号为 $1, 2, \ldots, a$。东西方向的 $b$ 条道路从南向北依次编号为 $1, 2, \ldots, b$。西边第 $i$ 条南北道路与南边第 $j$ 条东西道路的交点记作 $(i, j)$。

太郎君住在交点 $(1, 1)$ 附近，每天骑自行车去位于交点 $(a, b)$ 附近的 JOI 高中。自行车只能沿着道路行驶。为了缩短通学时间，太郎君只会向东或向北前进。

现在，JOI 市有 $n$ 个交点正在施工，分别为 $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$。太郎君不能经过正在施工的交点。

请编写程序，计算太郎君从 $(1, 1)$ 出发，只能向东或向北前进，并且不经过施工交点，到达 $(a, b)$ 的通学路线有多少条。输出通学路线的总数 $m$。

输入的第 $1$ 行包含用空格分隔的两个整数 $a, b$，分别表示南北方向和东西方向的道路数量。$1 \leq a, b \leq 16$。

第 $2$ 行包含一个整数 $n$，表示正在施工的交点数量。$1 \leq n \leq 40$。

接下来的 $n$ 行（第 $3$ 行到第 $n+2$ 行），每行包含两个用空格分隔的整数 $x_i, y_i$，表示施工交点的位置。$1 \leq x_i, y_i \leq 16$。

输出仅一行，包含太郎君的通学路线总数 $m$。

样例解释 1

下图为 $a=5, b=4, n=3$，施工交点为 $(2, 2), (2, 3), (4, 2)$ 的情况。

此时，通学路线共有 $m=5$ 条。所有 $5$ 条路线如下图所示。

由 ChatGPT 4.1 翻译