#include <bits/stdc++.h>
#define ff first
#define ss second
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long ll;
const ll N = 1e5+5, mod = 1e9;
ll sz[N], c[N], n, id[N];
bool used[N];
vector<int> edges[N];
vector<pair<int, int>> p;
ll ans;
void dfs(int u){
sz[u] = c[u];
used[u]=true;
for(auto v : edges[u]){
if(!used[v]){
dfs(v);
sz[u] += sz[v];
}
}ans += sz[u]*(n-sz[u]);ans%=mod;
}
void build(){
sort(all(p));
int timer=0;
for(int i=0;i<n;i++){
int e=i;
while(e+1<n && p[e].ff == p[e+1].ff && p[e+1].ss == p[e].ss+1)e++;
for(int j=i;j<=e;j++){
int x = lower_bound(all(p), make_pair(p[j].ff-1, p[j].ss))-p.begin();
if(p[x] == make_pair(p[j].ff-1, p[j].ss)){
edges[id[x]].push_back(timer);
edges[timer].push_back(id[x]);
}id[j] = timer;
}c[timer] = e-i+1;
timer++;
i = e;
}dfs(0);
for(int i=0;i<n;i++)c[i]=0, sz[i]=0, id[i]=0;
for(int i=0;i<=timer;i++)edges[i].clear(), used[i]=0;
}
int DistanceSum(int NN, int *X, int *Y) {
n = NN;
for(int i=0;i<n;i++){
p.push_back({X[i], Y[i]});
}build();
p.clear();
for(int i=0;i<n;i++){
p.push_back({Y[i], X[i]});
}build();
return (int)ans%mod;
}
