#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1000000000;
int DistanceSum(int n, int *X, int *Y){
map<pll, ll> mp;
vector<vl> conexiones(n);
ff(i, 0, n){
mp[{X[i], Y[i]}] = i;
}
for(auto &p : mp){
ll a = p.fi.fi, b = p.fi.se, c = p.se;
if(mp.count({a-1, b})){
conexiones[c].pb(mp[{a-1, b}]);
}
if(mp.count({a+1, b})){
conexiones[c].pb(mp[{a+1, b}]);
}
if(mp.count({a, b-1})){
conexiones[c].pb(mp[{a, b-1}]);
}
if(mp.count({a, b+1})){
conexiones[c].pb(mp[{a, b+1}]);
}
}
ll c = 0;
ff(i, 0, n){
queue<ll> q;
q.push(i);
vl dist(n, INT_MIN);
dist[i] = 0;
while(!q.empty()){
ll cur = q.front();
q.pop();
for(auto &x : conexiones[cur]){
if(dist[x] == INT_MIN){
dist[x] = dist[cur]+1;
q.push(x);
}
}
}
ff(j, i+1, n){
c += dist[j];
c %= MOD;
}
}
return c%MOD;
}
/*
int main() {
ll n;
cin >> n;
int *x, *y;
x = (int*) malloc(n * sizeof(int));
y = (int*) malloc(n * sizeof(int));
ff(i, 0, n){
cin >> x[i] >> y[i];
}
ll res = DistanceSum(n, x, y);
cout << res << ed;
return 0;
}
*/
