지하철 타고 가요

지호는 지하철 전문가이다. 지하철을 자주 이용하는 은호는 지호에게 하나의 지하철 노선에서 다른 지하철 노선으로 가는 방법을 자주 묻는다. 그런데 지호는 매번 환승을 가장 많이 해야 하는 방법을 알려 줘서 은호를 힘들게 한다.

악질인 지호에게 너무 많이 당한 은호는 다시는 지호에게 환승 방법을 묻지 않으려고 한다. 그래서 모든 두 지하철 노선에 대해 한 노선에서 다른 노선으로 가기 위한 최소 환승 수를 직접 알아내려 한다.

지하철 노선은 총 $N$개이며, 각 노선은 $x$축 또는 $y$축에 평행한 선분이다. 두 노선의 선분이 교점을 가지면, 한 번의 환승으로 한 노선에서 다른 노선으로 이동할 수 있다. $x$축에 평행한 노선끼리, 혹은 $y$축에 평행한 노선끼리는 환승할 수 없다. 모든 노선의 길이는 $1$ 이상이다.

은호를 도와 모든 두 지하철 노선에 대해 한 노선에서 다른 노선으로 가는 최소 환승 수를 구하자.

$i$번째 노선에서 $j$번째 노선으로 가는 최소 환승 수를 $d(i,j)$라 하자. $1 \leq i,j \leq N$인 모든 정수 순서쌍 $(i,j)$에 대해 $d(i,j) \times i \times j$의 합을 $1\,000\,000\,007$로 나눈 나머지를 구하여라. 만약 $i$번째 노선에서 $j$번째 노선으로 환승하는 것이 불가능하다면 $d(i,j) = 0$이다.

첫 번째 줄에 지하철 노선의 수 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄 중 $i$번째 줄에는 $i$번 노선의 정보를 나타내는 정수 4개 $x_1$, $y_1$, $x_2$, $y_2$가 공백으로 구분되어 주어진다. 이는 $i$번 노선이 $(x_1, y_1)$과 $(x_2, y_2)$를 잇는 선분이라는 뜻이다. 입력은 $x_1 = x_2$ 또는 $y_1 = y_2$이고, 선분의 길이가 $1$ 이상임을 보장한다.

첫 번째 줄에 문제의 정답을 출력한다.

• $1 \leq N \leq 7000$
• 모든 지하철 노선에서 $-10^9 \leq x_1, y_1, x_2, y_2 \leq 10^9$