#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int MOD = 1000000000;
int n, ans=0;
vector<int> sz;
vector<vector<int> > graph;
void dfs(int node, int p){
for (auto num:graph[node])if (num!=p)dfs(num, node), sz[node]+=sz[num], ans=(ans+sz[num]*(n-sz[num]))%MOD;
}
void calc(map<int, vector<int> > ord){
graph.clear();
sz.clear();
sz.resize(n+1, 0);
graph.resize(n+1);
int counter=0;
map<int, int> prev, now;
for (auto [c, vect]:ord){
sort(vect.begin(), vect.end());
for (int i=0; i<vect.size(); ++i){
if (!i||vect[i]!=vect[i-1]+1)++counter;
now[vect[i]]=counter;
++sz[counter];
if (prev[vect[i]])if (graph[counter].empty()||graph[counter].back()!=prev[vect[i]])graph[counter].pb(prev[vect[i]]), graph[prev[vect[i]]].pb(counter);
}
swap(prev, now);
now.clear();
}
dfs(1, -1);
}
signed DistanceSum(signed N, signed *x, signed *y){
n=N;
map<int, vector<int> > a, b;
for (int i=0; i<n; ++i)a[x[i]].pb(y[i]), b[y[i]].pb(x[i]);
calc(a);
calc(b);
return (signed)ans;
}
