走出迷宫的方法数2
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
有一个 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 22Hint
数据约束
对 50% 的数据：2 <= n, m <= 100, 1 <= k <= 100
对 100% 的数据：2 <= n, m <= 1000, 1 <= k <= 10000
