题目描述

题目译自 JOISC 2013 Day2 T2 「マスコットの片付け」

JOI 酱刚刚和朋友们一起玩了吉祥物玩偶，欢乐的时光转瞬即逝，朋友们离开后，现在到了收拾的时候。

JOI 酱拥有 $R \times C$ 个吉祥物玩偶，收拾时使用一个由纵向 $R$ 行、横向 $C$ 列方格组成的矩形区域。每个方格可以放置一个玩偶。我们将上数第 $A$ 行、左数第 $B$ 列的方格记为 $(A, B)$。在收拾开始时，已经有 $N$ 个玩偶放置在某些方格上，且至少有一个方格是空的。

JOI 酱会逐个放置剩余的玩偶。每当放置一个新玩偶后，若所有有玩偶的方格恰好组成一个矩形，她就会感到一丝小小的幸福（初始状态下有玩偶的方格已组成矩形的情况除外）。所谓“有玩偶的方格恰好组成一个矩形”，是指存在 $4$ 个整数 $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 酱感受到的小幸福次数越多，她今晚就能睡得越香。

在放置玩偶时，不区分玩偶的种类。你需要计算，JOI 酱能感受到最多小幸福次数的放置方式有多少种。

给定收拾玩偶的区域和已放置玩偶的信息，你需要编写一个程序，计算能让 JOI 酱感受到最多小幸福次数的玩偶放置方式的数量，并输出其对 $1000000007$ 取余的结果。

输入格式

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

• 第一行包含两个整数 $R, C$，用空格分隔，$R$ 表示收拾区域的行数，$C$ 表示列数。
• 第二行包含一个整数 $N$，表示开始收拾时已放置的玩偶数量。
• 接下来 $N$ 行中，第 $i$ 行包含两个整数 $A_{i}, B_{i}$，用空格分隔，表示方格 $(A_{i}, B_{i})$ 上初始已放置玩偶。这些坐标对不会重复。

输出格式

在标准输出中输出一行一个整数，表示可能放置方式的数量对 $1000000007$ 取余的结果。

2 3
2
1 2
2 2

8

初始状态下，$6$ 个方格的情况如下（$\triangle$ 表示初始已放置玩偶的方格）。

其中方格 $(1,2)$ 和 $(2,2)$ 已放置玩偶。小幸福次数的最大值为 $2$。能达到 $2$ 次小幸福的放置方式共有 $8$ 种（数字表示新放置玩偶的顺序）。

在上述 $8$ 种情况中，每次放置第 $2$ 个玩偶时，有玩偶的方格组成 $2 \times 2$ 的矩形；放置第 $4$ 个玩偶时，有玩偶的方格组成 $2 \times 3$ 的矩形，JOI 酱总共感受到 $2$ 次小幸福。

3 3
2
1 1
3 3

5040

无论按何种顺序放置玩偶，小幸福次数均为 $1$ 次。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq R \leq 3000$
• $2 \leq C \leq 3000$
• $1 \leq N \leq 100000$

详细子任务附加限制及分值如下表所示。