//In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll maxn = 2e5 + 100;
const ll mod = 1e9;
const ll inf = 1e18;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll n, t, ans, sz[maxn], dp[maxn];
pll a[maxn];
vector<pll> vec[maxn];
vector<ll> g[maxn];
bool vis[maxn];
void dfs(ll v){
vis[v] = 1;
dp[v] = sz[v];
for(ll u : g[v]){
if(!vis[u]){
dfs(u);
ans = (ans + dp[u] * (n - dp[u])) % mod;
dp[v] += dp[u];
}
}
return;
}
int DistanceSum(int _n, int *x, int *y){
n = _n;
ll mnx = inf;
for(ll i = 0; i < n; i++){
mnx = min(mnx, (ll)x[i]);
}
for(ll i = 0; i < n; i++){
x[i] -= mnx;
}
ll mny = inf;
for(ll i = 0; i < n; i++){
mny = min(mny, (ll)y[i]);
}
for(ll i = 0; i < n; i++){
y[i] -= mny;
}
for(ll i = 0; i < n; i++){
vec[x[i]].pb(Mp(y[i], -1));
}
for(ll i = 0; i < maxn; i++){
if(vec[i].empty()) break;
sort(all(vec[i]));
for(ll j = 0; j < Sz(vec[i]); j++){
if(j && vec[i][j].F != vec[i][j - 1].F + 1) t++;
sz[vec[i][j].S = t]++;
}
t++;
}
for(ll i = 0; i < maxn; i++){
if(vec[i + 1].empty()) continue;
ll p1 = 0, p2 = 0;
while(p1 < Sz(vec[i]) && p2 < Sz(vec[i + 1])){
if(vec[i][p1].F == vec[i + 1][p2].F){
g[vec[i][p1].S].pb(vec[i + 1][p2].S);
g[vec[i + 1][p2].S].pb(vec[i][p1].S);
}
if(vec[i][p1].F < vec[i + 1][p2].F) p1++;
else p2++;
}
}
dfs(0);
t = 0;
for(ll i = 0; i < maxn; i++){
vis[i] = 0;
sz[i] = 0;
vec[i].clear();
g[i].clear();
}
swap(x, y);
for(ll i = 0; i < n; i++){
vec[x[i]].pb(Mp(y[i], -1));
}
for(ll i = 0; i < maxn; i++){
if(vec[i].empty()) break;
sort(all(vec[i]));
for(ll j = 0; j < Sz(vec[i]); j++){
if(j && vec[i][j].F != vec[i][j - 1].F + 1) t++;
sz[vec[i][j].S = t]++;
}
t++;
}
for(ll i = 0; i < maxn; i++){
if(vec[i + 1].empty()) continue;
ll p1 = 0, p2 = 0;
while(p1 < Sz(vec[i]) && p2 < Sz(vec[i + 1])){
if(vec[i][p1].F == vec[i + 1][p2].F){
g[vec[i][p1].S].pb(vec[i + 1][p2].S);
g[vec[i + 1][p2].S].pb(vec[i][p1].S);
}
if(vec[i][p1].F < vec[i + 1][p2].F) p1++;
else p2++;
}
}
dfs(0);
return ans;
}
/*int main(){
fast_io;
int n, x[100], y[100];
cin >> n;
for(ll i = 0; i < n; i++){
cin >> x[i] >> y[i];
}
cout << DistanceSum(n, x, y);
return 0;
}*/
