P8915 [DMOI-R2] 回到过去

> 想回到过去\ 试着抱你在怀里\ 羞怯的脸带有一点稚气\ 想看你看的世界\ 想在你梦的画面\ 只要靠在一起就能感觉甜蜜\ 想回到过去\ 试着让故事继续\ 至少不再让你离我而去\ 分散时间的注意\ 这次会抱得更紧\ 这样挽留不知还来不来得及\ 想回到过去\ 沉默支撑跃过陌生\ 静静看着凌晨黄昏\ 你的身影 失去平衡\ 慢慢下沉\ 想回到过去\ —— 周杰伦《[回到过去](https://www.bilibili.com/video/BV1fx411N7bU?p=32&vd_source=2f4592e5507d6452d7d44dc098844d6b)》 > 什么阻碍着两颗心的碰面？什么阻碍着两个人的相见？ 或许是令人捉摸不透的时间吧。

给出 $n,m,t$ 以及 $t$ 个障碍物坐标，求在 $n$ 行 $m$ 列的矩阵中的非障碍位置上放置 $k$ 个两两之间没有公共边的方格的方案有多少种，答案对 $10^9+7$ 取模。

无

无

#### 【样例解释 #4】 对于测试点 1，可以画出如下的图：  其中用黑色格子表示障碍物，可发现只有 $\{(1,2)(1,4)\}\{(1,2)(2,3)\}\{(2,2)(1,4)\}\{(2,3)(1,4)\}$ 四种方案满足题意。 对于测试点 2，可以画出如下的图：  可发现只有 $\{(1,1)(1,3)(2,2)\}\{(1,1)(1,3)(2,4)\}\{(1,1)(2,2)(2,4)\}\{(1,3)(2,1)(2,4)\}\{(1,3)(2,2)(2,4)\}$ 五种情况符合题意。 ### 数据点约定 | 数据点编号 | $n$ | $m$ | $k$ | $t$ | | :----------: | :--------: | :--------: | :-------------: | :-----------------: | | $1$ | $=1$ | $\le 10^9$ | $=2$ | $=0$ | | $2$ | $=1$ | $\le 10^9$ | $=3$ | $=0$ | | $3$ | $\le 20$ | $\le 20$ | $=2$ | $=0$ | | $4$ | $\le 20$ | $\le 20$ | $=3$ | $=0$ | | $5$ | $\le 20$ | $\le 20$ | $=2$ | $\le 400$ | | $6$ | $\le 20$ | $\le 20$ | $=3$ | $\le 400$ | | $7,8$ | $\le 1000$ | $\le 1000$ | $=2$ | $=0$ | | $9,10$ | $\le 1000$ | $\le 1000$ | $=3$ | $=0$ | | $11$ | $\le 1000$ | $\le 1000$ | $=2$ | $\le 10$ | | $12$ | $\le 1000$ | $\le 1000$ | $=3$ | $\le 10$ | | $13,14$ | $\le 10^9$ | $=n$ | $=2$ | $=0$ | | $15,16$ | $\le 10^9$ | $=n$ | $=3$ | $=0$ | | $17,18$ | $\le 10^9$ | $\le 10^9$ | $=2$ | $=0$ | | $19,20$ | $\le 10^9$ | $\le 10^9$ | $=3$ | $=0$ | | $21,22$ | $\le 10^9$ | $\le 10^9$ | $=2$ | $\le 2 \times 10^4$ | | $23,24$ | $\le 10^9$ | $\le 10^9$ | $=3$ | $\le 2 \times 10^4$ | | $25$ | $\le 10^9$ | $\le 10^9$ | $2 \le k \le 3$ | $\le 2 \times 10^4$ | 对于 $100\%$ 的数据，$1 \le n,m \le 10^9$，$2 \le k \le 3$，$0 \le t \le \min(n\cdot m,2 \times 10^4)$，$1 \le x_i \le n$，$1 \le y_i \le m$，$1 \le T \le 10$。每个数据点等分值。