#include<bits/stdc++.h>
#define MAX_N 100005
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef pair<int,int> pii;
int n,m;
int cnt[MAX_N],num[MAX_N];
long long ans;
vector<int> adj[MAX_N];
vector<pii> V;
bool vis[MAX_N];
int dfs(int x){
vis[x]=true;
int sum = cnt[x];
for(int y:adj[x]){
if(vis[y]){
continue;
}
sum+=dfs(y);
}
ans = (ans + (long long) sum * (n-sum)) % 1000000000LL;
return sum;
}
void solve(){
int i;
sort(all(V));
for(i=0;i<n;i++){
int e=i;
while(e<n-1 && V[e].fi == V[e+1].fi && V[e].se + 1 == V[e+1].se) e++;
m++;
for(int j=i;j<=e;j++){
int x=lower_bound(all(V),make_pair(V[j].fi-1,V[j].se))-V.begin();
if(V[x] == make_pair(V[j].fi-1,V[j].se)){
adj[m].eb(num[x]);
adj[num[x]].eb(m);
}
num[j]=m;
cnt[m]++;
}
i=e;
}
dfs(1);
for(i=0;i<n;i++) num[i]=vis[i]=0;
for(i=1;i<=m;i++){
cnt[i]=0;
adj[i].clear();adj[i].resize(0);
}
m=0;
}
int DistanceSum(int N, int *X, int *Y) {
n=N;
int i;
for(i=0;i<n;i++){
V.eb(X[i],Y[i]);
}
solve();
for(i=0;i<n;i++){
swap(V[i].fi,V[i].se);
}
solve();
return ans;
}
