小红的网格路径 II

题号：NC317543
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个 $n \times m$ 的网格，小红初始位于左上角 $(1,1)$ ，目标是到达右下角 $(n,m)$ 。

$\hspace{15pt}$ 每次她可以向上、向下或向右移动一格，不能走出网格，也不能经过同一个格子两次。

$\hspace{15pt}$ 现在有 $k$ 个格子不可经过。请你求出，从 $(1,1)$ 走到 $(n,m)$ 的方案数。

$\hspace{15pt}$ 由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模后的结果。

$\hspace{15pt}$ 保证所有不可经过的格子两两不同，并且每一列中至多有一个不可经过的格子。

第一行输入三个整数 （，）。
接下来  行，每行输入两个整数 （，），表示格子  不可经过。
保证每一列中至多有一个不可经过的格子。
保证起点和终点都不是不可经过的格子。

输出一个整数，表示方案数对  取模后的结果。

示例1

复制

3 4 2
2 2
2 4

复制

第  列和第  列的第  行都不可经过。
由于路径不能向左，也不能重复经过格子，因此每一列中实际经过的格子一定形成一段连续区间。结合两个禁点的位置，可以算出本题共有  种合法方案。