P8915 [DMOI-R2] Back to the Past

> 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](https://www.bilibili.com/video/BV1fx411N7bU?p=32&vd_source=2f4592e5507d6452d7d44dc098844d6b)". > What keeps two hearts from meeting? What keeps two people from seeing each other? Maybe it is the unpredictable time.

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$.

**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 $T$ lines. Each line contains one integer, the answer for the corresponding test case.

#### 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 | Test Point ID | $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$ | 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