JOI 酱和朋友们一起玩吉祥物。快乐的时光总是过得很快，朋友们回家后，现在是收拾整理的时间了。

JOI 酱拥有 $R \times C$ 个吉祥物，整理时使用一个纵向 $R$ 行、横向 $C$ 列的矩形区域。每个格子里可以放置 1 个吉祥物。我们将从上往下第 $A$ 行、从左往右第 $B$ 列的格子表示为 $(A, B)$。在开始整理时，已经有 $N$ 个吉祥物被放置在格子里了。开始整理时，至少有一个格子是没有放置吉祥物的。

JOI 酱一个一个地放置吉祥物进行整理。每当新放置一个吉祥物时，如果所有放置了吉祥物的格子恰好构成一个矩形，JOI 酱就会感到“小确幸”（初始状态下所有吉祥物已经构成一个矩形的情况除外）。所谓所有放置了吉祥物的格子构成一个矩形，是指存在 4 个整数 $r_1, r_2, c_1, c_2$ ($1 \le r_1 \le r_2 \le R$ 且 $1 \le c_1 \le c_2 \le C$)，使得对于所有满足 $r_1 \le i \le r_2$ 且 $c_1 \le j \le c_2$ 的格子 $(i, j)$，都有吉祥物，且除此之外的其他任何格子都没有吉祥物。感到“小确幸”的次数越多，JOI 酱今晚就能睡得越香。

放置吉祥物时，不区分吉祥物的种类。请问在使得“小确幸”次数达到最大的前提下，放置吉祥物的顺序共有多少种？

题目描述

给定整理吉祥物的场所信息以及已经放置的吉祥物信息，求出使得“小确幸”次数达到最大的放置顺序的方案数，并输出其对 $1\,000\,000\,007$ 取模后的结果。

输入格式

从标准输入读取以下内容：

• 第 1 行包含两个整数 $R, C$，以空格分隔。$R$ 表示放置吉祥物的行数，$C$ 表示列数。
• 第 2 行包含一个整数 $N$，表示开始整理时已经放置的吉祥物数量。
• 接下来的 $N$ 行，每行包含两个整数 $A_i, B_i$，以空格分隔，表示格子 $(A_i, B_i)$ 在初始时已经放置了吉祥物。这些坐标对不会重复。

输出格式

输出使得“小确幸”次数达到最大的放置顺序的方案数，对 $1\,000\,000\,007$ 取模后的结果。

数据范围

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

• $2 \le R \le 3000$
• $2 \le C \le 3000$
• $1 \le N \le 100\,000$

子任务

子任务 1 [10 分] 满足以下条件： $R \le 3$ $C \le 3$

子任务 2 [30 分] 满足以下条件： $R \le 50$ $C \le 50$

子任务 3 [60 分] 没有额外限制。

样例

样例输入 1

2 3
2
1 2
2 2

样例输出 1

8

说明 1

初始状态下 6 个格子的分布如下（$\triangle$ 表示初始时已放置吉祥物的格子）：

在 6 个格子中，$(1, 2)$ 和 $(2, 2)$ 已经放置了吉祥物。“小确幸”次数的最大值为 2。 使得“小确幸”次数为 2 的配置共有以下 8 种（数字表示新放置吉祥物的顺序）：

在上述 8 种情况中，放置第 2 个吉祥物时，吉祥物所在的格子构成 $2 \times 2$ 的矩形；放置第 4 个吉祥物时，吉祥物所在的格子构成 $2 \times 3$ 的矩形，总共 JOI 酱会感到 2 次“小确幸”。

样例输入 2

3 3
2
1 1
3 3

样例输出 2

5040

说明 2

无论以何种顺序放置，感到“小确幸”的次数均为 1 次。