题目描述

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

输入格式

第 1 行有 3 个整数 n、m、k（2 <= n m <= 1000 1 <= k <= 10000）

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

输出格式

输出 1 个整数，表示总方法数

（数据类型用 int，默认发生溢出）

样例

输入

3 3 1

输出

2 2
2

提示

数据约束

对 50% 的数据：2 <= n m <= 100 1 <= k <= 100

对 100% 的数据：2 <= n m <= 1000 1 <= k <= 10000