#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5, mod=1e9;
ll n, t, sz[nx], dp[nx], res;
set<ll> d[nx];
map<ll, vector<ll>> mpx, mpy;
map<pair<ll, ll>, ll> mp;
void dfs(int u, int p)
{
dp[u]=sz[u];
for (auto v:d[u]) if (v!=p) dfs(v, u), dp[u]+=dp[v];
res+=(dp[u])*(n-dp[u]);
//cout<<"debug "<<u<<' '<<dp[u]<<' '<<res<<'\n';
}
int DistanceSum(int N, int *X, int *Y) {
n=N;
for (int i=0; i<N; i++) mpx[X[i]].push_back(Y[i]), mpy[Y[i]].push_back(X[i]);
for (auto [x, y]:mpx)
{
sort(y.begin(), y.end());
++t;
if (mp.find({x-1, y[0]})!=mp.end()) d[mp[{x-1, y[0]}]].insert(t), d[t].insert(mp[{x-1, y[0]}]);
mp[{x, y[0]}]=t;
sz[t]=1;
for (int i=1; i<y.size(); i++)
{
if (y[i]-1!=y[i-1]) t++;
sz[t]++;
mp[{x, y[i]}]=t;
if (mp.find({x-1, y[i]})!=mp.end()) d[mp[{x-1, y[i]}]].insert(t), d[t].insert(mp[{x-1, y[i]}]);
}
}
dfs(1, 1);
for (int i=1; i<=t; i++) d[i].clear(),sz[i]=0;
t=0;
mp.clear();
for (auto [x, y]:mpy)
{
sort(y.begin(), y.end());
++t;
if (mp.find({x-1, y[0]})!=mp.end()) d[mp[{x-1, y[0]}]].insert(t), d[t].insert(mp[{x-1, y[0]}]);
mp[{x, y[0]}]=t;
sz[t]=1;
for (int i=1; i<y.size(); i++)
{
if (y[i]-1!=y[i-1]) t++;
sz[t]++;
mp[{x, y[i]}]=t;
if (mp.find({x-1, y[i]})!=mp.end()) d[mp[{x-1, y[i]}]].insert(t), d[t].insert(mp[{x-1, y[i]}]);
}
}
dfs(1, 1);
/*
for (int i=1; i<=t; i++)
{
cout<<"size "<<sz[i]<<':';
for (auto x:d[i]) cout<<x<<' ';
cout<<'\n';
}*/
return res%mod;
}
