#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
const ll MOD=1e9;
vector<int>V[LIM];
pair<int,int>T[LIM];
map<int,int>mp;
ll F[LIM], ile[LIM], n, ans;
int fnd(int x) {
if(F[x]==x) return x;
return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
if(fnd(a)==fnd(b)) return;
ile[fnd(a)]+=ile[fnd(b)];
F[fnd(b)]=fnd(a);
}
ll DFS(int x, int o) {
ll s=ile[x];
for(auto i : V[x]) if(i!=o) s+=DFS(i, x);
ans+=s*(n-s);
ans%=MOD;
return s;
}
int DistanceSum(int N, int *X, int *Y) {
n=N;
rep(i, n) T[i]={X[i], Y[i]};
rep(j, 2) {
mp.clear();
rep(i, n) {
swap(T[i].st, T[i].nd);
F[i]=i;
ile[i]=1;
V[i].clear();
}
sort(T, T+n);
rep(i, n-1) {
if(T[i].st==T[i+1].st && T[i].nd+1==T[i+1].nd) uni(i, i+1);
}
rep(i, n) {
int x=mp[T[i].nd]-1;
if(x>=0 && T[x].st==T[i].st-1 && (!V[fnd(i)].size() || V[fnd(i)].back()!=fnd(x))) {
V[fnd(i)].pb(fnd(x));
V[fnd(x)].pb(fnd(i));
}
mp[T[i].nd]=i+1;
}
DFS(fnd(0), fnd(0));
}
return ans;
}
