#include <bits/stdc++.h>
using namespace std;
const int mod=1e9;
int p[100000],sz[100000],n,res,vis[100000];
vector <int> ke[100000];
int f(int i){
return (p[i]==i?i:p[i]=f(p[i]));
}
void unite(int i, int j){
i=f(i);
j=f(j);
if (i==j)
return;
if (sz[i]<sz[j])
swap(i,j);
sz[i]+=sz[j];
p[j]=i;
}
void dfs(int u, int p){
vis[u]=1;
for (int v:ke[u])
if (!vis[v]&&v!=p){
dfs(v,u);
sz[u]+=sz[v];
}
res=(res+1LL*sz[u]*(n-sz[u])%mod)%mod;
}
int calc(int *x, int *y){
map <pair <int, int>, int> mp;
for (int i=0;i<n;i++){
mp[{x[i],y[i]}]=i;
p[i]=i;
sz[i]=1;
vis[i]=0;
ke[i].clear();
}
for (int i=0;i<n;i++)
if (mp.count({x[i]-1,y[i]}))
unite(mp[{x[i]-1,y[i]}],i);
for (int i=0;i<n;i++)
if (mp.count({x[i],y[i]-1})){
int j=f(mp[{x[i],y[i]-1}]);
ke[f(i)].push_back(j);
ke[j].push_back(f(i));
}
res=0;
dfs(f(0),-1);
return res;
}
int DistanceSum(int N, int *X, int *Y){
n=N;
return (calc(X,Y)+calc(Y,X))%mod;
}
