#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
map<int,set<int>> mpx;
map<int,set<int>> mpy;
map<pair<int,int>,int> nv,nh; // mapping for (x,y) to node in vertical tree and node in horizontal tree
set<int> ma[N];
int lh=0,lv=0,w[N],sm[N],mod=1e9,n,ans=0;
void dfs(int x,int p=-1)
{
sm[x]=w[x];
// cout<<"At "<<x<<' '<<w[x]<<endl;
for(auto y:ma[x])
{
if(y==p)continue;
dfs(y,x);
// cout<<"down "<<y<<' '<<sm[y]<<endl;
ans+=((n-sm[y])*sm[y])%mod;
ans%=mod;
sm[x]+=sm[y];
}
}
int DistanceSum(int N, int x[], int y[])
{
n=N;
for(int i=0;i<n;i++)
{
mpx[x[i]].insert(y[i]);
mpy[y[i]].insert(x[i]);
}
for(auto t:mpx)
{
int x=t.first;
int lst=-1,ly=-1;
for(auto y:t.second)
{
if(ly==(y-1))
{
nh[{x,y}]=lst;
w[lst]++;
}
else{
nh[{x,y}]=++lh;
w[lh]++;
lst=lh;
}
ly=y;
auto it=nh.find({x-1,y});
if(it!=nh.end())
{
ma[it->second].insert(lst);
ma[lst].insert(it->second);
}
}
}
dfs(1);
// cout<<ans<<endl;
for(int i=1;i<=n;i++)ma[i].clear(),w[i]=0;
for(auto t:mpy)
{
int x=t.first;
int lst=-1,ly=-1;
for(auto y:t.second)
{
if(ly==(y-1))
{
nv[{x,y}]=lst;
w[lst]++;
}
else{
nv[{x,y}]=++lv;
w[lv]++;
lst=lv;
}
ly=y;
auto it=nv.find({x-1,y});
if(it!=nv.end())
{
ma[it->second].insert(lst);
ma[lst].insert(it->second);
}
}
}
// for(int i=1;i<=lv;i++)
// {
// cout<<"node "<<i<<' '<<w[i]<<endl;
// for(auto j:ma[i])cout<<j<<' ';
// cout<<endl;
// }
dfs(1);
return ans;
}
