P11704 [ROIR 2025] 旅行路线
题目背景
翻译自 [ROIR 2025 D2T4](https://neerc.ifmo.ru/school/archive/2024-2025/ru-olymp-regional-2025-day2.pdf)。
题目描述
一群学生来到一座新城市游览，决定参观这里的名胜古迹。这座城市可以看作一个 $n \times m$ 的矩形网格，其中某些格子上有景点。
他们从格子 $(1, 1)$ 开始旅程，想要先到达格子 $(n, m)$，然后再返回起点。此外，城市中有 $k$ 个景点，位于格子 $(x_1, y_1), \dots, (x_k, y_k)$，他们一定要全部参观到。
他们可以花费一分钟从格子 $(a, b)$ 移动到与之相邻（即满足 $|a - c| + |b - d| = 1$）的格子 $(c, d)$。显然，完成整个路线至少需要 $2n + 2m - 4$ 分钟。
我们称一条路线为“有趣的”，如果它满足以下条件：
- 完成该路线所需的时间恰好是 $2n + 2m - 4$ 分钟；
- 路线中的每个格子最多经过一次；
- 路线必须经过所有包含景点的格子。
请帮助他们计算一共有多少条不同的有趣的路线。由于结果可能很大，只需要输出其对 $10^9 + 7$ 取模的结果。
输入格式
无
输出格式
无
说明/提示
下图展示了样例一中所有有趣的路线，其中带有星号的格子存在名胜古迹。
本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。
|子任务|分数|特殊性质|
|:-:|:-:|:-:|
|$1$|$5$|$n=3$，$m, k \leq 100$|
|$2$|$9$|$n, m, k \leq 5$|
|$3$|$6$|$n, m, k \leq 8$|
|$4$|$17$|$n, m, k \leq 30$|
|$5$|$16$|$n, m, k \leq 100$|
|$6$|$8$|$k=0$|
|$7$|$11$|$k=1$|
|$8$|$12$|$k \leq 16$|
|$9$|$9$|$k \leq 100$|
|$10$|$7$|无|$