配点: 100 点
問題
太郎居住的JOI城,从北向南笔直延伸。 a 一条真正的从东向西笔直延伸的道路。 b 道路被分成棋盘形状的部分。
南北方向 a 在主要道路上,有 它的编号为 1, 2, \ldots, a 。另外,在东西方向 b 在主要道路上,有 它的编号为 1, 2, \ldots, b 。从西边来 i 南北向南路 j 东西路交叉口 由 (i, j) 代表。
太郎君在十字路口(1, 1),我住在十字路口附近( 我骑自行车去a, b附近的JOI高中。自行车只能沿着道路行驶。太郎只往东边或北边通勤,以缩短通勤时间。
目前,在JOI City,n 交叉路口 (x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) 正在进行施工。太郎无法通过正在施工的十字路口。
太郎在路口 (1, 1) 到交叉路口 (a, b) 只向东或向北行驶,同时避开正在建设的十字路口,有多少种方法可以去学校?太郎君的学路数 编写一个程序来查找 m 。
入力
输入 1 行由空格分隔。 写入 2 整数 给出了 a, b 。这代表南北方向的道路数量和东西方向的道路数量。a, b 是 1 \leqq a, b \leqq 16 满意。
2 行包含一个整数,表示正在建设的交叉口数量。 写入 n 。n 是 1 \leqq n \leqq 40 满意。
继续 n 行 (3 从行 n + 2 线)表示正在施工的路口位置。i + 2 行包含由空格分隔的整数 写入 x_i, y_i ,并且交集 (x_i, y_i) 正在建设中。x_i, y_i 是 1 \leqq x_i, y_i \leqq 16 满意。
出力
输出是太郎的通勤路线的数量。 仅包含 m 由 1 行组成。
入力例 1
5 4 3 2 2 2 3 4 2
出力例 1
5
下图是 a = 5, b = 4, n = 3 ,正在建设中的十字路口 它代表 (2, 2), (2, 3), (4, 2) 的情况。

在这种情况下,学校路线是 m = 5 方法有很多。5 到学校的整个路线如下所示。
