P10714 [MX-X1-T2] "KDOI-05" Simple Finite Grid Problem.

Original problem link: .

Player S is playing a mini game. In the game, there is an $n\times m$ chessboard, and there are stars on $k$ cells. Initially, there is a catcher at position $(x,y)$. In each operation, you can move the catcher to some cell in the same row or the same column, such that the new position is different from the old one, and the new position $(x',y')$ must satisfy $1\leq x'\leq n$, $1\leq y'\leq m$. **The catcher will capture all stars on the path from $(x,y)$ to $(x',y')$**. After a star is captured, it disappears. The goal of the game is to get as many stars as possible in exactly two moves. However, player S does not know how to play, so each time he randomly picks a new position that the catcher can move to. Among the $(n+m-2)^2$ different move plans of player S, find the sum of the numbers of stars captured. Output the answer modulo $10^9+7$.

The first line contains three positive integers $n,m,k$, representing the board size and the number of stars. The second line contains two positive integers $x,y$, representing the initial position of the catcher. The next $k$ lines each contain two positive integers, representing the position $(p,q)$ of each star. There may be multiple stars on the same cell.

One line with one non-negative integer, representing the sum, over all $(n+m-2)^2$ different move plans of player S, of the number of stars he can capture, modulo $10^9+7$.

**[Sample Explanation #1]** On the grid, one valid plan to move the catcher is: $$(2,2)\to(1,2)\to(1,3)$$ In this plan, it can capture $1$ star at $(1,2)$ and $1$ star at $(1,3)$. **[Constraints]** **This problem uses bundled testdata.** | Subtask ID | Score | $n\leq$ | $m\leq$ | |:--:|:--:|:--:|:--:| | $1$ | $5$ | $50$ | $50$ | | $2$ | $10$ | $1000$ | $1000$ | | $3$ | $20$ | $10^5$ | $10^5$ | | $4$ | $25$ | $10^5$ | $10^9$ | | $5$ | $25$ | $10^9$ | $10^9$ | | $6$ | $15$ | $10^{18}$ | $10^{18}$ | For $100\%$ of the data, $1\leq k\leq10^5$, $1\leq n,m\leq10^{18}$, $1\leq x,p\leq n$, $1\leq y,q\leq m$, $(x,y)\neq(p,q)$. Translated by ChatGPT 5