#include <bits/stdc++.h>
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;
const int N = 1e5 + 5;
const int mod = 1e9;
inline int add(int x, int y) {
return x + y >= mod ? x + y - mod : x + y;
}
inline int mul(int x, int y) {
return (ll) x * y % mod;
}
int n, ans;
ii a[N];
int gr[N], sz[N];
vector < int > v[N];
map < ii, int > M, p;
void add(int i) {
int x = a[i].first;
int y = a[i].second;
if(p.find(ii(x - 1, y)) != p.end()) {
int j = p[ii(x - 1, y)];
if(!M[ii(gr[i], gr[j])]) {
M[ii(gr[i], gr[j])] = M[ii(gr[j], gr[i])] = 1;
//printf("i, j = %d %d\n", gr[i], gr[j]);
v[gr[i]].push_back(gr[j]);
v[gr[j]].push_back(gr[i]);
}
}
//cout << flush;
}
int ch[N];
void dfs(int p, int x) {
ch[x] = sz[x];
foreach(it, v[x]) {
int u = *it;
if(u != p) {
dfs(x, u);
ch[x] += ch[u];
ans = add(ans, mul(ch[u], n - ch[u]));
}
}
}
void solve() {
M.clear();
p.clear();
for(int i = 0; i < n; i++)
v[i].clear();
sort(a, a + n);
for(int i = 0; i < n; i++) {
int j = i;
gr[i] = i;
sz[i] = 1;
p[a[i]] = i;
add(i);
while(j + 1 < n and a[j + 1] == ii(a[j].first, a[j].second + 1)) {
j++;
gr[j] = i;
sz[i]++;
p[a[j]]= j;
add(j);
}
i = j;
}
dfs(-1, 0);
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
for(int i = 0; i < n; i++) {
a[i] = ii(X[i], Y[i]);
}
solve();
for(int i = 0; i < n; i++) {
a[i] = ii(Y[i], X[i]);
}
solve();
return ans;
}
