#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define mp make_pair
#define pb push_back
#define ll long long
const int N=100050;
const int mod=1e9;
int comp[N],cnt;
map<pair<int,int> ,int> id;
vector<int> E[N];
int weg[N],sz[N],n;
int x[N],y[N],p[N];
void init(){ for(int i=0;i<N;i++) p[i]=i;}
int Find(int x){ return x==p[x]?x:p[x]=Find(p[x]);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
int dep[N];
ll ans;
void DFS(int u, int p)
{
int i;
//printf("DFS:%i %i\n",u,p);
sz[u]=weg[u];
dep[u]=dep[p]+1;
for(i=0;i<E[u].size();i++)
{
int v=E[u][i];
if(v!=p) DFS(v,u),sz[u]+=sz[v];
}
ll mul=0;
//int sub=0;
for(i=0;i<E[u].size();i++)
{
int v=E[u][i];
if(v!=p)
{
mul+=(ll)sz[v]*(sz[u]-sz[v])%mod;
mul%=mod;
//sub+=sz[v];
}
}
mul+=(ll)weg[u]*(weg[u]-1)%mod;
mul%=mod;
ans-=(ll)mul*dep[u]%mod;
if(ans<0) ans+=mod;
ans+=(ll)(n-sz[u]+weg[u]-1)*weg[u]%mod*dep[u]%mod;
ans%=mod;
//printf("u:%i -mul:%lld +mul:%lld weg:%lld sz:%lld\n",u,mul,(n-sz[u]+weg[u]-1)*weg[u],weg[u],sz[u]);
}
int SolveTree()
{
ans=0;
DFS(1,0);
return ans%mod;
}
int DistanceSum(int M, int X[], int Y[])
{
n=M;
int i,j;
for(i=1;i<=n;i++) x[i]=X[i-1],y[i]=Y[i-1];
for(i=1;i<=n;i++) id[mp(x[i],y[i])]=i;
for(i=1;i<=n;i++)
{
if(!comp[i])
{
cnt++;
comp[i]=cnt;
weg[cnt]=1;
j=1;
while(id.count(mp(x[i],y[i]+j))) comp[id[mp(x[i],y[i]+j)]]=cnt,j++,weg[cnt]++;
j=1;
while(id.count(mp(x[i],y[i]-j))) comp[id[mp(x[i],y[i]-j)]]=cnt,j++,weg[cnt]++;
}
}
//for(i=1;i<=n;i++) printf("%i ",comp[i]);printf("\n");
//for(i=1;i<=cnt;i++) printf("%i ",weg[i]);printf("\n");
init();
for(i=1;i<=n;i++)
{
int u=id[mp(x[i]+1,y[i])];
if(u && Find(comp[i])!=Find(comp[u]))
{
//printf("(%i - %i)\n",comp[i],comp[u]);
E[comp[i]].pb(comp[u]);
E[comp[u]].pb(comp[i]);
Union(comp[i],comp[u]);
}
u=id[mp(x[i]-1,y[i])];
if(u && Find(comp[i])!=Find(comp[u]))
{
//printf("(%i - %i)\n",comp[i],comp[u]);
E[comp[i]].pb(comp[u]);
E[comp[u]].pb(comp[i]);
Union(comp[i],comp[u]);
}
}
int sol=SolveTree();
//printf("->%i\n",sol);
for(i=1;i<=n;i++) comp[i]=0;
for(i=1;i<=cnt;i++) E[i].clear();
cnt=0;
for(i=1;i<=n;i++)
{
if(!comp[i])
{
cnt++;
comp[i]=cnt;
weg[cnt]=1;
j=1;
while(id[mp(x[i]+j,y[i])]) comp[id[mp(x[i]+j,y[i])]]=cnt,j++,weg[cnt]++;
j=1;
while(id[mp(x[i]-j,y[i])]) comp[id[mp(x[i]-j,y[i])]]=cnt,j++,weg[cnt]++;
}
}
//for(i=1;i<=n;i++) printf("%i ",comp[i]);printf("\n");
init();
for(i=1;i<=n;i++)
{
int u=id[mp(x[i],y[i]+1)];
if(u && Find(comp[i])!=Find(comp[u]))
{
//printf("(%i - %i)\n",comp[i],comp[u]);
E[comp[i]].pb(comp[u]);
E[comp[u]].pb(comp[i]);
Union(comp[i],comp[u]);
}
u=id[mp(x[i],y[i]-1)];
if(u && Find(comp[i])!=Find(comp[u]))
{
//printf("(%i - %i)\n",comp[i],comp[u]);
E[comp[i]].pb(comp[u]);
E[comp[u]].pb(comp[i]);
Union(comp[i],comp[u]);
}
}
sol+=SolveTree();
sol%=mod;
return sol;
}
