题目背景
翻译自 ROIR 2025 D2T4。
题目描述
一群学生来到一座新城市游览,决定参观这里的名胜古迹。这座城市可以看作一个 n×m 的矩形网格,其中某些格子上有景点。
他们从格子 (1,1) 开始旅程,想要先到达格子 (n,m),然后再返回起点。此外,城市中有 k 个景点,位于格子 (x1,y1),…,(xk,yk),他们一定要全部参观到。

他们可以花费一分钟从格子 (a,b) 移动到与之相邻(即满足 ∣a−c∣+∣b−d∣=1)的格子 (c,d)。显然,完成整个路线至少需要 2n+2m−4 分钟。
我们称一条路线为“有趣的”,如果它满足以下条件:
- 完成该路线所需的时间恰好是 2n+2m−4 分钟;
- 路线中的每个格子最多经过一次;
- 路线必须经过所有包含景点的格子。
请帮助他们计算一共有多少条不同的有趣的路线。由于结果可能很大,只需要输出其对 109+7 取模的结果。
输入格式
第一行输入三个整数 n,m 和 k(3≤n,m≤106,0≤k≤2000)。
接下来 k 行,每行包含两个整数 xi 和 yi(1≤xi≤n,1≤yi≤m)。保证所有的 (xi,yi) 都是不同的,即 ∀(i,j),xi=xj∨yi=yj。
输出格式
输出一个整数,表示有趣的路线的数量对 109+7 取模的结果。
3 4 2
2 2
2 3
6
3 4 3
3 1
2 3
1 4
0
提示
下图展示了样例一中所有有趣的路线,其中带有星号的格子存在名胜古迹。

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。
子任务 |
分数 |
特殊性质 |
1 |
5 |
n=3,m,k≤100 |
2 |
9 |
n,m,k≤5 |
3 |
6 |
n,m,k≤8 |
4 |
17 |
n,m,k≤30 |
5 |
16 |
n,m,k≤100 |
6 |
8 |
k=0 |
7 |
11 |
k=1 |
8 |
12 |
k≤16 |
9 |
k≤100 |
10 |
7 |
无 |