#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 1e5 + 10 , mod = 1e9;
int n;
long long ans;
struct Tree{
vector <int> adj[N];
int ar[N] , pos;
Tree()
{
pos = 1;
ar[1] = 1;
}
void Add_Edge(int id)
{
if(!adj[id].empty() && adj[id].back() == pos)
return;
adj[id].push_back(pos);
adj[pos].push_back(id);
}
void Solve(int v = 1 , int p = -1)
{
for(auto u : adj[v]) if(u != p)
{
Solve(u , v);
ar[v] += ar[u];
ans = (ans + 1LL * ar[u] * (n - ar[u]) % mod) % mod;
//cout << u << " " << ar[u] << " " << (n - ar[u]) << endl;
}
}
/*void Debug()
{
cout << pos << endl;
for(int i = 1 ; i <= pos ; i++)
cout << ar[i] << " ";
cout << endl;
for(int i = 1 ; i <= pos ; i++) for(auto u : adj[i])
cout << i << " ---- " << u << endl;
}*/
} row , col;
int DistanceSum(int nn, int *X, int *Y)
{
n = nn;
vector <pair<int , int>> r , c;
for(int i = 0 ; i < n ; i++)
{
r.push_back({X[i] , Y[i]});
c.push_back({Y[i] , X[i]});
}
sort(r.begin() , r.end());
sort(c.begin() , c.end());
map <pair <int , int> , int> mpr , mpc;
mpr[r[0]] = 1;
mpc[c[0]] = 1;
for(int i = 1 ; i < n ; i++)
{
if(r[i].F == r[i - 1].F && r[i].S == r[i - 1].S + 1)
row.ar[row.pos]++;
else
{
row.pos++;
row.ar[row.pos] = 1;
}
if(c[i].F == c[i - 1].F && c[i].S == c[i - 1].S + 1)
col.ar[col.pos]++;
else
{
col.pos++;
col.ar[col.pos] = 1;
}
mpr[r[i]] = row.pos;
mpc[c[i]] = col.pos;
if(mpr.find(make_pair(r[i].F - 1 , r[i].S)) != mpr.end())
row.Add_Edge(mpr[make_pair(r[i].F - 1 , r[i].S)]);
if(mpc.find(make_pair(c[i].F - 1 , c[i].S)) != mpc.end())
col.Add_Edge(mpc[make_pair(c[i].F - 1 , c[i].S)]);
}
row.Solve();
col.Solve();
return ans;
}
