Problem Background

Want to go back to the past\
Try to hold you in my arms\
Shy faces with a touch of innocence\
Want to see the world through your eyes\
Want to be in the dreams of your mind\
Just being close together feels sweet\
Want to go back to the past\
Try to let the story continue\
At least don't let you leave me anymore\
Distract the attention of time\
This time will hold tighter\
Is it still not too late to retain\
Want to go back to the past\
Silence supports leaping over the unfamiliar\
Silently watching the dawn and dusk\
Your figure, losing balance\
Sinking slowly\
Want to go back to the past\
— Jay Chou, "Back to the Past"

What hinders the meeting of two hearts? What hinders the meeting of two people?

Perhaps it's the elusive time.

Problem Description

Given \( n, m, t \) and \( t \) obstacle coordinates, find the number of ways to place \( k \) squares without common edges in a non-obstacle position in an \( n \) by \( m \) matrix, modulo \( 10^9+7 \).

Input Format

This problem contains multiple test cases.

The first line contains an integer \( T \), the number of test cases.

Next, \( T \) test cases follow. Each test case starts with four integers \( n, m, k, t \). The next \( t \) lines contain two integers each, \( x_i, y_i \), representing the coordinates of the \( i \)-th obstacle (guaranteed to be non-overlapping).

Output Format

Output \( T \) lines, each containing an integer representing the answer to the current query.

Sample Input and Output

Input Sample #1

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

Output Sample #1

49
4773
0
21
2369219

Input Sample #2

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

Output Sample #2

468372138
510295355
536959469
56564283
462091483
842203294
778629925
806214146
91259493
793676806

Input Sample #3

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

Output Sample #3

580170965
521412840
890711205
353426094
41995284
193113183
352219667
748854206
767819374
351309432

Input Sample #4

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

Output Sample #4

4
5
0
49
5
12
8
385
128
1

Notes

Sample Explanation #4

For test case 1, the following diagram can be drawn:

Where black squares represent obstacles, and only the following four schemes satisfy the problem requirements: \(\{(1,2)(1,4)\}\{(1,2)(2,3)\}\{(2,2)(1,4)\}\{(2,3)(1,4)\}\).

For test case 2, the following diagram can be drawn:

Only the following five situations meet the requirements: \(\{(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)\}\).

Data Point Constraints

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 data point is equally weighted.

见题面 Input 部分

见题面 Output 部分