[DMOI-R2] 回到过去

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

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

**本题有多组数据。** 第一行一个整数 $T$，表示测试点数量。 接下来 $T$ 个测试点，每个测试点的第一行四个整数 $n,m,k,t$。接下来 $t$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个障碍物的坐标（保证不重叠）。

共 $T$ 行，每行一个整数表示当前询问的答案。

5
4 3 2 0
5 7 3 0
2 2 3 0
1 8 2 0
19 13 3 0

49
4773
0
21
2369219

10
4329 12935 3 0
125891 5949823 2 0
95023489 15327384 3 0
28592394 32891538 2 0
5894392 52374853 2 0
58963495 32591238 3 0
438291538 42819324 3 0
58493683 234728 2 0
284952 823499 3 0
528394298 25892948 3 0

468372138
510295355
536959469
56564283
462091483
842203294
778629925
806214146
91259493
793676806

10
55888076 506356561 3 3
48940088 192152177
33004718 365781091
45088097 31400730
65004621 206038505 2 3
50919157 24882066
50919158 24882064
50919156 24882067
249418509 7616530 2 1
205309921 4639136
164784593 419325145 3 4
105814446 200482317
105814449 200482315
105814443 200482315
79723922 206425705
477366546 180501076 3 4
39819749 14485585
39819746 14485582
39819743 14485588
39819748 14485585
84215455 29656489 3 0
524291275 23244413 3 4
8149961 10903189
8149958 10903192
8149958 10903193
8149961 10903191
584987873 823324694 3 1
540008401 27919189
25681672 419244427 2 4
4753299 108169462
4753301 108169463
4753298 108169462
4753298 108169464
313195991 98402123 3 3
7016773 83186671
7016770 83186674
7016767 83186675

580170965
521412840
890711205
353426094
41995284
193113183
352219667
748854206
767819374
351309432

10
2 4 2 4
1 1
1 3
2 1
2 4
2 4 3 3
1 2
2 3
1 4
1 1 3 0
3 4 2 0
3 2 2 1
1 2
4 2 3 0
2 3 2 0
5 4 3 3
2 4
1 3
1 1
4 5 2 2
1 4
2 1
3 1 2 0

4
5
0
49
5
12
8
385
128
1

#### 【样例解释 #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$。每个数据点等分值。