#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
const int MXN = 1e5+5, MOD = 1e9;
int n;
pii a[MXN];
int N, w[MXN];
vector<int> g[MXN];
map<pii, int> cmp;
int ans;
void dfs(int v, int p=-1) {
for(int u : g[v])
if(u!=p) {
dfs(u, v);
w[v] += w[u];
(ans += 1ll*w[u]*(n-w[u])%MOD) %= MOD;
}
}
void solve() {
sort(a, a+n);
for(int i=0, j; i<n;) {
j=i;
while(j+1<n && a[j+1].X==a[i].X && a[j+1].Y==a[j].Y+1) j++;
for(int k=i; k<=j; k++)
w[cmp[a[k]] = N]++;
N++;
i = j+1;
}
pii lst = {-1, -1}, cur;
for(int i=0; i<n; i++)
if(cmp.find({a[i].X-1, a[i].Y})!=cmp.end()) {
cur = {cmp[{a[i].X-1, a[i].Y}], cmp[a[i]]};
if(lst!=cur) {
g[cur.X].push_back(cur.Y);
g[cur.Y].push_back(cur.X);
lst = cur;
}
}
dfs(0);
for(int i=0; i<N; i++) {
w[i] = 0;
g[i].clear();
}
cmp.clear();
N = 0;
}
int DistanceSum(int n, int *A, int *B) {
::n = n;
for(int i=0; i<n; i++) a[i] = {A[i], B[i]};
solve();
for(int i=0; i<n; i++) swap(a[i].X, a[i].Y);
solve();
return ans;
}
