#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MxN=1e5+10, mod=1e9;
ll cn[MxN][2], dp[MxN][2]; // how many nodes in group
map<pii, int> gr[2];
set<int> ad[MxN][2];
void build(int u, int k, int pst=-1)
{
// cout << k << " -> " << u << '\n';
// for(auto it : ad[u][k]){
// cout << it << " ";
// }
// cout << '\n';
dp[u][k]=cn[u][k];
for(auto it : ad[u][k]){
if(it==pst) continue;
build(it, k, u);
dp[u][k]+=dp[it][k];
}
}
ll ans=0;
void dfs(int u, int k, ll up=0, int pst=-1)
{
ans+=up*dp[u][k]%mod;
ans%=mod;
for(auto it : ad[u][k]){
if(it==pst) continue;
dfs(it, k, up+dp[u][k]-dp[it][k], u);
}
}
int DistanceSum(int n, int x[], int y[]) {
vector<pii> inf;
FOR(i, 0, n)
{
inf.pb({x[i],y[i]});
}
sort(inf.begin(), inf.end());
int now;
FOR(k, 0, 2)
{
// cout << k << ":\n";
// FOR(i, 0, n)
// {
// cout << inf[i].f << " " << inf[i].s << '\n';
// }
FOR(i, 0, n)
{
if(i==0 || inf[i-1].f!=inf[i].f || inf[i-1].s+1!=inf[i].s) now=i;
int a=inf[i].f, b=inf[i].s;
gr[k][{a,b}]=now;
cn[now][k]++;
if(gr[k].count({a-1,b})){
int nxt=gr[k][{a-1,b}];
ad[now][k].insert(nxt);
ad[nxt][k].insert(now);
}
}
build(0, k);
dfs(0, k);
FOR(i, 0, n) swap(inf[i].f, inf[i].s);
sort(inf.begin(), inf.end());
}
return ans;
}
