题目描述

JOI 酱正在和朋友玩吉祥物。快乐的时光转瞬即逝，朋友离开后，现在到了收拾整理的时间。

JOI 酱拥有 $R \times C$ 个吉祥物，收拾时使用一个由 $R$ 行 $C$ 列方格组成的长方形区域。每个方格放置一个吉祥物。从上数第 $A$ 行、从左数第 $B$ 列的方格记作 $(A, B)$。整理开始时，已有 $N$ 个方格放置了吉祥物。开始整理时，至少存在一个未放置吉祥物的方格。

JOI 酱逐个放置吉祥物进行整理。当新放置一个吉祥物后，所有有吉祥物的方格恰好构成一个完整的长方形时（排除初始状态已有吉祥物的方格本身就构成一个长方形的情况），JOI 酱会感到 小确幸。所谓所有有吉祥物的方格构成一个完整的长方形，是指存在四个整数 $r_1, r_2, c_1, c_2$（$1 \leq r_1 \leq r_2 \leq R$ 且 $1 \leq c_1 \leq c_2 \leq C$），使得对于所有满足 $r_1 \leq i \leq r_2$ 且 $c_1 \leq j \leq c_2$ 的方格 $(i, j)$ 上都有吉祥物，并且其他任何方格上都没有吉祥物。感到 小确幸 的次数越多，JOI 酱今晚就能睡得越香甜。

放置吉祥物时，不区分所放吉祥物的种类。请问，使得 小确幸 次数最大的放置方式共有多少种？

任务

给定收拾吉祥物的区域信息以及初始已放置吉祥物的信息，编写程序计算使得 小确幸 次数最大的放置方式的数量，并对 $1\,000\,000\,007$ 取模后的结果。

输入格式

从标准输入读取以下输入数据：

• 第 $1$ 行包含两个以空格分隔的整数 $R, C$。$R$ 表示放置吉祥物区域的行数，$C$ 表示列数。
• 第 $2$ 行包含一个整数 $N$。$N$ 表示整理开始时已放置吉祥物的数量。
• 后续 $N$ 行描述初始已放置吉祥物的信息。第 $i$ 行包含两个以空格分隔的整数 $A_i, B_i$，表示方格 $(A_i, B_i)$ 在初始时已放置吉祥物。这些数对互不重复。

输出格式

向标准输出输出可能的放置方式的数量对 $1\,000\,000\,007$ 取模后的结果。

2 3
2
1 2
2 2

8

3 3
2
1 1
3 3

5040

提示

样例 1 解释

初始状态下，$6$ 个方格的状态如下（△ 表示初始时已放置吉祥物的方格）：

:::align{center} :::

在 $6$ 个方格中，$(1, 2)$ 和 $(2, 2)$ 已放置吉祥物。小确幸 次数的最大值为 $2$。

使得 小确幸 次数达到 $2$ 次的放置方式有以下 $8$ 种（数字表示新放置吉祥物的顺序）：

:::align{center} :::

在所有这些 $8$ 个示例中，放置第 $2$ 个吉祥物后有吉祥物的方格构成一个 $2 \times 2$ 的长方形，放置第 $4$ 个吉祥物后有吉祥物的方格构成一个 $2 \times 3$ 的长方形，整个过程 JOI 酱总共感到 $2$ 次 一点幸福。

限制

所有输入数据满足以下条件：

• $2 \leq R \leq 3\,000$
• $2 \leq C \leq 3\,000$
• $1 \leq N \leq 100\,000$

子任务

子任务 1 [10 分]

满足以下条件：

• $R \leq 3$
• $C \leq 3$

子任务 2 [30 分]

满足以下条件：

• $R \leq 50$
• $C \leq 50$

子任务 3 [60 分]

无额外限制。

翻译由 DeepSeek V3 完成