Problem Description

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

Input Format

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 Format

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

3 1 5 6 1
2 3
2 4
4 2

24

Hint

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