Background

Want to go back to the past
Try to hold you in my arms
Your shy face has a bit of childishness
Want to see the world you see
Want to be in the scenes of your dreams
As long as we are close together, we can feel sweetness
Want to go back to the past
Try to let the story continue
At least, no longer let you leave me
Distract the attention of time
This time I will hold tighter
I do not know if it is still in time to keep you
Want to go back to the past
Silence supports jumping over strangeness
Quietly watching dawn and dusk
Your figure loses balance
Slowly sinking
Want to go back to the past
—— Jay Chou, "Back to the Past".

What keeps two hearts from meeting? What keeps two people from seeing each other?

Maybe it is the unpredictable time.

Problem Description

Given $n, m, t$ and the coordinates of $t$ obstacles, find the number of ways to place $k$ cells on an $n$-row $m$-column grid, only on non-obstacle positions, such that no two chosen cells share a common edge. Output the answer modulo $10^9+7$.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

Then follow $T$ test cases. For each test case, the first line contains four integers $n, m, k, t$. The next $t$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th obstacle (guaranteed not to overlap).

Output Format

Output $T$ lines. Each line contains one integer, the answer for the corresponding test case.

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

Hint

Sample Explanation #4

For test case 1, you can draw the following figure:

Black cells represent obstacles. You can find that only $\{(1,2)(1,4)\}\{(1,2)(2,3)\}\{(2,2)(1,4)\}\{(2,3)(1,4)\}$, four ways in total, satisfy the requirement.

For test case 2, you can draw the following figure:

You can find that only $\{(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)\}$, five cases in total, satisfy the requirement.

Test Point Specification

For $100\%$ of the data, $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$. Each test point has equal score.

Translated by ChatGPT 5