이상적인 도시

당대의 많은 이탈리아 과학자와 예술가처럼, 다빈치는 도시 계획과 디자인에 큰 관심을 가지고 있었다. 그는 편안하면서도 공간을 넓고 합리적으로 사용하며, 중세 도시의 좁고 답답함과는 거리가 먼 이상적인 도시를 설계하고자 했다.

무한히 큰 정사각형 셀 격자 위에 $N$개의 블록을 놓아 도시를 만든다. 각 셀은 (행, 열) 좌표쌍으로 나타낸다. 셀 $(i, j)$에 인접한 셀은 $(i-1, j)$, $(i+1, j)$, $(i, j-1)$, $(i, j+1)$이다. 각 블록은 정확히 하나의 셀을 덮으며, $1 \le i, j \le 2^{31} - 2$인 셀 $(i, j)$에만 놓을 수 있다. 서로 인접한 두 셀에 놓인 두 블록은 인접했다고 한다.

이상적인 도시에서는 모든 블록이 구멍 없이 연결되어야 한다. 정확히 말하면, 다음 두 조건을 만족해야 한다.

1. 비어 있는 임의의 두 셀에 대해, 인접한 빈 셀만을 지나 한 셀에서 다른 셀로 가는 경로가 적어도 하나 존재한다.
2. 비어 있지 않은 임의의 두 셀에 대해, 인접한 채워진 셀만을 지나 한 셀에서 다른 셀로 가는 경로가 적어도 하나 존재한다.

(아래 그림들은 모두 이상적인 도시가 아니다. 앞의 두 개는 조건 1을, 세 번째는 조건 2를, 네 번째는 두 조건 모두를 만족하지 않는다.)

도시 안에서 한 걸음은 한 블록에서 인접한 블록으로 이동하는 것을 뜻한다. 빈 셀로는 이동할 수 없다. 격자 위 $N$개 블록의 좌표를 $v_0, v_1, \dots, v_{N-1}$이라 하자. 서로 다른 두 블록 $v_i$, $v_j$ 사이의 거리 $d(v_i, v_j)$는 한 블록에서 다른 블록으로 가는 데 필요한 최소 걸음 수로 정의한다.

아래 그림은 좌표 $v_0=(2,5)$, $v_1=(2,6)$, $v_2=(3,3)$, $v_3=(3,6)$, $v_4=(4,3)$, $v_5=(4,4)$, $v_6=(4,5)$, $v_7=(4,6)$, $v_8=(5,3)$, $v_9=(5,4)$, $v_{10}=(5,6)$을 가지는 $N = 11$개 블록으로 이루어진 이상적인 도시를 나타낸다. 이때 $d(v_1, v_3)=1$, $d(v_1, v_8)=6$, $d(v_6, v_{10})=2$, $d(v_9, v_{10})=4$이다.

$0 \le i < j \le N-1$인 모든 블록 쌍 $v_i$, $v_j$에 대한 거리의 합, 즉 $\sum_{0 \le i < j \le N-1} d(v_i, v_j)$ 을 계산해야 한다. 위 예시의 도시에는 $11 \times 10 / 2 = 55$개의 블록 쌍이 있으며, 모든 쌍의 거리 합은 $174$이다.

결과가 매우 클 수 있으므로, 이 합을 1,000,000,000으로 나눈 나머지를 출력한다.

첫째 줄에 블록의 수 $N$이 주어진다. 이어지는 $N$개 줄 중 $i$번째 줄에는 블록 $i$의 좌표 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다 ($1 \le X_i, Y_i \le 2^{31} - 2$). 주어지는 도시는 항상 이상적인 도시임이 보장된다.

$0 \le i < j \le N-1$인 모든 블록 쌍의 거리 합을 1,000,000,000으로 나눈 나머지를 한 줄에 출력한다.