Sum of Shortest Path Distances in a Grid with Rectangular Obstacles

Two players, F and H, are playing a game on an \(N \times M\) grid. In this grid, there are \(P\) non‐overlapping rectangular obstacles. Each obstacle is described by four integers \(U, D, L, R\) (in \(\LaTeX\) format) which indicate that all cells from row \(U\) to row \(D\) and from column \(L\) to column \(R\) become blocked. It is guaranteed that:

• The rectangular obstacles do not intersect with each other.
• The remaining free cells (i.e. non‐obstacle cells) are connected (directly or indirectly) via moves to adjacent cells sharing a common side. The distance between two adjacent free cells is \(1\).

In each game, player F selects a free cell \(X\) and player H selects a different free cell \(Y\). A game is identified by the unordered pair \((X,Y)\) and its score is defined as the shortest path distance between \(X\) and \(Y\) in the grid. Player F needs to compute the sum of the scores over all possible games (i.e. over all unordered pairs of distinct free cells), and output the sum modulo \(10^9+7\).

Note: The cells are identified by their row and column number.

inputFormat

The input consists of multiple lines. The first line contains three integers \(N, M, P\) separated by spaces, representing the number of rows, the number of columns, and the number of obstacles respectively. Then \(P\) lines follow, each containing four integers \(U\), \(D\), \(L\), \(R\) which describe an obstacle that covers all cells from row \(U\) to row \(D\) and from column \(L\) to column \(R\).

outputFormat

Output a single integer representing the sum of the scores of all games (i.e. the sum of shortest path distances over all unordered pairs of free cells) modulo \(10^9+7\).

sample

2 2 0

8