题目背景

想回到过去
试着抱你在怀里
羞怯的脸带有一点稚气
想看你看的世界
想在你梦的画面
只要靠在一起就能感觉甜蜜
想回到过去
试着让故事继续
至少不再让你离我而去
分散时间的注意
这次会抱得更紧
这样挽留不知还来不来得及
想回到过去
沉默支撑跃过陌生
静静看着凌晨黄昏
你的身影 失去平衡
慢慢下沉
想回到过去
—— 周杰伦《回到过去》

什么阻碍着两颗心的碰面？什么阻碍着两个人的相见？

或许是令人捉摸不透的时间吧。

题目描述

给出 $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$			$=3$
$3$	$\le 20$		$=2$
$4$			$=3$
$5$			$=2$	$\le 400$
$6$			$=3$
$7,8$	$\le 1000$		$=2$	$=0$
$9,10$			$=3$
$11$			$=2$	$\le 10$
$12$			$=3$
$13,14$	$\le 10^9$	$=n$	$=2$	$=0$
$15,16$			$=3$
$17,18$		$\le 10^9$	$=2$
$19,20$			$=3$
$21,22$			$=2$	$\le 2 \times 10^4$
$23,24$			$=3$
$25$			$2 \le k \le 3$

对于 $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$。每个数据点等分值。