题目描述
在一个由 $n\times m$ 个方格构成的图中，有 $k$ 个方格是禁止进入的。请计算从左上角 $(1,1)$ 出发，每步朝右方或下方移动，不经过禁入的方格，最后到达右下角 $(n,m)$ 的路径条数。由于答案很大，输出模 $1,000,000,007$ 的余数。
输入
第一行：三个正整数表示 $n$，$m$ 与 $k$。
第二行到第 $n+1$ 行：第 $i+1$ 行表示一个禁入方格的坐标 $(x_i,y_i)$。保证 $(x_i,y_i)$ 不会等于 $(1,1)$ 或 $(n,m)$，也不会有一个坐标重复出现两次。
输出
单个自然数：表示路径数模 $1,000,000,007$ 的余数。
样例输入输出
输入#2
复制
100000 100000 4
50001 50001
50000 50000
50000 50001
50001 50000
提示
+ 对于 $30\%$ 的数据，$0\leq k\leq 200$；
+ 对于 $60\%$ 的数据，$0\leq k\leq 1500$；
+ 对于 $100\%$ 的数据，$0\leq k\leq 3000$；
+ $1\leq n,m\leq 10^5$。