#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod = 1e9, maxn = 1e5 + 5;
void upd(int &a, const int &b) { a = (a + b) % mod; }
int add(const int &a, const int &b) { return (a + b) % mod; }
int mul(const int &a, const int &b) { return (a * 1ll * b) % (ll)mod; }
vector<int> g[maxn];
int sz[maxn];
struct bod { int x, y; };
bool cmp(const bod &a, const bod &b) { return (a.x == b.x) ? a.y < b.y : a.x < b.x; }
int ans = 0, n;
void dfs(int u, int p = -1)
{
for (int v : g[u]) if (v != p) dfs(v, u), sz[u] += sz[v];
upd(ans, mul(sz[u], n - sz[u]));
}
void calculate_x_dist(vector<bod> v)
{
for (int i = 0; i < n; i++) g[i].clear(), sz[i] = 0;
map<pair<int, int>, int> m;
set<pair<int, int> > e;
sort(v.begin(), v.end(), cmp);
int cnt = 0;
for (int i = 0; i < n; i++)
{
if (i && (v[i-1].x != v[i].x || v[i-1].y+1 != v[i].y)) cnt++;
m[{v[i].x, v[i].y}] = cnt;
sz[cnt]++;
if (m.count({v[i].x-1, v[i].y})) e.insert({m[{v[i].x-1, v[i].y}], cnt});
}
for (pair<int, int> i : e) g[i.first].push_back(i.second), g[i.second].push_back(i.first);
dfs(0);
}
int DistanceSum(int N, int *x, int *y)
{
n = N; vector<bod> v;
for (int i = 0; i < n; i++) v.push_back({x[i], y[i]});
calculate_x_dist(v);
for (int i = 0; i < n; i++) swap(v[i].x, v[i].y);
calculate_x_dist(v);
return ans;
}
