#P11704. [ROIR 2025] 旅行路线

[ROIR 2025] 旅行路线

题目背景

翻译自 ROIR 2025 D2T4

题目描述

一群学生来到一座新城市游览,决定参观这里的名胜古迹。这座城市可以看作一个 n×mn \times m 的矩形网格,其中某些格子上有景点。

他们从格子 (1,1)(1, 1) 开始旅程,想要先到达格子 (n,m)(n, m),然后再返回起点。此外,城市中有 kk 个景点,位于格子 (x1,y1),,(xk,yk)(x_1, y_1), \dots, (x_k, y_k),他们一定要全部参观到。

原题一个不明觉厉的配图

他们可以花费一分钟从格子 (a,b)(a, b) 移动到与之相邻(即满足 ac+bd=1|a - c| + |b - d| = 1)的格子 (c,d)(c, d)。显然,完成整个路线至少需要 2n+2m42n + 2m - 4 分钟。

我们称一条路线为“有趣的”,如果它满足以下条件:

  • 完成该路线所需的时间恰好是 2n+2m42n + 2m - 4 分钟;
  • 路线中的每个格子最多经过一次;
  • 路线必须经过所有包含景点的格子。

请帮助他们计算一共有多少条不同的有趣的路线。由于结果可能很大,只需要输出其对 109+710^9 + 7 取模的结果。

输入格式

第一行输入三个整数 nnmmkk3n,m1063 \leq n, m \leq 10^60k20000 \leq k \leq 2000)。

接下来 kk 行,每行包含两个整数 xix_iyiy_i1xin1 \leq x_i \leq n1yim1 \leq y_i \leq m)。保证所有的 (xi,yi)(x_i, y_i) 都是不同的,即 (i,j),xixjyiyj\forall (i, j), x_i \neq x_j \vee y_i \neq y_j

输出格式

输出一个整数,表示有趣的路线的数量对 109+710^9 + 7 取模的结果。

3 4 2
2 2
2 3
6
3 4 3
3 1
2 3
1 4
0

提示

下图展示了样例一中所有有趣的路线,其中带有星号的格子存在名胜古迹。

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。

子任务 分数 特殊性质
11 55 n=3n=3m,k100m, k \leq 100
22 99 n,m,k5n, m, k \leq 5
33 66 n,m,k8n, m, k \leq 8
44 1717 n,m,k30n, m, k \leq 30
55 1616 n,m,k100n, m, k \leq 100
66 88 k=0k=0
77 1111 k=1k=1
88 1212 k16k \leq 16
99 k100k \leq 100
1010 77