P14435 [JOISC 2013] 收拾吉祥物 / Mascots

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$ 取模后的结果。

### 样例 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 完成