U306395 军训(Hard version)

军训时，教官要求要把总共 $N \times M$ 个人排成一个 $N$ 行 $M$ 列的一个矩阵，要求有以下两点： - 对于任意一排，总是左边的人高于右边的人； - 对于任意一列，总是前面的人高于后面的人。 因为所有人的身高**都不相同**，所以为了方便起见，我们把所有人的身高令为 $1, 2, \dots, N \times M$。 现在有 $K$ 对同学，他们是好朋友，他们希望在最终的矩阵中相邻（相邻指的是在前后左右四个方向相邻）。 现在教官想知道总共有多少种排列方式符合要求，并且满足所有同学的需求。

共 $K + 2$ 行： 第一行两个整数，分别表示 $N$ 和 $M$。 第二行一个整数，表示有 $K$ 对好朋友。 接下来 $K$ 行，每行两个整数 $X_i$ 和 $Y_i$，表示身高为 $X_i$ 和 $Y_i$ 的同学是好朋友。

一个整数，表示总共有多少种排列方式符合要求，并且满足所有同学的需求。

| 5 | 6 | | :----------: | :----------: | | **3** | **4** | | 1 | 2 | | 5 | 6 | | :----------: | :----------: | | 2 | **4** | | 1 | **3** | | 4 | 6 | | :----------: | :----------: | | **3** | **5** | | 1 | 2 |