#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
const ll mod = 1e9;
ll result;
class tree {
public:
int usize[maxn], uparent[maxn], n;
int value[maxn];
ll total_sum, sbtsize[maxn];
vector<int>g[maxn];
void init(int _n) {
n = _n;
for(int i=1;i<=n;i++) {
usize[i] = 1;
uparent[i] = i;
}
}
int ufind(int x) {
while(x != uparent[x]) {
x = uparent[x];
}
return x;
}
void add_edge(int x, int y) {
g[x].pb(y);
g[y].pb(x);
}
void unite(int x, int y) {
int _x = x, _y = y;
x = ufind(x);
y = ufind(y);
if(x == y) return;
add_edge(_x, _y);
if(usize[x] > usize[y]) {
uparent[y] = x;
usize[x] += usize[y];
}
else {
uparent[x] = y;
usize[y] += usize[x];
}
}
void init_dfs() {
for(int i=1;i<=n;i++) {
total_sum += value[i];
}
}
void dfs(int node, int p) {
sbtsize[node] = value[node];
for(int i:g[node]) {
if(i != p) {
dfs(i, node);
result += sbtsize[i] * (total_sum - sbtsize[i]);
result %= mod;
sbtsize[node] += sbtsize[i];
}
}
}
}t1, t2;
map<pair<int,int>, int> rcomp, ccomp;
map<pair<int,int>, bool> exist;
set<int> rs, cs;
map<int,set<int> > r, c;
int DistanceSum(int N, int *X, int *Y) {
for(int i=0;i<N;i++) {
rs.insert(X[i]);
cs.insert(Y[i]);
exist[mp(X[i], Y[i])] = true;
r[X[i]].insert(Y[i]);
c[Y[i]].insert(X[i]);
}
t1.init(N);
t2.init(N);
int br = 0;
for(auto i:rs) {
for(int j:r[i]) {
int cx = i;
int cy = j;
if(!exist[mp(cx, cy-1)])
br++;
rcomp[mp(cx, cy)] = br;
t1.value[br]++;
if(exist[mp(cx-1, cy)]) {
t1.unite(rcomp[mp(cx-1, cy)], br);
}
}
}
br = 0;
for(auto i:cs) {
for(int j:c[i]) {
int cx = j;
int cy = i;
if(!exist[mp(cx-1, cy)])
br++;
ccomp[mp(cx, cy)] = br;
t2.value[br]++;
if(exist[mp(cx, cy-1)]) {
t2.unite(ccomp[mp(cx, cy-1)], br);
}
}
}
t1.init_dfs();
t2.init_dfs();
t1.dfs(1, -1);
t2.dfs(1, -1);
return result;
}
