#include <bits/stdc++.h>
// #define int long long
// #define fi first
// #define se second
// #define sz(a) (int)((a).size())
// #define all(a) (a).begin(), (a).end()
//
// #define lsb(x) (x & (-x))
// #define vi vector<int>
// #define YES { cout << "YES" << endl; return; }
// #define NO { cout << "NO" << endl; return; }
//
// using ll = long long;
// using pii = std::pair<int, int>;
const int MOD = 1e9;
using namespace std;
int n;
map<int, vector<int>>lin, col;
int solve(map<int, vector<int>>& mp) {
vector<vector<int>>T;
map<pair<int, int>, int>id;
vector<int>s;
int cnt = 0, idx = 0;
for (auto &[v, ap] : mp) {
sort(ap.begin(), ap.end());
++idx;
for (int i = 0; i < ap.size(); ++i) {
if (i == 0 || ap[i] != ap[i - 1] + 1) {
++cnt;
T.push_back({});
s.push_back(0);
}
id[{v, ap[i]}] = cnt;
++s.back();
if (idx != 1 && id.find({v - 1, ap[i]}) != id.end() && (T[cnt].empty() || id[{v - 1, ap[i]}]) != T[cnt].back()) {
T[cnt].push_back(id[{v - 1, ap[i]}]);
T[id[{v - 1, ap[i]}]].push_back(cnt);
}
}
}
vector<int>SZ(cnt + 1, 0);
int ans = 0;
function<void(int, int)> dfs = [&](int nod, int p) {
SZ[nod] = s[nod] - 1;
for (int &son : T[nod]) {
if (son == p) continue;
dfs(son, nod);
SZ[nod] += SZ[son];
ans += (n - SZ[son]) * SZ[son];
}
};
dfs(0, -1);
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
for (int i = 0; i < n; ++i) {
col[X[i]].push_back(Y[i]);
lin[Y[i]].push_back(X[i]);
}
return (solve(lin) + solve(col)) % MOD;
}
// signed main() {
// cin.tie(nullptr)->sync_with_stdio(false);
//
// int n;
// cin >> n;
//
// vector<int> X(n), Y(n);
// for (int i = 0; i < n; ++i) {
// cin >> X[i] >> Y[i];
// }
//
// cout << DistanceSum(n, X.data(), Y.data()) << '\n';
//
// return 0;
// }
