P11011 "ALFR Round 4" Coverage of Point A

In the 2D Cartesian coordinate system, if both the $x$-coordinate and the $y$-coordinate of a point are integers, we call it an integer point. Given a rectangle $A$ whose vertices are all integer points and whose sides are parallel to the coordinate axes, and given $n$ integer points $p_1, p_2, p_3, \cdots, p_n$ inside rectangle $A$ (possibly on its boundary), ask how many sub-rectangles of $A$ satisfy: - All vertices are integer points. - All four sides are parallel to a coordinate axis. - They can completely cover (boundary is allowed) $p_1, p_2, p_3, \cdots, p_n$. In this problem, the length or width of a rectangle may be $0$.

The first line contains five integers, which are the number of given integer points $n$, the $x$-coordinate of the upper-left vertex of rectangle $A$, the $y$-coordinate of the upper-left vertex, the $x$-coordinate of the lower-right vertex, and the $y$-coordinate of the lower-right vertex. Lines $2$ to $n+1$: in line $i$, two integers give the $x$-coordinate and $y$-coordinate of $p_{i-1}$.

Output one integer in one line, representing the answer modulo $10^9+7$.

| Subtask | Score | Constraints | | :----------: | :----------: | :----------: | | $0$ | $20$ | $n \le 10^2$, the coordinates of all points are less than $10^2$ | | $1$ | $20$ | All points except the vertices of $A$ have the same $x$-coordinate | | $2$ | $60$ | - | For $100\%$ of the testdata, $1 \le n \le 10^6$, all point coordinates are positive integers and less than $10^9$. Translated by ChatGPT 5