32993번 - 지하철 타고 가요

문제

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

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

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

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

$i$번째 노선에서 $j$번째 노선으로 가는 최소 환승 수를 $d(i,j)$라 할 때, 1ドル \leq i,j \leq N$인 모든 정수 순서쌍 $(i,j)$에 대해 $d(i,j) \cdot i \cdot 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$

힌트