题目描述

Aki 在一张 $n \times m$ 的棋盘左上角，坐标记为 $(1,1)$。他的目标是走到右下角 $(n,m)$。

在任意时刻，他只能执行下面两种移动之一：

• 向下走一格；
• 向右走一格。

棋盘中有若干个障碍格，不能进入。题目保证起点 $(1,1)$ 和终点 $(n,m)$ 都不是障碍格。

请你计算：从起点走到终点一共有多少条不同的合法路径。由于答案可能很大，请对 $10^9+7$ 取模后输出。

输入格式

第一行输入三个整数 $n,m,k$，表示棋盘大小以及障碍格数量。
接下来 $k$ 行，每行两个整数 $x,y$，表示格子 $(x,y)$ 是障碍格。
数据范围：

• $1 \le n,m \le 200$
• $0 \le k \le n\times m-2$

输出格式

输出一行，一个整数，表示合法路径条数对 $10^9+7$ 取模后的结果。

3 3 2
2 2
3 2

1