题目描述

有一个 $n \times m$ 的矩阵迷宫，其中有 $k$ 个位置有障碍，障碍位置无法通过。从 $(1,1)$ 点出发，每次只能向下或者向右行走，请问走到 $(n,m)$ 点有多少种不同的方法。

输入格式

第一行有三个整数 $n, m, k$，分别表示迷宫的行数、列数和障碍个数。

接下来 $k$ 行，每行两个整数 $x_i, y_i$，表示一个障碍物的位置。保证障碍物不会在起点或终点。

输出格式

一行一个整数，表示总方法数（数据类型用 int，默认可能发生溢出）。

样例

3 3 1
2 2

2

数据范围

• 对于 $50\%$ 的数据：$2 \le n, m \le 100$，$1 \le k \le 100$。
• 对于 $100\%$ 的数据：$2 \le n, m \le 1000$，$1 \le k \le 10000$。