P7136 [THUPC 2021 Preliminary] Grid Game

Little F and Little H are playing a game. Today, they are playing on an $N \times M$ chessboard. Little H wants to test Little F's math skills, but Little F is naturally not good at math, so he asks you for help. To make it harder, Little H will add $P$ rectangular obstacles on the board. Each rectangular obstacle is described by $U$, $D$, $L$, $R$: all cells from row $U$ to row $D$ and from column $L$ to column $R$ become obstacles. Little H guarantees that all rectangular obstacles do not intersect each other, and that all non-obstacle cells are mutually reachable directly or indirectly. If two non-obstacle cells share a common edge, then they are directly reachable, and the distance between them is $1$. In each game, Little F picks a non-obstacle cell $X$ on the board, and Little H picks another non-obstacle cell $Y$. The score of this game $(X, Y)$ is the length of the shortest path from $X$ to $Y$. Little F needs to compute the sum of scores over all possible games, modulo $1,000,000,007$. Note that two games are considered the same if the two chosen cells are the same, i.e., $(X, Y)$ is equivalent to $(Y, X)$.

The first line contains three integers $N$ ($1 \le N \le 1,000,000,000$), $M$ ($1 \le M \le 1,000,000,000$), and $P$ ($0 \le P \le 100,000$). The next $P$ lines each contain four positive integers $U_i, D_i$ ($1 < U_i \le D_i < N$), $L_i, R_i$ ($1 < L_i \le R_i < M$), describing the $i$-th rectangular obstacle. For any two different rectangular obstacles $i$ and $j$, it holds that $D_i + 1 < U_j$ or $D_j + 1 < U_i$, and also $R_i + 1 < L_j$ or $R_j + 1 < L_i$.

A single line with one positive integer: the sum of scores of all games modulo $1,000,000,007$.

**Sample Explanation #1** There are $8$ pairs with distance $1$. There are $8$ pairs with distance $2$. There are $8$ pairs with distance $3$. There are $4$ pairs with distance $4$. The total score is $64$. **Source** From the preliminary round of the 2021 Tsinghua University Programming Contest and Intercollegiate Invitational Contest (THUPC2021). Resources such as the solution can be found at . Translated by ChatGPT 5