// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10;
const int Nine = (int)1e9;
vector<int> v[maxn];
int pr[maxn];
int fnd(int u){
return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
bool mrg(int a, int b){
if( (a = fnd(a)) == (b = fnd(b)) )
return 0;
if(pr[a] > pr[b])
swap(a, b);
pr[a]+= pr[b];
pr[b] = a;
return 1;
}
int SZ[maxn];
int dfs(int tot, int u, int par = -1){
int ans = 0;
SZ[u] = -pr[fnd(u)];
for(int y : v[u]){
if(y != par){
ans = (ans + dfs(tot, y, u)) % Nine;
SZ[u]+= SZ[y];
}
}
ans = (1ll * ans + 1ll * SZ[u] * (tot - SZ[u])) % Nine;
return ans;
}
void add_edge(int a, int b){
v[a].PB(b);
v[b].PB(a);
}
int solve(int n, int *X, int *Y){
for(int i = 0; i < n; i++){
v[i].clear();
}
memset(pr, -1, sizeof pr);
map<pii, int> mp;
for(int i = 0; i < n; i++)
mp[{X[i], Y[i]}] = i;
vector<int> vc;
for(int i = 0; i < n; i++){
if(mp.count({X[i], Y[i]+1}))
mrg(i, mp[{X[i], Y[i]+1}]);
}
for(int i = 0; i < n; i++){
if(mp.count({X[i]+1, Y[i]}))
vc.PB(i);
}
sort(vc.begin(), vc.end(), [&](int i, int j){ return Y[i] < Y[j]; });
for(int a : vc){
int b = mp[{X[a]+1, Y[a]}];
if(mp.count({X[a], Y[a]+1}) == 0 || mp.count({X[a]+1, Y[a]+1}) == 0)
add_edge(fnd(a), fnd(b));
}
return dfs(n, fnd(0));
}
int ITER = 0;
int DistanceSum(int n, int *X, int *Y){
assert(++ITER <= 1);
return (solve(n, X, Y) + solve(n, Y, X)) % Nine;
}
