#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#define x first
#define y second
#define MOD 1000000000
void dfs(int x, std::vector < bool > &viz, std::vector < std::vector < int > > &g, std::vector < int > &sum) {
viz[x] = 1;
for (auto &y : g[x]) {
if (viz[y] == 0) {
dfs(y, viz, g, sum);
sum[x] += sum[y];
}
}
}
inline int solve(int n, int *X, int *Y) {
std::vector < std::pair < int, int > > v(n);
for (int i = 0; i < n; i++)
v[i] = {X[i], Y[i]};
std::sort(v.begin(), v.end());
int k = 1;
std::vector < int > boss(n, 1);
for (int i = 1; i < n; i++)
if (v[i].x == v[i - 1].x && v[i].y == v[i - 1].y + 1)
boss[i] = boss[i - 1];
else
boss[i] = ++k;
std::map < std::pair < int, int > , int > mp;
std::vector < int > sum(k + 1, 0);
for (int i = 0; i < n; i++)
mp[v[i]] = boss[i], sum[boss[i]]++;
std::vector < std::vector < int > > g(k + 1);
std::vector < int > last(k + 1, 0);
for (int i = 0; i < n; i++) {
int x = mp[{v[i].x - 1, v[i].y}];
if (x && last[boss[i]] != x) {
last[boss[i]] = x;
g[boss[i]].push_back(x);
g[x].push_back(boss[i]);
}
}
std::vector < bool > viz(k + 1, 0);
int rad = 1;
dfs(rad, viz, g, sum);
int ans = 0;
for (int i = 1; i <= k; i++)
ans = (ans + 1LL * sum[i] * (n - sum[i])) % MOD;
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
return (solve(N, X, Y) + solve(N, Y, X)) % MOD;
}
