棋盘上卒的走法（有陨石坑）

题目描述

在一张大小为 $n \times m$ 的棋盘上，左上角格子记为 $(1,1)$，右下角格子记为 $(n,m)$。
现在在 $(1,1)$ 有一个卒，它每一步只能向右或向下移动一格。

棋盘上有一些格子被陨石砸出坑，卒不能经过这些格子。

给定棋盘大小以及所有陨石坑的位置，问：从 $(1,1)$ 走到 $(n,m)$，一共有多少种不同的走法？
如果无法到达，输出 $0$。

输入格式

第一行包含三个整数 $n,m,k$，表示棋盘的行数、列数和陨石坑的数量。
接下来 $k$ 行，每行包含两个整数 $x,y$，表示第 $x$ 行第 $y$ 列的格子被陨石砸中，不能经过。

保证起点 $(1,1)$ 和终点 $(n,m)$ 不会是陨石坑，输入中不会出现重复的坑位。

输出格式

输出一行，一个整数，表示不同走法的数量。

输入输出样例 #1

输入 #1

3 3 1
2 2

输出 #1

2

样例解释

原本从 $(1,1)$ 到 $(3,3)$ 有 $6$ 种走法，但因为中间格子 $(2,2)$ 被砸出陨石坑，不能经过，剩下 $2$ 条合法路径。

数据范围

对于 $100\%$ 的数据，保证：

• $1 \le n,m \le 30$；
• $0 \le k \le n \times m - 2$。

答案不超过 $64$ 位有符号整数范围。