Subway Ride

Jiho is an expert on the subway. Eunho rides the subway often and keeps asking Jiho how to get from one subway line to another. Jiho always gives the route that requires the most transfers, which wears Eunho out.

Fed up with Jiho's answers, Eunho wants to stop asking him. For every pair of subway lines, Eunho will find the minimum number of transfers needed to get from one line to the other.

There are $N$ subway lines in total. Each line is a segment parallel to the x-axis or the y-axis. If the segments of two subway lines share a point, you can move from one line to the other with one transfer. Two lines that are both parallel to the x-axis, or both parallel to the y-axis, never allow a transfer between them. The length of every line is at least $1$.

Help Eunho compute, for every pair of lines, the minimum number of transfers needed to go from one line to the other.

Let $d(i,j)$ be the minimum number of transfers needed to go from line $i$ to line $j$. Find the sum of $d(i,j) \times i \times j$ over all ordered pairs of integers $(i,j)$ with $1 \leq i,j \leq N$, modulo $1\,000\,000\,007$. If it is impossible to transfer from line $i$ to line $j$, then $d(i,j) = 0$.

The first line contains the number of subway lines $N$.

Each of the next $N$ lines contains four integers $x_1$, $y_1$, $x_2$, $y_2$, separated by spaces, that describe line $i$. Line $i$ is the segment connecting $(x_1, y_1)$ and $(x_2, y_2)$. The input guarantees that $x_1 = x_2$ or $y_1 = y_2$, and that the length of each segment is at least $1$.

Print the answer to the problem on the first line.

• $1 \leq N \leq 7000$
• For every subway line, $-10^9 \leq x_1, y_1, x_2, y_2 \leq 10^9$