#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
const ll MOD = 1e9;
int N;
pair<int, int> sorted[2][100001];
set<int> graphs[2][100001];
ll num_blocks[2][100001], dp[2][100001], ans = 0;
int x = 0, y = 0;
map<pair<int, int>, int> x_cmp, y_cmp;
void dfs1(int dir, int node, int parent = 0) {
for (int i : graphs[dir][node]) if (i != parent) {
dfs1(dir, i, node);
dp[dir][node] += dp[dir][i];
}
}
void dfs2(int dir, int node, int parent = 0) {
for (int i : graphs[dir][node]) if (i != parent) {
dfs2(dir, i, node);
ans = (ans + (N - dp[dir][i]) * dp[dir][i]) % MOD;
}
}
int DistanceSum(int N, int *X, int *Y) {
::N = N;
FOR(i, 0, N) {
sorted[0][i] = {X[i], Y[i]};
sorted[1][i] = {Y[i], X[i]};
}
sort(sorted[0], sorted[0] + N);
sort(sorted[1], sorted[1] + N);
FOR(i, 0, N) {
if (i == 0 || sorted[0][i].second - sorted[0][i - 1].second != 1 || sorted[0][i].first != sorted[0][i - 1].first) {
y++;
}
dp[0][y]++;
y_cmp[sorted[0][i]] = y;
if (y_cmp[{sorted[0][i].first - 1, sorted[0][i].second}]) {
graphs[0][y_cmp[{sorted[0][i].first - 1, sorted[0][i].second}]].insert(y);
graphs[0][y].insert(y_cmp[{sorted[0][i].first - 1, sorted[0][i].second}]);
}
}
FOR(i, 0, N) {
if (i == 0 || sorted[1][i].second - sorted[1][i - 1].second != 1 || sorted[1][i].first != sorted[1][i - 1].first) {
x++;
}
dp[1][x]++;
x_cmp[sorted[1][i]] = x;
if (x_cmp[{sorted[1][i].first - 1, sorted[1][i].second}]) {
graphs[1][x_cmp[{sorted[1][i].first - 1, sorted[1][i].second}]].insert(x);
graphs[1][x].insert(x_cmp[{sorted[1][i].first - 1, sorted[1][i].second}]);
}
}
dfs1(0, 1);
dfs2(0, 1);
dfs1(1, 1);
dfs2(1, 1);
return (int)ans;
}
